# Analyzing Privacy Leakage in Machine Learning via Multiple Hypothesis
Testing: A Lesson From Fano

Chuan Guo, Alexandre Sablayrolles, Maziar Sanjabi
Meta AI
<EMAIL_ADDRESS>

###### Abstract

Differential privacy (DP) is by far the most widely accepted framework for
mitigating privacy risks in machine learning. However, exactly how small the
privacy parameter $\epsilon$ needs to be to protect against certain privacy
risks in practice is still not well-understood. In this work, we study data
reconstruction attacks for discrete data and analyze it under the framework of
multiple hypothesis testing. We utilize different variants of the celebrated
Fano’s inequality to derive upper bounds on the inferential power of a data
reconstruction adversary when the model is trained differentially privately.
Importantly, we show that if the underlying private data takes values from a
set of size $M$, then the target privacy parameter $\epsilon$ can be $O(\log
M)$ before the adversary gains significant inferential power. Our analysis
offers theoretical evidence for the empirical effectiveness of DP against data
reconstruction attacks even at relatively large values of $\epsilon$.

##  1 Introduction

As machine learning becomes increasingly ubiquitous in the real world, proper
understanding of the privacy risks of ML also becomes a crucial aspect for its
safe adoption. Numerous prior works have demonstrated privacy vulnerabilities
throughout the ML training pipeline (Shokri et al., 2017; Song et al., 2017;
Nasr et al., 2019; Zhu et al., 2019; Carlini et al., 2021). So far the only
comprehensive defense against privacy attacks is differential privacy (DP)
(Dwork et al., 2006), which has been successfully adapted for training private
ML models (Chaudhuri et al., 2011; Shokri and Shmatikov, 2015; Abadi et al.,
2016).

Unfortunately, differentially private training also comes at a huge cost to
model accuracy if a small privacy parameter $\epsilon$ is desired. This is not
unexpected since, in principle, some degree of memorization may be necessary
for high-performance ML models (Feldman, 2020). In contrast, in terms of the
level of empirical protection conferred by DP against privacy attacks, the
picture is much more optimistic: Across a wide range of attacks including
membership inference, attribute inference, data reconstruction and gradient
inversion, even a small amount of DP noise is sufficient for thwarting most
attacks (Jayaraman and Evans, 2019; Zhu et al., 2019; Carlini et al., 2019;
Hannun et al., 2021). However, there is very little theoretical understanding
of this phenomenon.

In this paper, we analyze privacy leakage in connection to the multiple
hypothesis testing problem in information theory, and show that the empirical
privacy protection conferred by DP with high $\epsilon$ may be more than
previously thought. To this end, we define a game (see Figure 1) between a
private learner and an adversary that tries to perform a _data reconstruction
attack_ against the learned model, and analyze it to derive upper bounds on
the inferential power of the adversary when the model is trained
differentially privately. The central tool in our analysis is Fano’s
inequality, which we utilize to bound the advantage of an adversary in terms
of the mutual information between the private data and the trained model. In
particular, our analysis reveals an interesting and important insight that the
DP parameter $\epsilon$ should scale _logarithmically_ with the number of
possible values $M$ that the private data can take on. When $M$ is large,
_e.g._ , $M=10^{10}$ when extracting social security numbers from a trained
language model (Carlini et al., 2019), even a relatively large $\epsilon$ has
sufficient protection against data reconstruction attacks.

Figure 1: Illustration of the data reconstruction attack game. The target data
takes on $M$ possible values $\mathbf{u}_{1},\ldots,\mathbf{u}_{M}$ with
conditional probabilities
$\mathbb{P}(\mathbf{u}_{m}|\mathbf{x})=\mathbf{p}_{m}$. The game begins with
${\color[rgb]{1,0,0}k}$ drawn from $\text{Categorical}(\mathbf{p})$, and the
private learner  trains a model
$h\leftarrow\mathcal{M}(\mathcal{D}\cup\\{\mathbf{z}_{\color[rgb]{1,0,0}k}\\})$.
The adversary guesses ${\color[rgb]{.75,.5,.25}\hat{k}}$ and wins if
${\color[rgb]{.75,.5,.25}\hat{k}}={\color[rgb]{1,0,0}k}$. Advantage is defined
so that $\texttt{Adv}\leq 1$ and guessing
${\color[rgb]{.75,.5,.25}\hat{k}}=\operatorname*{arg\,max}_{m}\mathbf{p}_{m}$
achieves zero advantage. Processes inside the box marked with  are unobserved
by the adversary, while everything else is observable.

We derive general bounds on mutual information from Rényi DP (Mironov, 2017),
as well as give specialized bounds for two common DP primitives—randomized
response (Warner, 1965) and Gaussian mechanism (Dwork et al., 2014)—to upper
bound the advantage of a data reconstruction adversary. Furthermore, we
empirically validate these bounds against two attacks proposed in prior work:
1. Attribute inference attack in pharmacogenetics modeling (Fredrikson et al.,
2014); and 2. Canary extraction attack for language models (Carlini et al.,
2019). Our evaluation gives concrete semantic privacy guarantees for DP
mechanisms under practical settings, and validates the empirical finding that
models trained using DP can achieve sufficient protection against data
reconstruction attacks even when $\epsilon$ is high. As a result, we advocate
for the use of our analysis for selecting the appropriate value of $\epsilon$
in practice.

#### Contributions.

Our main contributions are:

  1. 1.

Formalizing data reconstruction attacks for discrete data as an attack game
(section 3).

  2. 2.

Using Fano’s inequality to upper bound the adversary’s advantage in terms of
mutual information (section 4).

  3. 3.

Bounding mutual information for Rényi DP mechanisms and specializing the
analysis to two common DP primitives: randomized response and Gaussian
mechanism (section 5).

  4. 4.

Experimentally validating our advantage bounds for DP mechanisms against
existing attacks (section 6).

##  2 Background and Motivation

#### Privacy attacks.

The machine learning pipeline exposes training samples to the outside world
through the training procedure and/or trained model. Prior works showed that
adversaries can exploit this exposure to compromise the privacy of training
samples. The most well-studied type of privacy attack is _membership inference
attack_ (Shokri et al., 2017; Salem et al., 2018; Yeom et al., 2018;
Sablayrolles et al., 2019), which aims to infer whether a sample $\mathbf{z}$
corresponding to an individual’s data was part of the model’s training set.
This membership status can be a very sensitive attribute, _e.g._ , whether or
not an individual participated in a cancer study indicates their disease
status. Most state-of-the-art attacks (Ye et al., 2021; Watson et al., 2021;
Carlini et al., 2022) follow a common strategy of measuring the model’s loss
compared to that of a random model trained without the target sample
$\mathbf{z}$, with a large difference indicating that the sample was seen
during training (_i.e._ , a member).

Other privacy attacks can extract more detailed information about a training
sample beyond membership status. _Attribute inference attacks_ (Fredrikson et
al., 2014; Yeom et al., 2018) aim to reconstruct a training sample given
access to the trained model and partial knowledge of the sample. _Data
reconstruction attacks_ (Fredrikson et al., 2015; Carlini et al., 2019, 2021;
Balle et al., 2022) relax the partial knowledge assumption of attribute
inference attacks and can recover training samples given only the trained
model. In federated learning (McMahan et al., 2017), adversaries that observe
the gradient updates can reconstruct private training samples using a process
called _gradient inversion attack_ (Zhu et al., 2019; Geiping et al., 2020).
The existence of these privacy attacks calls for countermeasures that can
preserve the utility of ML models while preventing unintended leakage of
private information.

Differential privacy (Dwork et al., 2006) is a mathematical definition of
privacy that upper bounds the amount of information leakage through a private
mechanism. In the context of ML, the private mechanism $\mathcal{M}$ is a
learning algorithm that, given any pair of datasets $\mathcal{D}$ and
$\mathcal{D}^{\prime}$ that differ in a single training sample, ascertains
that $\mathcal{M}(\mathcal{D})$ and $\mathcal{M}(\mathcal{D}^{\prime})$ are
$\epsilon$-close in distribution for some chosen privacy parameter
$\epsilon>0$. In the classical definition of differential privacy,
$\epsilon$-closeness is defined in terms of _max divergence_ : $\mathcal{M}$
is $\epsilon$-differentially private (denoted $\epsilon$-DP) if:

$\displaystyle D$
${}_{\infty}(\mathcal{M}(\mathcal{D})||\mathcal{M}(\mathcal{D}^{\prime})):=\sup_{O}\left[\log\mathbb{P}(\mathcal{M}(\mathcal{D})\in
O)-\log\mathbb{P}(\mathcal{M}(\mathcal{D}^{\prime})\in O)\right]\leq\epsilon,$
(1)

where $O$ denotes a subset of the model space. One variant of DP that uses
Rényi divergence to quantify closeness is _Rényi DP_ (RDP) (Mironov, 2017).
For a given $\alpha\geq 1$, we say that $\mathcal{M}$ is
$(\alpha,\epsilon)$-RDP if:

$\displaystyle D_{\alpha}($
$\displaystyle\mathcal{M}(\mathcal{D})||\mathcal{M}(\mathcal{D}^{\prime})):=\frac{1}{\alpha-1}\log\mathbb{E}_{h\sim\mathcal{M}(\mathcal{D}^{\prime})}\left[\frac{\mathbb{P}(\mathcal{M}(\mathcal{D}))^{\alpha}}{\mathbb{P}(\mathcal{M}(\mathcal{D}^{\prime}))^{\alpha}}\right]\leq\epsilon.$
(2)

Another variant that will be useful in our analysis is _mutual information DP_
(MI-DP) (Cuff and Yu, 2016; Wang et al., 2016), which we specialize to our
setting in the following definition.

######  Definition 1.

Let $\mathcal{D}$ be a fixed dataset and let
$\mathbf{z}_{1},\ldots,\mathbf{z}_{M}$ be a set of data samples. Let $X$ be a
categorical random variable taking value in $\\{1,\ldots,M\\}$, defined by the
sampling probability vector $\mathbf{p}$. Let $Y$ be the output of a private
mechanism $\mathcal{M}$ with distribution
$(Y|X=k)=\mathcal{M}(\mathcal{D}\cup\\{\mathbf{z}_{k}\\})$. We say that
$\mathcal{M}$ satisfies $\epsilon$-mutual information DP ($\epsilon$-MI-DP)
with respect to distribution $\mathbf{p}$ if $I(X;Y)\leq\epsilon$.

Intuitively, $I(X;Y)$ measures the amount of information leaked about the data
$\mathbf{z}_{k}$ through the trained model, and a DP learning algorithm can
limit this leakage to reduce the advantage of a data reconstruction adversary.
Note that our definition of MI-DP differs slightly from Cuff and Yu (2016)
since it depends on the sampling distribution $\mathbf{p}$, public set
$\mathcal{D}$, and the set of values $\mathbf{z}_{1},\ldots,\mathbf{z}_{M}$
that the private record can take on. Nevertheless, it is easy to show that our
definition still satisfies key properties of DP such as adaptive composition
and post-processing, which are crucial for building complex private mechanisms
from simple primitives.

#### Semantic privacy.

Differential privacy has been shown to effectively prevent all of the
aforementioned privacy attacks when the privacy parameter $\epsilon$ is small
enough (Jayaraman and Evans, 2019; Zhu et al., 2019; Carlini et al., 2019;
Hannun et al., 2021). Conceptually, when $\epsilon\approx 0$, the learning
algorithm outputs roughly the same distribution of models when a single
training sample $\mathbf{z}$ is removed/replaced, hence an adversary cannot
accurately infer any private information about $\mathbf{z}$. However, this
reasoning does not quantify _how small $\epsilon$ needs to be to prevent a
certain class of privacy attacks to a certain degree_. In practice, this form
of _semantic guarantee_ is arguably more meaningful, as it may inform policy
decisions regarding the suitable range of $\epsilon$ to provide sufficient
privacy protection, and enables privacy auditing (Jagielski et al., 2020) to
verify that the learning algorithm’s implementation is compliant.

Several existing works made partial progress towards answering this question.
Yeom et al. (2018) formalized membership inference attacks by defining a game
between the private learner and an adversary, and showed that the adversary’s
_advantage_ —how well the adversary can infer a particular sample’s membership
status—is bounded by $e^{\epsilon}-1$ when the learning algorithm is
$\epsilon$-DP. This bound has been tightened significantly in subsequent works
(Erlingsson et al., 2019; Humphries et al., 2020; Mahloujifar et al., 2022;
Thudi et al., 2022). Similarly, Bhowmick et al. (2018); Balle et al. (2022);
Guo et al. (2022) formalized data reconstruction attacks and showed that for
DP learning algorithm, the adversary’s expected reconstruction error can be
lower bounded using DP, Rényi-DP (Mironov, 2017), and Fisher information
leakage (Hannun et al., 2021) privacy accounting. Our work makes further
progress in this direction by analyzing data reconstruction attacks using
tools from the multiple hypothesis testing literature, which we show is well-
suited for discrete data.

##  3 Formalizing Data Reconstruction

To understand the semantic privacy guarantee for DP mechanisms against data
reconstruction attacks, we first formally define a data reconstruction game
for discrete data. Our formulation generalizes the membership inference game
in existing literature (Yeom et al., 2018; Humphries et al., 2020), while
specializing the formulation of Balle et al. (2022) to discrete data.

#### Data reconstruction game.

Let $\mathcal{D}_{\text{train}}=\mathcal{D}\cup\\{\mathbf{z}\\}$ be the
training set consisting of a _public set_ $\mathcal{D}$ and a _private record_
$\mathbf{z}=(\mathbf{x},\mathbf{u})$, where $\mathbf{x}$ are attributes known
to the adversary and $\mathbf{u}$ is unknown. Let $\mathcal{M}$ be the
learning algorithm. We consider a white-box adversary with full knowledge of
the public set $\mathcal{D}$ and the trained model
$h=\mathcal{M}(\mathcal{D}_{\text{train}})$ whose objective is to infer the
unknown attributes $\mathbf{u}$. Importantly, we assume that the unknown
attribute is discrete (_e.g._ , gender, race, marital status) and can take on
$M$ values $\mathbf{u}_{1},\ldots,\mathbf{u}_{M}$. For example, the experiment
setting of Carlini et al. (2019) can be stated as $\mathbf{x}=``\texttt{My
social security number is}"$ and $\mathbf{u}\in\\{0,1,\ldots,9\\}^{10}$ is the
SSN number.

The attack game (see Figure 1 for an illustration) begins by drawing a random
index $k$ from a categorical distribution defined by the probability vector
$\mathbf{p}$ (also known to the adversary) and setting the unknown attribute
$\mathbf{u}=\mathbf{u}_{k}$. The private learner $\mathcal{M}$ then trains a
model $h$ with $\mathbf{z}=\mathbf{z}_{k}=(\mathbf{x},\mathbf{u}_{k})$ and
gives it to the adversary, who then outputs a guess $\hat{k}$ of the
underlying index $k$. Note that both the random index $k$ and any randomness
in the learning algorithm $\mathcal{M}$ are unobserved by the adversary, but
the learning algorithm itself is known to the adversary.

#### Success metric.

We generalize the _advantage_ metric (Yeom et al., 2018) used in membership
inference attack games to multiple categories. Here, the (Bayes) optimal
guessing strategy without observing $h$ is to simply guess
$\hat{k}=\operatorname*{arg\,max}_{m}\mathbf{p}_{m}$ with success rate
$\max_{m}\mathbf{p}_{m}$. The probability of successfully guessing $k$ upon
observing $h$, _i.e._ , $\mathbb{P}(\hat{k}=k)$, must be at least
$\max_{m}\mathbf{p}_{m}$ in order to meaningfully leverage the private
information contained in $h$ about $\mathbf{u}$. Thus, we define advantage as
the (normalized) difference between $\mathbb{P}(\hat{k}=k)$ and the _baseline
success rate_ $p^{*}:=\max_{m}\mathbf{p}_{m}$, _i.e._ ,

$\texttt{Adv}:=\frac{\mathbb{P}(\hat{k}=k)-p^{*}}{1-p^{*}}\in[0,1].$ (3)

#### Interpretation.

Our data reconstruction game has the following important implications for
privacy semantics.

1\. _The private attribute $\mathbf{u}$ is considered leaked if and only if it
is guessed exactly._ This is a direct consequence of defining adversary
success as $\hat{k}=k$. For example, if the attribute is a person’s age, then
guessing $\hat{k}=50$ when the ground truth is $k=49$ should be considered
more successful than when $k=40$. In such settings, it may be more suitable to
partition the input space into broader categories, _e.g._ , age ranges 0-9,
10-19, _etc._ , so that inexact guesses can also be considered successful.

2\. _The attack game subsumes attribute inference attacks._ This can be done
by setting the known attribute $\mathbf{x}$ accordingly. When
$\mathbf{x}=\emptyset$, our game corresponds to the scenario commonly referred
to as _data reconstruction_ or _data extraction_ in existing literature
(Carlini et al., 2019, 2021; Balle et al., 2022).

3\. _Prior information is captured through the sampling probability
$\mathbf{p}$._ Success rate of the Bayes optimal strategy is
$p^{*}=\max_{m}\mathbf{p}_{m}$, which depends on the sampling probability
vector $\mathbf{p}$. In the extreme case where $\mathbf{p}$ is a delta
distribution on some $k^{*}$, which corresponds to the adversary having
perfect knowledge of the private attribute $\mathbf{u}$, the model $h$
provides _no additional information_ about $\mathbf{u}$. This is in accordance
with the “no free lunch theorem” in differential privacy, which says that
inference of private information is not preventable when the adversary is
given arbitrary prior information (Dwork and Naor, 2010).

#### Relation to prior work.

Our attack game is a direct generalization of the membership inference attack
game in Yeom et al. (2018). In particular, the “strong adversary” game defined
in Humphries et al. (2020); Nasr et al. (2021) is a special case of our data
reconstruction game with $M=2$. Our game formulation also complements Guo et
al. (2022), which bounds the inferential power of a data reconstruction attack
under the assumption that semantic similarity between private records is
measured by mean squared error (MSE), which is better suited to continuous-
valued data. In contrast, our formulation considers discrete data with the
zero-one similarity measure, which is better suited for categorical data such
as gender, race and marital status.

Our definition can also be viewed as a specialization of the data
reconstruction attack game defined in Bhowmick et al. (2018); Balle et al.
(2022). In Balle et al. (2022), the learning algorithm $\mathcal{M}$ is said
to be $(\eta,\gamma)$-ReRo (reconstruction robust) if

$\mathbb{P}_{k\sim\text{Categorical}(\mathbf{p}),h\sim\mathcal{M}(\mathcal{D}\cup\\{\mathbf{z}_{k}\\})}(\ell(\mathbf{z}_{k},\hat{\mathbf{z}})\leq\eta)\leq\gamma,$
(4)

where $\hat{\mathbf{z}}$ is the adversary’s reconstruction of $\mathbf{z}_{k}$
and $\ell$ is an error function that measures how faithful the reconstruction
$\hat{\mathbf{z}}$ is to $\mathbf{z}_{k}$. By setting
$\ell(\mathbf{z}_{k},\hat{\mathbf{z}})=\mathds{1}(\hat{\mathbf{z}}=\mathbf{z}_{k})$
and $\eta=0$, one can show that Equation 4 is satisfied if and only if
$\mathbb{P}(\hat{k}=k)\leq\gamma$, thus if $\mathcal{M}$ is
$(\eta,\gamma)$-ReRo with $\eta<1$ then
$\texttt{Adv}\leq(\gamma-p^{*})/(1-p^{*})$.

##  4 Connecting Data Reconstruction to Multiple Hypothesis Testing

In this section, we analyze the data reconstruction game defined in section 3
and derive upper bounds on the advantage when $\mathcal{M}$ is differentially
private.

#### Fano’s inequality.

The central tool in our analysis is Fano’s inequality—a celebrated result in
information theory that lower bounds the error rate in multiple hypothesis
testing. In detail, suppose that $X$ is a discrete random variable taking on
$M$ different values, and $Y$ is an observed random variable determined by
$X$, _e.g._ , $Y$ is the output of the private learning algorithm
$\mathcal{M}$. Let $\hat{X}$ be an estimate of $X$, and define the error
random variable $E=(\hat{X}\neq X)\in\\{0,1\\}$. Then

$H(X|Y)\leq H(E)+\mathbb{P}(E=1)\log(M-1),$ (5)

where $H(E)$ denotes the entropy of $E$ and $H(X|Y)$ denotes the conditional
entropy of $X$ given $Y$.

#### From Fano to advantage bound.

The attack game defined in Figure 1 essentially tasks the adversary with a
_multiple hypothesis test_ , where the hypotheses are
$H_{k}:h\sim\mathcal{M}(\mathcal{D}\cup\\{\mathbf{z}_{k}\\})$ for
$k=1,\ldots,M$. When $M=2$, we recover the binary hypothesis testing
interpretation of membership inference attack (Yeom et al., 2018; Humphries et
al., 2020). Consequently, we can apply Fano’s inequality to bound the
adversary’s advantage (_cf._ Equation 3) by setting
$X=\text{Categorical}(\mathbf{p})$ and
$Y=\mathcal{M}(\mathcal{D}_{\text{train}})$. In effect, $X$ encodes all the
information contained in the sensitive attribute $\mathbf{u}$, and $Y$ is the
output of a private mechanism that the adversary observes with partial
information about $X$. For any adversary, let
$t=\mathbb{P}(E=1)=\mathbb{P}(\hat{k}\neq k)$ be the error probability, and
define:

$f(t)=H(X|Y)+t\log t+(1-t)\log(1-t)-t\log(M-1).$ (6)

Since $t=\mathbb{P}(E=1)$, Fano’s inequality (_cf._ Equation 5) defines a
constraint $f(t)\leq 0$ on $t$. In other words, the error probability of _any_
adversary must satisfy $f(t)\leq 0$, and thus we can upper bound advantage (or
equivalently, lower bound error probability) by solving

$t^{*}=\min\\{t\in[0,1]:f(t)\leq 0\\},$ (7)

and the advantage bound is $\texttt{Adv}\leq(1-t^{*}-p^{*})/(1-p^{*})$.

#### Computing advantage bound.

In order to compute the advantage bound, we need to first compute the
conditional entropy term $H(X|Y)$ in Equation 6. An alternative expression for
conditional entropy is $H(X|Y)=H(X)-I(X;Y)$, where $I(X;Y)$ is the mutual
information between $X$ and $Y$. Since $H(X)$ depends only on the sampling
probability vector $\mathbf{p}$, the only factor that the DP mechanism
controls is $I(X;Y)$—a fact that has been delineated in prior work on mutual
information DP (MI-DP; see Definition 1). Thus, to compute $t^{*}$ in Equation
7, we assume that the mechanism $\mathcal{M}$ is $\epsilon$-MI-DP (_i.e._ ,
$I(X;Y)\leq\epsilon$) for some $\epsilon>0$, and define:

$f_{\epsilon}(t)=H(X)-\epsilon+t\log t+(1-t)\log(1-t)-t\log(M-1).$ (8)

Since $H(X|Y)=H(X)-I(X;Y)\geq H(X)-\epsilon$, we have that
$f_{\epsilon}(t^{*})\leq f(t^{*})\leq 0$. Thus, we can instead minimize $t$
subject to $f_{\epsilon}(t)\leq 0$ to obtain a lower bound
$t^{*}\leq\min\\{t\in[0,1]:f_{\epsilon}(t)\leq 0\\}$ for the error probability
of _any_ data reconstruction adversary. The detailed procedure for computing
$t^{*}$ is given in Algorithm 1 in Appendix A.

##  5 Bounding Mutual Information for DP Mechanisms

The advantage bound in section 4 depends crucially on the upper bound
$I(X;Y)\leq\epsilon$ for the mutual information between the private attribute
and the trained model. We first present a general bound for Rényi DP
mechanisms (such as the popular Gaussian mechanism used in DP-SGD (Abadi et
al., 2016)), and then derive tighter bounds using specialized analyses for two
commonly used DP primitives—randomized response and Gaussian mechanism.

###  5.1 Bound from RDP

We first derive a general bound for Rényi DP mechanisms. Our result involves a
generalization of mutual information known as _Arimoto information_ (Arimoto,
1977; Verdú, 2015), denoted $I_{\alpha}(X;Y)$; see Equation 19 in Appendix A.
Notably, Arimoto information has natural connections to the order-$\alpha$
Rényi divergence used to define RDP, and coincides with mutual information
when $\alpha\rightarrow 1$. In the following theorem, we show that if the
private mechanism $\mathcal{M}$ is $(\alpha,\epsilon)$-RDP, then
$I_{\alpha}(X;Y)\leq\epsilon$. In particular, if $\alpha=1$ then
$I(X;Y)=I_{\alpha}(X;Y)\leq\epsilon$, which we can use in Algorithm 1 to
derive an advantage bound. Proof is given in Appendix B.

######  Theorem 1.

For any $\alpha\geq 1$, if $\mathcal{M}$ is $(\alpha,\epsilon)$-RDP then
$I_{\alpha}(X;Y)\leq\epsilon$.

#### Generalized Fano’s inequality.

For $(\alpha,\epsilon)$-RDP mechanisms with $\alpha>1$, one can apply Theorem
1 by simply leveraging monotonicity of Rényi divergence with respect to the
order $\alpha$. That is, if $\mathcal{M}$ is $(\alpha,\epsilon)$-RDP then it
is also $(1,\epsilon)$-RDP, so $I(X;Y)\leq\epsilon$. However, this will give a
loose advantage bound since the full range of $\alpha$ is not being
effectively utilized. Fortunately, Fano’s inequality can be generalized
accordingly using Arimoto information for any order $\alpha$, which enables us
to generalize the advantage bound in section 4 with improved tightness. We
give details for this generalized analysis in Appendix A.

Figure 2: Reconstruction advantage vs. $\alpha=1$ Rényi DP parameter
$\epsilon$ for different values of $M$. As the number of possibilities $M$ for
the private attribute increases, the advantage curve becomes flatter,
suggesting that a high $\epsilon$ still gives strong protection against data
reconstruction.

#### Example.

We showcase the power of the Fano’s inequality analysis in combination with
Theorem 1 in the following example. Here, we consider $M$ training samples
$\mathbf{z}_{1},\ldots,\mathbf{z}_{M}$ with uniform sampling probability
$\mathbf{p}_{m}=1/M$ for $m=1,\ldots,M$, hence $H(X)=\log M$. For a
$(1,\epsilon)$-RDP learning algorithm $\mathcal{M}$, we can use Theorem 1 to
upper bound $I(X;Y)$ and use Algorithm 1 to compute $t^{*}=\mathbb{P}(E=1)$
and the advantage bound accordingly. Figure 2 shows the advantage bound as a
function of $\epsilon$ for different values of $M$. As expected, all curves
are monotonically increasing in $\epsilon$, _i.e._ , more privacy leakage
results in higher advantage for the adversary.

More interestingly, for the same value of $\epsilon$, having a higher $M$
reduces advantage, which reflects the fact that there is more entropy in the
private attribute and thus the adversary’s success probability decreases with
$M$. In fact, it is easy to show that for a given $c>0$, the adversary’s
advantage at $\epsilon=c\log M$ is the same for all values of $M$, suggesting
that the target privacy parameter $\epsilon$ should be $O(\log M)$ to target a
specific level of privacy risk. This theoretical analysis confirms the
empirical observation that even a large $\epsilon$ confers non-trivial
protection against data reconstruction attacks (Carlini et al., 2019). For
instance, the membership inference advantage at $\epsilon=1$ is the same as
the data reconstruction advantage at $\epsilon=\log M\approx 23$ when the
private attribute is uniformly randomly sampled from a set of size
$M=10^{10}$.

###  5.2 Analysis for Randomized Response

Next, we derive a specialized mutual information bound for the (generalized)
randomized response (RR) mechanism defined as follows:

$Y|X=\begin{cases}X&\text{w.p. }1-q,\\\
\text{Unif}(\\{1,\ldots,M\\})&\text{w.p. }q\end{cases}$ (9)

where $q\in[0,1]$. It can be shown that the mechanism is $\epsilon$-DP with
$\epsilon=\log\left(\frac{1-q+q/M}{q/M}\right)$.

#### Exact computation of mutual information.

To derive $I(X;Y)$, first note that $\mathbb{P}(X=x,Y=y)=P(X=x)P(Y=y|X=x)$ and
$\mathbb{P}(Y=y)=\sum_{x}\mathbb{P}(X=x,Y=y)$ can be easily computed given
$q$, $M$ and the sampling probability vector $\mathbf{p}$. We can then
numerically compute:

$\displaystyle I$
$\displaystyle(X;Y)=\sum_{x}\sum_{y}\mathbb{P}(X=x,Y=y)\log\frac{\mathbb{P}(X=x,Y=y)}{\mathbb{P}(X=x)\mathbb{P}(Y=y)}.$
(10)

#### Tightness of Fano’s inequality.

For the randomized response mechanism, one can show that the _maximum a
posteriori_ (MAP) adversary attains equality in Fano’s inequality when the
sampling probability for $X$ is uniform, _i.e._ , $\mathbf{p}_{m}=1/M$ for all
$m$. This can be done by deriving the posterior distribution for $X$ given any
$Y=y$, which we include in Appendix A for completeness.

###  5.3 Analysis for Gaussian Mechanism

The Gaussian mechanism is a common primitive in the design of more complex
private mechanisms such as DP-SGD (Abadi et al., 2016). Here, the mechanism
first maps each private record $\mathbf{z}_{m}$ to some encoding
$\mathbf{e}_{m}\in\mathbb{R}^{d}$ and outputs

$(Y|X=m)=\mathbf{e}_{m}+\mathcal{N}(0,\sigma^{2}\mathbf{I}_{d\times d}).$ (11)

As a result, $Y$ is a Gaussian mixture with mixture probabilities
$\mathbf{p}$. For example, in output perturbation (Chaudhuri et al., 2011),
$\mathbf{e}_{m}$ is the model obtained when training a convex model on
$\mathcal{D}\cup\\{\mathbf{z}_{m}\\}$; in DP-SGD, $\mathbf{e}_{m}$ is the
gradient of the training loss for sample $\mathbf{z}_{m}$. For the purpose of
this analysis, it is equivalent to treat $\mathbf{e}_{m}$ as the private
record instead of $\mathbf{z}_{m}$ since the mapping can be easily inverted
(Zhu et al., 2019).

#### Mutual information bound.

It is well-known that the Gaussian mechanism satisfies $(\alpha,\epsilon)$-RDP
with $\epsilon=\alpha\Delta^{2}/2\sigma^{2}$ when the encoding function has
$L_{2}$-sensitivity $\Delta$ (Mironov, 2017). This readily gives a bound for
$I(X;Y)$ using Theorem 1 by setting $\alpha=1$. Below we present a tighter
bound for the mutual information of Gaussian mechanisms.

######  Theorem 2.

Let $\mathbf{e}_{m}$ be the encoding for the private record $\mathbf{z}_{m}$
for $m=1,\ldots,M$, and let
$\Delta=\max_{m,l}\|\mathbf{e}_{m}-\mathbf{e}_{l}\|_{2}$ be the
$L_{2}$-sensitivity of the encoding function. Then the Gaussian mechanism
(_cf._ Equation 11) satisfies:

$I(X;Y)\leq-\sum_{m}\mathbf{p}_{m}\log\bigg{(}\mathbf{p}_{m}+(1-\mathbf{p}_{m})\exp\left(\frac{-\Delta^{2}}{2\sigma^{2}}\right)\bigg{)}.$
(12)

#### Approximation via Monte-Carlo.

One can show that (see Equation 21 in Appendix B)

$I(X;Y)=\sum_{x}\mathbb{P}(X=x)D_{1}((Y|X=x)||Y),$

where $D_{1}$ denotes KL divergence. For the Gaussian mechanism, each term in
the sum is the KL divergence between a Gaussian distribution and a mixture of
Gaussians. Although this quantity is difficult to bound in closed form, it can
be approximated via Monte-Carlo simulation by drawing
$k\sim\text{Categorical}(\mathbf{p})$ and computing the KL divergence
$D_{1}((Y|X=k)||Y)$. Taking expectation over multiple draws gives an unbiased
estimate of $I(X;Y)$.

##  6 Experiment

We perform a series of experiments to show that the Fano’s inequality bound
provides meaningful semantic guarantees against attribute inference and data
reconstruction attacks.

###  6.1 Synthetic Data Experiments

(a) Randomized response

(b) Gaussian mechanism

Figure 3: Advantage plot for randomized response and the Gaussian mechanism.
The advantage bound using Fano’s inequality and exact/approximate mutual
information closely matches the empirical lower bound. See text for details.

We first experiment on synthetic data to numerically evaluate our Fano’s
inequality bound for both randomized response and the Gaussian mechanism.

#### Data generation.

We generate data with $M=10$ possible values sampled uniformly randomly,
_i.e._ , $\mathbf{p}_{m}=1/M$ for $m=1,\ldots,M$. For randomized response, we
sample the output value $Y$ according to Equation 9 with different values of
$q\in[0,1]$. For the Gaussian mechanism, we encode the data as one-hot vectors
$\mathbf{e}_{1},\ldots,\mathbf{e}_{M}$ and output $Y$ according to Equation 11
with $\sigma\in(0,3]$.

#### Advantage bounds.

We evaluate our Fano’s inequality bound using three different upper bounds for
mutual information: Bound from RDP (Theorem 1), specialized bound for the
Gaussian mechanism (Theorem 2), and either exact computation of mutual
information using Equation 10 for randomized response or approximation via
Monte-Carlo for the Gaussian mechanism. As a baseline, we evaluate the
$(\eta,\gamma)$-ReRo bound from Balle et al. (2022), which upper bounds the
adversary’s success probability as:
$\mathbb{P}(E=0)\leq(e^{\epsilon}/M)^{\frac{\alpha-1}{\alpha}}$ if
$\mathcal{M}$ is $(\alpha,\epsilon)$-RDP. We minimize this upper bound over
$\alpha$ and convert it to an advantage bound for comparison.

#### Empirical lower bound.

To compute an empirical lower bound for the advantage, we simulate a data
reconstruction adversary using the _maximum a posteriori_ (MAP) estimator
$\hat{X}(Y)$, which returns the most likely value for $X$ given $Y$ using
Bayes’ rule. Each experiment then consists of: 1. Sampling $X$ from
$1,\ldots,M$ uniformly; 2. Using either randomized response or the Gaussian
mechanism to sample $Y$; 3. Computing the MAP estimate $\hat{X}(Y)$ and
comparing it to $X$. We repeat this experiment $100,000$ times to compute an
empirical lower bound for the advantage.

#### Result.

Figure 3 plots advantage as a function of the sampling probability $q$ for
randomized response (left) and noise standard deviation $\sigma$ for the
Gaussian mechanism (right). For randomized response (3(a)), a higher $q$
increases the probability of sampling $Y$ from the uniform distribution and
hence improves privacy. This is reflected in the empirical lower bound (dashed
line) as the adversary’s advantage decreases to $0$ when $q=1$. Both the
baseline (gray) and the advantage bound using Theorem 1 (blue) rely on RDP
accounting. We observe that the bound from Theorem 1 is consistently lower
than the baseline bound, although both are relatively loose compared to the
empirical lower bound. In contrast, using Fano’s inequality with exact mutual
information gives a _tight_ advantage upper bound, matching the empirical
lower bound. This validates the derivation in subsection 5.2 showing that the
MAP estimator attains equality in Fano’s inequality.

For the Gaussian mechanism (3(b)), a higher $\sigma$ introduces more
randomness and increases privacy, and thus both the empirical lower bound as
well as the upper bounds decrease as $\sigma$ increases. Similar to the
randomized response result, the baseline bound is strictly dominated by
Theorem 1, whereas Theorem 2 further tightens the advantage bound for lower
values of $\sigma$. Using Monte-Carlo to approximate mutual information gives
the tightest advantage bound that closely matches the behavior of the
empirical lower bound. These results demonstrate the power and tightness of
the Fano’s inequality analysis for bounding data reconstruction advantage.
They also suggest that tight mutual information privacy accounting can enable
strong semantic privacy guarantees for relatively low amounts of DP noise
addition.

###  6.2 Attribute Inference for Pharmacogenetics Modeling

(a) Advantage vs. $\sigma$

(b) Test MSE vs. $\sigma$

Figure 4: Advantage and test mean squared error (MSE) plots for the IWPC
attribute inference attack experiment. The model is trained using output
perturbation by adding Gaussian noise with standard deviation $\sigma$ to the
loss minimizer. At $\sigma=0.1$, advantage is relatively low when measured
according to both the Fano bound and the empirical attacks, while the model’s
test MSE increases only moderately.

Next, we evaluate our advantage bound for privately trained pharmacogenetics
models studied in Fredrikson et al. (2014) and show that it gives meaningful
protection against attribute inference attacks.

#### Dataset and model.

The IWPC dataset (Klein et al., 2009) contains data for clinical trial
subjects, with the goal of training an ML model to predict the stable dosage
of warfarin given the subjects’ attributes. One particularly privacy-sensitive
attribute is the VKORC1 gene type, which can be one of three values: CC, CT or
TT. We train an $L_{2}$-regularized linear regression model on the attributes
to predict the warfarin dosage (_i.e._ , target label) according to Hannun et
al. (2021).

#### DP mechanism.

We employ the output perturbation mechanism (Chaudhuri et al., 2011), which
adds Gaussian noise to the model parameters to guarantee differential privacy.
For each sample $j$, let $\mathcal{D}_{-j}$ be the data subset containing all
but the $j$-th sample $\mathbf{z}^{(j)}$. For the privacy analysis, we train
three different models on datasets
$\mathcal{D}_{-j}\cup\\{\mathbf{z}_{m}^{(j)}\\}$ for $m=1,2,3$, where
$\mathbf{z}_{m}^{(j)}$ represents the $j$-th sample with its VKORC1 gene set
to one of the three values CC, CT or TT. We can then treat the three models’
parameters as encodings of the private gene types under our data
reconstruction game formulation, and the output perturbation mechanism is
equivalent to the Gaussian mechanism applied to these encodings. To compute
the advantage bound, we use the specialized mutual information bound in
Theorem 2.

#### Attacks.

We consider attribute inference attacks for inferring the VKORC1 gene type
from the trained model. Following Hannun et al. (2021), we implement a white-
box attack with full knowledge of the data subset $\mathcal{D}_{-j}$ and all
attributes of sample $\mathbf{z}^{(j)}$ except for the VKORC1 gene type. The
attack essentially implements a maximum likelihood estimator, and we augment
it with prior knowledge of the marginal distribution of the three gene types
to produce a Bayesian variant. We also implement the Informed Adversary attack
from Balle et al. (2022), which only has access to $\mathcal{D}_{-j}$ for
predicting the VKORC1 gene type of $\mathbf{z}^{(j)}$. Details for the attacks
are given in Appendix A.

#### Result.

4(a) shows the adversary’s advantage as a function of $\sigma$, which shows a
decreasing trend as expected. We observe that the white-box attack with prior
knowledge of the marginal distribution of the VKORC1 gene (dark blue) attains
the highest advantage. Notably, its advantage converges to 0 as
$\sigma\rightarrow\infty$, whereas the white-box attack without prior (light
blue) and the Informed Adversary attack (orange) have negative advantage as
$\sigma\rightarrow 0$. This is because the VKORC1 gene’s marginal distribution
is non-uniform, with probabilities $0.367,0.339,0.294$ for CC, CT and TT,
respectively. Since advantage as defined in Equation 3 uses $p^{*}=0.367$
(corresponding to always predicting CC) as the baseline, it is sub-optimal to
predict the uniform distribution when the model contains close to no
information about $\mathbf{z}^{(j)}$ when $\sigma$ is large.

The advantage bound using Fano’s inequality (black line) strictly dominates
the advantage of the three attacks. In particular, at $\sigma=0.1$ the
advantage bound predicts close to $0.1$ advantage, which can be considered
relatively low risk. Moreover, the test mean squared error (MSE) in 4(b) shows
that model utility remains reasonable when $\sigma=0.1$. Our analysis suggests
that $\sigma=0.1$ can be a reasonable value for the output perturbation
mechanism applied to this dataset for optimal privacy-utility trade-off.

###  6.3 Language Model Training with Canaries

Figure 5: Result for the language model canary extraction attack. The model is
fine-tuned on the canary sequence for $T$ steps using DP-SGD. The advantage
upper bound using Fano’s inequality gives non-trivial semantic guarantee
against reconstruction attacks even for relatively large values of RDP
parameter $\epsilon$. See text for details.

Finally, we consider a language model canary extraction attack similar to the
experiment performed in Carlini et al. (2019).

#### Setup.

We experiment using a pre-trained GPT-2 (Radford et al., 2019) model—a causal
language model for predicting the next token given a context token sequence.
The vocabulary consists of $M=50,256$ tokens. We fine-tune the model using DP-
SGD (Abadi et al., 2016) on a single _canary sequence_ of the form “John
Smith’s credit card number is X”, with X being a token chosen uniformly
randomly from the vocabulary. For the DP-SGD hyperparameters, we use a
clipping norm of $C=1$ and vary the number of fine-tuning steps $T$ and the
noise multiplier $\sigma$. For any $\alpha\geq 1$, one can show that DP-SGD is
$(\alpha,\epsilon)$-RDP with $\epsilon=\alpha T/2\sigma^{2}$, and then use
Fano’s inequality with Theorem 1 to obtain the advantage upper bound.

#### Attack.

Since the model is fine-tuned to predict a single secret token X in the canary
sequence, we can perform an extraction attack that compares the log-
likelihood111We also experimented using the likelihood and found that the
attack performs significantly worse. of every token X before and after fine-
tuning. The adversary then predicts the token with the largest difference.
Note that such a differencing attack has been used in state-of-the-art
membership inference attacks such as Ye et al. (2021); Watson et al. (2021);
Carlini et al. (2022). Thus, each experiment run consists of sampling X
uniformly from $M=50,256$ tokens, fine-tuning the GPT-2 model using DP-SGD on
the canary sequence, and then running the extraction attack to recover X. We
perform this experiment $1000$ times to compute the adversary’s advantage
empirically.

#### Result.

Figure 5 shows the adversary’s advantage as a function of the $\alpha=1$ RDP
parameter $\epsilon=2T/\sigma^{2}$, where $T\in\\{1,2,5\\}$ is the number of
fine-tuning steps. We include two variants of the fine-tuning method, either
fine-tune only the last layer (red) or fine-tune all layers (blue). As
expected, the adversary’s advantage increases monotonically as $\epsilon$
increases, while the advantage bound using Fano’s inequality strictly
dominates the advantage of simulated extraction attacks. Although the
advantage bound drastically overestimates the empirically computed advantage,
it can still serve as a useful guideline for selecting the privacy parameter
$\epsilon$. For instance, at $\epsilon=6$, the advantage upper bound is close
to $0.5$, which is certainly a non-trivial level of privacy protection for a
relatively large value of $\epsilon$. We suspect that the large gap is a
result of upper bounding mutual information using the generic RDP bound in
Theorem 1 and is an inherent limitation of using RDP accounting. A closer
privacy analysis of the Gaussian mechanism directly in terms of mutual
information may be able to close this gap significantly.

##  7 Conclusion

We presented a rigorous formulation of data reconstruction attacks and
analyzed the privacy leakage of DP mechanisms using Fano’s inequality. Our
analysis gives upper bounds on the advantage of a reconstruction adversary,
which we show empirically can be a strong indicator for the mechanism’s actual
privacy protection against privacy attacks. Consequently, we advocate for the
use of our bounds both for interpreting the DP parameter $\epsilon$ and as a
guideline for selecting it.

## References

  * Abadi et al. [2016] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In _Proceedings of the 2016 ACM SIGSAC conference on computer and communications security_ , pages 308–318, 2016.
  * Arimoto [1977] Suguru Arimoto.  Information measures and capacity of order $\alpha$ for discrete memoryless channels.  _Topics in information theory_ , 1977.
  * Balle et al. [2022] Borja Balle, Giovanni Cherubin, and Jamie Hayes.  Reconstructing training data with informed adversaries.  _arXiv preprint arXiv:2201.04845_ , 2022.
  * Bhowmick et al. [2018] Abhishek Bhowmick, John Duchi, Julien Freudiger, Gaurav Kapoor, and Ryan Rogers.  Protection against reconstruction and its applications in private federated learning.  _arXiv preprint arXiv:1812.00984_ , 2018.
  * Carlini et al. [2019] Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song.  The secret sharer: Evaluating and testing unintended memorization in neural networks.  In _28th USENIX Security Symposium (USENIX Security 19)_ , pages 267–284, 2019.
  * Carlini et al. [2021] Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al.  Extracting training data from large language models.  In _30th USENIX Security Symposium (USENIX Security 21)_ , pages 2633–2650, 2021.
  * Carlini et al. [2022] Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer.  Membership inference attacks from first principles.  In _2022 IEEE Symposium on Security and Privacy (SP)_ , pages 1897–1914. IEEE, 2022.
  * Chaudhuri et al. [2011] Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate.  Differentially private empirical risk minimization.  _Journal of Machine Learning Research_ , 12(3), 2011.
  * Cuff and Yu [2016] Paul Cuff and Lanqing Yu.  Differential privacy as a mutual information constraint.  In _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ , pages 43–54, 2016.
  * Dwork and Naor [2010] Cynthia Dwork and Moni Naor.  On the difficulties of disclosure prevention in statistical databases or the case for differential privacy.  _Journal of Privacy and Confidentiality_ , 2(1), 2010.
  * Dwork et al. [2006] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In _Theory of cryptography conference_ , pages 265–284. Springer, 2006.
  * Dwork et al. [2014] Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  _Found. Trends Theor. Comput. Sci._ , 9(3-4):211–407, 2014.
  * Erlingsson et al. [2019] Úlfar Erlingsson, Ilya Mironov, Ananth Raghunathan, and Shuang Song.  That which we call private.  _arXiv preprint arXiv:1908.03566_ , 2019.
  * Feldman [2020] Vitaly Feldman.  Does learning require memorization? a short tale about a long tail.  In _Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing_ , pages 954–959, 2020.
  * Fredrikson et al. [2015] Matt Fredrikson, Somesh Jha, and Thomas Ristenpart.  Model inversion attacks that exploit confidence information and basic countermeasures.  In _Proceedings of the 22nd ACM SIGSAC conference on computer and communications security_ , pages 1322–1333, 2015.
  * Fredrikson et al. [2014] Matthew Fredrikson, Eric Lantz, Somesh Jha, Simon Lin, David Page, and Thomas Ristenpart.  Privacy in pharmacogenetics: An $\\{$End-to-End$\\}$ case study of personalized warfarin dosing.  In _23rd USENIX Security Symposium (USENIX Security 14)_ , pages 17–32, 2014.
  * Geiping et al. [2020] Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller.  Inverting gradients-how easy is it to break privacy in federated learning?  _Advances in Neural Information Processing Systems_ , 33:16937–16947, 2020.
  * Guo et al. [2022] Chuan Guo, Brian Karrer, Kamalika Chaudhuri, and Laurens van der Maaten.  Bounding training data reconstruction in private (deep) learning.  _arXiv preprint arXiv:2201.12383_ , 2022.
  * Hannun et al. [2021] Awni Hannun, Chuan Guo, and Laurens van der Maaten.  Measuring data leakage in machine-learning models with fisher information.  In _Uncertainty in Artificial Intelligence_ , pages 760–770. PMLR, 2021.
  * Humphries et al. [2020] Thomas Humphries, Matthew Rafuse, Lindsey Tulloch, Simon Oya, Ian Goldberg, Urs Hengartner, and Florian Kerschbaum.  Differentially private learning does not bound membership inference.  _arXiv preprint arXiv:2010.12112_ , 2020.
  * Jagielski et al. [2020] Matthew Jagielski, Jonathan Ullman, and Alina Oprea.  Auditing differentially private machine learning: How private is private sgd?  _Advances in Neural Information Processing Systems_ , 33:22205–22216, 2020.
  * Jayaraman and Evans [2019] Bargav Jayaraman and David Evans.  Evaluating differentially private machine learning in practice.  In _28th USENIX Security Symposium (USENIX Security 19)_ , pages 1895–1912, 2019.
  * Klein et al. [2009] T.E. Klein, R.B. Altman, N. Eriksson, B.F. Gage, S.E. Kimmel, M.-T.M. Lee, N.A. Limdi, D. Page, D.M. Roden, M.J. Wagner, M.D. Caldwell, and J.A. Johnson.  Estimation of the warfarin dose with clinical and pharmacogenetic data.  _New England Journal of Medicine_ , 360(8):753–764, 2009.
  * Mahloujifar et al. [2022] Saeed Mahloujifar, Alexandre Sablayrolles, Graham Cormode, and Somesh Jha.  Optimal membership inference bounds for adaptive composition of sampled gaussian mechanisms.  _arXiv preprint arXiv:2204.06106_ , 2022.
  * McMahan et al. [2017] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In _Artificial intelligence and statistics_ , pages 1273–1282. PMLR, 2017.
  * Mironov [2017] Ilya Mironov.  Rényi differential privacy.  In _2017 IEEE 30th computer security foundations symposium (CSF)_ , pages 263–275. IEEE, 2017.
  * Nasr et al. [2019] Milad Nasr, Reza Shokri, and Amir Houmansadr.  Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning.  In _2019 IEEE symposium on security and privacy (SP)_ , pages 739–753. IEEE, 2019.
  * Nasr et al. [2021] Milad Nasr, Shuang Songi, Abhradeep Thakurta, Nicolas Papernot, and Nicholas Carlin.  Adversary instantiation: Lower bounds for differentially private machine learning.  In _2021 IEEE Symposium on Security and Privacy (SP)_ , pages 866–882. IEEE, 2021.
  * Nielsen and Nock [2017] Frank Nielsen and Richard Nock.  On $w$-mixtures: Finite convex combinations of prescribed component distributions.  _arXiv preprint arXiv:1708.00568_ , 2017.
  * Radford et al. [2019] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9, 2019.
  * Rényi et al. [1961] Alfréd Rényi et al.  On measures of entropy and information.  In _Proceedings of the fourth Berkeley symposium on mathematical statistics and probability_ , volume 1. Berkeley, California, USA, 1961.
  * Sablayrolles et al. [2019] Alexandre Sablayrolles, Matthijs Douze, Cordelia Schmid, Yann Ollivier, and Hervé Jégou.  White-box vs black-box: Bayes optimal strategies for membership inference.  In _International Conference on Machine Learning_ , pages 5558–5567. PMLR, 2019.
  * Salem et al. [2018] Ahmed Salem, Yang Zhang, Mathias Humbert, Pascal Berrang, Mario Fritz, and Michael Backes.  Ml-leaks: Model and data independent membership inference attacks and defenses on machine learning models.  _arXiv preprint arXiv:1806.01246_ , 2018.
  * Sason and Verdú [2016] Igal Sason and Sergio Verdú.  $f$-divergence inequalities.  _IEEE Transactions on Information Theory_ , 62(11):5973–6006, 2016.
  * Shokri and Shmatikov [2015] Reza Shokri and Vitaly Shmatikov.  Privacy-preserving deep learning.  In _Proceedings of the 22nd ACM SIGSAC conference on computer and communications security_ , pages 1310–1321, 2015.
  * Shokri et al. [2017] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov.  Membership inference attacks against machine learning models.  In _2017 IEEE symposium on security and privacy (SP)_ , pages 3–18. IEEE, 2017.
  * Song et al. [2017] Congzheng Song, Thomas Ristenpart, and Vitaly Shmatikov.  Machine learning models that remember too much.  In _Proceedings of the 2017 ACM SIGSAC Conference on computer and communications security_ , pages 587–601, 2017.
  * Thudi et al. [2022] Anvith Thudi, Ilia Shumailov, Franziska Boenisch, and Nicolas Papernot.  Bounding membership inference.  _arXiv preprint arXiv:2202.12232_ , 2022.
  * Verdú [2015] Sergio Verdú.  $\alpha$-mutual information.  In _2015 Information Theory and Applications Workshop (ITA)_ , pages 1–6. IEEE, 2015.
  * Wang et al. [2016] Weina Wang, Lei Ying, and Junshan Zhang.  On the relation between identifiability, differential privacy, and mutual-information privacy.  _IEEE Transactions on Information Theory_ , 62(9):5018–5029, 2016.
  * Warner [1965] Stanley L Warner.  Randomized response: A survey technique for eliminating evasive answer bias.  _Journal of the American Statistical Association_ , 60(309):63–69, 1965.
  * Watson et al. [2021] Lauren Watson, Chuan Guo, Graham Cormode, and Alex Sablayrolles.  On the importance of difficulty calibration in membership inference attacks.  _arXiv preprint arXiv:2111.08440_ , 2021.
  * Ye et al. [2021] Jiayuan Ye, Aadyaa Maddi, Sasi Kumar Murakonda, and Reza Shokri.  Enhanced membership inference attacks against machine learning models.  _arXiv preprint arXiv:2111.09679_ , 2021.
  * Yeom et al. [2018] Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha.  Privacy risk in machine learning: Analyzing the connection to overfitting.  In _2018 IEEE 31st computer security foundations symposium (CSF)_ , pages 268–282. IEEE, 2018.
  * Zhu et al. [2019] Ligeng Zhu, Zhijian Liu, and Song Han.  Deep leakage from gradients.  _Advances in neural information processing systems_ , 32, 2019.

##  Appendix A Method Details

###  A.1 Algorithm for Computing Advantage Bound

To compute $t^{*}$ in Equation 7, we assume that the mechanism $\mathcal{M}$
is $\epsilon$-MI-DP (_i.e._ , $I(X;Y)\leq\epsilon$) for some $\epsilon>0$, and
define:

$f_{\epsilon}(t)=H(X)-\epsilon+t\log t+(1-t)\log(1-t)-t\log(M-1).$

Since $H(X|Y)=H(X)-I(X;Y)\geq H(X)-\epsilon$, we have that
$f_{\epsilon}(t^{*})\leq f(t^{*})\leq 0$. Thus, we can instead minimize $t$
subject to $f_{\epsilon}(t)\leq 0$ to obtain a lower bound
$t^{*}\leq\min\\{t\in[0,1]:f_{\epsilon}(t)\leq 0\\}$ for the error probability
of _any_ data reconstruction adversary. Taking derivative gives:

$f_{\epsilon}^{\prime}(t)=\log t+1-\log(1-t)-1-\log(M-1)=\log
t-\log(1-t)-\log(M-1).$ (13)

It is easy to see that $f_{\epsilon}^{\prime}(t)\geq 0$ if and only if $t\geq
1-1/M$, so $f_{\epsilon}$ is decreasing for $t\in[0,1-1/M)$ and increasing for
$t\in(1-1/M,1]$. Moreover, we know that $f_{\epsilon}(0)>0$ if
$\epsilon<H(X)$, and $f_{\epsilon}(1-1/M)=H(X)-\epsilon-\log(M)\leq 0$. Hence
we can use binary search over the interval $[0,1-1/M]$ to find
$\min\\{t\in[0,1]:f_{\epsilon}(t)\leq 0\\}$. Algorithm 1 summarizes the
computation in pseudo-code.

Algorithm 1 Computing the advantage bound using Fano’s inequality.

1: Input: Upper bound $I(X;Y)\leq\epsilon$, number of distinct attributes $M$,
sampling probability vector $\mathbf{p}$.

2: $p^{*}\leftarrow\max_{m}\mathbf{p}_{m}$

3: if $\epsilon\geq H(\mathbf{p})$ then

4: return $1$

5: else

6: Define $f_{\epsilon}(t)=H(\mathbf{p})-\epsilon+t\log
t+(1-t)\log(1-t)-t\log(M-1)$.

7: assert $f_{\epsilon}(0)>0$ and $f_{\epsilon}(1-1/M)\leq 0$

8: Use binary search to find $t^{*}=\min\\{t\in[0,1-1/M]:f_{\epsilon}(t)\leq
0\\}$.

9: return $(1-t^{*}-p^{*})/(1-p^{*})$

10: end if

###  A.2 Generalized Fano’s Inequality Analysis

We derive a generalized version of the Fano’s inequality analysis in section 4
using Arimoto information. We first define a few key quantities in information
theory below.

#### Measures of information.

In information theory, _entropy_ measures the amount of information contained
in a random variable. For a discrete random variable $X$, the entropy of $X$
is defined as

$H(X)=-\sum_{x}\mathbb{P}(X=x)\log\mathbb{P}(X=x).$ (14)

A closely related notion is _conditional entropy_ $H(X|Y)$. For two random
variables $X$ and $Y$, $H(X|Y)$ measures the amount of information contained
in $X$ after observing $Y$, and is defined as

$H(X|Y)=\sum_{y}\mathbb{P}(Y=y)H(X|Y=y),$ (15)

where $H(X|Y=y)$ denotes entropy of the conditional distribution $X|Y=y$. In
essence, if $X$ and $Y$ are highly dependent then $H(X|Y)\approx 0$, which
suggests that there is very little entropy left in $X$ after observing $Y$. On
the other hand, if $X$ and $Y$ are independent then $H(X|Y)=H(X)$, meaning
that observing $Y$ gives no additional information about $Y$. Thus, the
difference

$I(X;Y):=H(X)-H(X|Y),$ (16)

known as _mutual information_ , is a non-negative quantity that measures the
amount of dependence between $X$ and $Y$.

#### Generalization using Rényi entropy.

The three measures of information defined above can be generalized. We start
from the generalization of entropy to _Rényi entropy of order $\alpha$_ [Rényi
et al., 1961], denoted $H_{\alpha}$, given by:

$H_{\alpha}(X)=\frac{1}{1-\alpha}\log\sum_{x}\mathbb{P}(X=x)^{\alpha}$ (17)

for $\alpha>1$. Notably, it can be shown that this definition recovers the
standard entropy $H(X)$ when $\alpha\rightarrow 1$. The corresponding
generalization of conditional entropy is the so-called _Arimoto-Rényi
conditional entropy_ [Arimoto, 1977], defined as

$H_{\alpha}(X|Y)=\frac{\alpha}{1-\alpha}\log\mathbb{P}(Y=y)\exp\left(\frac{1-\alpha}{\alpha}H_{\alpha}(X|Y=y)\right).$
(18)

The generalization of mutual information $I_{\alpha}(X;Y)$, known as _Arimoto
information_ [Verdú, 2015], is the difference $H_{\alpha}(X)-H_{\alpha}(X|Y)$,
and has the following form:

$I_{\alpha}(X;Y)=\frac{\alpha}{\alpha-1}\log\sum_{y}\left(\sum_{x}\mathbb{P}(X_{\alpha}=x)\mathbb{P}(Y=y|X=x)^{\alpha}\right)^{1/\alpha},$
(19)

where $X_{\alpha}$ denotes the $\alpha$-scaled distribution with
$\mathbb{P}(X_{\alpha}=x)\propto\mathbb{P}(X=x)^{\alpha}$. Similar to Rényi
entropy, Arimoto-Rényi conditional entropy and Arimoto information both
converge to the corresponding conditional entropy and mutual information as
$\alpha\rightarrow 1$.

#### Generalized Fano’s inequality.

Fano’s inequality can be generalized using an analogue of conditional entropy
known as _Arimoto-Rényi conditional entropy_ [Arimoto, 1977]. The generalized
version is given in Sason and Verdú [2016], which states:

$H_{\alpha}(X|Y)\leq\log
M-D_{\alpha}(\text{Bernoulli}(t)||\text{Bernoulli}(1-1/M)),$ (20)

where $\text{Bernoulli}(t)$ denotes the Bernoulli distribution with success
probability $t$. It can be shown that
$H_{\alpha}(X|Y)=H_{\alpha}(X)-I_{\alpha}(X;Y)$. $H_{\alpha}(X)$ can be
computed directly using Equation 17, while $I_{\alpha}(X;Y)$ can be upper
bounded using Theorem 1. Thus, we can lower bound $H_{\alpha}(X|Y)$ and
establish an inequality for $t$ using the generalized Fano’s inequality. We
can then apply the binary search method in Algorithm 1 to upper bound the
advantage for a given $\alpha$. Algorithm 2 details the computation in pseudo-
code.

Algorithm 2 Computing the advantage bound using generalized Fano’s inequality.

1: Input: $\alpha\geq 1$, upper bound $I_{\alpha}(X;Y)\leq\epsilon$, number of
distinct attributes $M$, sampling probability vector $\mathbf{p}$.

2: $p^{*}\leftarrow\max_{m}\mathbf{p}_{m}$

3: if $\epsilon\geq H_{\alpha}(\mathbf{p})$ then

4: return $1$

5: else

6: Define $f_{\epsilon}(t)=H_{\alpha}(\mathbf{p})-\epsilon-\log
M+D_{\alpha}(\text{Bernoulli}(t)||\text{Bernoulli}(1-1/M))$.

7: assert $f_{\epsilon}(0)>0$ and $f_{\epsilon}(1-1/M)\leq 0$

8: Use binary search to find $t^{*}=\min\\{t\in[0,1-1/M]:f_{\epsilon}(t)\leq
0\\}$.

9: return $(1-t^{*}-p^{*})/(1-p^{*})$

10: end if

###  A.3 Tightness of Fano’s Inequality for Randomized Response

Recall the generalized randomized response mechanism in subsection 5.2. We
show that the Fano’s inequality analysis is tight when the input is sampled
uniformly randomly. For any $Y=y$, we can derive the posterior distribution
for $X$ using Bayes rule:

$\mathbb{P}(X=x|Y=y)=\mathbb{P}(Y=y|X=x)\mathbb{P}(X=i)/\mathbb{P}(Y=y)=\begin{cases}1-q+q/M&\text{if
}x=y,\\\ q/M&\text{otherwise.}\end{cases}$

Suppose $q<1$ so that $1-q+q/M>q/M$, then the MAP adversary’s estimate is
$\hat{X}(Y)=Y$, with error probability $\mathbb{P}(E=1)=q-q/M$. For any $y$,
we can derive the conditional entropy $H(X|Y=y)$ in closed form:

$\displaystyle H(X|Y=y)$
$\displaystyle=\left(-(1-q+q/M)\log(1-q+q/M)-\sum_{x\neq
y}\frac{q}{M}\log\frac{q}{M}\right)$
$\displaystyle=\left(-(1-q+q/M)\log(1-q+q/M)-(q-q/M)\log\frac{q(M-1)}{M(M-1)}\right)$
$\displaystyle=(-(1-q+q/M)\log(1-q+q/M)-(q-q/M)\log(q-q/M)+(q-q/M)\log(M-1))$
$\displaystyle=H(E)+\mathbb{P}(E=1)\log(M-1).$

Multiplying both sides by $\mathbb{P}(Y=y)$ and taking sum over $y$ gives
$H(X|Y)=H(E)+\mathbb{P}(E=1)\log(M-1)$, which attains equality in Equation 5.

###  A.4 Attribute Inference Attack Details

We give details for the white-box attribute inference attack in subsection
6.2. Fix sample $j$, and for $m=1,2,3$ let $\mathbf{w}_{m}$ be the parameter
vector of the model trained on
$\mathcal{D}_{-j}\cup\\{\mathbf{z}_{m}^{(j)}\\}$. Suppose the output
perturbation mechanism returns the parameter vector $\mathbf{w}$. Since the
mechanism obtained $\mathbf{w}$ by perturbing one of
$\mathbf{w}_{1},\mathbf{w}_{2},\mathbf{w}_{3}$ with Gaussian noise, we can
evaluate the likelihood of $\mathbf{w}$ under all three choices and maximize
it to determine $X$:

$\log\mathbb{P}(X=m|Y=\mathbf{w})=-\|\mathbf{w}-\mathbf{w}_{m}\|_{2}^{2}/2\sigma^{2}+\text{constant}.$

This is possible since the adversary has access to $\mathcal{D}_{-j}$ and all
attributes of $\mathbf{z}^{(j)}$ except for the VKORC1 gene, and hence can
enumerate all possible values for $\mathbf{z}_{i}^{(j)}$ to obtain
$\mathbf{w}_{1},\mathbf{w}_{2},\mathbf{w}_{3}$. To derive the MAP estimator,
we apply Bayes’ rule:

$\displaystyle\mathbb{P}(X=m|Y=\mathbf{w})$
$\displaystyle\propto\mathbb{P}(Y=\mathbf{w}|X=m)\mathbb{P}(X=m)=\mathbb{P}(Y=\mathbf{w}|X=m)\mathbf{p}_{m}$
$\displaystyle\Rightarrow\log\mathbb{P}(X=m|Y=\mathbf{w})$
$\displaystyle=-\|\mathbf{w}-\mathbf{w}_{m}\|_{2}^{2}/2\sigma^{2}+\log\mathbf{p}_{m}+\text{constant},$

where $\mathbf{p}=(0.367,0.339,0.294)$ is the marginal distribution of the
VKORC1 gene.

##  Appendix B Proofs

######  Theorem 1.

For any $\alpha\geq 1$, if $\mathcal{M}$ is $(\alpha,\epsilon)$-RDP then
$I_{\alpha}(X;Y)\leq\epsilon$.

###### Proof.

We first prove this for $\alpha=1$. By definition:

$\displaystyle I(X;Y)$
$\displaystyle=\sum_{x}\sum_{y}\mathbb{P}(X=x,Y=y)\log\frac{\mathbb{P}(X=x,Y=y)}{\mathbb{P}(X=x)\mathbb{P}(Y=y)}$
$\displaystyle=\sum_{x}\mathbb{P}(X=x)\sum_{y}\mathbb{P}(Y=y|X=x)\log\frac{\mathbb{P}(Y=y|X=x)}{\mathbb{P}(Y=y)}$
$\displaystyle=\sum_{x}\mathbb{P}(X=x)D_{1}((Y|X=x)||Y),$ (21)

where $D_{1}$ denotes KL divergence, which is equivalent to the order
$\alpha=1$ Rényi divergence. By convexity,

$\displaystyle D_{1}((Y|X=x)||Y)$
$\displaystyle\leq\sum_{x^{\prime}}\mathbb{P}(X=x^{\prime})D_{1}((Y|X=x)||(Y|X=x^{\prime}))$
$\displaystyle\leq\sum_{x^{\prime}}\mathbb{P}(X=x^{\prime})\epsilon\quad\quad\text{since
$\mathcal{M}$ is $(1,\epsilon)$-RDP}$ $\displaystyle=\epsilon.$

Plugging back into Equation 21 gives the desired result. For $\alpha>1$, let
$X_{\alpha}$ denote the $\alpha$-scaled distribution in the definition of
Arimoto information, _i.e._ ,
$\mathbb{P}(X_{\alpha}=x)\propto\mathbb{P}(X=x)^{\alpha}$. Then:

$\displaystyle I_{\alpha}(X;Y)$
$\displaystyle=\frac{\alpha}{\alpha-1}\log\sum_{y}\left(\sum_{x}\mathbb{P}(X_{\alpha}=x)\mathbb{P}(Y=y|X=x)^{\alpha}\right)^{1/\alpha}$
$\displaystyle=\frac{\alpha}{\alpha-1}\log\sum_{y}\mathbb{P}(Y=y)\left(\sum_{x}\mathbb{P}(X_{\alpha}=x)\frac{\mathbb{P}(Y=y|X=x)^{\alpha}}{\mathbb{P}(Y=y)^{\alpha}}\right)^{1/\alpha}$
$\displaystyle\leq\frac{1}{\alpha-1}\log\sum_{y}\mathbb{P}(Y=y)\left(\sum_{x}\mathbb{P}(X_{\alpha}=x)\frac{\mathbb{P}(Y=y|X=x)^{\alpha}}{\mathbb{P}(Y=y)^{\alpha}}\right)\quad\text{by
convexity of $z\mapsto z^{\alpha}$}$
$\displaystyle\leq\max_{x}\frac{1}{\alpha-1}\log\left(\sum_{y}\mathbb{P}(Y=y)\frac{\mathbb{P}(Y=y|X=x)^{\alpha}}{\mathbb{P}(Y=y)^{\alpha}}\right)\quad\text{by
monotonicity of $z\mapsto\frac{1}{\alpha-1}\log z$}$
$\displaystyle=\max_{x}D_{\alpha}((Y|X=x)||Y).$

The proof follows by quasi-convexity of Rényi divergence and the fact that
$\mathcal{M}$ is $(\alpha,\epsilon)$-RDP. ∎

######  Theorem 2.

Let $\mathbf{e}_{m}$ be the encoding for the private record $\mathbf{z}_{m}$
for $m=1,\ldots,M$, and let
$\Delta=\max_{m,l}\|\mathbf{e}_{m}-\mathbf{e}_{l}\|_{2}$ be the
$L_{2}$-sensitivity of the encoding function. Then the Gaussian mechanism
(_cf._ Equation 11) satisfies:

$I(X;Y)\leq-\sum_{m}\mathbf{p}_{m}\log\bigg{(}\mathbf{p}_{m}+(1-\mathbf{p}_{m})\exp\left(\frac{-\Delta^{2}}{2\sigma^{2}}\right)\bigg{)}.$
(22)

###### Proof.

First note that $I(X;Y)=H(Y)-H(Y|X)$ with $H(Y|X)=\frac{M}{2}\log(2\pi
e\sigma^{2})$. By Section 3.1 of Nielsen and Nock [2017], because $Y$ is a
mixture of Gaussians we have the following bound for $H(Y)$:

$\displaystyle H(Y)$
$\displaystyle\leq\sum_{m}\mathbf{p}_{m}H\bigg{(}\mathcal{N}(\mathbf{e}_{m},\sigma^{2}\mathbf{I}_{dxd})\bigg{)}-\sum_{m}\mathbf{p}_{m}\log\left(\sum_{l}\mathbf{p}_{l}\exp\bigg{(}-D_{1}\bigg{(}\mathcal{N}(\mathbf{e}_{m},\sigma^{2}\mathbf{I}_{dxd}),\mathcal{N}(\mathbf{e}_{l},\sigma^{2}\mathbf{I}_{dxd})\bigg{)}\bigg{)}\right)$
$\displaystyle\leq\frac{M}{2}\log\bigg{(}2\pi
e\sigma^{2}\bigg{)}-\sum_{m}\mathbf{p}_{m}\log\bigg{(}\mathbf{p}_{m}+(1-\mathbf{p}_{m})\exp\left(\frac{-\Delta^{2}}{2\sigma^{2}}\right)\bigg{)}.$

Combining the two quantities gives the desired result. ∎