
Analyzing Privacy Leakage in Machine Learning via Multiple Hypothesis Testing: A Lesson From Fano
when the privacy parameter
ϵ
is small enough (Jayaraman &
Evans,2019;Zhu et al.,2019;Carlini et al.,2019;Hannun
et al.,2021). Conceptually, when
ϵ≈0
, the learning algo-
rithm outputs roughly the same distribution of models when
a single training sample
z
is removed/replaced, hence an
adversary cannot accurately infer any private information
about
z
. However, this reasoning does not quantify how
small
ϵ
needs to be to prevent a certain class of privacy
attacks to a certain degree. In practice, this form of se-
mantic guarantee is arguably more meaningful, as it may
inform policy decisions regarding the suitable range of
ϵ
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 an-
swering this question. Yeom et al. (2018) formalized mem-
bership inference attacks by defining a game between the
private learner and an adversary, and showed that the ad-
versary’s advantage—how well the adversary can infer
a particular sample’s membership status—is bounded by
eϵ−1
when the learning algorithm is
ϵ
-DP. This bound
has been tightened significantly in subsequent works (Er-
lingsson 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 algo-
rithm, the adversary’s expected reconstruction error can be
lower bounded using DP, R
´
enyi-DP (Mironov,2017), and
Fisher information leakage (Hannun et al.,2021) privacy ac-
counting. 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 mech-
anisms 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
Dtrain =D ∪ {z}
be
the training set consisting of a public set
D
and a pri-
vate record
z= (x,u)
, where
x
are attributes known to
the adversary and
u
is unknown. Let
M
be the learn-
ing algorithm. We consider a white-box adversary with
full knowledge of the public set
D
and the trained model
h=M(Dtrain)
whose objective is to infer the unknown
attributes
u
. Importantly, we assume that the unknown at-
tribute is discrete (e.g., gender, race, marital status) and
can take on
M
values
u1,...,uM
. For example, the
experiment setting of Carlini et al. (2019) can be stated
as
x= “My social security number is”
and
u∈ {0,1,...,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
p
and setting the unknown
attribute
u=uk
. The private learner
M
then trains a model
h
with
z=zk= (x,uk)
and gives it to the adversary, who
then outputs a guess
ˆ
k
of the underlying index
k
. Note
that both the random index
k
and any randomness in the
learning algorithm
M
are unobserved by the adversary, but
the learning algorithm itself is known.
Success metric. We generalize the advantage met-
ric (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
ˆ
k= arg maxmpm
with success rate
maxmpm
. The prob-
ability of successfully guessing
k
upon observing
h
,i.e.,
P(ˆ
k=k)
, must be at least
maxmpm
in order to mean-
ingfully leverage the private information contained in
h
about
u
. Thus, we define advantage as the (normalized)
difference between
P(ˆ
k=k)
and the baseline success rate
p∗:= maxmpm,i.e.,
Adv := P(ˆ
k=k)−p∗
1−p∗∈[0,1].(1)
Interpretation. Our data reconstruction game has the fol-
lowing important implications for privacy semantics.
1. The private attribute
u
is considered leaked if and only if
it is guessed exactly. This is a direct consequence of defining
adversary success as
ˆ
k=k
. For example, if the attribute
is a person’s age, then guessing
ˆ
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., to allow inexact guesses.
2. The attack game subsumes attribute inference attacks.
This can be done by setting the known attribute
x
accord-
ingly. When
x=∅
, our game corresponds to the scenario
commonly referred to as data reconstruction in existing
literature (Carlini et al.,2019;2021;Balle et al.,2022).
3. Prior information is captured through the sampling prob-
ability
p
.Success rate of the Bayes optimal strategy is
p∗= maxmpm
, which depends on the sampling proba-
bility vector
p
. In the extreme case where
p
is a delta
distribution on some
k∗
, which corresponds to the adver-
sary having perfect knowledge of the private attribute
u
,
the model
h
provides no additional information about
u
.
This is in accordance with the “no free lunch theorem” in
3