# SoK: Let the Privacy Games Begin!
A Unified Treatment of Data Inference Privacy in Machine Learning

Ahmed Salem13, Giovanni Cherubin1, David Evans2, Boris Köpf1
Andrew Paverd1, Anshuman Suri2, Shruti Tople1, Santiago Zanella-Béguelin13
1Microsoft
{t-salem.ahmed, giovanni.cherubin, boris.koepf, andrew.paverd, shruti.tople,
<EMAIL_ADDRESS>2University of Virginia
{evans<EMAIL_ADDRESS>
###### Abstract

Deploying machine learning models in production may allow adversaries to infer
sensitive information about training data. There is a vast literature
analyzing different types of inference risks, ranging from membership
inference to reconstruction attacks. Inspired by the success of games (i.e.
probabilistic experiments) to study security properties in cryptography, some
authors describe privacy inference risks in machine learning using a similar
game-based style. However, adversary capabilities and goals are often stated
in subtly different ways from one presentation to the other, which makes it
hard to relate and compose results. In this paper, we present a game-based
framework to systematize the body of knowledge on privacy inference risks in
machine learning. We use this framework to  (1) provide a unifying structure
for definitions of inference risks,  (2) formally establish known relations
among definitions, and  (3) to uncover hitherto unknown relations that would
have been difficult to spot otherwise.

###### Index Terms:

privacy, machine learning, differential privacy, membership inference,
attribute inference, property inference

3 Corresponding author3 Corresponding authorfootnotetext:

##  I Introduction

MIRCDPDPIAILABEL:thmt@@DPDtoMILABEL:thmt@@DPDtoMILABEL:thmt@@MItoAILABEL:thmt@@MItoAILABEL:thmt@@RCtoMILABEL:thmt@@RCtoMILABEL:thmt@@DPDtoRCLABEL:thmt@@DPDtoRCLABEL:thmt@@AItoMILABEL:thmt@@AItoMILABEL:thmt@@PItoMILABEL:thmt@@PItoMILABEL:thmt@@MItoDPDLABEL:thmt@@MItoDPDLABEL:thmt@@MItoRCLABEL:thmt@@MItoRCLABEL:thmt@@MItoPILABEL:thmt@@MItoPILABEL:thmt@@RCtoDPDLABEL:thmt@@RCtoDPDLABEL:thmt@@DPDtoPILABEL:thmt@@DPDtoPIMIMembership
InferenceAIAttribute InferenceDPDDP DistinguishabilityPIProperty
InferenceRCData ReconstructionReductionSeparationImplied reductionImplied
separation Figure 1:  Relations among adversary goals (under selected threat
models). A solid arrow from node $A$ to $B$ means that security against $A$
(i.e. a nontrivial advantage bound) implies security against $B$. A struck-
through arrow from $A$ to $B$ means that security against $A$ does not imply
in general security against $B$; we show this separation with a construction
that is secure against $A$ but completely insecure against $B$. Dashed arrows
are implied by solid arrows. Labels over solid arrows refer to the theorem
showing the relationship. Some separations stem from differences in adversary
capabilities, e.g. $\mathsf{MI}\not\rightarrow\mathsf{RC}$.

Since the pioneering studies of attribute inference [69, 22] and membership
inference [56, 37], research on the inference risks of deploying machine
learning (ML) models has bloomed. There is a growing interest in understanding
and mitigating the leakage of information about training data under various
threat models that capture different adversarial capabilities (e.g., observing
model outputs, model parameters, or transcripts of iterative optimization
methods) and goals (e.g., membership inference [56], attribute inference [69,
22], property inference [74, 42, 23, 58], and data reconstruction [11, 4]).

An emerging trend in the literature is to capture threat models using _privacy
games_. This originates from the seminal work of Wu et al. [69] on formalizing
attribute inference. A privacy game is a probabilistic experiment where an
_adversary_ interacts with a _challenger_. The challenger drives the
experiment, invoking the adversary to provide them with information and to
allow them to make certain choices, possibly while interacting with oracles
controlled by the challenger. The adversary eventually produces a guess for a
confidential value. This experiment defines a probability space where the
success of the adversary can be measured in terms of the probability of their
guess being correct.

The use of games for privacy in ML is inspired by the well-established use of
games to define and reason about security properties in cryptography.
Cryptographic games are used to standardize and compare security definitions
[25, 57], and to structure [6] and even mechanize proofs of security [5, 9].
In comparison, the use of privacy games in the ML literature is still in its
infancy:

  1. (1)

there are no well-established standards for game-based definitions,

  2. (2)

relationships between different privacy games have only been partially
explored, and

  3. (3)

games are rarely used as an integral part of proofs, despite being especially
convenient for this task.

This has resulted in many game variants in the literature that attempt to
formalize the same adversary goal but have subtle yet important differences.
This fragmentation leads to confusion and hinders progress—for membership
inference alone, we found variants that differ in details that can change
their meaning and substantially alter results. To address this problem, we
present the first systematization of knowledge about privacy inference risks
in machine learning, going above and beyond the problem left open since 2016
by Wu et al. [69] of merely devising rigorous game-based definitions.
Concretely,

  * •

We break down the _anatomy_ of game-based privacy definitions for ML systems
into individual components: adversary’s capabilities and goals, ways of
choosing datasets and challenges, and measures of success (Section II).

  * •

Based on this anatomy, we propose a _unified representation_ of five
fundamental privacy risks as games: membership inference, attribute inference,
property inference, differential privacy distinguishability, and data
reconstruction (Section III).

  * •

Using the game-based framework, we _establish and rigorously prove
relationships_ between the above risks. Similarly to the study of _concrete
security_ in cryptography [7], we define a quantitative notion of _reduction_
between privacy properties. Using this notion, we prove a set of relations
among the above five privacy risks. This allows us to establish, for every
possible ordered pair of risks $A,B$, either a reduction showing that security
against $A$ implies security against $B$, or a separation result showing the
impossibility of a generic reduction from $A$ to $B$. Figure 1 summarizes the
conclusions of this systematization effort for selected games.

  * •

We present a _case study_ (Section V), where we prove that a scenario
described as a variant of membership inference in the literature can actually
be decomposed into a combination of membership and property inference.
Importantly, in this case we exploit _code-based_ reductions, structured as a
sequence of games; i.e., our arguments rely on transforming code with a formal
semantics. This way of conducting proofs has seen great success in
cryptography. However, before our work, it had not reached the same level of
rigor when reasoning about privacy inference risks in ML.

Scope The focus of this SoK is to formalize and systematize game-based
definitions that capture the risk of leaking information about the training
data of ML models. We used the following methodology to identify existing
game-based definitions from the literature: starting from the seminal works of
Wu et al. [69] and Yeom et al. [70], we surveyed all peer-reviewed
publications in Google Scholar as of August 2022 that cite either of these
works. We examined these publications and collected all game-based definitions
of attacks that aim to infer information about the training data of ML models.
Our primary objective is to systematize games appearing in the literature.
However, we also demonstrate the versatility of our framework by presenting
new game-based definitions of attacks that have not been previously formulated
as games.

Summary of contributions We propose a unifying game-based framework for
formalizing privacy inference risks of training data in ML, which we use to
systematize definitions from the literature and to establish relations between
them. Our work aims to reduce ambiguity and increase rigor when reasoning and
communicating about ML privacy, and gives a solid foundation to future
research and decision-making.

##  II Anatomy of a Privacy Game

Privacy games are parametrized by an adversary ($\mathcal{A}$) and a training
pipeline that specifies the training algorithm ($\mathcal{T}$), data
distribution ($\mathcal{D}$), and the size of the training dataset ($n$). A
challenger simulates the ML system. The adversary uses their
capabilities—defined by a threat model—to interact with the system and infer
information about the training dataset.

Input: $\mathcal{A},\mathcal{T},n,\mathcal{D}$

$S\sim\mathcal{D}^{n}$

// sample $n$ i.i.d. points from distribution $\mathcal{D}$

$b\sim\\{0,1\\}$

// flip a fair coin

1 if  _$b=0$_ then

$z\sim S$

// sample a challenge point uniformly from $S$

2

3else

$z\sim\mathcal{D}$

// sample a challenge point from $\mathcal{D}$

4

5 end if

$\theta\leftarrow\mathcal{T}(S)$

// train a model $\theta$

$\tilde{b}\leftarrow\mathcal{A}(\mathcal{T},\mathcal{D},n,\theta,z)$

// adversary guesses $b=\tilde{b}$

Game 1 Membership Inference

Game 1 formalizes the membership inference experiment of Yeom et al. [70],
which we use as a running example. The challenger samples a training dataset
$S$ (line 1) and flips a fair coin $b$ (line 2). Depending on the outcome,
they either sample a challenge point $z$ from the training dataset $S$, or
from the data distribution $\mathcal{D}$ (lines 3–7). We discuss alternatives
for choosing training datasets and challenges in Section II-B. The challenger
then trains a target model $\theta$ (line 8), and asks the adversary to make a
guess $\tilde{b}$ for $b$ (line 9). In this game, the adversary is given the
training algorithm ($\mathcal{T}$), data distribution ($\mathcal{D}$), dataset
size ($n$), target model ($\theta$), and the challenge point ($z$). We discuss
alternatives for adversary’s capabilities in Section II-B and Section II-C.
The success of the adversary in making a correct guess ($\tilde{b}=b$) is
measured with respect to the baseline of a random guess. Any advantage over
this baseline indicates leakage of membership information. We discuss other
ways to quantify the adversary’s success in Section II-D.

We now discuss in more detail the building blocks of games described above and
highlight common choices.

###  II-A Adversary Goals

We identify five adversary goals from the literature that enable an adversary
to directly infer information about the training dataset of an ML model. We
describe these goals informally below and formalize them as games in Section
III.

Membership Inference (MI) The adversary aims to determine whether a specific
_record_ [70, 56] or _subject_ [41, 59] (an entity who may contribute more
than one record) was present in the training dataset of the target model. For
example, a successful MI attack against a model trained on clinical records of
patients with an infective disease can reveal that a target patient was
infected.

Attribute Inference (AI) The adversary aims to use the model to infer unknown
attributes of a record in the training dataset given partial information about
the record [70]. A successful AI attack can result in the reconstruction of
sensitive attributes of a target individual.

Property Inference (PI) The adversary aims to learn sensitive _statistical_
properties of the target model’s training distribution. For example, in a
malware classifier, the training dataset may have been generated using a
particular testing environment, and it may benefit the adversary to learn
certain properties of this environment [23]. From an auditing perspective,
property inference could be used to assess the training dataset for harms
(e.g., under-representation) [74].

Differential Privacy Distinguishability (DPD) The adversary aims to determine
which of a pair of adjacent datasets (e.g. differing in the data of one
record) of their choosing was used to train the target model. This goal
recasts differential privacy in a game-based setting by making the adversary
explicit. This connection can be used to estimate the differential privacy
budget of training pipelines [43, 46, 72].

Data Reconstruction (RC) The adversary aims to reconstruct samples from the
training dataset of a target model [10, 11, 4]. A successful attack can
partially reconstruct the training dataset, potentially violating
confidentiality requirements.

Beyond training data inference Other adversary goals, such as model stealing
[62, 48] and hyperparameter stealing [66] are beyond the scope of this SoK
because they do not enable the adversary to directly infer information about
the training data. However, the _effects_ of these other goals are readily
captured by our game-based analysis. For example, a successful model stealing
attack that is used as a precursor to membership inference can be represented
by changing the adversary access from black-box to white-box (Section II-C).

###  II-B Selecting Challenges and Datasets

An important aspect of any privacy game is how the challenges and datasets are
selected. In Game 1, the challenge point is a single record $z$; in other
games, the challenge could comprise multiple points or even a data
distribution. For the discussion below, we simplify the language by talking
about a single challenge point. We discuss below three methods commonly used
in the literature.

Randomly sampled The challenge is sampled from a distribution by the
challenger as part of the game [70, 67, 31]. A randomly sampled challenge
provides a measure of _average case_ privacy. While average case privacy
measures the risk for average users, the risk for outliers can be
significantly higher.

Externally provided The challenge is provided as a parameter of the game [41,
31]. This may be used to measure privacy of specific points, i.e., it provides
_individual case_ privacy.

Adversarially chosen The challenge is selected by the adversary during the
game [13, 43, 46]. Since the adversary can select the most advantageous
challenge based on the information provided, this provides a measure of _worst
case_ privacy, i.e., measuring the risks for all users including outliers. For
example, a strong membership inference adversary could choose a challenge that
is an outlier w.r.t. the training data distribution, so that a target
classification model is unlikely to classify it correctly unless it is
included in the training dataset. This setting is usually considered when
auditing a system to identify risks.

Additional considerations When the challenge is externally provided or
adversarially chosen, the parameters of the game cannot completely determine a
correct adversary guess. Otherwise, security statements that universally
quantify over adversaries are void because the quantification includes
adversaries with a hardcoded correct guess. This is similar to the difficulty
of defining collision resistance of hash functions [51].

Selecting datasets The training dataset can also be selected using any of the
three options above: it can be randomly sampled by the challenger, externally
provided, or (partially) chosen by the adversary. The latter can be used to
represent the case where the model has been trained on (poisoned) data
contributed by potentially malicious users [42, 64].

###  II-C Adversary Access

Depending on the scenario, the adversary may have different levels of access
to the target model, training algorithm, training distribution, and training
dataset. This allows the game to capture different threat models, which should
ideally match the known or assumed capabilities of real-world adversaries.
Most games assume one of two settings: _black-box_ or _white-box_ access.

Black-box In this scenario, the adversary only has query access to the target
model (e.g., a cloud-hosted model with an inference API) [12]. To formalize
this setting, we give the adversary access to the model through an oracle
$\mathbf{Oracle}~{}\mathcal{O}^{\theta}(x):\textnormal{{return}}~{}\theta(x)$.
This allows the adversary to query the model $\theta$ on inputs of their
choosing and observe the responses, but does not reveal internal workings of
the model, such as its architecture or weights. Depending on the scenario, the
oracle can return a confidence for each label, or only the highest-confidence
label [38, 17]. The latter setting matches inference APIs that do not reveal
confidence values, like some email spam classifiers or auto-completion
systems. Additionally, the oracle can be instrumented to post-process
responses, or to only emit responses for queries satisfying a (stateful)
predicate, e.g., to enforce a bound $N$ on the number of allowed queries the
challenge can initialize $q_{0}=0$ and provide

$\displaystyle\begin{array}[]{l}\textbf{Oracle }\mathcal{O}_{N}^{\theta}(x)\\\
\qquad q_{\theta}\leftarrow q_{\theta}+1\\\ \qquad\textbf{if }q_{\theta}\leq
N\textbf{ then }\textnormal{{return}}\arg\max\theta(x)\textbf{ else
}\textnormal{{return}}~{}\bot\end{array}$

White-box The white-box setting represents the strongest adversary, who has
full direct access to the target model i.e., $\mathcal{A}(\theta,\ldots)$.
This obviously provides the adversary with all the capabilities of the black-
box setting, but also allows the adversary to inspect the internals of the
model including its trained weights [52, 36]. For instance, a model deployed
on clients’ devices gives white-box access to malicious clients.
Alternatively, a successful black-box model stealing attack would enable an
adversary to operate in a white-box setting.

Grey-box In between the black-box and white-box settings, there is a range of
_grey-box_ threat models in which the adversary has more than black-box but
less than full white-box access to the target model. For example, the
adversary could know the architecture of a target model, some of its training
hyperparameters, or the public model from which the model has been fine-tuned
[56, 53]. Such extra information can be the output of a hyperparameter
stealing attack [66].

Auxiliary information In addition to having access to the target model, an
adversary may have auxiliary information that could be useful for certain
attacks. For example, most MI attacks assume the adversary has access to
auxiliary data distributed similarly to the target model’s training data,
e.g., for building shadow models. This is captured in games by giving the
adversary the distribution from which the training data was sampled.

Resource constraints Most game-based formulations do not explicitly limit the
resources available to an adversary, i.e., they consider information-theoretic
adversaries. It could be important to consider resource-limited adversaries
that can only issue a specific number of queries to an oracle, or can use a
certain amount of memory, or are otherwise computationally bounded.
Intuitively, limiting these resources can reduce the effectiveness of an
attack. These limitations can be specified outside the game as constraints on
the adversary, enforced by instrumenting the code of the game (as in Oracle
$\mathcal{O}_{N}^{\theta}$ above), or incorporated into the measure of
success.

###  II-D Measuring Adversary Success

There are various ways of quantifying the adversary’s success in games. We
discuss commonly used metrics next.

#### Attack Success Rate

The _attack success rate_ (ASR) measures the expected number of times the
adversary succeeds (i.e., wins the game) over multiple runs. ASR is arguably
the most intuitive and widespread metric for quantifying adversary success;
for example, it matches the attacker’s accuracy in membership inference.

However, the main drawback of ASR is that it does not take into account the
baseline success probability for a given task. For example, if we evaluate an
ML model’s resilience to attribute inference, the prior distribution of that
attribute will play a role in the adversary’s success. For instance, if the
attribute can only take one value, it is trivial for an adversary to achieve
100% ASR, but this will not be a meaningful measure. Similarly, the prior
probability that an example belongs to the training set affects membership
inference accuracy.

Ideally, the metric should quantify the success of an adversary relative to a
suitable _baseline_. The baseline should represent the _a priori_ adversary
success rate; that is, it should quantify the adversary’s success rate if they
used only their prior knowledge and had no access to the model.

#### Adversary Advantage

The notion of _advantage_ is a commonly used metric in cryptography, which
relates an adversary’s success rate to a baseline. This gives a better
intuition of how much an adversary gains by having access to the model (in any
of the forms defined in Section II-C). In general terms, suppose the adversary
is trying to infer some variable $p$; this could be the membership of a data
record or the value of a coin toss. If $\Pr[\mathcal{A}=p]$ is the adversary’s
success rate (probability to guess $p$ correctly), and $G$ is the baseline
success rate, the advantage can be expressed as
$\mathsf{Adv}(\mathcal{A})=\nicefrac{{\Pr[\mathcal{A}=p]-G}}{{1-G}}.$ Assuming
$\Pr[\mathcal{A}=p]\geq G$, this metric quantifies the adversary’s advantage
on a scale of $[0,1]$ relative to the baseline $G$; $0$ represents no
advantage over the baseline and $1$ is a perfect attack. When the secret
information $p$ is binary with a uniform prior, $G=\nicefrac{{1}}{{2}}$. This
leads to the familiar expression
$\mathsf{Adv}(\mathcal{A})=2\Pr[\mathcal{A}=p]-1.$ Advantage is commonly used
as a metric for ML privacy attacks. For example, Yeom et al. [70] define the
MI advantage for an adversary $\mathcal{A}$ as follows:

$\mathsf{Adv}_{\mathsf{MI}}(\mathcal{A},\mathcal{T},n,\mathcal{D})=2\Pr\\!\left[\mathsf{MI}(\mathcal{A},\mathcal{T},n,\mathcal{D})\\!:\\!\tilde{b}=b\right]-1,$

where $\mathsf{MI}$ is the membership inference experiment in Game 1, and
$\Pr\\!\left[G\\!:\\!E\right]$ denotes the probability of event $E$ in the
probability space defined by game $G$.

Providing an adequate baseline may be difficult because it may not be possible
to accurately model the adversary’s knowledge. This issue can often be
bypassed by careful design of the game. For example, instead of asking the
adversary to reconstruct an arbitrary attribute’s value, the game can be
designed such that the adversary must distinguish between two equally-likely
values of the attribute.

#### Beyond advantage

Average case metrics such as ASR fail to capture inference risks for
individuals or subpopulations. For example, a MI attack against a model may
achieve roughly 50% accuracy (with a 50% baseline) on average across the
population, yet the same attack may perform better when targeting specific
individuals or subpopulations [13, 35]. Having raised similar concerns,
Carlini et al. [12] suggest that an adversary should be considered successful
if it reliably succeeds even on small number of cases. For instance, a MI
attack that achieves a high true positive rate (TPR) at some low false
positive rate (FPR) could be consequential even if it has low accuracy.

In this paper, we focus on advantage as a metric, since it has the following
benefits:  (1) it has an easy interpretation—it represents the gain of an
adversary from having access to the system under scrutiny versus an adversary
with only prior knowledge;  (2) it is directly related to other metrics, such
as ASR (which can be derived directly from it), true and false positive rates
(e.g., [70]), and Differential Privacy [31, 14];  (3) if the attacker’s
challenge is binary (e.g., distinguishing between members and nonmembers), the
advantage computed when assuming the two choices have a uniform prior gives a
bound for any other prior [14]. Nevertheless, given a game formulation, one
can consider other metrics of interest: e.g., area under the ROC curve (AUC-
ROC), F1-score, and TPR at fixed FPR thresholds [12].

###  II-E Consequences of Attacks

The anatomy we presented can be used to specify threat models and quantify the
chances that an adversary successfully achieves their goal. However, the
_consequences_ of a successful attack depend less on the threat model but
rather on the adversary’s goal (Section II-A) and on the design of the ML
system, e.g., the sensitivity of the training data. For example, the
consequences of successful membership inference will be the same irrespective
of whether it was performed in a black-box or white-box setting.

##  III Game-based Formalization of Inference Risks

In this section we present privacy games for the five adversary goals
introduced in Section II-A. We summarize the notation in Table I and the
threat models considered in all games in Table II.

TABLE I: Summary of notation Notation | Description
---|---
$\mathcal{T}$ | A stochastic training algorithm
$\mathcal{D}$ | A distribution over examples
$\mathcal{D}^{n}$ | Distribution of $n$ independent examples from $\mathcal{D}$
$\mathcal{A}$, $\mathcal{A}^{\prime}$ | Adversary procedures sharing mutable state
$z\sim\mathcal{D}$ | Draw an example $z$ from $\mathcal{D}$
$S\sim\mathcal{D}^{n}$ | Draw $n$ examples $S$ independently from $\mathcal{D}$
$b\sim\\{0,1\\}$ | Sample a bit $b$ uniformly
$b\sim 0\oplus_{p}1$ | Sample 0 with probability $p$, 1 with probability $1-p$
$y\leftarrow\mathcal{P}(\vec{x})$ | Call $\mathcal{P}$ with arguments $\vec{x}$ and assign result to $y$

###  III-A Membership Inference

Membership inference aims to predict the participation of an entity in the
training dataset of the model. The first (record-level) membership inference
attack on supervised learning was proposed by Shokri et al. [56] against ML-
based classifiers. Subsequent work has explored membership inference attacks
with differing degrees of access to the model (e.g., white-box [52, 36] or
label-only attacks [38, 17]), against different types of models (e.g.,
generative models [16, 29, 27], image segmentation [28], contrastive learning
[40], recommender systems [73], and Graph Neural Networks (GNN) [68]), and
under entirely different threat models [55, 53, 30].

We present MI variants that have been formalized as games. We divide the games
into two categories depending on whether they focus on a single record
(_record-level_) or a _user_ represented by a collection of records (_user-
level_).

#### Record-level Membership Inference

The most common interpretation of record-level membership inference is given
by the game introduced by Yeom et al. [70], which we presented as Game 1 in
Section II. Game 2 below presents a semantically equivalent reformulation
$\mathsf{MI}$. The reader can verify that $b,\theta,z_{0}$ are distributed
identically to $b,\theta,z$ in Game 1 and thus the joint distribution of
$b,\tilde{b}$ is the same in both games. This game considers an adversary with
white-box access to the model—they have the model at their disposal and can
query it freely, analyze its architecture and parameters, and observe its
dynamic behavior. Since the training dataset and the challenge $z_{0}$ are
sampled from $\mathcal{D}$, this game measures average case MI resilience.

Input:
$\mathcal{T},\mathcal{D},n,\definecolor{currentcolor}{rgb}{0,0,0}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\dbox{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}$p$}},\definecolor{currentcolor}{rgb}{0,0,0}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\dbox{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}$\mathcal{A}^{\prime}$}},\mathcal{A}$

1 $S\sim\mathcal{D}^{n-1}$

2
$b\sim\definecolor{currentcolor}{rgb}{0,0,0}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\framebox{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}$\\{0,1\\}$}}\,\,\definecolor{currentcolor}{rgb}{0,0,0}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\dbox{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}$0\oplus_{p}1$}}\,\,\definecolor{currentcolor}{rgb}{0,0,0}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\dbox{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}$\\{0,1\\}$}}$

3
$z_{0}\sim\definecolor{currentcolor}{rgb}{0,0,0}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\framebox{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}$\mathcal{D}$}}\,\,\definecolor{currentcolor}{rgb}{0,0,0}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\dbox{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\mathcal{D}}}\,\,\definecolor{currentcolor}{rgb}{0,0,0}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\dbox{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}$\mathcal{A}^{\prime}(\mathcal{T},\mathcal{D},n)$}}$

4 $z_{1}\sim\mathcal{D}$

5 $\theta\leftarrow\mathcal{T}(S\cup\\{z_{b}\\})$

$\tilde{b}\leftarrow\mathcal{A}(\mathcal{T},\mathcal{D},n,\definecolor{currentcolor}{rgb}{0,0,0}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\dbox{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}$p$}},\theta,z_{0})$

Game 2 $\mathsf{MI}^{\phantom{|}}$ $\mathsf{MI}^{\textsf{skew}}$
$\mathsf{MI}^{\mathsf{Adv}}$

Several variants of the basic MI game have been considered in the literature;
some are semantically equivalent (e.g., [35, 31]) whilst others alter its
semantics. We next systematize these latter variants using the anatomy
presented in Section II.

Jayaraman et al. [34] consider game $\mathsf{MI}^{\textsf{skew}}$ which
generalizes $\mathsf{MI}$ by introducing a parameter $p$ representing the
prior membership probability (Game 2, line 2). The original $\mathsf{MI}$ game
assumes a balanced prior and is recovered as a special case when
$p=\nicefrac{{1}}{{2}}$.

Chang and Shokri [13] consider game $\mathsf{MI}^{\mathsf{Adv}}$ in Game 2
which strengthens the adversary by allowing them to select the challenge point
(line 3). This game measures worst case MI resilience for an average dataset,
i.e., resilience against this variant protects all records—even
outliers—against MI. See $\mathsf{SMI}$ in Game 10 for an even stronger attack
where $S$ is adversarially chosen.

Carlini et al. [12] consider game $\mathsf{MI}^{\textsf{BB}}$ which differs in
two aspects from $\mathsf{MI}$. Firstly, it assumes a black-box adversary who
is given only inference access to the model through an oracle,
$\textbf{Oracle}~{}\mathcal{O}^{\theta}(x):\textnormal{{return}}~{}\theta(x)$
(modifying line 9 in Game 1). This is appropriate when the target model is
hosted in the cloud or in a trusted execution environment that ensures its
confidentiality. Secondly, rather than sampling the challenge point from
$\mathcal{D}$ when $b=1$, the challenger samples it from $\mathcal{D}\setminus
S$ (modifying line 6 in Game 1), thus excluding the case where the challenge
happens to be in $S$ by chance. This is in contrast to game $\mathsf{MI}$,
where nonmembers are sampled from the complete distribution and may be
contained in $S$. While doing this seems intuitive, Yeom et al. [70, p.41]
note that it is problematic since an adversary could gain advantage not
through access to the model but rather by analyzing $\mathcal{D}$ to infer
which points are more likely to have been sampled into $S$. For instance,
consider a distribution $\mathcal{D}$ with support $\\{x_{0},\dotsc,x_{m}\\}$
that assigns probability $\nicefrac{{1}}{{2}}$ to $x_{0}$ and
$\nicefrac{{1}}{{2m}}$ to each of $x_{1},\dotsc,x_{m}$. An adversary that
ignores $\theta$ and guesses $\tilde{b}=0$ if and only if $z=x_{0}$ has
advantage greater than $\nicefrac{{1}}{{2}}-\nicefrac{{1}}{{2^{n}}}$.

Tramèr et al. [64] introduce a generic privacy game where the goal of the
adversary is to guess which point from a universe $\mathcal{U}$ has been
included in the training dataset of the target model. They present variants
with ($\mathsf{MI}^{\textsf{Pois}}$) and without
($\mathsf{MI}^{\textsf{Diff}}$) poisoning, shown in Game 3.
$\mathsf{MI}^{\textsf{Pois}}$ lets the adversary statically poison part of the
training dataset (Section II-B). By considering
$\mathcal{U}=\\{\hat{z},\bot\\}$, where $\bot$ indicates the absence of an
example, the generic game can represent a black-box membership inference
attack for a fixed externally provided target example $\hat{z}$. Compared to
variants of membership inference discussed previously, this results in
training datasets of different sizes depending on the outcome of sampling the
challenge $z$: e.g. in $\mathsf{MI}^{\textsf{Diff}}$ the model may be trained
on $S\cup\\{\hat{z}\\}$ or just on $S$. This usually does not make a
significant difference as training datasets are large and models do not leak
the size of their training dataset. As in $\mathsf{MI}^{\textsf{BB}}$, values
in $S$ are excluded when sampling $z$, which leads to similar problems.

Input: $\mathcal{T},\mathcal{D},\mathcal{U},n,\mathcal{A}$,
$\mathcal{A}^{\prime},n^{\prime}$

$S\sim\mathcal{D}^{n}$

$z\sim\mathcal{U}\setminus S$

$S^{\prime}\leftarrow\mathcal{A}^{\prime}(\mathcal{T},\mathcal{D},\mathcal{U},n^{\prime})$

// $|S^{\prime}|=n^{\prime}$

$\theta\leftarrow\mathcal{T}(S\cup\\{z\\}$ $\cup\,S^{\prime}$$)$

$\tilde{z}\leftarrow\mathcal{A}(\mathcal{T},\mathcal{D},\mathcal{U},n,\mathcal{O}^{\theta}(\cdot),$$S^{\prime}$$)$

Oracle $\mathcal{O}^{\theta}(x)$: return $\theta(x)$

Game 3 $\mathsf{MI}^{\textsf{Diff}}$ $\mathsf{MI}^{\textsf{Pois}}$

Other variants Humphries et al. [31] sample the training dataset and challenge
point from different distributions (Game 11); we use this variant as the basis
for our case study in Section V. Tang et al. [61] define single-query
membership inference games where the adversary is only given the output of the
trained model on the challenge point, but where the adversary selects the set
of examples from where the training dataset is subsampled (see Section -A in
the Appendix). Gao et al. [24] consider _deletion inference_ , a variant of
membership inference in the setting of _machine unlearning_ , where the
adversary is given access to a model before and after one of two examples is
deleted and is asked to guess which example was deleted.

#### User-level Membership Inference

Privacy laws such as GDPR require generalizing the goal of MI. Instead of
focusing on a single record, the interest is now the complete data of an
individual. For instance, an auditor would be interested in learning if a
user’s data—usually modeled as a collection of records—was used to train a
target model. User-level membership inference was introduced to model such
scenarios. Mahloujifar et al. [41] formalize user-level MI as in Game 4. They
consider a meta-distribution $\mathcal{D}$ from where $m$ user distributions
are sampled. The adversary targets a particular user contributing a dataset
$S^{*}$. This game presents the adversary with a task easier than Game 1 since
they must infer whether an entire group of records is within the training
dataset, i.e., it measures _group_ privacy.

Input: $\mathcal{T},\mathcal{D},n,\mathcal{A},S^{*},m$

$b\sim\\{0,1\\}$

$\mathcal{D}_{1},\dotsc,\mathcal{D}_{m}\sim\mathcal{D}$

for  _$i=1,\dotsc,m-1$_ do

$S_{i}\leftarrow\mathcal{D}^{n}_{i}$

end for

if  _$b=0$_ then

$S_{m}=S^{*}$

else

$S_{m}\leftarrow\mathcal{D}^{n}_{m}$

end if

$\theta\leftarrow\mathcal{T}(\bigcup_{i=1}^{m}S_{i})$

$\tilde{b}\leftarrow\mathcal{A}\left(\mathcal{T},\mathcal{D},n,\mathcal{O}^{\theta}(\cdot),S^{*},m\right)$

Oracle $\mathcal{O}^{\theta}(x)$: return $\theta(x)$

Game 4 $\mathsf{MI}^{\mathsf{User}}$

###  III-B Attribute Inference

In attribute inference (AI) attacks, the adversary aims to infer a sensitive
attribute of a target record. Wu et al. [69] were the first to formalize AI,
confusingly under the name of _model inversion_. We follow here the more
general formalization given by Yeom et al. [70] shown in Game 5. Recently the
scope of AI expanded to other settings [75, 33].

Input: $\mathcal{T},\mathcal{D},n,\mathcal{A},\varphi,\pi$

$S\sim\mathcal{D}^{n}$

$b\sim\\{0,1\\}$

if  _$b=0$_ then

$z\sim$ $S$ $\mathcal{D}$

else

$z\sim\mathcal{D}$

end if

$\theta\leftarrow\mathcal{T}(S)$

$\tilde{a}\leftarrow\mathcal{A}(\mathcal{T},\mathcal{D},n,\theta,\varphi(z))$

Game 5 $\mathsf{AI}$ $\mathsf{Inv}$

In the $\mathsf{AI}$ game, $\varphi(z)$ denotes the adversary’s knowledge
about the challenge $z$, and $\pi$ a function that extracts the information
targeted by the attack, e.g., if $t$ represents the target sensitive
attributes, then $\pi(z)=t$. The experiment is similar to the basic membership
inference experiment (Game 1) except for the information that the adversary is
given and the winning condition. The adversary is given $\varphi(z)$ and aims
to infer $\pi(z)$. The adversary wins if it correctly predicts these
attributes, i.e., $\tilde{a}=\pi(z)$. Training data poisoning can be
considered by including adversarially chosen data when training the target
model as done for $\mathsf{MI}$ in Game 3 ($\mathsf{MI}^{\textsf{Pois}}$), an
instance of the generic game of Tramèr et al. [64].

Model inversion Another adversary goal with a similar aim to $\mathsf{AI}$ is
model inversion [67]. Model inversion attacks were introduced by Fredrikson et
al. [22] and subsequently formalized by Wang et al. [67] ($\mathsf{Inv}$ in
Game 5). The difference between attribute inference and model inversion
according to Wang et al. [67] is in how the challenge is sampled: in
$\mathsf{AI}$ it is sampled from the training dataset, while in $\mathsf{Inv}$
it is sampled from the distribution $\mathcal{D}$. While AI measures privacy
risk for members of a model’s training dataset, model inversion measures the
privacy loss of publishing the model for members of the underlying population.
Whether this is considered a privacy risk is up to debate: a successful attack
may lead to the adversary learning information from records that are not part
of the training dataset or that do not even exist. Model owners concerned only
with the privacy of the training dataset would use the $\mathsf{AI}$ game,
whilst those concerned about population privacy would prefer $\mathsf{Inv}$.

###  III-C Reconstruction

Reconstruction attacks aim to recover entire examples in the training dataset
of a model. Reconstruction has been studied in various settings, including
Graph Neural Networks [75], image classification [54], and text generation
[10, 71, 11]. A distilled scenario, where the adversary learns the training
data of the target model except for a target example was first formalized by
Balle et al. [4] as experiment $\mathsf{RC}$ in Game 6.

Input: $S$, $\mathcal{D},n$, $\pi,\mathcal{T},\mathcal{A}$

$S\sim\mathcal{D}^{n-1}$

$z\sim\pi$

$\theta\leftarrow\mathcal{T}(S\cup\\{z\\})$

$\tilde{z}\leftarrow\mathcal{A}(\mathcal{T},\theta,\definecolor{currentcolor}{rgb}{0,0,0}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\dbox{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}$\mathcal{D},n$}},S)$

Game 6 $\mathsf{RC}$ $\mathsf{RC}^{\textsf{Ran}}$

Reconstruction robustness is parametrized by bounds on the error and success
probability and defined as follows.

######  Definition 1 (Balle et al. [4], Definition 2).

A training pipeline is $(\eta,\gamma)$-reconstruction robust with respect to a
prior $\pi$ and reconstruction loss $\ell$ if for any dataset $S$ and any
reconstruction adversary $\mathcal{A}$,

$\Pr\\!\left[\mathsf{RC}\\!:\\!\ell(z,\tilde{z})\leq\eta\right]\leq\gamma$

The adversary is given the model $\theta$, training algorithm $\mathcal{T}$,
and the training dataset $S$ except for one point $z$ which they need to
reconstruct. Game $\mathsf{RC}^{\textsf{Ran}}$ models how other points in the
training dataset are sampled, instead of considering a fixed dataset $S$. The
advantage of an adversary $\mathcal{A}$ against $\mathsf{RC}$ w.r.t. a
baseline that ignores $\theta$ and just samples $\tilde{z}$ from $\mathcal{D}$
is

$\mathsf{Adv}_{\mathsf{RC}}(\mathcal{A})=\Pr\\!\left[\mathsf{RC}\\!:\\!\tilde{z}=z\right]-\Pr\\!\left[z,\tilde{z}\sim\mathcal{D}\\!:\\!\tilde{z}=z\right]$

Alternatively, one can consider the baseline success of an adversary that
picks $\tilde{z}$ according to $\pi$,

$\sup_{\tilde{z}\in\operatorname{supp}(\pi)}\Pr\\!\left[z\sim\pi\\!:\\!\ell(z,\tilde{z})\leq\eta\right]$
(1)

Both games can be adapted to consider a poisoning-capable adversary as
demonstrated in Game 3.

Reconstruction in language models Recent work focused on large language models
and evaluated reconstruction attacks against them. Attacks can be categorized
as untargeted [11] or targeted [10]. Untargeted attacks aim to reconstruct any
training data from the generative model, whilst targeted attacks aim to
reconstruct specific training data records, which may have been inserted as
canaries during training. To demonstrate the flexibility of privacy games, we
formalize an example from each category, as shown in Game 7.

We formalize a black-box untargeted data reconstruction attack by Carlini et
al. [11] tailored to large generative language models as
$\mathsf{RC}^{\textsf{Untarg}}$. The authors measure the success of an attack
by its true positive rate or recall, that is, the fraction of examples in
$\widetilde{S}$ that are in the training dataset $S$.

We formalize a black-box targeted reconstruction attack by Carlini et al. [10]
as $\mathsf{RC}^{\textsf{Targ}}$. The authors insert a _canary_ multiple times
into the training data as a way to measure unintended memorization in
generative models. Canaries are specified by a format sequence $s[\cdot]$ that
fixes some tokens and leaves _holes_ to be filled with secrets sampled from a
randomness space $\mathcal{R}$. For example, $s=$ “the PIN is  ” with
$\mathcal{R}$ being the space of 4-digit decimal numbers. Carlini et al. [10]
measure the success of targeted canary reconstruction as the reduction in the
guessing entropy of secrets in canaries given the model.

Input: $\mathcal{T},\mathcal{D},n,\mathcal{A}$, $\mathcal{R},s,m$

$S\sim\mathcal{D}^{n}$

$r\sim\mathcal{R}$

$\theta\leftarrow\mathcal{T}(S$ $\cup\\{s[r]\\}^{m}$ $)$

$\widetilde{S}\leftarrow\mathcal{A}(\mathcal{T},\mathcal{D},n,\mathcal{O}^{\theta}(\cdot),$
$\mathcal{R},s$$)$

Oracle $\mathcal{O}^{\theta}$(x): return $\theta(x)$

Game 7 $\mathsf{RC}^{\textsf{Untarg}}$ $\mathsf{RC}^{\textsf{Targ}}$

Selecting a game Game $\mathsf{RC}$ is appropriate when evaluating the worst
case risk of reconstructing an example in the training dataset. It
conservatively considers an informed adversary that knows all examples but the
target, and incorporates the adversary’s background knowledge in a prior. Game
$\mathsf{RC}^{\textsf{Ran}}$ considers an equally informed adversary, but
averages the reconstruction risk over the choice of other training examples.
Game $\mathsf{RC}^{\textsf{Untarg}}$ represents a more realistic threat model
and should be chosen when evaluating the risk of indiscriminately
reconstructing training data, while $\mathsf{RC}^{\textsf{Targ}}$ is
appropriate for auditing the risk of extracting data following certain
patterns.

Other variants Similar to MI, reconstruction attacks have been adapted to the
machine unlearning setting. Gao et al. [24] consider _deletion reconstruction_
, where an adversary is given access to a model before and after a random
training example is deleted and is asked to reconstruct it.

###  III-D Distribution Inference

Distribution inference attacks do not focus on specific data records, but
instead aim at inferring properties about the training data distribution. We
next describe two variants of distribution inference. The first is property
inference, e.g., where the adversary is interested in learning about the
prevalence of specific sensitive attributes in the training data, such as sex
or ethnicity. The second is subject-level distribution inference, where the
training data is sampled from a mixture of distributions, each corresponding
to a subject that may participate in training. The adversary’s goal is to
infer whether a subject has participated knowing the subject’s data
distribution rather than concrete samples like in game
$\mathsf{MI}^{\textsf{User}}$ in Game 4.

#### Property Inference

Property inference attacks were first proposed by Ganju et al. [23] in the
white-box setting and by Zhang et al. [74] in the black-box setting. Zhou et
al. [76] showed them to be effective against generative models and GANs
specifically. Suri and Evans [58] formalized property inference attacks as
$\mathsf{PI}$ in Game 8, parametrized by two functions
$\mathcal{G}_{0},\mathcal{G}_{1}$ that transform an underlying distribution.

Input:
$\definecolor{currentcolor}{rgb}{0,0,0}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\framebox{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}$\mathcal{D},\mathcal{G}_{0},\mathcal{G}_{1}$}}\,\,\definecolor{currentcolor}{rgb}{0,0,0}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\dbox{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}$\mathcal{D}_{0},\mathcal{D}_{1}$}},n,\mathcal{T},\mathcal{A}$

$b\sim\\{0,1\\}$

$S\sim$$\mathcal{G}_{b}(\mathcal{D})^{n}$ $\mathcal{D}_{b}^{n}$

$\theta\leftarrow\mathcal{T}(S)$

$\tilde{b}\leftarrow\mathcal{A}(\mathcal{T},\definecolor{currentcolor}{rgb}{0,0,0}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\framebox{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}$\mathcal{D},\mathcal{G}_{0},\mathcal{G}_{1}$}}\,\,\definecolor{currentcolor}{rgb}{0,0,0}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\dbox{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}$\mathcal{D}_{0},\mathcal{D}_{1}$}},n,\theta)$

Game 8 $\mathsf{PI}^{\phantom{|}}$ $\mathsf{PI}^{\textsf{Gen}}$

$\mathsf{PI}^{\textsf{Gen}}$ is an equivalent formulation parametrized by two
distributions corresponding to the application of $\mathcal{G}_{0}$,
$\mathcal{G}_{1}$ to the base distribution $\mathcal{D}$ in $\mathsf{PI}$.
Hartmann et al. [26] generalize this to more than two distributions.

Similarly to $\mathsf{MI}$ and $\mathsf{AI}$, poisoning can be modelled as in
Game 3 by letting the adversary choose part of the training dataset of the
target model. Mahloujifar et al. [42] and Chaudhari et al. [15] show that
poisoning increases inference risk by injecting data to maximize leakage of
properties of the training dataset. For instance, in multi-party learning, a
malicious participant may contribute poisoned data crafted to amplify property
leakage of data from other participants.

#### Subject-level Distribution Inference

Subject-level distribution inference broadens the scope of user-level
membership inference by not assuming access to the user’s exact data that may
have been used to train a model. Instead, it only requires the adversary know
the distribution from which the target user’s data is sampled. Suri et al.
[59] present subject membership inference as a special case of distribution
inference. We similarly formalize subject-level inference in Game 9.

Input: $\mathcal{T},\mathcal{D},\mathcal{D}_{*},n,m,\mathcal{A}$

1 $b\sim\\{0,1\\}$

2 $\mathcal{D}_{1},\dotsc,\mathcal{D}_{m}\sim\mathcal{D}$

3 for  _$i=1,\dotsc,m-1$_ do

4 $S_{i}\sim{\mathcal{D}}_{i}^{n}$

5 end for

6if  _$b=0$_ then

7 $S_{m}\sim\mathcal{D}_{*}^{n}$

8else

9 $S_{m}\sim\mathcal{D}_{m}^{n}$

10 end if

11$\theta\leftarrow\mathcal{T}(\bigcup_{i=1}^{m}S_{i})$

$\tilde{b}\leftarrow\mathcal{A}\left(\mathcal{T},\mathcal{D},\mathcal{D}_{*},n,m,\theta\right)$

Game 9 $\mathsf{MI}^{\textsf{Subj}}$

The training data distribution is structured as a mixture of distributions
corresponding to a set of subjects. This is a property inference attack
because the adversary seeks to infer which of two distributions the training
data is sampled from. However, conceptually, the adversary’s goal is to infer
membership of a subject’s data since the only difference between the two
distributions is the presence of the target subject in the mixture.

A successful subject-level distribution inference attack can identify if a
user’s data was used to train the target model without knowing which exact
examples were used; i.e., with access to only the user’s data distribution and
not the sampled dataset as in Game 4.

###  III-E Differential Privacy Distinguishability

Differential Privacy Distinguishability (DPD) formalizes the threat model
underlying the definition of DP, where the adversary aims to distinguish
between models trained on adjacent datasets. We formalize as game
$\mathsf{DPD}$ in Game 10 the variant corresponding to the _substitute one_
adjacency relation, where two datasets are adjacent if one can be obtained
from the other by substituting a single record. The $\mathsf{DPD}$ game
represents a worst-case variant of the membership inference game $\mathsf{MI}$
where the training data and challenges are adversarially chosen.

Prior work used DP distinguishing attacks to statistically estimate or audit
the privacy of training pipelines [46, 32, 72, 63]. Marathe and Kanani [44]
define subject-level differential privacy by considering datasets as adjacent
when they differ in the data of a user, which can be seen as a counterpart to
user-level membership inference. Humphries et al. [31] and Balle et al. [4]
discuss strong membership inference, a threat model in between DPD and MI. In
this game, formalized as $\mathsf{SMI}$ in Game 10, the adversary knows but
does not choose the two adjacent datasets. As mentioned in Section II-B this
narrows the scope of the measured privacy, e.g., from worst to individual case
privacy.

Input:
$\mathcal{T},\mathcal{A},\definecolor{currentcolor}{rgb}{0,0,0}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\framebox{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}$\mathcal{A}^{\prime},n$}},$$S,z_{0},z_{1}$

$S,z_{0},z_{1}\leftarrow\mathcal{A}^{\prime}(\mathcal{T},n)$

// $|S|=n-1$

$b\sim\\{0,1\\}$

$\theta\leftarrow\mathcal{T}(S\cup\\{z_{b}\\})$

$\tilde{b}\leftarrow\mathcal{A}(\mathcal{T},\theta,S,z_{0},z_{1})$

Game 10 $\mathsf{DPD}$ $\mathsf{SMI}$ TABLE II: An overview of different games
and features of their corresponding threat models.
✓ indicates the game has this feature, – indicates the game does not have this feature, $\times$ indicates that the feature is not applicable. |  | Adversary Access | Challenge | Training Dataset | Adversary Interest
---|---|---|---|---|---
Game | Definition | Black-box | White-box | Rand | Adv | Param | Rand | Adv | Param | Record | Subject | Distribution
Membership Inference
$\mathsf{MI}$ |  Game 2 [70, 35, 31] | – | ✓ | ✓ | – | – | ✓ | – | – | ✓ | – | –
$\mathsf{MI}^{\textsf{skew}}$ |  Game 2 [34] | – | ✓ | ✓ | – | – | ✓ | – | – | ✓ | – | –
$\mathsf{MI}^{\textsf{BB}}$ |  Game 2 [12] | ✓ | – | ✓ | – | – | ✓ | – | – | ✓ | – | –
$\mathsf{MI}^{\mathsf{Adv}}$ |  Game 2 [13] | – | ✓ | – | ✓ | – | ✓ | – | – | ✓ | – | –
$\mathsf{MI}^{\textsf{Diff}}$ |  Game 3 [64] | ✓ | – | ✓ | – | – | ✓ | – | – | ✓ | – | –
$\mathsf{MI}^{\textsf{Pois}}$ |  Game 3 [64] | ✓ | – | ✓ | – | – | ✓ | ✓ | – | ✓ | – | –
$\mathsf{MI}^{\textsf{User}}$ |  Game 4 [41] | ✓ | – | – | – | ✓ | ✓ | – | – | – | ✓ | –
$\mathsf{MM}$ |  Game 11 [31] | – | ✓ | ✓ | – | – | ✓ | – | – | ✓ | – | ✓
$\mathsf{MI}^{\textsf{SQ}}$ |  Game 17 [61] | ✓ | – | ✓ | – | – | – | ✓ | – | ✓ | – | –
Attribute Inference and Model Inversion
$\mathsf{AI}$ |  Game 5 [70] | – | ✓ | ✓ | – | – | ✓ | – | – | ✓ | – | –
$\mathsf{Inv}$ |  Game 5 [67] | – | ✓ | ✓ | – | – | ✓ | – | – | ✓ | – | –
Data Reconstruction
$\mathsf{RC}$ |  Game 6 [4] | – | ✓ | ✓ | – | – | – | – | ✓ | ✓ | – | –
$\mathsf{RC}^{\textsf{Untarg}}$ |  Game 7 [11] | ✓ | – | $\times$ | $\times$ | $\times$ | ✓ | – | – | ✓ | – | –
$\mathsf{RC}^{\textsf{Targ}}$ |  Game 7 [10] | ✓ | – | ✓ | – | – | ✓ | – | – | ✓ | – | –
Distribution Inference
$\mathsf{PI}$ |  Game 8 [58] | – | ✓ | $\times$ | $\times$ | $\times$ | ✓ | – | – | – | – | ✓
$\mathsf{MI}^{\textsf{Subj}}$ |  Game 9 [59] | – | ✓ | ✓ | – | – | ✓ | – | – | – | ✓ | ✓
Differential Privacy Distinguishability
$\mathsf{DPD}$ |  Game 10 [43, 46] | – | ✓ | – | ✓ | – | – | ✓ | – | ✓ | – | –
$\mathsf{SMI}$ |  Game 10 [31, 4] | – | ✓ | – | – | ✓ | – | – | ✓ | ✓ | – | –

##  IV Relations and Proofs

In this section we establish relationships between privacy games. To this end,
we define a notion of _reduction_ and use it to translate attacks and
guarantees between the five fundamental games from the previous section, or
show that no generic connection can exist.

###  IV-A Reductions for Privacy Games

Inspired by notions of reduction from complexity theory and cryptography [1],
we introduce reductions between privacy games as a means of comparing the
various inference risks. Whilst reductions in cryptography are traditionally
based on asymptotic behavior governed by a security parameter, the reductions
we define here are closer to those used in _concrete security_ proofs, in that
the constants underlying the loss incurred in the reduction are made explicit.

######  Definition 2.

We say that game $G_{1}$ is reducible to game $G_{2}$ if there is a constant
$c>0$ such that, for any adversary $\mathcal{A}$ against $G_{2}$, there exists
an adversary $\mathcal{B}$ against $G_{1}$ such that

$\mathsf{Adv}_{G_{1}}(\mathcal{B})\geq
c\cdot\mathsf{Adv}_{G_{2}}(\mathcal{A})$

We denote this using the shorthand $G_{1}\preceq_{c}G_{2}$ and sometimes drop
the constant $c$.

The intuition behind the shorthand is that game $G_{1}$ is at most as hard to
win as $G_{2}$—modulo the constant $c$. This intuition holds for $c$ around or
larger than 1. For $c\ll 1$, however, the lower bound on
$\mathsf{Adv}_{G_{1}}(\mathcal{B})$ can get close to $0$, in which case the
intuition may be misleading.

Resilience to attacks Reductions between privacy games imply that attacks
against one game translate into attacks against the other. An equivalent
reading is the contrapositive, that resilience against attacks in one game
implies resilience against attacks in the other.

######  Definition 3.

A game $G$ is _$p$ -resilient_ if for all adversaries $\mathcal{A}$ against
$G$,

$\mathsf{Adv}_{G}(\mathcal{A})<p$

######  Proposition 1.

If $G_{1}\preceq_{c}G_{2}$ and $G_{1}$ is $p$-resilient then $G_{2}$ is
$p/c$-resilient.

###### Proof.

By contradiction: If there is an attack on $G_{2}$ with advantage more than
$p/c$, then there is one on $G_{1}$ with advantage more than $p$. ∎

Proofs of resilience are rare in the literature. Prime examples are results
that establish upper bounds on the advantage of a DP distinguisher when the
model is trained with differential privacy [70, 31]. The tightest known bound
is given in the following proposition.

######  Proposition 2 (Humphries et al. [31, Theorem 3.1]).

Let $\mathcal{T}$ be an $(\varepsilon,\delta)$-differentially private training
algorithm. Then

$\mathsf{Adv}_{\mathsf{DPD}}(\mathcal{A})\leq\frac{e^{\varepsilon}-1+2\delta}{e^{\varepsilon}+1}$

Therefore, any game the DP distinguisher inference game can be reduced to (see
Figure 1 for an overview) inherits the security benefits of training with
differential privacy via Propositions 1 and 2.

Separation Results No reductions exist between several games. For them, we
show separation results of the form $G_{1}\not\preceq{}G_{2}$. We establish
such results by showing that there is an instance of $G_{1}$ that is resilient
to attacks whereas its $G_{2}$ counterpart is not, and use 1 to conclude that
no reduction exists.

###  IV-B Overview of Relations between Games

Figure 1 shows the relations between the five fundamental privacy games. Each
node in the figure and in the following theorems refers to the basic game-
based definition of the corresponding inference risk, i.e., $\mathsf{MI}$,
$\mathsf{AI}$, $\mathsf{RC}$, $\mathsf{DPD}$, and $\mathsf{PI}$.

As expected, $\mathsf{PI}$ is fully disconnected: there exists a separation
result between it and every other game. This can be attributed to the PI
adversary’s goal of learning properties of the training data distribution
rather than about individual records as in the other games. $\mathsf{RC}$ and
$\mathsf{DPD}$ have the strongest threat models, where the adversary controls
the entire training dataset except for one example, and hence are
unsurprisingly the hardest to reduce from other games. Finally, $\mathsf{MI}$
and $\mathsf{AI}$ are reducible to each other and their relatively weak threat
models make both $\mathsf{RC}$ and $\mathsf{DPD}$ reducible to them. For this
reason, we use the $\mathsf{MI}$ game as the anchor for our proofs. We next
present results for a set of edges (solid lines) in Figure 1 that imply all
other relations. We defer the proofs to the Appendix.

###  IV-C Reductions

Despite reductions in either direction, $\mathsf{MI}$ and $\mathsf{AI}$ are
separable by constants in the reductions, with resilience against
$\mathsf{AI}$ easier to achieve than resilience against $\mathsf{MI}$. The
following theorems proved by Yeom et al. [70] relate $\mathsf{MI}$ and
$\mathsf{AI}$.

######  Theorem 1 ($\mathsf{MI}\preceq_{1}\mathsf{AI}$ [T]heorem 6).

Yeom:2020] For any adversary $\mathcal{A}_{\mathsf{AI}}$ against attribute
inference, there exists an adversary $\mathcal{A}_{\mathsf{MI}}$ against
membership inference such that

$\mathsf{Adv}_{\mathsf{MI}}(\mathcal{A}_{\mathsf{MI}})=\mathsf{Adv}_{\mathsf{AI}}(\mathcal{A}_{\mathsf{AI}})$

######  Theorem 2 ($\mathsf{AI}\preceq_{1/m}\mathsf{MI}$ [T]heorem 7).

Yeom:2020] Assume that for all $z\in\operatorname{supp}(\mathcal{D})$,
$\varphi(z)$ and $\pi(z)$ uniquely determine $z$. For any adversary
$\mathcal{A}_{\mathsf{MI}}$ against membership inference, there exists an
adversary $\mathcal{A}_{\mathsf{AI}}$ against attribute inference such that

$\mathsf{Adv}_{\mathsf{AI}}(\mathcal{A}_{\mathsf{AI}})=\frac{1}{m}\cdot\mathsf{Adv}_{\mathsf{MI}}(\mathcal{A}_{\mathsf{MI}})$

where $m$ is the number of possible values for the target attribute $\pi(z)$.

Resilience against $\mathsf{DPD}$ implies resilience against all other attacks
except $\mathsf{PI}$. We present the necessary theorems below. The remaining
reductions ($\mathsf{RC}\preceq\mathsf{AI},\mathsf{DPD}\preceq\mathsf{AI}$)
are implied by the ones we show.

Balle et al. [4, Theorem 3] show that training pipelines satisfying Rényi DP
(and thus $(\varepsilon,\delta)$-DP) enjoy resilience against reconstruction
attacks. In contrast, a bound on $\mathsf{Adv}_{\mathsf{DPD}}$ does not imply
a nontrivial bound on $\varepsilon$ in $(\varepsilon,\delta)$. In fact,
$\mathsf{Adv}_{\mathsf{DPD}}\leq\delta$ is equivalent to $(0,\delta)$-DP.
Thus, we require an anti-concentration bound on the prior $\pi$ and that
reconstruction succeeds with probability at least $\nicefrac{{1}}{{2}}$ to
reduce $\mathsf{DPD}$ to $\mathsf{RC}$.

######  Theorem 3 (proof:DPDtoRC).

$\mathsf{DPD}\preceq\mathsf{RC}$] Let $\pi$ be a prior over samples, $S$ a
dataset of $n-1$ samples, and $\ell$ a symmetric reconstruction loss
satisfying the triangle inequality. Let $\mathcal{A}$ be an adversary against
data reconstruction ($\mathsf{RC}$) w.r.t. $S$ and $\pi$ that reconstructs its
challenge within error $\eta$ with probability
$\gamma\geq\nicefrac{{1}}{{2}}$. Let

$\alpha=\inf_{z_{0}\in\operatorname{supp}(\pi)}\Pr\\!\left[z_{1}\sim\pi\\!:\\!\ell(z_{0},z_{1})>2\eta\right]$

There exists a DP distinguisher $\mathcal{A}_{\mathsf{DPD}\to\mathsf{RC}}$
such that

$\mathsf{Adv}_{\mathsf{DPD}}(\mathcal{A}_{\mathsf{DPD}\to\mathsf{RC}})\geq
2\alpha\left(\gamma-\frac{1}{2}\right)$

DP distinguishability can be reduced to membership inference. This is an
example of a generic class of reductions: In both games the adversary has the
same goal and their advantage is identically defined, but in game
$\mathsf{MI}$ the adversary has strictly fewer capabilities than in
$\mathsf{DPD}$. Thus, any adversary against $\mathsf{MI}$ can be turned into a
valid adversary against $\mathsf{DPD}$ with the same advantage. In general, a
more informed/capable adversary, such as a DP distinguisher, can be used to
build a reduction to games with a less informed/capable adversary.

######  Theorem 4 (proof:DPDtoMI).

$\mathsf{DPD}\preceq\mathsf{MI}$] For any adversary
$\mathcal{A}_{\mathsf{MI}}$ against membership inference, there exists a DP
distinguisher $\mathcal{A}_{\mathsf{DPD}}$ such that

$\mathsf{Adv}_{\mathsf{DPD}}(\mathcal{A}_{\mathsf{DPD}})=\mathsf{Adv}_{\mathsf{MI}}(\mathcal{A}_{\mathsf{MI}})$

Finally, we show that a membership inference attack can be turned into a
reconstruction attack, with a constant depending on the size of the support of
the training data distribution.

######  Theorem 5 (proof:RCtoMI).

$\mathsf{RC}\preceq_{1/|\operatorname{supp}(\mathcal{D})|}\mathsf{MI}$] For
any membership inference adversary $\mathcal{A}$ against
$\mathsf{MI}(\mathcal{T},\mathcal{D},n)$ there exists a reconstruction
adversary $\mathcal{B}$ against
$\mathsf{RC}^{\textsf{Ran}}(\mathcal{D},n,\mathcal{D},\mathcal{T})$ (i.e.,
with prior $\pi=\mathcal{D}$) such that

$\mathsf{Adv}_{\mathsf{RC}^{\textsf{Ran}}}(\mathcal{B})=\frac{1}{|\operatorname{supp}(\mathcal{D})|}\cdot\mathsf{Adv}_{\mathsf{MI}}(\mathcal{A})$

###  IV-D Separation Results

######  Theorem 6 (proof:MItoPI).

$\mathsf{MI}\not\preceq\mathsf{PI}$] Resilience against membership inference
does not imply resilience against property inference.

######  Theorem 7 (proof:MItoDPD).

$\mathsf{MI}\not\preceq\mathsf{DPD}$] Resilience against membership inference
does not imply resilience against DP distinguishability.

######  Theorem 8 (proof:MItoRC).

$\mathsf{MI}\not\preceq\mathsf{RC}$] Resilience against membership inference
does not imply resilience against reconstruction.

This last counterintuitive separation result stems from a discrepancy between
adversary capabilities: The $\mathsf{MI}$ game is based on an average case
scenario, while the reconstruction game assumes a more informed worst-case
adversary. By considering a membership adversary matching the capabilities of
the adversary in the $\mathsf{RC}$ game, we can build a reduction to data
reconstruction. We show this in LABEL:thmt@@SMItoRC in the Appendix, which
reduces the strong membership inference game $\mathsf{SMI}$ (Game 10) to game
$\mathsf{RC}$.

######  Theorem 9 (proof:PItoMI).

$\mathsf{PI}\not\preceq\mathsf{MI}$] Resilience against property inference
does not imply resilience against membership inference.

######  Theorem 10 (proof:RCtoDPD).

$\mathsf{RC}\not\preceq\mathsf{DPD}$] Resilience against reconstruction does
not imply resilience against DP distinguishability.

######  Theorem 11 (proof:DPDtoPI).

$\mathsf{DPD}\not\preceq\mathsf{PI}$] Resilience against DP distinguishability
does not imply resilience against property inference.

##  V Case Study: Mixture Model Membership Inference

We present a case study where we showcase the expressive power and rigor of
privacy games. In particular, we show that a novel variant of membership
inference can be decomposed into a combination of membership and property
inference. This complex relationship goes beyond the direct reductions
presented in Section IV. In our proofs, we exploit _code-based_ reductions
structured as a sequence of games; i.e., our arguments rely on transforming
code with a formal semantics.

The game we target is due to Humphries et al. [31], who use it to model
membership inference attacks in the presence of dependencies in the training
data. In their game ($\mathsf{MM}$ in Game 11), the training data follows a
two-stage _mixture model_. Examples in the training dataset and the target
example are chosen independently from two data distributions,
$\mathcal{D}_{k}$ and $\mathcal{D}_{k^{\prime}}$, which are chosen uniformly
at random without replacement from $K$ possible distributions
$\boldsymbol{\mathcal{D}}=\\{\mathcal{D}_{1},\dotsc,\mathcal{D}_{K}\\}$.

Input: $\mathcal{T},\boldsymbol{\mathcal{D}},n,\mathcal{A}$

$k\sim[K]$

$k^{\prime}\sim[K]\setminus\\{k\\}$

$S\sim\mathcal{D}_{k}^{n}$

$\theta\leftarrow\mathcal{T}(S)$

$b\sim\\{0,1\\}$

if  _$b=0$_ then

$z\sim S_{\phantom{}}$ $z\sim\mathcal{D}_{k}$

else

$z\sim\mathcal{D}_{k^{\prime}}$

end if

$\tilde{b}\leftarrow\mathcal{A}(\mathcal{T},\boldsymbol{\mathcal{D}},n,\theta,z)$

Game 11 $\mathsf{MM}_{\phantom{}}$ $G_{0}$

Input: $\mathcal{T},\boldsymbol{\mathcal{D}},n,\mathcal{A}$

$k\sim[K]$

$k^{\prime}\sim[K]\setminus\\{k\\}$

$z\sim\mathcal{D}_{k}$

$b\sim\\{0,1\\}$

if  _$b=0$_ then

$S\sim\mathcal{D}_{k}^{n}$

else

$S\sim\mathcal{D}_{k^{\prime}}^{n}$

end if

$\theta\leftarrow\mathcal{T}(S)$

$\tilde{b}\leftarrow\mathcal{A}(\mathcal{T},\boldsymbol{\mathcal{D}},n,\theta,z)$

Game 12 $G_{1}$

We show that $\mathsf{MM}$ can be decomposed into a property inference goal
(inferring the training data distribution) and a membership inference goal
(inferring whether a target example has been sampled from the training data
distribution $\mathcal{D}_{k}$ or from the training dataset $S$).

######  Theorem 12.

For any adversary $\mathcal{A}$ against $\mathsf{MM}$, there exist adversaries
$\mathcal{A}_{\mathsf{MI}}^{i}$ and $\mathcal{A}_{\mathsf{PI}}^{i,j}$ such
that

$\mathsf{Adv}_{\mathsf{MM}}(\mathcal{A})\leq\max_{i\in[K]}\mathsf{Adv}_{\mathsf{MI}_{i}}(\mathcal{A}_{\mathsf{MI}}^{i})+\max_{i\neq
j\in[K]}\mathsf{Adv}_{\mathsf{PI}_{i,j}}(\mathcal{A}_{\mathsf{PI}}^{i,j})$

where $\mathsf{MI}_{i}$ is the membership inference game with training data
distribution $\mathcal{D}_{i}$, and in $\mathsf{PI}_{i,j}$ the property to
infer is whether the training data distribution is $\mathcal{D}_{i}$ or
$\mathcal{D}_{j}$.

###### Proof.

Let $\mathcal{A}$ be an adversary against $\mathsf{MM}$. Consider $G_{0}$
shown alongside $\mathsf{MM}$ in Game 11. Its only difference w.r.t.
$\mathsf{MM}$ is that when $b=0$, the example $z$ is freshly sampled from the
training data distribution $\mathcal{D}_{k}$ rather than from the training
dataset $S$. Conditioned on $b=0,k=i$, distinguishing between games $G_{0}$
and $\mathsf{MM}$ is as difficult as winning a membership inference game. We
show this using a black-box reduction: fixing $k=i$, we construct an adversary
$\mathcal{A}_{\mathsf{MI}}^{i}$ that uses $\mathcal{A}$ as an oracle to guess
the challenge bit $b$ in game $\mathsf{MI}_{i}$ (see Game 13).
$\mathcal{A}_{\mathsf{MI}}^{i}$ simply forwards its inputs
$\mathcal{T},n,\theta,z$ to $\mathcal{A}$, passing to it in addition the
distribution set $\boldsymbol{\mathcal{D}}$.

Input: $\mathcal{T},\mathcal{D}_{i},n,\mathcal{A}$

$S\sim\mathcal{D}_{i}^{n}$

$\theta\leftarrow\mathcal{T}(S)$

$b\sim\\{0,1\\}$

if  _$b=0$_ then $z\sim S$ else $z\sim\mathcal{D}_{i}$

$\tilde{b}\leftarrow\mathcal{A}_{\mathsf{MI}}^{i}(\mathcal{T},\mathcal{D}_{i},n,\theta,z)$

Game 13 $\mathsf{MI}_{i}$

Input: $\mathcal{T},\mathcal{D}_{i},n,\theta,z$

return $\mathcal{A}(\mathcal{T},\boldsymbol{\mathcal{D}},n,\theta,z)$

Adversary 14 $\mathcal{A}_{\mathsf{MI}}^{i}$

Game $\mathsf{MM}$ conditioned on $b=0,k=i$ is equivalent to $\mathsf{MI}_{i}$
conditioned on $b=0$. Likewise, game $G_{0}$ conditioned on $b=0,k=i$ is
equivalent to $\mathsf{MI}_{i}$ conditioned on $b=1$. Hence,

$\displaystyle\mathsf{Adv}_{\mathsf{MI}_{i}}(\mathcal{A}_{\mathsf{MI}}^{i})$
$\displaystyle=\Pr\\!\left[\mathsf{MI}_{i}\\!:\\!\lnot\tilde{b}\mid\lnot
b\right]-\Pr\\!\left[\mathsf{MI}_{i}\\!:\\!\lnot\tilde{b}\mid b\right]$
$\displaystyle=\Pr\\!\left[\mathsf{MM}\\!:\\!\lnot\tilde{b}\mid\lnot
b,k=i\right]-\Pr\\!\left[G_{0}\\!:\\!\lnot\tilde{b}\mid\lnot b,k=i\right]$ (2)

Game $\mathsf{MM}$ conditioned on $b=1$ is equivalent to $G_{0}$ conditioned
on $b=1$, and so we have

$\displaystyle\mathsf{Adv}_{\mathsf{MM}}(\mathcal{A})$
$\displaystyle=\Pr\\!\left[\mathsf{MM}\\!:\\!\lnot\tilde{b}\mid\lnot
b\right]-\Pr\\!\left[\mathsf{MM}\\!:\\!\lnot\tilde{b}\mid b\right]$
$\displaystyle=\\!\frac{1}{K}\\!\sum_{i=1}^{K}\Pr\\!\left[\mathsf{MM}\\!:\\!\lnot\tilde{b}\mid\lnot
b,k=i\right]-\Pr\\!\left[\mathsf{MM}\\!:\\!\lnot\tilde{b}\mid b,k=i\right]$
$\displaystyle=\\!\frac{1}{K}\\!\sum_{i=1}^{K}\mathsf{Adv}_{\mathsf{MI}_{i}}(\mathcal{A}_{\mathsf{MI}}^{i})\\!+\\!\Pr\\!\left[G_{0}\\!:\\!\lnot\tilde{b}\\!\mid\\!\lnot
b\right]\\!\\!-\\!\\!\Pr\\!\left[G_{0}\\!:\\!\lnot\tilde{b}\\!\mid\\!b\right]$
(3)

where the last equation follows from (2) and the fact that $b$ and $k$ are
independent.

We reformulate $G_{0}$ as $G_{1}$ (see Game 12). To see why both formulations
are equivalent, note that conditioned on $b=0$, in both games $S$ and $z$ are
sampled from the same distribution chosen uniformly from
$\boldsymbol{\mathcal{D}}$, while conditioned on $b=1$, $S$ and $z$ are
sampled each from one of two distributions sampled without replacement from
$\boldsymbol{\mathcal{D}}$. Since $b$ is independently sampled in the same
way, both games result in the same joint distribution of $\theta,z,b$, and
therefore $\tilde{b},b$:

$\displaystyle\Pr\\!\left[G_{0}\\!:\\!\lnot\tilde{b}\mid\lnot b\right]$
$\displaystyle=\Pr\\!\left[G_{1}\\!:\\!\lnot\tilde{b}\mid\lnot b\right]$ (4)
$\displaystyle\Pr\\!\left[G_{0}\\!:\\!\lnot\tilde{b}\mid b\right]$
$\displaystyle=\Pr\\!\left[G_{1}\\!:\\!\lnot\tilde{b}\mid b\right]$ (5)

Next, we show using a black-box reduction that distinguishing between the case
when $b=0$ and $b=1$ in $G_{1}$ conditioned on $k=i,k^{\prime}=j$ is as hard
as guessing the challenge bit in the property inference experiment
$\mathsf{PI}_{i,j}$ shown in Game 15. To do this, we construct an adversary
$\mathcal{A}_{\mathsf{PI}}^{i,j}$ that uses $\mathcal{A}$ as a black-box.
$\mathcal{A}_{\mathsf{PI}}^{i,j}$ perfectly simulates the inputs to
$\mathcal{A}$ in $G_{1}$ by forwarding its own inputs and freshly sampling $z$
from $\mathcal{D}_{i}$.

$\displaystyle\mathsf{Adv}_{\mathsf{PI}_{i,j}}(\mathcal{A}_{\mathsf{PI}}^{i,j})$
$\displaystyle=\Pr\\!\left[\mathsf{PI}_{i,j}\\!:\\!\lnot\tilde{b}\mid\lnot
b\right]-\Pr\\!\left[\mathsf{PI}_{i,j}\\!:\\!\lnot\tilde{b}\mid b\right]$
$\displaystyle=\Pr\\!\left[G_{1}\\!:\\!\lnot\tilde{b}\\!\mid\\!\lnot
b,k\\!=\\!i,k^{\prime}\\!=\\!j\right]\\!-\\!\Pr\\!\left[G_{1}\\!:\\!\lnot\tilde{b}\\!\mid\\!b,k\\!=\\!i,k^{\prime}\\!=\\!j\right]$

Putting this and (3)–(5) together we obtain

$\displaystyle\mathsf{Adv}_{\mathsf{MM}}(\mathcal{A})$
$\displaystyle=\begin{aligned}
&\frac{1}{K}\sum_{i=1}^{K}\mathsf{Adv}_{\mathsf{MI}_{i}}(\mathcal{A}_{\mathsf{MI}}^{i})\\\
&+\frac{1}{K(K-1)}\sum_{i=1}^{K}\sum_{j=1,i\neq
j}^{K}\mathsf{Adv}_{\mathsf{PI}_{i,j}}(\mathcal{A}_{\mathsf{PI}}^{i,j})\end{aligned}$
$\displaystyle\leq\max_{i\in[K]}\mathsf{Adv}_{\mathsf{MI}_{i}}(\mathcal{A}_{\mathsf{MI}}^{i})+\max_{i\neq
j\in[K]}\mathsf{Adv}_{\mathsf{PI}_{i,j}}(\mathcal{A}_{\mathsf{PI}}^{i,j})\qed$

Input: $\mathcal{T},\mathcal{D}_{i},\mathcal{D}_{j},n,\mathcal{A}$

$b\sim\\{0,1\\}$

if  _$b=0$_ then

$S\sim\mathcal{D}_{i}^{n}$

else

$S\sim\mathcal{D}_{j}^{n}$

end if

$\theta\leftarrow\mathcal{T}(S)$

$\tilde{b}\leftarrow\mathcal{A}_{\mathsf{PI}}^{i,j}(\mathcal{T},\mathcal{D}_{i},\mathcal{D}_{j},n,\theta)$

Game 15 $\mathsf{PI}_{i,j}$

Input: $\mathcal{T},\mathcal{D}_{i},\mathcal{D}_{j},n,\theta$

$z\sim\mathcal{D}_{i}$

return $\mathcal{A}(\mathcal{T},\boldsymbol{\mathcal{D}},n,\theta,z)$

Adversary 16 $\mathcal{A}_{\mathsf{PI}}^{i,j}$

##  VI Discussion

We discuss strategies for choosing privacy games, their current and future
uses, and their limitations.

###  VI-A Selecting Games

With the variety of privacy games in the literature, it is natural to ask
whether there is a _canonical_ game that should be used instead of others. We
believe this is not the case, i.e., no single game is the best choice in all
circumstances because subtle differences in threat scenarios can lead to
vastly different privacy evaluations (see, e.g., [46]). Instead, we recommend
that users of games leverage the building blocks we provide in this paper to
design games that accurately capture their application-specific threat models.
For a given threat model, however, some differences between modelling choices
are less important (e.g., in MI, whether one samples nonmembers from the full
distribution or excluding the training set), and we highlight this distinction
throughout the paper.

###  VI-B Current Uses of Privacy Games

The use of privacy games has become prevalent in the literature on machine
learning privacy. As of today, there have been two main applications:  1.
supporting the _empirical evaluation_ of machine learning systems against a
variety of threats, and  2. _comparing_ the strength of privacy properties and
attacks.  Reductions enable a third application: translating _provable
guarantees_ from one property to another.

Game-based definitions of inference risks are presented in often inconsistent
form fragmented across the literature and only a few of the reductions and
separation results in Figure 1 were made explicit. We present a common
vocabulary for game-based definitions, formalize games for five fundamental
inference risks, and establish connections between them.

###  VI-C Prospective Uses of Privacy Games

We highlight two other promising uses for games.

Communicating privacy properties Reasoning about ML privacy risks is not the
exclusive purview of researchers. Other personas, e.g., privacy managers and
auditors, need to make decisions about the compliance of training pipelines
with regulatory or contractual constraints. Based on our experience, privacy
managers currently base their reasoning on (1) empirical privacy evaluations,
(2) formal guarantees of mechanisms such as DP-SGD, and (3) informal texts
such as the _Opinion 05/2014_ [2] of the European Commission’s Article 29
Working Party. They are then faced with the daunting task of combining these
pieces into a coherent picture to assess the privacy risks of specific
applications. Privacy games can help with this task: by making the threat
model and assumptions about dataset creation and training explicit, they can
disambiguate interpretations and can abstract an application scenario with
respect to its (provable and empirical) privacy properties. Indeed, based on
our initial experience, games facilitate discussing privacy goals and
guarantees with stakeholders making guidelines and decisions around ML
privacy.

Mechanization of proofs An advantage of the game-based formalism is that games
can be given an unambiguous semantics as probabilistic programs. This enables
reasoning about games using program logics and manipulating them using program
transformations. Reusable program transformations (e.g., procedure inlining)
and proof techniques (e.g., conditioning on events) arise naturally and make
proofs more amenable. As we show in Section V, our proofs exhibit some of
these patterns.

We envisage techniques and frameworks to reason about game-based cryptographic
proofs (e.g., EasyCrypt, FCF) being repurposed to reason about privacy games.
The apparent complexity of privacy games compared to cryptographic games is
not an obstacle since most proofs manipulate training algorithms, models, and
data as abstract objects with minimal structure. For instance, we think it is
possible to formalize the proof in Section V in a tool like EasyCrypt. The
main challenge for mechanizing proofs about privacy games is that, unlike
cryptographic games, privacy games sometimes require reasoning about
continuous distributions (e.g., Gaussian noise in DP-SGD), but logics
implemented in existing frameworks often assume a discrete probability space.

###  VI-D Limitations of Privacy Games

Privacy games are sequential probabilistic programs; they are not an immediate
fit for expressing concurrent computations. This prevents the direct
application of games to important scenarios such as federated learning (FL).
Intuitively, this is due to the hardness of modeling the various possible
parallel interactions between the different parties. The situation is similar
for cryptographic games, where process calculi are used instead of games for
modeling more complex multi-party interactions [8, 45]. It is an open question
whether these calculi could also be used in the context of concurrent ML
scenarios such as FL.

##  VII Related Work

Alternatives We discuss below informal and formal alternatives to games to
express privacy properties.

A key example of a _formal_ property is Differential Privacy [21]. The
definition of Differential privacy is relational, in that it compares the
probability of events in two alternative worlds. DP abstracts from many
details that are relevant for threat modelling, such as adversary
capabilities, goals, and background knowledge, as well as the way datasets are
created. This has led to disagreements in the literature about the
consequences of differential privacy (see [65]).

A key example of an _informal_ account of privacy properties is the _Opinion
05/2014 on Anonymization Techniques_ [2] that complements the EU General Data
Protection Regulation (GDPR) with practical recommendations for the use of
anonymization techniques to meet the requirements set out by the regulator. In
this influential document, the authors identify three privacy risks: _singling
out_ , _linkability_ , and _inference_. They analyze the suitability of
different anonymization techniques—including $k$-anonymity and DP—for
mitigating these risks, but the discussion remains inconclusive due to the
lack of precise definitions. Subsequent research [18] rigorously revisited the
notion of singling out and suggested reconsidering the Opinion
recommendations.

Game-based definitions address shortcomings of both alternatives: They make
the threat model and assumptions explicit and precise, which helps
disambiguate interpretations.

Game-based privacy proofs Nissim et al. [47] construct a privacy game that
reflects the requirements of the U.S. Family Educational Rights and Privacy
Act (FERPA) for protecting privacy in releases of education records, and show
in a proof structured as a sequence of games that DP is enough to satisfy
these requirements. While constructing the game, they identify dimensions
similar to our anatomy in Section II.

Surveys and taxonomies on privacy Several papers propose taxonomies of privacy
attacks against machine learning systems [39, 50, 19]. Papernot et al. [49]
focus on systematizing the possible attack surfaces of standard machine
learning pipelines. Desfontaines and Pejó [20] systematically study variants
and extensions of differential privacy. Before attacks against ML systems were
demonstrated, Li et al. [37] proposed a unifying framework for membership and
differential privacy definitions mainly applicable to database systems.

## Acknowledgment

This work was partially funded by the U.S. National Science Foundation through
the Center for Trustworthy Machine Learning (#1804603).

## References

  * Arora and Barak [2009] S. Arora and B. Barak.  _Computational Complexity: A Modern Approach_.  Cambridge University Press, 2009.
  * Article 29 Data Protection Working Party [2014] Article 29 Data Protection Working Party.  Opinion 05/2014 on anonymization techniques, Nov 2014.
  * Ateniese et al. [2015] G. Ateniese, L. V. Mancini, A. Spognardi, A. Villani, D. Vitali, and G. Felici.  Hacking smart machines with smarter ones: How to extract meaningful data from machine learning classifiers.  _Int. J. Secur. Netw._ , 10(3):137–150, 2015\.
  * Balle et al. [2022] B. Balle, G. Cherubin, and J. Hayes.  Reconstructing training data with informed adversaries.  In _43rd IEEE Symposium on Security and Privacy (S &P)_, pp. 1138–1156. IEEE, 2022.
  * Barthe et al. [2009] G. Barthe, B. Grégoire, and S. Zanella-Béguelin.  Formal certification of code-based cryptographic proofs.  In _36th annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL)_ , pp. 90–101. ACM, 2009.
  * Bellare and Rogaway [2006] M. Bellare and P. Rogaway.  The security of triple encryption and a framework for code-based game-playing proofs.  In _Advances in Cryptology – EUROCRYPT_ , pp. 409–426. Springer, 2006.
  * Bellare et al. [1997] M. Bellare, A. Desai, E. Jokipii, and P. Rogaway.  A concrete security treatment of symmetric encryption.  In _38th Annual Symposium on Foundations of Computer Science (FOCS)_ , pp. 394–403. IEEE, 1997.
  * Blanchet [2007] B. Blanchet.  Computationally sound mechanized proofs of correspondence assertions.  In _20th IEEE Computer Security Foundations Symposium (CSF)_ , pp. 97–111. IEEE, 2007.
  * Blanchet [2012] B. Blanchet.  Mechanizing game-based proofs of security protocols.  _Software Safety and Security_ , 33:1–25, 2012.
  * Carlini et al. [2019] N. Carlini, C. Liu, Ú. Erlingsson, J. Kos, and D. Song.  The secret sharer: Evaluating and testing unintended memorization in neural networks.  In _28th USENIX Security Symposium_ , pp. 267–284. USENIX Association, 2019.
  * Carlini et al. [2021] N. Carlini, F. Tramèr, E. Wallace, M. Jagielski, A. Herbert-Voss, K. Lee, A. Roberts, T. Brown, D. Song, Ú. Erlingsson, A. Oprea, and C. Raffel.  Extracting training data from large language models.  In _30th USENIX Security Symposium_ , pp. 2633–2650. USENIX Association, 2021.
  * Carlini et al. [2022] N. Carlini, S. Chien, M. Nasr, S. Song, A. Terzis, and F. Tramèr.  Membership inference attacks from first principles.  In _43rd IEEE Symposium on Security and Privacy (S &P)_, pp. 1546–1564. IEEE, 2022.
  * Chang and Shokri [2021] H. Chang and R. Shokri.  On the privacy risks of algorithmic fairness.  In _6th IEEE European Symposium on Security and Privacy (EuroS &P)_, pp. 292–303. IEEE, 2021.
  * Chatzikokolakis et al. [2020] K. Chatzikokolakis, G. Cherubin, C. Palamidessi, and C. Troncoso.  The Bayes security measure.  _arXiv preprint arXiv:2011.03396 [cs.CR]_ , 2020.
  * Chaudhari et al. [2023] H. Chaudhari, J. Abascal, A. Oprea, M. Jagielski, F. Tramèr, and J. Ullman.  SNAP: Efficient extraction of private properties with poisoning.  In _44th IEEE Symposium on Security and Privacy (S &P)_, pp. 1935–1952. IEEE, 2023.
  * Chen et al. [2020] D. Chen, N. Yu, Y. Zhang, and M. Fritz.  GAN-leaks: A taxonomy of membership inference attacks against generative models.  In _27th ACM SIGSAC Conference on Computer and Communications Security (CCS)_ , pp. 343–362. ACM, 2020.
  * Choquette Choo et al. [2021] C. A. Choquette Choo, F. Tramèr, N. Carlini, and N. Papernot.  Label-only membership inference attacks.  In _International Conference on Machine Learning (ICML)_ , vol. 139, pp. 1964–1974. PMLR, 2021.
  * Cohen and Nissim [2020] A. Cohen and K. Nissim.  Towards formalizing the GDPR’s notion of singling out.  _Proc. Natl. Acad. Sci. USA_ , 117(15):8344–8352, 2020.
  * De Cristofaro [2021] E. De Cristofaro.  A critical overview of privacy in machine learning.  _IEEE Security & Privacy_, 19(4):19–27, 2021\.
  * Desfontaines and Pejó [2020] D. Desfontaines and B. Pejó.  SoK: Differential privacies.  _Priv. Enhancing Technol._ , 2020(2):288–313, 2020.
  * Dwork et al. [2006] C. Dwork, F. McSherry, K. Nissim, and A. Smith.  Calibrating noise to sensitivity in private data analysis.  In _3rd Theory of Cryptography Conference (TCC)_ , pp. 265–284. Springer, 2006.
  * Fredrikson et al. [2015] M. Fredrikson, S. Jha, and T. Ristenpart.  Model inversion attacks that exploit confidence information and basic countermeasures.  In _22nd ACM SIGSAC Conference on Computer and Communications Security (CCS)_ , pp. 1322–1333. ACM, 2015.
  * Ganju et al. [2018] K. Ganju, Q. Wang, W. Yang, C. A. Gunter, and N. Borisov.  Property inference attacks on fully connected neural networks using permutation invariant representations.  In _26th ACM SIGSAC Conference on Computer and Communications Security (CCS)_ , pp. 619–633. ACM, 2018.
  * Gao et al. [2022] J. Gao, S. Garg, M. Mahmoody, and P. N. Vasudevan.  Deletion inference, reconstruction, and compliance in machine (un)learning.  _Priv. Enhancing Technol._ , pp. 415–436, 2022.
  * Goldwasser and Micali [1982] S. Goldwasser and S. Micali.  Probabilistic encryption & how to play mental poker keeping secret all partial information.  In _14th Annual ACM Symposium on Theory of Computing (STOC)_ , pp. 365–377. ACM, 1982.
  * Hartmann et al. [2023] V. Hartmann, L. Meynent, M. Peyrard, D. Dimitriadis, S. Tople, and R. West.  Distribution inference risks: Identifying and mitigating sources of leakage.  In _IEEE Conference on Secure and Trustworthy Machine Learning (SaTML)_ , 2023.  To appear.
  * Hayes et al. [2019] J. Hayes, L. Melis, G. Danezis, and E. D. Cristofaro.  LOGAN: Evaluating privacy leakage of generative models using generative adversarial networks.  _Priv. Enhancing Technol._ , 2019:133–152, 2019.
  * He et al. [2020] Y. He, S. Rahimian, B. Schiele1, and M. Fritz.  Segmentations-Leak: Membership inference attacks and defenses in semantic image segmentation.  In _European Conference on Computer Vision (ECCV)_ , pp. 519–535. Springer, 2020.
  * Hilprecht et al. [2019] B. Hilprecht, M. Härterich, and D. Bernau.  Monte Carlo and reconstruction membership inference attacks against generative models.  _Priv. Enhancing Technol._ , 2019:232–249, 2019.
  * Hui et al. [2021] B. Hui, Y. Yang, H. Yuan, P. Burlina, N. Z. Gong, and Y. Cao.  Practical blind membership inference attack via differential comparisons.  In _28th Network and Distributed System Security Symposium (NDSS)_. Internet Society, 2021.
  * Humphries et al. [2020] T. Humphries, S. Oya, L. Tulloch, M. Rafuse, I. Goldberg, U. Hengartner, and F. Kerschbaum.  Investigating membership inference attacks under data dependencies.  _arXiv preprint arXiv:2010.12112 [cs.CR]_ , 2020.
  * Jagielski et al. [2020] M. Jagielski, J. Ullman, and A. Oprea.  Auditing differentially private machine learning: How private is private SGD? In _Advances in Neural Information Processing Systems (NeurIPS)_ , vol. 33, pp. 22205–22216. Curran Associates, Inc., 2020.
  * Jayaraman and Evans [2022] B. Jayaraman and D. Evans.  Are attribute inference attacks just imputation? In _29th ACM SIGSAC Conference on Computer and Communications Security (CCS)_ , pp. 1569–1582. ACM, 2022.
  * Jayaraman et al. [2021] B. Jayaraman, L. Wang, K. Knipmeyer, Q. Gu, and D. Evans.  Revisiting membership inference under realistic assumptions.  _Priv. Enhancing Technol._ , pp. 348–368, 2021.
  * Kulynych et al. [2022] B. Kulynych, M. Yaghini, G. Cherubin, M. Veale, and C. Troncoso.  Disparate vulnerability to membership inference attacks.  _Priv. Enhancing Technol._ , pp. 460–480, 2022.
  * Leino and Fredrikson [2020] K. Leino and M. Fredrikson.  Stolen memories: Leveraging model memorization for calibrated white-box membership inference.  In _29th USENIX Security Symposium_ , pp. 1605–1622. USENIX Association, 2020.
  * Li et al. [2013] N. Li, W. Qardaji, D. Su, Y. Wu, and W. Yang.  Membership privacy: A unifying framework for privacy definitions.  In _20th ACM SIGSAC Conference on Computer and Communications Security (CCS)_ , pp. 889–900. ACM, 2013.
  * Li and Zhang [2021] Z. Li and Y. Zhang.  Membership leakage in label-only exposures.  In _28th ACM SIGSAC Conference on Computer and Communications Security (CCS)_ , pp. 880–895. ACM, 2021.
  * Liu et al. [2021a] B. Liu, M. Ding, S. Shaham, W. Rahayu, F. Farokhi, and Z. Lin.  When machine learning meets privacy: A survey and outlook.  _ACM Comput. Surv._ , 54(2):1–36, 2021a.
  * Liu et al. [2021b] H. Liu, J. Jia, W. Qu, and N. Z. Gong.  EncoderMI: Membership inference against pre-trained encoders in contrastive learning.  In _28th ACM SIGSAC Conference on Computer and Communications Security (CCS)_ , pp. 2081–2095. ACM, 2021b.
  * Mahloujifar et al. [2021] S. Mahloujifar, H. A. Inan, M. Chase, E. Ghosh, and M. Hasegawa.  Membership inference on word embedding and beyond.  _arXiv preprint arXiv:2106.11384 [cs.CL]_ , 2021.
  * Mahloujifar et al. [2022] S. Mahloujifar, E. Ghosh, and M. Chase.  Property inference from poisoning.  In _43rd IEEE Symposium on Security and Privacy (S &P)_, pp. 1120–1137. IEEE, 2022.
  * Malek Esmaeili et al. [2021] M. Malek Esmaeili, I. Mironov, K. Prasad, I. Shilov, and F. Tramèr.  Antipodes of label differential privacy: PATE and ALIBI.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , vol. 34, pp. 6934–6945. Curran Associates, Inc., 2021.
  * Marathe and Kanani [2022] V. J. Marathe and P. Kanani.  Subject granular differential privacy in federated learning.  _arXiv preprint arXiv:2206.03617 [cs.LG]_ , 2022.
  * Meier et al. [2013] S. Meier, B. Schmidt, C. Cremers, and D. Basin.  The TAMARIN prover for the symbolic analysis of security protocols.  In _Computer Aided Verification (CAV)_ , pp. 696–701. Springer, 2013\.
  * Nasr et al. [2021] M. Nasr, S. Songi, A. Thakurta, N. Papernot, and N. Carlini.  Adversary instantiation: Lower bounds for differentially private machine learning.  In _42nd IEEE Symposium on Security and Privacy (S &P)_, pp. 866–882. IEEE, 2021.
  * Nissim et al. [2018] K. Nissim, A. Bembenek, A. Wood, M. Bun, M. Gaboardi, U. Gasser, D. O’Brien, S. P. Vadhan, and T. Steinke.  Bridging the gap between computer science and legal approaches to privacy.  _Harvard Journal of Law & Technology_, 31(2):687–780, 2018.
  * Orekondy et al. [2019] T. Orekondy, B. Schiele, and M. Fritz.  Knockoff nets: Stealing functionality of black-box models.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 4949–4958. IEEE, 2019.
  * Papernot et al. [2018] N. Papernot, P. McDaniel, A. Sinha, and M. P. Wellman.  SoK: Security and privacy in machine learning.  In _3rd IEEE European Symposium on Security and Privacy (EuroS &P)_, pp. 399–414. IEEE, 2018.
  * Rigaki and Garcia [2020] M. Rigaki and S. Garcia.  A survey of privacy attacks in machine learning.  _arXiv preprint arXiv:2007.07646 [cs.CR]_ , 2020.
  * Rogaway [2006] P. Rogaway.  Formalizing human ignorance.  In _Progress in Cryptology – VIETCRYPT_ , pp. 211–228. Springer, 2006.
  * Sablayrolles et al. [2019] A. Sablayrolles, M. Douze, C. Schmid, Y. Ollivier, and H. Jégou.  White-box vs black-box: Bayes optimal strategies for membership inference.  In _International Conference on Machine Learning (ICML)_ , vol. 97, pp. 5558–5567. PMLR, 2019.
  * Salem et al. [2019] A. Salem, Y. Zhang, M. Humbert, P. Berrang, M. Fritz, and M. Backes.  ML-Leaks: Model and data independent membership inference attacks and defenses on machine learning models.  In _26th Annual Network and Distributed System Security Symposium (NDSS)_. Internet Society, 2019.
  * Salem et al. [2020] A. Salem, A. Bhattacharya, M. Backes, M. Fritz, and Y. Zhang.  Updates-Leak: Data set inference and reconstruction attacks in online learning.  In _29th USENIX Security Symposium_ , pp. 1291–1308. USENIX Association, 2020.
  * Shejwalkar and Houmansadr [2021] V. Shejwalkar and A. Houmansadr.  Membership privacy for machine learning models through knowledge transfer.  In _AAAI Conference on Artificial Intelligence (AAAI)_ , pp. 9549–9557. AAAI Press, 2021.
  * Shokri et al. [2017] R. Shokri, M. Stronati, C. Song, and V. Shmatikov.  Membership inference attacks against machine learning models.  In _37th IEEE Symposium on Security and Privacy (S &P)_, pp. 3–18. IEEE, 2017.
  * Stern [2003] J. Stern.  Why provable security matters? In _Advances in Cryptology – EUROCRYPT_ , pp. 449–461. Springer, 2003.
  * Suri and Evans [2022] A. Suri and D. Evans.  Formalizing and estimating distribution inference risks.  _Priv. Enhancing Technol._ , pp. 528–551, 2022.
  * Suri et al. [2022] A. Suri, P. Kanani, V. J. Marathe, and D. W. Peterson.  Subject membership inference attacks in federated learning.  _arXiv preprint arXiv:2206.03317 [cs.LG]_ , 2022.
  * Suri et al. [2023] A. Suri, Y. Lu, Y. Chen, and D. Evans.  Dissecting distribution inference.  In _IEEE Conference on Secure and Trustworthy Machine Learning (SaTML)_ , 2023.  To appear.
  * Tang et al. [2022] X. Tang, S. Mahloujifar, L. Song, V. Shejwalkar, M. Nasr, A. Houmansadr, and P. Mittal.  Mitigating membership inference attacks by self-distillation through a novel ensemble architecture.  In _31st USENIX Security Symposium_ , pp. 1433–1450. USENIX Association, 2022.
  * Tramèr et al. [2016] F. Tramèr, F. Zhang, A. Juels, M. K. Reiter, and T. Ristenpart.  Stealing machine learning models via prediction APIs.  In _25th USENIX Security Symposium_ , pp. 601–618. USENIX Association, 2016.
  * Tramèr et al. [2022] F. Tramèr, A. Terzis, T. Steinke, S. Song, M. Jagielski, and N. Carlini.  Debugging differential privacy: A case study for privacy auditing.  _arXiv preprint arXiv:2202.12219 [cs.LG]_ , 2022.
  * Tramèr et al. [2022] F. Tramèr, R. Shokri, A. S. Joaquin, H. Le, M. Jagielski, S. Hong, and N. Carlini.  Truth serum: Poisoning machine learning models to reveal their secrets.  In _29th ACM SIGSAC Conference on Computer and Communications Security (CCS)_ , pp. 2779–2792. ACM, 2022.
  * Tschantz et al. [2020] M. C. Tschantz, S. Sen, and A. Datta.  SoK: Differential privacy as a causal property.  In _41st IEEE Symposium on Security and Privacy (S &P)_, pp. 354–371. IEEE, 2020.
  * Wang and Gong [2018] B. Wang and N. Z. Gong.  Stealing hyperparameters in machine learning.  In _39th IEEE Symposium on Security and Privacy (S &P)_, pp. 36–52. IEEE, 2018.
  * Wang et al. [2021] T. Wang, Y. Zhang, and R. Jia.  Improving robustness to model inversion attacks via mutual information regularization.  In _AAAI Conference on Artificial Intelligence (AAAI)_ , pp. 11666–11673. AAAI Press, 2021.
  * Wu et al. [2021] B. Wu, X. Yang, S. Pan, and X. Yuan.  Adapting membership inference attacks to GNN for graph classification: Approaches and implications.  In _IEEE International Conference on Data Mining (ICDM)_ , pp. 1421–1426. IEEE, 2021.
  * Wu et al. [2016] X. Wu, M. Fredrikson, S. Jha, and J. F. Naughton.  A methodology for formalizing model-inversion attacks.  In _29th IEEE Computer Security Foundations Symposium (CSF)_ , pp. 355–370. IEEE, 2016.
  * Yeom et al. [2020] S. Yeom, I. Giacomelli, A. Menaged, M. Fredrikson, and S. Jha.  Overfitting, robustness, and malicious algorithms: A study of potential causes of privacy risk in machine learning.  _J. of Comput. Secur._ , 28(1):35–70, 2020.
  * Zanella-Béguelin et al. [2020] S. Zanella-Béguelin, L. Wutschitz, S. Tople, V. Rühle, A. Paverd, O. Ohrimenko, B. Köpf, and M. Brockschmidt.  Analyzing information leakage of updates to natural language models.  In _27th ACM SIGSAC Conference on Computer and Communications Security (CCS)_ , pp. 363–375. ACM, 2020.
  * Zanella-Béguelin et al. [2022] S. Zanella-Béguelin, L. Wutschitz, S. Tople, A. Salem, V. Rühle, A. Paverd, M. Naseri, and B. Köpf.  Bayesian estimation of differential privacy.  _arXiv preprint arXiv:2206.05199 [cs.LG]_ , 2022.
  * Zhang et al. [2021a] M. Zhang, Z. Ren, Z. Wang, P. Ren, Z. Chen, P. Hu, and Y. Zhang.  Membership inference attacks against recommender systems.  In _28th ACM SIGSAC Conference on Computer and Communications Security (CCS)_ , pp. 864–879. ACM, 2021a.
  * Zhang et al. [2021b] W. Zhang, S. Tople, and O. Ohrimenko.  Leakage of dataset properties in Multi-Party machine learning.  In _30th USENIX Security Symposium_ , pp. 2687–2704. USENIX Association, 2021b.
  * Zhang et al. [2022] Z. Zhang, M. Chen, M. Backes, Y. Shen, and Y. Zhang.  Inference attacks against graph neural networks.  In _31st USENIX Security Symposium_ , pp. 4543–4560. USENIX Association, 2022.
  * Zhou et al. [2022] J. Zhou, Y. Chen, C. Shen, and Y. Zhang.  Property inference attacks against GANs.  In _29th Network and Distributed System Security Symposium (NDSS)_. Internet Society, 2022.

###  -A Direct, Single-Query Membership Inference

Tang et al. [61] present single-query variants of membership inference where
the adversary is given only the model output on the challenge point. In their
base game (Game 17), the adversary selects a universe of $2n$ points from
where $n$ points are sub-sampled to construct the training dataset of the
target model. The adversary goal is to infer whether a challenge $z_{j}$
uniformly sampled from the initial $2n$ points was used to train the model,
i.e., guess $B[j]$, given just the model output on $z_{j}$. They also consider
variants where the set of $2n$ points is fixed externally, and a worst-case
variant where the challenge $z_{j}$ is selected by the adversary.

Input: $\mathcal{T},n,\mathcal{A},\mathcal{A}^{\prime}$

$\\{z_{i}\\}_{i\in[2n]}\leftarrow\mathcal{A}^{\prime}(\mathcal{T},n)$

$B\sim\\{0,1\\}^{2n}\textrm{~{}s.t.~{}}\sum_{i\in[2n]}B[i]=n$

$S\leftarrow\\{z_{i}\,|\,B[i]=0\\}_{i\in[2n]}$

$\theta\leftarrow\mathcal{T}(S)$

$j\sim[2n]$

$\tilde{b}\leftarrow\mathcal{A}(\mathcal{T},n,\\{z_{i}\\}_{i\in[2n]},j,\theta(z_{j}))$

Game 17 $\mathsf{MI}^{\textsf{SQ}}$

###  -B Deferred Proofs

######  Theorem 13 ($\mathsf{SMI}\preceq\mathsf{RC}$).

Let $z_{0},z_{1}$ be two samples, $S$ a dataset of $n-1$ samples, and $\ell$ a
symmetric reconstruction loss satisfying the triangle inequality. Let
$\mathcal{A}$ be an adversary against data reconstruction ($\mathsf{RC}$)
w.r.t. $S$ and the uniform prior on $\\{z_{0},z_{1}\\}$ that reconstructs its
challenge with error $\eta<\ell(z_{0},z_{1})/2$ with probability $\gamma$.
Then, there exists a strong membership inference adversary
$\mathcal{A}_{\mathsf{SMI}\to\mathsf{RC}}$ such that

$\mathsf{Adv}_{\mathsf{SMI}}(\mathcal{A}_{\mathsf{SMI}\to\mathsf{RC}})\geq
2\gamma-1$

###### Proof.

Input: $\mathcal{T},\theta,S,z_{0},z_{1}$

$\tilde{z}\leftarrow\mathcal{A}(\mathcal{T},\theta,S)$

if  _$\ell(z_{0},\tilde{z}) <\ell(z_{1},\tilde{z})$_ then

return $0$

else

return $1$

end if

Adversary 18 $\mathcal{A}_{\mathsf{SMI}\to\mathsf{RC}}$

Define $\mathcal{A}_{\mathsf{SMI}\to\mathsf{RC}}$ as in Adversary 18. For any
$\tilde{z}$, we have from the triangle inequality,

$\displaystyle\ell(z_{0},\tilde{z})$
$\displaystyle<\ell(z_{0},z_{1})/2<(\ell(z_{0},\tilde{z})+\ell(\tilde{z},z_{1}))/2\implies$
$\displaystyle\ell(z_{0},\tilde{z})$ $\displaystyle<\ell(z_{1},\tilde{z})$

Therefore, when $b=0$ in $\mathsf{SMI}$ and $\mathcal{A}$ succeeds in
reconstructing $z_{0}$ within error $\eta$,
$\mathcal{A}_{\mathsf{SMI}\to\mathsf{RC}}$ guesses correctly. Similarly, when
$b=1$ and $\mathcal{A}$ succeeds in reconstructing $z_{1}$ within error
$\eta$, $\mathcal{A}_{\mathsf{SMI}\to\mathsf{RC}}$ guesses correctly. Thus,
$\mathcal{A}_{\mathsf{SMI}\to\mathsf{RC}}$ guesses $b$ correctly at least with
probability $\gamma$ and

$\mathsf{Adv}_{\mathsf{SMI}}(\mathcal{A}_{\mathsf{SMI}\to\mathsf{RC}})=2\\!\Pr\\!\left[\mathsf{SMI}(\cdots)\\!:\\!\tilde{b}=b\right]\\!-\\!1\geq
2\gamma\\!-1\qed$

See 3

###### Proof.

Observe that $1-\alpha$ is the baseline success of a reconstruction adversary
with error $2\eta$ (see Equation 1).

Define $\mathcal{A}^{\prime}_{\mathsf{DPD}\to\mathsf{RC}}$ as in Adversary 19
and $\mathcal{A}_{\mathsf{DPD}\to\mathsf{RC}}$ as in Adversary 20.

Input: $\mathcal{T},n$

$z_{0},z_{1}\sim\pi$

return $S,z_{0},z_{1}$

Adversary 19 $\mathcal{A}^{\prime}_{\mathsf{DPD}\to\mathsf{RC}}$

Input: $\mathcal{T},\theta,S,z_{0},z_{1}$

if  _$\ell(z_{0},z_{1})\leq 2\eta$_ then

$\tilde{b}\sim\\{0,1\\}$

else

$\tilde{b}\leftarrow\mathcal{A}_{\mathsf{SMI}\to\mathsf{RC}}(\mathcal{T},\theta,S,z_{0},z_{1})$

end if

return $\tilde{b}$

Adversary 20 $\mathcal{A}_{\mathsf{DPD}\to\mathsf{RC}}$

In the $\mathsf{DPD}$ game, when $\ell(z_{0},z_{1})>2\eta$, which occurs with
probability at least $\alpha$, a similar analysis as in LABEL:thmt@@SMItoRC
shows that $\mathcal{A}_{\mathsf{DPD}\to\mathsf{RC}}$ guesses $b$ correctly
whenever $\mathcal{A}$ succeeds in reconstructing its challenge within error
$\eta$. Otherwise, the adversary guesses with probability $1/2$. Thus,

$\begin{array}[]{@{}l@{~}l}\Pr\\!\left[\mathsf{DPD}\\!:\\!\tilde{b}=b\right]\hfil~{}&\geq\Pr\\!\left[\mathsf{DPD}\\!:\\!\tilde{b}=b|\ell(z_{0},z_{1})>2\eta\right]\alpha\
+\\\
\hfil~{}&\quad\Pr\\!\left[\mathsf{DPD}\\!:\\!\tilde{b}=b|\ell(z_{0},z_{1})\leq
2\eta\right](1-\alpha)\\\
\hfil~{}&=\gamma\alpha+\frac{1}{2}(1-\alpha)\end{array}$

The DPD advantage of $\mathcal{A}_{\mathsf{DPD}\to\mathsf{RC}}$ is

$\displaystyle\mathsf{Adv}_{\mathsf{DPD}}(\mathcal{A}_{\mathsf{DPD}\to\mathsf{RC}})$
$\displaystyle=2\Pr\\!\left[\mathsf{DPD}\\!:\\!\tilde{b}=b\right]-1$
$\displaystyle\geq 2\alpha\left(\gamma-\frac{1}{2}\right)\;\qed$

See 4

###### Proof.

Let $\mathcal{A}$ be an adversary against
$\mathsf{MI}(\mathcal{T},\mathcal{D},n)$. We construct an adversary against
$\mathsf{DPD}(\mathcal{T},n)$ as in Adversary 21 and 22. These adversary
procedures, when inlined in $\mathsf{DPD}(\mathcal{T},n)$ (Game 10), result in
an experiment semantically equivalent to
$\mathsf{MI}(\mathcal{T},\mathcal{D},n,\mathcal{A})$ (Game 2). Thus,

$\mathsf{Adv}_{\mathsf{DPD}}(\mathcal{A}_{\mathsf{DPD}\to\mathsf{MI}})=\mathsf{Adv}_{\mathsf{MI}}(\mathcal{A})\qed$

Input: $\mathcal{T},n$

$S\sim\mathcal{D}^{n-1}$

$z_{0},z_{1}\sim\mathcal{D}$

return $S,z_{0},z_{1}$

Adversary 21 $\mathcal{A}^{\prime}_{\mathsf{DPD}\to\mathsf{MI}}$

Input: $\mathcal{T},\theta,S,z_{0},z_{1}$

$\tilde{b}\leftarrow\mathcal{A}(\mathcal{T},\mathcal{D},n,\theta,z_{0})$

return $\tilde{b}$

Adversary 22 $\mathcal{A}_{\mathsf{DPD}\to\mathsf{MI}}$

See 5

###### Proof.

Consider Game 23, which is equivalent to $\mathsf{AI}$ except the adversary is
also given $S$.

Input: $\mathcal{T},\mathcal{D},n,\mathcal{B},\varphi,\pi$

$S\sim\mathcal{D}^{n-1}$

$z_{0},z_{1}\sim\mathcal{D}$

$b\sim\\{0,1\\}$

$\theta\leftarrow\mathcal{T}(S\cup\\{z_{b}\\})$

$\tilde{z}\leftarrow\mathcal{B}(\mathcal{T},\mathcal{D},n,\theta,S,\varphi(z_{0}))$

Game 23 $\mathsf{AI}^{\prime}$

The reconstruction advantage of $\mathcal{B}$ coincides with its advantage in
$\mathsf{AI}^{\prime}$ in the special case where $\varphi(z)=\bot$ and
$\pi(z)=z$, i.e., the adversary has to reconstruct all attributes. This is
because $\varphi(z_{0})=\bot$ and thus the guess $\tilde{z}$ is independent of
$z_{0}$ conditioned on $b=1$.

$\mathsf{Adv}_{\mathsf{RC}^{\textsf{Ran}}}(\mathcal{B})=\Pr\\!\left[\mathsf{AI}^{\prime}\\!:\\!\tilde{z}=z_{0}|b=0\right]-\Pr\\!\left[\mathsf{AI}^{\prime}\\!:\\!\tilde{z}=z_{0}|b=1\right]$

The rest of the proof is similar to the proof of LABEL:thmt@@AItoMI, but we
present it for the sake of completeness.

Let $\mathcal{A}$ be an adversary against
$\mathsf{MI}(\mathcal{T},\mathcal{D},n)$. We construct an adversary
$\mathcal{B}$ against
$\mathsf{RC}^{\textsf{Ran}}(\mathcal{D},n,\mathcal{D},\mathcal{T})$, shown in
Game 24, which uses $\mathcal{A}$ to reconstruct its challenge.

Input: $\mathcal{T},\theta,S$

$z^{\prime}\sim\operatorname{supp}(\mathcal{D})$

$\tilde{b}\leftarrow\mathcal{A}(\mathcal{T},\mathcal{D},n,\theta)$

if  _$\tilde{b}=0$_ then

return $z^{\prime}$

else

return $\bot$

end if

Adversary 24 $\mathcal{B}$

Denote $\mathcal{D}(z_{i})$ the quantity
$\Pr\\!\left[z\sim\mathcal{D}\\!:\\!z=z_{i}\right]$, i.e., the probability
mass of $\mathcal{D}$ at $z_{i}$ and let
$m=|\operatorname{supp}(\mathcal{D})|$. In the following, we use $\mathsf{RC}$
to denote the game
$\mathsf{RC}^{\textsf{Ran}}(\mathcal{D},n,\mathcal{D},\mathcal{T},\mathcal{B})$
and $\mathsf{MI}$ to denote
$\mathsf{MI}(\mathcal{T},\mathcal{D},n,\mathcal{A})$.

Since $\mathcal{B}$ guesses $\tilde{z}=z$ if and only if $z^{\prime}=z$ and
$\tilde{b}=0$, for any $z_{i}\in\operatorname{supp}(\mathcal{D})$ we have for
$\hat{b}\in\\{0,1\\}$

$\\!\\!\Pr\\!\left[\mathsf{AI}^{\prime}\\!:\\!\tilde{z}\\!=\\!z|b\\!=\\!\hat{b},z\\!=\\!z_{i}\right]\\!=\\!\frac{1}{m}\\!\Pr\\!\left[\mathsf{AI}^{\prime}\\!:\\!\tilde{b}\\!=\\!0|b\\!=\\!\hat{b},z\\!=\\!z_{i}\right]$
(6)

Hence, the advantage of $\mathcal{B}$ is

$\begin{split}&\mathsf{Adv}_{\mathsf{RC}^{\textsf{Ran}}}(\mathcal{B})\\\
&=\\!\\!\\!\\!\sum_{z_{i}\in\operatorname{supp}(\mathcal{D})}\\!\\!\\!\\!\mathcal{D}(z_{i})\left(\Pr\\!\left[\mathsf{AI}^{\prime}\\!:\\!\tilde{z}=z_{0}|b=0,z=z_{i}\right]\right.\\\
&\qquad\qquad\qquad\quad\left.-\Pr\\!\left[\mathsf{AI}^{\prime}\\!:\\!\tilde{z}=z_{0}|b=1,z=z_{i}\right]\right)\\\
&=\frac{1}{m}\\!\\!\\!\\!\sum_{z_{i}\in\operatorname{supp}(\mathcal{D})}\\!\\!\\!\\!\mathcal{D}(z_{i})\left(\Pr\\!\left[\mathsf{AI}^{\prime}\\!:\\!\tilde{b}=0|b=0,z=z_{i}\right]\right.\\\
&\qquad\qquad\qquad\qquad\left.-\Pr\\!\left[\mathsf{AI}^{\prime}\\!:\\!\tilde{b}=0|b=1,z=z_{i}\right]\right)\\\
&=\frac{1}{m}\left(\Pr\\!\left[\mathsf{AI}^{\prime}\\!:\\!\tilde{b}=0|b=0\right]-\Pr\\!\left[\mathsf{AI}^{\prime}\\!:\\!\tilde{b}=0|b=1\right]\right)\\\
&=\frac{1}{m}\mathsf{Adv}_{\mathsf{MI}}(\mathcal{A})\end{split}$

The penultimate equality holds because $b$ and $z$ are independent. The last
equality holds because game
$\mathsf{AI}^{\prime}(\mathcal{T},\mathcal{D},n,\mathcal{B})$ matches game
$\mathsf{MI}(\mathcal{T},\mathcal{D},n,\mathcal{A})$ and so the joint
distribution of $\tilde{b},b$ is the identical in both games. ∎

See 7

###### Proof.

We show that there are training pipelines that are arbitrarily resilient
against membership inference attacks but completely insecure against DP
distinguishing attacks.

We construct a training pipeline $(\mathcal{T},\mathcal{D},n)$ such that the
MI advantage of an adversary against it is at most
$\nicefrac{{1}}{{\sqrt{n}}}$, and so vanishes as $n$ grows. Yet, we exhibit a
DP distinguisher against the pipeline that achieves perfect advantage.

Input: $\mathcal{T},\mathcal{D},n,\mathcal{A}$

$b\sim\\{0,1\\}$

$S\sim\mathcal{D}^{n-1}$

$z_{0},z_{1}\sim\mathcal{D}$

$\theta\leftarrow\mathcal{T}(S\cup\\{z_{b}\\})$

$\tilde{b}\leftarrow\mathcal{A}(\mathcal{T},\mathcal{D},n,\theta,z_{0},z_{1})$

Game 25 $\mathsf{MI}^{\prime}$

Let $\mathcal{D}=\mathrm{Bernoulli}(p)$ and $\mathcal{T}(S)=\sum_{x\in S}x$.
Consider Game 25. If the adversary were only given $z_{0}$, this game would be
equivalent to the basic $\mathsf{MI}$ game (Game 1). Since the adversary is
given strictly more information, any bound on its advantage in this game would
also bound the MI advantage of adversaries against the training pipeline. The
adversary must distinguish between two simple hypotheses:

  * •

$H_{0}:\theta\sim\mathrm{Binomial}(n-1,p)+z_{0}$

  * •

$H_{1}:\theta\sim\mathrm{Binomial}(n-1,p)+z_{1}$

When $z_{0}=z_{1}$, these coincide and the advantage of the adversary is 0.
Otherwise, without loss of generality, assume $z_{b}=b$. By the Neyman-Pearson
lemma, a likelihood ratio test yields the most powerful test for a
significance $\alpha$ (i.e., Type-I error, false positive rate). Let $f$ and
$F$ be the probability mass and cumulative distribution function of
$\mathrm{Binomial}(n-1,p)$, respectively. The likelihood ratio is

$\Lambda(\theta=k)=\begin{cases}\infty&\text{if }k=0\\\ 0&\text{if }k=n\\\
\frac{f(k)}{f(k-1)}=\frac{(n-k)p}{k(1-p)}&\text{otherwise}\end{cases}$

The test rejects $H_{0}$ when $\Lambda(\theta)<c$, for some $c$. The false
positive rate $\alpha$ (the probability of rejecting $H_{0}$ when $H_{0}$ is
true) is

$\displaystyle\Pr_{H_{0}}(\Lambda(\theta)<c)$
$\displaystyle=\Pr_{H_{0}}\left(\frac{(n-k)p}{k(1-p)}<c\right)$
$\displaystyle=\Pr_{H_{0}}\left(k>\frac{np}{p+c(1-p)}\right)$
$\displaystyle=1-F\left(\frac{np}{p+c(1-p)}\right)$

The false negative rate $\beta$ is

$\displaystyle\Pr_{H_{1}}(\Lambda(\theta)\geq c)$
$\displaystyle=\Pr_{H_{1}}\left(\frac{(n-k)p}{k(1-p)}\geq c\right)$
$\displaystyle=\Pr_{H_{1}}\left(k\leq\frac{np}{p+c(1-p)}-1\right)$
$\displaystyle=F\left(\frac{np}{p+c(1-p)}-1\right)$

Now, take $p=0.5$ and assume that $n\geq 4$ and that $n$ is even so that the
mode of $\mathrm{Binomial}(n-1,p)$ is $n/2$. The MI advantage of the adversary
is

$\displaystyle\mathsf{Adv}_{\mathsf{MI}}(\mathcal{A})$
$\displaystyle=\frac{1}{2}(f(0)+f(n-1)+(1-\alpha-\beta))$
$\displaystyle=f(0)+\frac{1}{2}f\left(\frac{np}{p+c(1-p)}\right)$
$\displaystyle\leq\frac{1}{2^{n-1}}+\frac{f(n/2)}{2}$
$\displaystyle\leq\frac{1}{2\sqrt{n}}+\frac{1}{2\sqrt{n}}=\frac{1}{\sqrt{n}}$

On the other hand, a DP distinguisher $\mathcal{A}$ that chooses
$z_{0}=0,z_{1}=1$, an arbitrary $S$, and that guesses
$\tilde{b}=\theta-\sum_{x\in S}S$, has perfect advantage
$\mathsf{Adv}_{\mathsf{DPD}}(\mathcal{A})=1$. ∎

See 6

###### Proof.

We construct a training pipeline $(\mathcal{T},\mathcal{D}_{b},n)$ that is
arbitrarily resilient to membership inference for $b\in\\{0,1\\}$. Yet, we
exhibit a property inference attack against it that achieves perfect
advantage.

Let $\mathcal{D}_{b}=\mathrm{Bernoulli}(p_{b})$ with $p_{0}\neq p_{1}$ and
$\mathcal{T}(S)=\sum_{x\in S}x$. As shown in LABEL:thmt@@MItoDPD, the
advantage of a membership inference adversary against
$(\mathcal{T},\mathcal{D}_{b},n)$ is at most $\nicefrac{{1}}{{\sqrt{n}}}$.
However, as $n$ grows, $\mathcal{T}(S)/n$ is an unbiased estimator for the
mean $p_{b}$, which allows a property inference adversary to easily
distinguish between $\mathcal{D}_{0}$ and $\mathcal{D}_{1}$, particularly when
$p_{0}$ and $p_{1}$ are far apart. ∎

See 8

###### Proof.

It suffices to show that the training pipeline from LABEL:thmt@@MItoDPD, which
is resilient to membership inference attacks, admits a reconstruction attack.
For this, recall that in $\mathsf{RC}$ the adversary knows the dataset $S$
(but not the target sample $z$). For the pipeline
$(\mathcal{T},\mathcal{D},n)$ given in LABEL:thmt@@MItoDPD, $z$ can be
perfectly reconstructed since $z=\theta-\sum_{x\in S}x$. ∎

See 9

###### Proof.

We exhibit a pipeline resilient to property inference that is completely
vulnerable to a membership inference attack.

Let $\mathcal{D}$ be an arbitrary distribution and define $\mathcal{D}_{b}$ so
that $z\sim\mathcal{D}_{b}\equiv x\sim\mathcal{D};z\leftarrow(x,b)$. Let $n>0$
and define

$\mathcal{T}(S)=\\{x\in S|(x,y)\in S\\}$

A membership inference adversary against
$\mathsf{MI}(\mathcal{T},\mathcal{D},n)$ that given $\theta,z_{0}=(x,y)$
returns 0 if and only if $x\in S$ achieves the maximum advantage, i.e.,

$1-\Pr\\!\left[S\sim\mathcal{D}^{n};x\sim\mathcal{D}\\!:\\!x\in S\right]$

However, a property inference adversary gets no information about $b$ as
$\theta$ and $b$ are independent, so its advantage is 0. ∎

See 10

###### Proof.

Balle et al. [4, Theorem 5] show that resilience against reconstruction w.r.t.
all priors in a family of distributions concentrated on all ordered pairs of
distinct examples implies $(\varepsilon,\delta)$-DP, and hence via 2
resilience against $\mathsf{DPD}$.

However, resilience against a single prior $\pi$, even if its support includes
all possible examples, is clearly insufficient to guarantee resilience against
$\mathsf{DPD}$. To see why, consider a deterministic $\mathsf{DPD}$ adversary
that picks $S,z_{0},z_{1}$. Given error bound $\eta$ and success probability
$\gamma$, all reconstruction adversaries can have error larger than $\eta$
when $z\notin\\{z_{0},z_{1}\\}$ but reconstruct $z\in\\{z_{0},z_{1}\\}$
perfectly, as long as
$\Pr\\!\left[z\sim\pi\\!:\\!z\in\\{z_{0},z_{1}\\}\right]<\gamma$, i.e., the
probability mass of the prior on $\\{z_{0},z_{1}\\}$. The situation is worse
when $z_{0},z_{1}\notin\operatorname{supp}(\pi)$, where resilience against
reconstruction for arbitrary $\eta,\gamma$ is compatible with perfect
$\mathsf{DPD}$ advantage. ∎

See 11

###### Proof.

Let $\varepsilon,\delta\in(0,1)$. We build two training pipelines
$(\mathcal{T},\mathcal{D}_{b},n)$, $b\in\\{0,1\\}$, that satisfy
($\varepsilon,\delta$)-DP and thus are resilient against $\mathsf{DPD}$ (see
2). We then show an adversary against
$\mathsf{PI}(\mathcal{D}_{0},\mathcal{D}_{1},n,\mathcal{T})$ whose advantage
grows with $n$.

Let $\mathcal{D}_{b}=\mathrm{Bernoulli}(p_{b})$ with $p_{0}\neq p_{1}$ and
define $\mathcal{T}(S)=\sum_{x\in S}x+\mathcal{N}(0,\sigma^{2})$ where
$\sigma^{2}=2\ln(1.25/\delta)\varepsilon^{-1}.$ Since the sum above has
sensitivity 1 and $\mathcal{T}$ is the standard Gaussian mechanism, the
training pipeline is ($\varepsilon,\delta$)-DP.

Note that for $S$ sampled from $\mathcal{D}_{b}$, the random variable
$\mathcal{T}(S)$ is distributed as
$\mathrm{Binomial}(n,p_{b})+\mathcal{N}(0,\sigma^{2}).$ We can use Berry-
Esséen theorem to approximate the binomial distribution with a normal
distribution, so that approximately

$\displaystyle\mathcal{T}(S)$
$\displaystyle\sim\mathcal{N}(np_{b},np_{b}(1-p_{b}))+\mathcal{N}(0,\sigma^{2})$
$\displaystyle\sim\mathcal{N}(np_{b},np_{b}(1-p_{b})+\sigma^{2})$

The approximation error is $O(\sqrt{n})$. $\mathcal{T}(S)/n$ is an unbiased
estimator for $p_{b}$ with variance
$p_{b}(1-p_{b})+\nicefrac{{\sigma^{2}}}{{n}}$. Since $\sigma$ does not depend
on $n$, as $n$ grows the approximation error and the variance of the estimate
decrease. This allows a property inference adversary to distinguish between
$\mathcal{D}_{0}$ and $\mathcal{D}_{1}$, particularly when $p_{0}$ and $p_{1}$
are far apart. ∎

Ateniese et al. [3, Section 4.2] were the first to observe that differential
privacy does not protect against property inference and provided a practical
counterexample: a differentially private $k$-means network traffic classifier
that nonetheless leaks the presence of traces from Google.com web traffic in
their training dataset. However, their argument remains informal, appealing to
visual differences in the centroids of just two trained models. Suri et al.
[60, Section V] give a more compelling example where property inference risk
remains high on neural networks trained with DP-SGD.