Investigating Statistical Privacy Frameworks from the Perspective of Hypothesis Testing

able quantity. Only a limited number of previous works[29, 34, 35] have investigated the question of how to
select a proper value of ǫ, but these approaches either require complicated economic models or lack the
analysis of adversaries with arbitrary auxiliary information (see Section 2.3 for more details). Our work is inspired by the interpretation of differential privacy via
hypothesis testing, initially introduced by Wasserman
and Zhou [27, 30, 60]. However, this interpretation has
not been systematically investigated before in the context of our research objective, i.e., reasoning about the
choice of the privacy parameter ǫ (see Section 2.4 formore details).
We consider hypothesis testing [2, 45, 61] as the tool
used by the adversary to infer sensitive information of
an individual record (e.g., the presence or absence ofa record in the database for unbounded DP) from theoutputs of privacy mechanisms. In particular, we employ
the precision-recall (PR) relation from the perspectiveof hypothesis testing by the adversary as the measurable quantity of interest. The PR relation considers thetrade-off between the precision (the fraction of examples classified as input records that are truly existing in
the input data for unbounded DP) and the recall (thefraction of truly existing input records that are correctly
detected for unbounded DP) from the adversary’s perspective.
With this context of hypothesis testing, we consider three research questions in this work: how do we
set the value of ǫ, how does auxiliary information affect the choice of ǫ, and can hypothesis testing be used
to systematically compare across heterogeneous privacy
frameworks? We introduce our concrete approach to address these questions below.
Investigating Differential Privacy. To explore thechoice of an appropriate value of ǫ, we consider an adversary who tries to infer the existence of a record diin the database D from the output of a differentiallyprivate mechanism A(D). Our threat model is an adversary who uses hypothesis testing with the NeymanPearson criterion [47], which is one of the most powerful
criteria in hypothesis testing, on the noisy query results
obtained by DP mechanisms. We focus on using the
Neyman-Pearson criterion for the Laplace perturbation
mechanism [17] in order to perform a concrete analysis.
We also show how to generalize our approach to othermechanisms such as the Gaussian perturbation mechanism. Particularly, we leverage the PR-relation and thecorresponding Fβscore (the weighted harmonic averageof precision and recall [56]) as effective metrics to quantify the performance of adversaries’ hypothesis testing,234

which can provide a natural and interpretable guideline for selecting proper privacy parameters by systemdesigners and researchers. Furthermore, we extend ouranalysis on unbounded DP to bounded DP and the approximate (ǫ, δ)-DP.
Impact of Auxiliary Information. The conjecturethat auxiliary information can influence the design ofDP mechanisms has been made in prior work [8, 28, 32,
33, 39, 65]. We therefore investigate the adversary’s capability based on hypothesis testing under three types
of auxiliary information: the prior distribution of the input record, the correlation across records, and the correlation across time. Our analysis demonstrates that theauxiliary information indeed influences the appropriate
selection of ǫ. The results suggest that, when possible
and available, the practitioners of DP should explicitly
incorporate adversary’s auxiliary information into theparameter design of their privacy frameworks. Hence,
our results provide a rigorous and systematic answer
to the important question posted by Dwork and Smith[20].
Comparison of Statistical Privacy Frameworks. In
addition to the two primary questions regarding differential privacy, we also extend our hypothesis testing
analysis to a comparative study of a range of state-ofthe-art privacy-preserving frameworks [10, 24, 28, 33,
38, 39]. Some of these frameworks [8, 28, 32, 33, 65] haveconsidered adversaries with auxiliary knowledge in theirdefinitions, but no prior work has applied a common
technique to compare and understand their relationshipamong each other and with differential privacy.
Overall, our work makes the following contributions.
• We investigate differential privacy from the perspective of hypothesis testing by the adversary who observes the differentially private outputs. We comprehensively analyze (i) the unbounded and (ii)bounded scenarios of DP, and (iii) (ǫ, δ)-DP.
• We theoretically derive the PR-relation and the corresponding Fβscore as criteria for selecting the valueof ǫ that would limit (to the desired extent) the adversary’s success in identifying a particular record,in an interpretable and quantitative manner.
• We analyze the effect of three types of auxiliary information, namely, the prior distribution of the input record, the correlation across records, and thecorrelation across time, on the appropriate choice ofǫ via the hypothesis testing by the adversary.
• Furthermore, we systematically compare the stateof-the-art statistical privacy notions from the perspective of the adversary’s hypothesis testing, including Pufferfish privacy [33], Blowfish privacy [28],Investigating Statistical Privacy Frameworks from the Perspective of Hypothesis Testing

dependent differential privacy [39], membershipprivacy [38], inferential privacy [24] and mutualinformation based differential privacy [10].

2 Background and Related WorkIn this section, we briefly discuss the frameworks of differential privacy and hypothesis testing, as well as related works regarding these two topics.

2.1 Differential Privacy
Differential privacy is a rigorous mathematical framework aimed at protecting the privacy of the user’s record
in a statistical database [13–15, 17, 20]. The goal of DP
is to randomize the query results to ensure that therisk to the user’s privacy does not increase substantially(bounded by a function of ǫ) as a result of participatingin the statistical database. The notion of ǫ-differential
privacy is formally defined as follows.
Definition 1. (ǫ-differential privacy [13]) A randomized algorithm A provides ǫ-differential privacy if for
any two neighboring databases D and D′ such that D
and D′ differ by adding/removing a record, and for any(A(D)∈S)
subset of outputs S ⊆ S, maxD,D′ PP(A(D′ )∈S) ≤ exp(ǫ),′
where A(D) (resp. A(D )) is the output of A on input
D (resp. D′ ) and ǫ is the privacy budget.
It is worth noting that the smaller the privacy budget ǫ, the higher the privacy level. This privacy definition is also known as unbounded DP as the databasesize is unknown. When the database size is known, D
and D′ are neighbors if D can be obtained from D′ byreplacing one record in D′ with another record. Definition 1 based on this notion of neighbors is known
as bounded DP [32]. Approximate DP is another variant of DP, also named (ǫ, δ)-DP [16], and is defined as
P (A(D) ∈ S) ≤ P (A(D′ ) ∈ S) exp(ǫ) + δ, which relaxes
DP by ignoring noisy outputs with a certain probability
controlled by the parameter δ. In Section 4, we will analyze mechanisms that satisfy these DP guarantees fromthe adversary’s perspective of hypothesis testing.
The Laplace perturbation mechanism (LPM) [17]is a classic and popular mechanism that achieves ǫ-DP,
which makes use of the concept of global sensitivity.
Definition 2. (Global sensitivity) [17] The global sensitivity of a query Q : D → Rq is the maximum differ-235

ence between the values of the function when one inputchanges, i.e. ∆Q = maxD,D′ kQ(D) − Q(D′ )k1 .
Theorem 1. (Laplace Perturbation Mechanism) [17]For any query Q : D → Rq , the Laplace perturbation
mechanism, denoted by A, and any database D ∈ D ,A(D) = Q(D) + (η1 , . . . , ηq ) achieves ǫ-differential privacy, where ηi are i.i.d random variables drawn fromthe Laplace distribution with a parameter ζ = ∆Q/ǫ,
de

ǫ|z|
ǫ
exp − ∆Q.
noted by Lap(ζ), that is Pr[ηi = z] ∝ 2∆Q

In order to perform a concrete analysis, our work mainly
focuses on the Laplace perturbation mechanism. However, our approach also generalizes to other mechanisms
such as the Gaussian perturbation mechanism (as discussed in Section 4.3).
In the literature, several statistical privacy frameworks have also been proposed as important generalization of DP, such as Pufferfish privacy [33], Blowfish privacy [28], dependent differential privacy [39],membership privacy [38], inferential privacy [24] andmutual-information based differential privacy [10].
These privacy frameworks are important statistical privacy frameworks for releasing aggregate information of
databases while ensuring provable guarantees, similar
to DP. We will systematically compare them with DPfrom the adversary’s perspective of hypothesis testingin Section 6.

2.2 Hypothesis Testing
Hypothesis testing [2, 45, 61] is the use of statistics on
the observed data to determine the probability that agiven hypothesis is true. The common process of hypothesis testing consists of four steps: 1) state the hypotheses; 2) set the criterion for a decision; 3) computethe test statistic; 4) make a decision. The binary hypothesis testing problem1 decides between a null hypothesis
H = h0 and an alternative hypothesis H = h1 based on
observation of a random variable O [2, 45]. Under hypothesis h0 , O follows the probability distribution P0 ,while under h1 , O follows distribution P1 . A decision
rule Ĥ is a criterion that maps every possible observation O = o to either h0 or h1 .
The most popularly used criteria for decision are
maximum likelihood [50], maximum posterior probability [25], minimum cost [43] and the Neyman-Pearson
criterion [47].
1 We consider the binary hypothesis testing problem since theadversary aims to distinguish two neighboring databases in DP.

Investigating Statistical Privacy Frameworks from the Perspective of Hypothesis Testing

Definition 3. The Neyman-Pearson criterion aims tomaximize the true detection rate (the probability of correctly accepting the alternative hypothesis) subject to a
maximum false alarm rate (the probability of mistakenly
accepting the alternative hypothesis) [47, 61], i.e.,max PT D s.t., PF A ≤ α(1)where PT D and PF A denote the true detection rate andthe false alarm rate, respectively.
The Neyman-Pearson criterion has the highest statistical power [37] since it maximizes the true detection
rate under a given requirement of the false alarm rate
(as defined above). According to the Neyman-Pearson
Lemma [46], an efficient way to solve Eq. 1 is to implement the likelihood ratio test [49, 57]. In practice,
the likelihood ratio, or equivalently its logarithm, canbe used directly to construct test statistics to compare
the goodness of fit of the two hypotheses. Other criteriasuch as maximum likelihood [50], maximum posterior
probability [25] and minimum cost [43] cannot guarantee the highest statistical power in general, and they arebased on a fixed threshold on the likelihood ratio thatcannot incorporate α. In contrast, the Neyman-Pearson
criterion treats the testing performance as a functionof the threshold for the likelihood ratio controlled byα ([1], pp. 67). Therefore, the Neyman-Pearson criterion can provide more flexibility to optimize a range ofevaluation metrics by setting different values of α [37].

2.3 Setting the Privacy Budget ǫ
Setting the privacy budget ǫ in DP is a challenging task.
Prior work [29, 34–36] attempted to address this problem, but has several limitations. Hsu et al. [29] proposed
an economic method to express the balance between theaccuracy of a DP release and the strength of privacy
guarantee in terms of a cost function when bad events
happen. However, this work involves complicated economic models consisting of bad events and their corresponding cost functions. It is difficult to quantify thecost of a bad event for general applications. Krehbiel [34]takes each data owner’s privacy preference into consideration and aims to select a proper privacy parameter forachieving a good tradeoff between utility and privacy.
This mechanism focuses more on an economic perspective for collecting and distributing payments under achosen level of privacy parameter and their privacy definition is not the standard DP.

236

Other related works by Lee and Clifton [35, 36] determine ǫ for LPM based on the posterior probability
that the adversary can infer the value of a record. The
Neyman-Pearson criterion adopted in our approach has
an advantage over the maximum posterior probability
analysis [25]. As stated in Section 2.2, the NeymanPearson criterion in our work can be used to optimize arange of evaluation metrics by selecting a proper valueof the false alarm rate while maximizing the true detection rate. In addition, their analysis [35] only assumes
uniform distribution of the input data (equivalent to thescenarios without any prior distribution) in both theirexperiments and theoretical derivations.
Finally, these previous works are noticeably different from our approach as they do not utilize the statistical tool of hypothesis testing (especially the NeymanPearson criterion) by the adversary. Furthermore, ourwork is not limited to the selection of the ǫ value, but isalso extended to the analysis on the impact of the auxiliary information possessed by the adversary and thecomparison across the state-of-the-art statistical privacy
frameworks, which has not been studied before.

2.4 Hypothesis Testing in DP
Previous work in [21, 48, 58] has investigated how to accurately compute the test statistics in hypothesis testing while using DP to protect data. Ding et al. designed an algorithm to detect privacy violations of DP
mechanisms from a hypothesis testing perspective [12].
Wasserman and Zhou [60], Hall et al. [27], and Kairouz
et al. [30] are our inspiration for using hypothesis testing on DP. These works propose a view of DP from theperspective of hypothesis testing by the adversary who
observes the differentially private outputs. Specifically,
the observation is first made by Wasserman and Zhou[60] for bounding the probability for the adversary tocorrectly reject a false hypothesis of the input database.
Hall et al. [27] later extend such analysis to (ǫ, δ)-DP.
Kairouz et al. [30] then apply this concept in their proof
of composition of DP. However, these prior works havenot applied hypothesis testing to our objectives of determining the appropriate value of ǫ.
In contrast, our work extensively analyzes the adversary’s capability of implementing hypothesis testing
using Neyman-Pearson’s criterion [47] on outputs of DP
mechanisms, such as LPM and the Gaussian perturbation mechanism. We apply it to the problem of determining ǫ, the analysis of the effect of auxiliary information on the choice of ǫ, and the comparative analysis

Investigating Statistical Privacy Frameworks from the Perspective of Hypothesis Testing

From Eq. 3, we know that precision is the probability that hypothesis h1 , which the adversary’s hypothesis testing says is true, is indeed true; and recall is theprobability that hypothesis h1 , which is indeed true, isdetected as true by the adversary’s hypothesis testing.
Note that the randomness in the process of computing precision and recall comes from the statistical noise
added in DP mechanisms. Therefore, our analysis aims
to quantify the capability of the adversary that leverages the hypothesis testing technique in identifying any
specific record from DP outputs.
PR-relation quantifies the actual detection accuracyof the adversary, which has a one-to-one correspondencewith the false alarm rate PF A and the missed detection
rate 1 − PT D [30]. Different from Kairouz et al. [30] thatquantifies the relative relationship between PF A and
1 − PT D , we obtain explicit expression of the precisionand recall of the adversary that exploits the NeymanPearson criterion (in Sections 4.1.3, 5.1, 5.2, 5.3). It
is also interesting to note that there exists a one-toone correspondence between PR-relation and the receiver operating characteristic (ROC) [11]. Therefore,
our analysis in the domain of PR-relation can be directly transferred to the domain of ROC.
Furthermore, we theoretically prove that the adversary that implements Neyman-Pearson criterion
achieves the optimal PR-relation (in Theorem 2) andthis optimality is generally applicable for correlated
records (in Corollary 1). The corresponding proofs aredeferred to the appendix.
Theorem 2. The Neyman-Pearson criterion characterizes the optimal adversary that can achieve the best
PR-relation.
Corollary 1. The optimality of Neyman-Pearson criterion given in Theorem 2 holds for correlated records
in the database.
In addition, we leverage Fβscore (weighted harmonic average of precision and recall), to further quantify the
relationship between the adversary’s hypothesis testing
and the privacy parameter ǫ, which also provides aninterpretable guideline to practitioners and researchers
1(forfor selecting ǫ. Fβscore =β2
1(1+β 2 )precision+ (1+β 2 )recall

any real number β > 0) is an example for quantifying
the PR-relation in order to understand the adversary’s
power in a more convenient manner, since it combines
the two metrics, precision and recall, into a single metric. However, this combination has the potential of infor-

238

mation loss of the PR-relation which broadly covers theadversary’s hypothesis testing in the entire space (morediscussions in Section 4.1.4). Note that every step of ouranalysis in Figure 1 is accurate in quantifying the adversary’s hypothesis testing under the Neyman-Pearson
criterion using the metrics of PR-relation and Fβscore .
Generalizing to Other Privacy Mechanisms andPractical Adversaries: We further generalize ouranalysis of the conventional ǫ-DP to its variants such as(ǫ, δ)-DP (adopting the Gaussian perturbation mechanism), more advanced privacy notions, and also adversaries with auxiliary information. Our analysis showsthat the adversary’s auxiliary information in the formof prior distribution of the input database, the correlation across records and time can affect the relationshipbetween the two posterior probabilities (corresponding
to the two hypotheses made by the adversary), thus impacting the proper value of privacy parameter ǫ.

4 Quantification of DP from theAdversary’s Hypothesis Testing
In this section, we theoretically analyze the capabilityof the adversary’s hypothesis testing for inferring sensitive information of a particular record from DP outputs. Specifically, we implement our analysis on the unbounded and bounded scenarios of DP and (ǫ, δ)-DP.

4.1 Quantification of Unbounded DP
4.1.1 Hypothesis Testing Problem
Recall that the Neyman-Pearson criterion [47] aims tomaximize the true detection rate of the hypothesis test
given a constrained false alarm rate (Definition 3). Following our threat model and methodology in Section 3,
the adversary would assume the following two hypotheses, corresponding to the presence or the absence of arecord di :(h0 : di does not exists in D, i.e., D = D′H=(4)
h1 : di exists in D, i.e., D = DThis is clearly the unbounded DP setting (we will analyze the bounded DP setting and other DP variations in
the next subsections.). After observing the noisy query
result A(D) = o, the adversary tries to distinguish thetwo events D = D and D = D′ by analyzing the corresponding posterior probabilities of P (D = D|A(D) =239

Investigating Statistical Privacy Frameworks from the Perspective of Hypothesis Testingo, d−i ) and P (D = D′ |A(D) = o, d−i ). Following theBayes’ rule of
P (D = D|A(D) = o, d−i ) ==P (A(D) = o|d−i , D = D)P (D = D)
P (A(D) = o|d−i )P (A(D) = o)P (D = D),
P (A(D) = o|d−i )(5)

we know that distinguishing the two posterior probabilities is equivalent to differentiating the two conditional
probabilities of P (A(D) = o) and P (A(D′ ) = o),2 foradversaries that have no access to the prior distributionof the input database and thus assume a uniform prior,i.e., P (D = D) = P (D = D′ ).

Under a given requirement of the false alarm rate α,
we can uniquely determine the threshold θ of the noisy
output. Then, we can compute λ from θ. Next, let us
discuss each step of this proof in detail.
Construct Likelihood Ratio Test: Given the noisy
scalar output o = A(D) = Q(D) + Lap(ζ) = Q(D) +Lap(∆Q/ǫ) from the LPM, we can compute the likelihood ratio Λ(o) corresponding to the two hypotheses
defined in Eq. 4 asǫ|o−Q(D)|ǫΛ(o) ==

4.1.2 Decision Rule
Adversary’s Hypothesis Testing for Scalar
Query: We first consider the situation where the query
output is a scalar and then generalize our analysis tovector output. It is worth noting that DP is defined interms of probability measures but likelihood is definedin terms of probability densities. However, we use theminterchangeably in this paper (we can change the probability densities to the probability measures throughquantizing over the query output for instance). Without loss of generality, we assume Q(D) ≥ Q(D′ ). Then,
we have the following theorem.
Theorem 3. Applying Neyman-Pearson criterion of
maximizing the true detection rate under a given requirement of false alarm rate α in Definition 3 is equivalent to the following hypothesis testing which is of asimpler formulation: setting a threshold ∆Q log 2α−+ Q(D′ ),α ∈ [0, 0.5]θ=ǫ ∆Q log 2(1 − α) + Q(D′ ), α ∈ (0.5, 1](6)

P (A(D) = o)=
P (A(D ′ ) = o)2∆Q exp−

ǫ2∆Q exp−
exp(ǫ)

 
exp




∆Q

ǫ|o−Q(D ′ )|∆Q

if o > Q(D)2o − Q(D) − Q(D ′ )ǫ∆Qexp(−ǫ)′

if o ∈ [Q(D ), Q(D)]′if o < Q(D )(7)Assume the decision threshold for the likelihood ratio
is λ, then the corresponding decision rule in Neymanh1

Pearson criterion is Λ(o) ≷ λ.
h0Uniquely Determine θ from α: Under a thresholdθ on the noisy output o, PF A can be computed asR∞
R ∞ ǫ − ǫ|x−Q(D′ )|∆Qdx,
1 − θ P (A(D′ ) = o)do = 1 − θ 2∆Qe(θ−Q(D ′ ))ǫ

(θ−Q(D ′ ))ǫ

which is 1 − 21 e− ∆Q
if θ < Q(D′ ), or 21 e ∆Q
if θ ≥ Q(D′ ). Therefore, for a given requirement of thefalse alarm rate α, we can obtain Eq. 6.

Compute λ from θ: Based on Eq. 7, we know that
(A(D)=o)exp(−ǫ) ≤ Λ(o) = PP(A(D′ )=o) ≤ exp(ǫ). Therefore, it issufficient to choose λ such that exp(−ǫ) ≤ λ ≤ exp(ǫ).
Then, the decision rule becomes e2o−Q(D)−Q(D ′ )
ǫ
∆Q

h1

≷

h0
h1

λ =⇒ o ≷h0′) 4log λ∆Q+ Q(D)+Q(D.
2ǫ2Therefore, thethreshold λ for the likelihood ratio Λ(o) can be computed from the threshold θ for the noisy output o asǫfor the output of LPM-based DP mechanisms A(D) =o, then the decision rule of the adversary’s hypothesis
h1

testing is o ≷ θ.3
h0

Proof. Following the Neyman-Pearson Lemma [46], we
utilize the likelihood ratio test [49, 57] to realize the
Neyman-Pearson criterion. Therefore, we first computethe likelihood ratio Λ(o) of the two hypotheses and set
a threshold λ on this ratio for the adversary’s decision.

λ=e2θ−Q(D)−Q(D ′ )ǫ
∆QBased on the analysis above, we know that there exists a one-to-one correspondence between the false alarm
rate α and the threshold of the noisy output θ. This
uniquely determined θ satisfies the existence and sufficient conditions for achieving Neyman-Pearson Lemma(see Theorem 3.2.1 in [37]). Therefore, the NeymanPearson criterion in our setting is equivalent to making
h1

a decision rule of o ≷ θ by setting a threshold θ to theh0

2 P (A(D) = o) represents the same conditional probability as
P (A(D) = o|D = D).

noisy output o, which is of a simpler formulation.

h0

3 The decision rule is o ≷ θ if Q(D) ≤ Q(D′ ).
h1(8)

4 We consider the natural base for logarithm in this paper.

241

Investigating Statistical Privacy Frameworks from the Perspective of Hypothesis Testing

1

Table 1. The Maximal ǫ under a Required Bound of Fβscore .

1
β=0.5

0.9

ǫ=0.1

0.8

ǫ=0.4
ǫ=0.7

β=0.6

0.8

β=0.8

0.7

β=1

*

0.9

Fβ score

Precision

ǫ=0.01

0.7
ǫ=1

β=1.5

0.6

0.6

ǫ=2
0.5

0.5
0.5
Recall

0

2

4

6

1
2
1
+ (1+β 2β)recall(1+β 2 )precisionǫ < log(1 + β 2 )

0.83

0.9

0.95

1.42

2.04

3

4.29

β = 0.6

—
—
—
—
—

0.33

0.54

0.83

1.45

2.11

3.11

4.43

—
—
—
—

0.49

0.8

1.46

2.16

3.21

4.58

—
—
—

0.71

1.4

2.12

3.2

4.6

—
—

1.17

1.88

2.99

4.41

—

1.61

2.69

4.12

β=2

ure 3(b) are accurate quantification of the adversary’s
hypothesis testing from the perspective of Fβscore , fromwhich we observe that the adversary’s capability of inferring the existence of an individual record is generally
enhanced with an increasing value of ǫ.
Fβscore can be interpreted as a summary statistic for
the PR-relation, which provides a more convenient wayof quantifying the relationship between the adversary’
hypothesis testing and the privacy parameter ǫ. Under a∗desired bound of Fβscorethat the adversary’s hypothesis
testing can achieve, the privacy mechanism practitioners can refer to Eq. 12 and Figure 3(b) to choose anappropriate value of ǫ. Furthermore, we provide numerical bounds of ǫ under different requirements of Fβscore
for commonly-used weights of β ∈ [0.5, 2] in Table 1, as
an easier way to look up for privacy practitioners.
When the summary statistics of the precision andrecall are used (as opposed to using the full PR-relation
information), such as the use of the Fβscore , there ispotential for information loss, especially in the regime
corresponding to smaller values of ǫ (Eq. 12 and Fig∗ure 3(b)). It is interesting to note that Fβscorekeeps
2
the same for ǫ < log(1 + β ), and then monotonicallyincreases with ǫ for ǫ ≥ log(1 + β 2 ). This turning pointǫ = log(1+β 2 ) approaches 0 for smaller values of β, mak∗ing Fβscorecloser to be monotonically increasing with ǫthus capturing the privacy benefits of smaller values ofǫ (as shown Figure 3(b)).
Finally, we emphasize that the alternative approachof using the entire PR-relation to guide the selection of ǫ
does not suffer from the limitations discussed above, andalso shows privacy benefits of using smaller ǫ (smaller
precision for a given recall as shown in Figure 3(a)).

(12)

p

(1 + β 2 )( 1 + 4β 2 eǫ − 1), ǫ ≥ log(1 + β 2 )p(1 + β 2 )

0.76

0.82

β = 1.5(b)

The privacy parameter ǫ can relatively measure the privacy guarantees of DP mechanisms. However, choosing
appropriate values for ǫ is non-trivial since its impact on
the privacy risks of the input data in practice are notwell understood. Our method of choosing ǫ considers
the capability of the adversary’s hypothesis testing to
identify any particular record as being in the database.
Specifically, we provide guidelines for selecting proper
values of ǫ using PR-relation and Fβscore , respectively.
Guidelines under PR-relation: Our analysis byleveraging PR-relation generally covers the adversary’s
trade-offs between precision and recall in the entire
space. Figure 3(a) demonstrates that, with sufficiently
low privacy budget ǫ, an adversary’s ability to identify
an individual record in the database is indeed limited.
Under a given requirement of trade-offs between precision and recall of the adversary’s hypothesis testing, theprivacy mechanism designer can refer to the PR-relation
obtained in Eqs. 9, 10, 11 and Figure 3(a) to choose anappropriate privacy budget ǫ.
Guidelines under Fβscore : Besides the PR-relation,
we also leverage the Fβscore , which is a weighted harmonic average of precision and recall, as another appropriate metric for quantifying the effectiveness of the adversary’s hypothesis testing. Furthermore, we can theoretically derive the highest Fβscore (by selecting a proper
threshold θ) that the adversary can achieve for arbitrary
real number β > 0 as

=

0.67

0.55

β=1

4.1.4 Choosing Proper ǫ 1 + β2 2 + β2 ,

0.62

0.34

β = 0.8

8

Fig. 3. (a) PR-relation and (b) the highest Fβscore of detecting a particular record under unbounded DP.

θ

0.58

0.22

Privacy Budget ǫ

1

(a)

∗
Fβscore
= max

0.55

β=2

ǫ=5
0

Fβscoreβ = 0.5

1 + 4β 2 eǫ − 1 + β 2

and the detailed proof is deferred to the Appendix.
∗
Next, we show Fβscorewith varying privacy parameter ǫ in Figure 3(b). Our results in Eq. 12 and Fig-

4.1.5 Plausible Deniability Property
There are multiple ways to interpret semantics of DP
guarantees such as hypothesis testing [27, 30, 60] andplausible deniability (Page 9 in Dwork [13], Page 2 inDwork and Smith [20], Definition 1 in Dwork, McSherry,Investigating Statistical Privacy Frameworks from the Perspective of Hypothesis Testing

Nissim and Smith [17], Section 2 in Kasiviswanathan
and Smith [31], Section 4 in Li et al. [38]). The potential of randomness providing plausible deniability was
first recognized by Warner [59]. Bindschaedler et al. provide a formal definition of plausible deniability for datasynthesis, compared to which DP is a stronger privacy
guarantee [5].
Definition 4. (Plausible Deniability) [5] For any
database D with |D| > k (|D| is the number of records inD), and any record y generated by a perturbation mechanism M such that y = M(d1 ) for d1 ∈ D, we state that yis releasable with (k, γ)-plausible deniability, if there exist at least k − 1 distinct records d2 , · · · , dk ∈ D \ d1 such
P (M(di )=y)that γ −1 ≤ P(M(dj )=y) ≤ γ for any i, j ∈ {1, 2, · · · , k}.
We interpret DP as hypothesis testing — how wellan adversary in DP can infer the existence of an individual record (unbounded DP) or the exact value ofa record (bounded DP) in binary hypothesis testing
problem involving two neighboring databases (Dwork[13], Dwork, McSherry, Nissim and Smith [17], Kiferand Machanavajjhala [32]). Theorem 3 demonstrates
that the adversary implements the likelihood ratio test
(A(D)=o)Λ(o) = PP(A(D′ )=o) to satisfy the Neyman-Pearson criterion and the decision rule in Eq. 6 is equivalent toh1

Λ(o) ≷ λ. Combining Eq. 6 and Eq. 8, we know that
h0
−ǫ

−ǫ

e
e
λ = 4α2 if α ∈ [0, 0.5], or 4(1−α)2 if α ∈ (0.5, 1]. According to Definition 4, the plausible deniability also quantifies the likelihood ratio between two data (although it
only considers the scenario of privacy-preserving datasynthesis [5]). Therefore, our analysis of using hypothesis testing to guide selection of proper privacy parameters in DP has implicitly incorporated the plausible
deniability of any individual records in the database(controlled by the maximum false alarm rate α in the
Neyman-Person criterion). Furthermore, α determinesa trade-off between the false alarm rate PF A and thetrue detection rate PT D (Definition 3). Therefore, ouranalysis of using PR-relation (which has a one-to-one
correspondence with PF A , PT D ) and Fβscore (summary
statistics of precision and recall) generated by varying
α quantifies the randomness and the plausible deniability [59] [5] of any individual records in the database.

4.2 Quantification of Bounded DP
Bounded DP corresponds to the setting where the neighboring databases differ in one (record’s) value and their242

size is the same. For simplicity, we first discuss a scenario
where the i-th record of the input data di can only takebinary values di1 , di2 . Note that the hypothesis testingby the adversary in the bounded scenario is different
from the unbounded scenario in that the adversary is
no longer aiming to distinguish the absence/presence ofa record, but to estimate the true value of a record.
Thus, the adversary’s hypothesis testing now becomes:H=

h0 : di = di1

h1 : di = di2(13)Comparing Eq. 4 and Eq. 13, we know that the two hypotheses for unbounded and bounded cases are different.
However, according to Theorem 5, their corresponding
P R-relation (and Fβscore ) are the same. This means,the hypothesis testing implemented by the adversary
for bounded DP with binary records is the same as thatfor unbounded DP.
Next, we consider a more general scenario where di
takes multiple values di1 , di2 , · · · , dik . Without loss ofgenerality, we assume Q(di1 ) ≤ Q(di2 ) ≤ · · · ≤ Q(dik ).
Therefore, the distance between any two query results
computed over two different values of di is smaller than
the sensitivity of the query ∆Q = max kQ(dik )−Q(di1 )k.
Since the inserted noise for satisfying DP is calculated
based on ∆Q (i.e., Lap( ∆Qǫ )), we know that the hypothesis testing achieved by the adversary in distinguishing
any two values of di is not worse than distinguishing
di1 and dik . We thus conclude that the best hypothesis
testing of the adversary for the bounded scenario is thesame as that for the unbounded scenario.

4.3 Quantification of (ǫ, δ)-DP
Approximate DP, also named (ǫ, δ)-DP [16] is defined as
P (A(D) ∈ S) ≤ exp(ǫ)P (A(D′ ) ∈ S) + δ for any neighboring databases D, D′ . One of the most popular mechanisms to achieve (ǫ, δ)-DP is the Gaussian perturbation
mechanism, where a Gaussian
noise with zero mean andpstandard variant σ = 2 log(1.25/δ)∆Q/ǫ is added tothe query output [16, 18].
Similar to Section 4.1, we first derive the mechanism
for the adversary’s hypothesis testing that satisfies the
Neyman-Pearson criterion based on the following theorem (detailed proof is deferred to the Appendix).
Theorem 6. Applying Neyman-Pearson criterion in
Definition 3 is equivalent to the following hypothesis
testing which is of a simpler formulation: setting athreshold θ = Φ−1 (1 − α)σ + Q(D′ ) (where α is the max-243

Investigating Statistical Privacy Frameworks from the Perspective of Hypothesis Testing1

0.8

ǫ =0.01ǫ =0.1
ǫ =0.3
ǫ =0.5ǫ =0.7
ǫ =0.9
ǫ =1

0.85
0.8

Precision

Precision

5 Quantification of DP under
Auxiliary Information from theAdversary’s Hypothesis Testing0.9
δ=0.01
δ=0.1
δ=0.2
δ=0.6
δ=0.8
δ=0.9
δ=1

0.9

0.7

0.75
0.7
0.65
0.6

0.6
0.55
0.5

0.5
0

0.2

0.4
0.6
Recall

0.8

1

0

0.2

(a)

0.4
0.6
Recall0.8

1

We now demonstrate how to control the adversary’s success rate in identifying of a particular record with several
important variations of the adversary’s belief including
the input data’s prior distribution, record correlationand temporal correlation.

(b)

Fig. 4. PR-relation of detecting a particular record from(ǫ, δ)-DP results with varying (a) ǫ and (b) δ, respectively.

imum PF A and Φ(·) is the cumulative distribution function of the standard normal distribution) for the outputof the Gaussian perturbation mechanism o, the decisionh1

for the adversary’s hypothesis testing is o ≷ θ.

5.1 Quantification of DP under Prior
Distributionh0

According to Theorem 6 and Eq. 11, we can theoretically derive precision and recall of the adversary’s hypothesis testing for the Gaussian mechanism asθ−Q(D)
precision =

1−Φ

2−Φ

θ−Q(D)σθ − Q(D)recall = 1 − Φ
σ



σ



−Φ

θ−Q(D ′ )
σ





(14)

We further show the corresponding PR-relation of theadversary’s hypothesis testing in Figure 4(a) and Figure 4(b) with varying ǫ and δ, respectively. We observethat the adversary’s performance of hypothesis testingis enhanced with an increasing value of ǫ and δ. Comparing Figure 3(a) and Figure 4, we know that different
mechanisms vary in their power of defending against
adversaries’ hypothesis testing since their output distributions are different. Note that our approach can begenerally applied to any DP mechanism (Figure 1), although we focus on LPM and GPM.
Next, the highest Fβscore of the adversary’s hypothesis testing under different values of privacy parametersǫ, δ can be directly derived from Eq. 14 asθ−Q(D)∗
Fβscore= max
θ(1 + β 2 ) 1 − Φθ−Q(D)
2 + β2 − Φ
σ



σ

−Φ

θ−Q(D ′ )
σ



(15)

Balle and Wang [4] developed the analytic Gaussianmechanism whose variance is calibrated using the Gaussian cumulative density function instead of a tail boundapproximation. Other recent works also proposed tightlower bounds for the variance of the added Gaussian
noise while satisfying (ǫ, δ)-DP [23, 51]. How to adapt
our analysis for the classical Gaussian mechanism inTheorem 6 and Eqs. 14, 15 to these improved Gaussianmechanisms [4, 23, 51] is an interesting future direction.

Let us first consider an adversary with known prior distribution of the input data. Although such an adversary
is not explicitly considered in conventional DP frameworks5 , we still analyze this adversary’s inference forsensitive information in a particular record as an interesting and practical case study. In some scenarios, theadversary’s prior is non-uniform, which will result in adifferent decision rule. Similar to our analysis in Section 4.2, we still consider a binary hypothesis testing
problem where the adversary aims to distinguish thetwo neighboring databases in Eq. 13.
Next, we quantify the hypothesis testing of the adversary to distinguish the two posterior distributionsof P (di = di1 |A(D) = o, d−i ), P (di = di2 |A(D) =o, d−i ). According to Bayes’ rule, we have P (di =P (A(D)=o|d−i ,di =di1 )P (di =di1 )=di1 |A(D) = o, d−i ) =P (A(D)=o|d−i )P (A(D)=o)P (di =di1 ). Then, we get
P (A(D)=o|d−i )P (di = di1 |A(D) = o, d−i )P (A(D) = o)P (di = di1 )=P (d = di2 |A(D) = o, d−i )P (A(D ′ ) = o)P (di = di2 )(16)

Based on Eq. 16, we know that the adversary’s hypothesis testing under prior distribution is equivalent
to distinguishing the two probabilities of P (A(D) =o)P (di = di1 ) and P (A(D′ ) = o)P (di = di2 ). Figure 5(a)shows the hypothesis testing procedure of the adversary,
where θ is the decision threshold on the noisy querydi1

outputs and the adversary’s decision rule is o ≷ θ. We
di2further define the coefficient of prior distribution ρp as
P (di =di1 )ρp = 1 − mindi1 ,di2 P(di =di2 ) , where ρp ∈ [0, 1]. ρp = 0
corresponds to the scenario where the adversary has noknowledge about the prior distribution and thus makes
the assumption of uniform distribution (the same as in
Section 4.1). Combining Eq. 11 with Eq. 16, we can de5 DP guarantees are not influenced by the prior distribution of
the input data.

Investigating Statistical Privacy Frameworks from the Perspective of Hypothesis Testinging always reduces entropy (uncertainty) in information
theory [9]. Therefore, choosing a proper privacy budget ǫ needs more careful consideration when designingprivacy-preserving mechanisms against adversaries who
have access to these auxiliary information.

1
0.95

F1*score

0.9
0.85

ρ =0, ρ =0, ρ =0pct

ρ =0, ρ =0.1, ρ =0

0.8

p

c

t

ρ =0, ρ =0.1, ρ =0.2
p

0.75

c

t

ρ =0.5, ρ =0, ρ =0pct

ρ =0.5, ρ =0.1, ρ =0
p

0.7

t

ρ =0.5, ρ =0.1, ρ =0.2
p

0.65

c

0

2

c

4
6
Privacy Budget ǫ

t

8

246

10

Fig. 8. The highest Fβscore achieved by the adversary under
different auxiliary information (setting β = 1, i.e., F 1score ).

5.3.1 Relating PR-relation to DP Guarantees
recall for this adversary’s hypothesis testing as
t RSR
Pi1
precision = t
t GSR
Pi1 RSR + Pi2=

1
1 + (1 − ρp − (2 − ρp )(ρc + ρt (1 − ρc ))) GSR
RSR,

recall = RSR.
(23)
Pt
Eq. 23 holds since max Pi1
t
i2
1
1
(1+
)(1−ρ
)(1−ρ
)
c
t
1−ρp
1−ρp

t
Pi1
max 1−Pti1=== (2−ρp )(1−ρ1c )(1−ρt )−1 =1
1(1+ 1−ρ
)(1−ρc )(1−ρt )1− 1−ρpp
11−ρp −(2−ρp )(ρc +ρt (1−ρc )) . From Eq. 23, we know thatprecision is increased under the same level of recall
when the adversary has access to the temporal correlation of the input data, resulting in a better P R-relationcompared to the static scenario. We show the enhanced
PR-relation in Figure 7(b) by setting ρp = 0.2, ρc =0.1, ρt = 0.1 for example. Furthermore, we theoreticallycompute the highest Fβscore under given values of privacy budget ǫ, coefficient of prior distribution ρp , coefficient of record correlation ρc and coefficient of temporalcorrelation ρt as∗

Fβscore


1+β

,

 2 + β − ρ − (2 − ρ )(ρ + ρ (1 − ρ ))p=
(1 + β )(
− 1)
1+

,

p

−1+β
(1 + β )
1+
2

2

p

2

2

p

c

t

4β 2 eǫ
1−ρp −(2−ρp )(ρc +ρt (1−ρc ))4β 2 eǫ
1−ρp −(2−ρp )(ρc +ρt (1−ρc ))ǫ < ǫ(ρp , ρc , ρt )cǫ ≥ ǫ(ρp , ρc , ρt )

2

(24)
2

where ǫ(ρp , ρc , ρt ) = log(1 + 1−ρp −(2−ρp β)(ρc +ρt (1−ρc )) )and the corresponding proof is deferred to the Appendix. From Eq. 24, we know that the temporal correlation can benefit the adversary’s hypothesis testing∗to achieve an enhanced Fβscore. Therefore, the correlation of the input data across time should be consideredin selecting appropriate privacy parameters of privacy
preserving mechanisms.
Summary for the Quantification of DP under
Auxiliary Information: Figure 8 shows the highest
Fβscore (setting β = 1) varying with ǫ under different
auxiliary information. We can observe that the adversary can infer more information of the input data withmore auxiliary information (higher values of ρp , ρc , ρt ).
This property can also be explained by using condition-

Since the computation of PR-relation involves a specific adversary model, the connection between the PRrelation and privacy guarantees (DP) depend on whatassumptions we make for the adversaries.
Optimal Adversary: considering an optimal adversary that implements the Neyman-Pearson criterion
and with full access to the possible auxiliary information of the data, under a specific mechanism, the PRrelation achieved by the adversary would be fixed (since
every step of our analysis in Figure 1 is exact) as shownin Eqs. 9, 10, 11 for Laplacian mechanism, Eq. 14 forGaussian mechanism, and Eqs. 17, 20, 23 under auxiliary information. For a given PR-relation that follows
this fixed pattern (named as P Roptimal ), we thus can infer the values of privacy parameters in DP guarantees bycomputing them directly from the corresponding equations (Eqs. 9, 10, 11, 14, 17, 20, 23) of PR-relation or
the corresponding Figures 3(a), 4, 5(b), 6(b), 7(b).
Realistic Adversary: considering a realistic adversary that may not have access to the full auxiliary
information, the PR-relation (named as P Rrealistic )may be different. Nevertheless, we can still obtain alower bound for the corresponding privacy parameters,by finding a lower bound of P Rrealistic , denoted as
P RoptimalLow , within all possible P Roptimal relations(corresponding to different privacy parameters). Since
the best PR-relation achieved by the optimal adversary
under this mechanism should be better than P Rrealistic ,we know that the values of privacy parameters corresponding to the given P Rrealistic should be larger
than the privacy parameters corresponding to the lowerbound optimal PR-relation P RoptimalLow .

6 Quantification of Other Privacy
Notions from the Adversary’s
Hypothesis Testing
In this section, we systematically compare several existing statistical privacy frameworks from the perspective

Investigating Statistical Privacy Frameworks from the Perspective of Hypothesis Testing

PR-relation that can be achieved by the adversary. A
privacy notion with a smaller ǫ in Theorem 7 is weakerin restricting an adversary’s capability of performing hypothesis testing to infer an individual record. Combining
the qualitative analysis in Section 6.1 and the quantitative comparison shown in Theorem 7, we know that under the same level of PR-relation, a larger value of ǫ canbe selected for a privacy notion with less restrictions in
the definition of neighboring databases. Based on Theorem 7, we further compare these privacy notions under
two special data distributions: 1) independent records
and 2) independent and uniform records, as shown in
the following propositions.
Proposition 1. Privacy Comparison under Independent Records: If the individual records in the
database are independent of each other, we haveǫBP (ht) = ǫDDP (ht) = ǫIP (ht) = ǫDP (ht)ǫDDP (ht) ≤ 2ǫM P (ht)ǫM IDP (ht) ≤ ǫM P (ht)Proposition 2. Privacy Comparison under Independent and Uniform Records: If the individual
records in the database are independent of each other,and each record is uniformly distributed, we haveǫBP (ht) = ǫDDP (ht) = ǫIP (ht) = ǫDP (ht)ǫDDP (ht) ≤ 2ǫM P (ht)ǫM IDP (ht) ≤ ǫM P (ht)

7 Discussions, Limitations andFuture Works
Differential privacy provides a stability condition to theperturbation mechanism towards changes to the input,
and there are ways to interpret its semantic privacy
guarantee, such as hypothesis testing [27, 30, 60] andplausible deniability [59][5]. In our work, we focus onleveraging hypothesis testing to provide a privacy interpretation for DP mechanisms, which has implicitly
taken the plausible deniability of any individual records
in the database into consideration (recall Section 3).
Our analysis focuses on the popular LPM-based DP
mechanisms, based on which we illustrate how hypothesis testing can be used for the selection of privacy parameters. We have shown the generality of our approachby applying it to the Gaussian perturbation mechanism
in Section 4.3. Investigating how to generalize our analysis to a broader range of privacy mechanisms and met-

248

rics such as the exponential mechanism, randomized response, local DP and geo-indistinguishability [3] could
be interesting future directions.
In our work, we consider the adversary who aims
to infer the presence/absence of any particular record(for unbounded DP) or the true value of a record (forbounded DP), which is the standard adversary considered in DP framework. In practice, the adversary may
be more interested in some aggregate statistics of therecord, for instance, whether the value of the record diis higher than a given value γ. Under this scenario, thetwo hypotheses of the adversary can be constructed as
h0 : di > γ, h1 : di ≤ γ and then similar analysis in
Sections 4, 5 can be conducted for implementing hypothesis testing. We will study the hypothesis testing ofthese adversaries in the future.
Our analysis considers adversaries with accurate
auxiliary information of the prior distribution and correlation across records/time of the input database. In
practice, it can be challenging for defenders to have an
accurate estimate of the adversary’s auxiliary information. Therefore, investigating the capability of adversary’s hypothesis testing with approximate auxiliary information could be another interesting future work.
Motivated by composition properties of DP [22, 30,41], it is interesting to investigate the composability of
our analysis across different privacy mechanisms andexplore tighter composition properties under specificmechanisms similar to [30] in the future.

8 Conclusion
In this paper, we investigate the state-of-the-art statistical privacy frameworks (focusing on DP) from the perspective of hypothesis testing of the adversary. We rigorously analyze the capability of an adversary for inferringa particular record of the input data using hypothesis
testing. Our analysis provides a useful and interpretableguideline for how to select the privacy parameter ǫ inDP, which is an important question for practitioners andresearchers in the community. Our findings show thatan adversary’s auxiliary information – in the form ofprior distribution of the database, and correlation acrossrecords and time – indeed influences the proper choiceof ǫ. Finally, our work systematically compares several
state-of-the-art privacy notions from the perspective ofadversary’s hypothesis testing and showcases their relationship with each other and with DP.

Investigating Statistical Privacy Frameworks from the Perspective of Hypothesis Testing

9 Acknowledgement
The authors would like to thank Esfandiar Mohammadi
for shepherding the paper, the anonymous reviewers fortheir valuable feedback. This work is supported in partby the National Science Foundation (NSF) under the
grant CNS-1553437 and CCF-1617286, an Army Research Office YIP Award, and faculty research awards
from Google, Cisco, Intel, and IBM. This work is also
partly sponsored by the U.S. Army Research Laboratory and the U.K. Ministry of Defence under Agreement Number W911NF-16-3-0001. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing theofficial policies, either expressed or implied, of the U.S.
Army Research Laboratory, the U.S. Government, theU.K. Ministry of Defence or the U.K. Government. The
U.S. and U.K. Governments are authorized to reproduce and distribute reprints for Government purposes
notwithstanding any copyright notation hereon.

References
[1]
[2]

[3]

[4]

[5]

[6]

[7]

Detection, decision, and hypothesis testing.
http://web.mit.edu/gallager/www/papers/chap3.pdf.
David R Anderson, Kenneth P Burnham, and William L
Thompson. Null hypothesis testing: problems, prevalence,
and an alternative. The journal of wildlife management,
pages 912–923, 2000.
Miguel E Andrés, Nicolás E Bordenabe, Konstantinos Chatzikokolakis, and Catuscia Palamidessi. Geoindistinguishability: Differential privacy for location-based
systems. In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, pages
901–914. ACM, 2013.
Borja Balle and Yu-Xiang Wang. Improving the gaussianmechanism for differential privacy: Analytical calibration andoptimal denoising. In International Conference on Machine
Learning (ICML), 2018.
Vincent Bindschaedler, Reza Shokri, and Carl A Gunter.
Plausible deniability for privacy-preserving data synthesis. Proceedings of the VLDB Endowment, 10(5):481–492,
2017.
Yang Cao, Masatoshi Yoshikawa, Yonghui Xiao, and
Li Xiong. Quantifying differential privacy under temporalcorrelations. In Data Engineering (ICDE), 2017 IEEE 33rd
International Conference on, pages 821–832. IEEE, 2017.
Thee Chanyaswad, Alex Dytso, H Vincent Poor, and Prateek
Mittal. Mvg mechanism: Differential privacy under matrixvalued query. In Proceedings of the 25nd ACM SIGSAC
Conference on Computer and Communications Security.
ACM, 2018.

[8]

249

Rui Chen, Benjamin C Fung, Philip S Yu, and Bipin C Desai. Correlated network data publication via differential
privacy. volume 23, pages 653–676. Springer-Verlag New
York, Inc., 2014.
[9] Thomas M Cover and Joy A Thomas. Elements of information theory. John Wiley & Sons, 2012.
[10] 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. ACM, 2016.
[11] Jesse Davis and Mark Goadrich. The relationship between
precision-recall and roc curves. In Proceedings of the 23rd
international conference on Machine learning, pages 233–
240. ACM, 2006.
[12] Zeyu Ding, Yuxin Wang, Guanhong Wang, Danfeng Zhang,and Daniel Kifer. Detecting violations of differential privacy.
In Proceedings of the 2018 ACM SIGSAC Conference on
Computer and Communications Security, pages 475–489.
ACM, 2018.
[13] Cynthia Dwork. Differential privacy. In Automata, languages
and programming. 2006.
[14] Cynthia Dwork. Differential privacy: A survey of results. In
Theory and Applications of Models of Computation. 2008.
[15] Cynthia Dwork. A firm foundation for private data analysis.
Communications of the ACM, 2011.
[16] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry,
Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy
via distributed noise generation. In Annual International
Conference on the Theory and Applications of Cryptographic
Techniques, pages 486–503. Springer, 2006.
[17] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam
Smith. Calibrating noise to sensitivity in private data analysis. In Springer Theory of cryptography. 2006.
[18] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends® in
Theoretical Computer Science, 9(3–4):211–407, 2014.
[19] Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. arXiv preprint arXiv:1603.01887, 2016.
[20] Cynthia Dwork and Adam Smith. Differential privacy forstatistics: What we know and what we want to learn. Journal of Privacy and Confidentiality, 2010.
[21] Marco Gaboardi, Hyun-Woo Lim, Ryan M Rogers, andSalil P Vadhan. Differentially private chi-squared hypothesis testing: Goodness of fit and independence testing. In
ICML’16 Proceedings of the 33rd International Conferenceon International Conference on Machine Learning-Volume
48. JMLR, 2016.
[22] Srivatsava Ranjit Ganta, Shiva Prasad Kasiviswanathan, andAdam Smith. Composition attacks and auxiliary informationin data privacy. In Proceedings of the 14th ACM SIGKDD
international conference on Knowledge discovery and data
mining, pages 265–273. ACM, 2008.
[23] Quan Geng, Wei Ding, Ruiqi Guo, and Sanjiv Kumar. Optimal Noise-Adding Mechanism in Additive Differential Privacy. In Proceedings of the 22th International Conference on
Artificial Intelligence and Statistics (AISTATS), 2019.
[24] Arpita Ghosh and Robert Kleinberg. Inferential privacy guarantees for differentially private mechanisms. arXiv preprint
arXiv:1603.01508, 2016.

Investigating Statistical Privacy Frameworks from the Perspective of Hypothesis Testing[25] Dorothy M Greig, Bruce T Porteous, and Allan H Seheult.
Exact maximum a posteriori estimation for binary images.
Journal of the Royal Statistical Society. Series B (Methodological), pages 271–279, 1989.
[26] Andreas Haeberlen, Benjamin C Pierce, and Arjun Narayan.
Differential privacy under fire. In USENIX Security Symposium, 2011.
[27] Rob Hall, Alessandro Rinaldo, and Larry Wasserman. Differential privacy for functions and functional data. Journal of
Machine Learning Research, 14(Feb):703–727, 2013.
[28] Xi He, Ashwin Machanavajjhala, and Bolin Ding. Blowfish
privacy: Tuning privacy-utility trade-offs using policies. In
Proceedings of the 2014 ACM SIGMOD international conference on Management of data, pages 1447–1458. ACM,
2014.
[29] Justin Hsu, Marco Gaboardi, Andreas Haeberlen, Sanjeev
Khanna, Arjun Narayan, Benjamin C Pierce, and Aaron
Roth. Differential privacy: An economic method for choosing
epsilon. In Computer Security Foundations Symposium(CSF), 2014 IEEE 27th, pages 398–410. IEEE, 2014.
[30] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The
composition theorem for differential privacy. IEEE Transactions on Information Theory, 63(6):4037–4049, 2017.
[31] Shiva P Kasiviswanathan and Adam Smith. On
the’semantics’ of differential privacy: A bayesian formulation. Journal of Privacy and Confidentiality, 6(1), 2014.
[32] Daniel Kifer and Ashwin Machanavajjhala. No free lunchin data privacy. In Proceedings of the 2011 ACM SIGMODInternational Conference on Management of data, pages
193–204. ACM, 2011.
[33] Daniel Kifer and Ashwin Machanavajjhala. A rigorous andcustomizable framework for privacy. In Proceedings of the
31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems, pages 77–88. ACM, 2012.
[34] Sara Krehbiel. Markets for database privacy. 2014.
[35] Jaewoo Lee and Chris Clifton. How much is enough? choosing ε for differential privacy. In International Conference on
Information Security, pages 325–340. Springer, 2011.
[36] Jaewoo Lee and Chris Clifton. Differential identifiability.
In Proceedings of the 18th ACM SIGKDD international
conference on Knowledge discovery and data mining, pages
1041–1049. ACM, 2012.
[37] Erich L Lehmann and Joseph P Romano. Testing statistical
hypotheses. Springer Science & Business Media, 2006.
[38] Ninghui Li, Wahbeh Qardaji, Dong Su, Yi Wu, and Weining
Yang. Membership privacy: a unifying framework for privacy definitions. In Proceedings of the 2013 ACM SIGSAC
conference on Computer & communications security, pages
889–900. ACM, 2013.
[39] Changchang Liu, Supriyo Chakraborty, and Prateek Mittal.
Dependence makes you vulnerable: Differential privacy under
dependent tuples. In The Network and Distributed System
Security Symposium (NDSS), 2016.
[40] Ashwin Machanavajjhala, Xi He, and Michael Hay. Differential privacy in the wild: A tutorial on current practices &open challenges. In Proceedings of the 2017 ACM International Conference on Management of Data, pages 1727–
1730. ACM, 2017.
[41] Frank D McSherry. Privacy integrated queries: an extensible
platform for privacy-preserving data analysis. In Proceedings

250of the 2009 ACM SIGMOD International Conference on
Management of data, pages 19–30. ACM, 2009.
[42] Sebastian Meiser and Esfandiar Mohammadi. Tight onbudget?: Tight bounds for r-fold approximate differential privacy. In Proceedings of the 2018 ACM SIGSAC Conference
on Computer and Communications Security, pages 247–264.
ACM, 2018.
[43] Deepak K Merchant and George L Nemhauser. Optimality
conditions for a dynamic traffic assignment model. Transportation Science, 12(3):200–207, 1978.
[44] Ilya Mironov. Renyi differential privacy. In Computer Security Foundations Symposium (CSF), 2017 IEEE 30th, pages
263–275. IEEE, 2017.
[45] Whitney K Newey and Daniel McFadden. Large sample estimation and hypothesis testing. Handbook of econometrics,
4:2111–2245, 1994.
[46] J Neyman and ES Pearson. On the problem of the mostefficient tests of statistical hypotheses. Phil. Trans. R. Soc.
Lond, pages 289–337, 1933.
[47] Jerzy Neyman and Egon S Pearson. On the use and interpretation of certain test criteria for purposes of statisticalinference: Part i. Biometrika, pages 175–240, 1928.
[48] Ryan Rogers, Aaron Roth, Adam Smith, and Om Thakkar.
Max-information, differential privacy, and post-selection
hypothesis testing. arXiv preprint arXiv:1604.03924, 2016.
[49] Albert Satorra and Willem E Saris. Power of the likelihood
ratio test in covariance structure analysis. Psychometrika,
50(1):83–90, 1985.
[50] Lawrence A Shepp and Yehuda Vardi. Maximum likelihood
reconstruction for emission tomography. IEEE transactions
on medical imaging, 1(2):113–122, 1982.
[51] David Sommer, Sebastian Meiser, and Esfandiar Mohammadi. Privacy loss classes: The central limit theorem in
differential privacy. Proceedings on privacy enhancing technologies, 2019.
[52] Shuang Song, Yizhen Wang, and Kamalika Chaudhuri.
Pufferfish privacy mechanisms for correlated data. In Proceedings of the 2017 ACM International Conference on
Management of Data, pages 1291–1306. ACM, 2017.
[53] Jun Tang, Aleksandra Korolova, Xiaolong Bai, Xueqiang
Wang, and Xiaofeng Wang. Privacy loss in apple’s implementation of differential privacy on macos 10.12. arXiv
preprint arXiv:1709.02753, 2017.
[54] Michael Carl Tschantz, Shayak Sen, and Anupam Datta.
Differential privacy as a causal property. arXiv preprint
arXiv:1710.05899, 2017.
[55] Yiannis Tsiounis and Moti Yung. On the security of elgamal
based encryption. In International Workshop on Public Key
Cryptography, pages 117–134. Springer, 1998.
[56] Cornelis Joost van Rijsbergen. Information retrieval. In
Butterworth-Heinemann Newton, MA, USA, 1979.
[57] Quang H Vuong. Likelihood ratio tests for model selection
and non-nested hypotheses. Econometrica: Journal of the
Econometric Society, pages 307–333, 1989.
[58] Yue Wang, Jaewoo Lee, and Daniel Kifer. Differentiallyprivate hypothesis testing, revisited. ArXiv e-prints, 2015.
[59] Stanley L Warner. Randomized response: A survey techniquefor eliminating evasive answer bias. Journal of the American
Statistical Association, 60(309):63–69, 1965.

251

Investigating Statistical Privacy Frameworks from the Perspective of Hypothesis Testing[60] Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):375–389, 2010.
[61] Rand R Wilcox. Introduction to robust estimation and hypothesis testing. Academic press, 2011.
[62] Xiaotong Wu, Taotao Wu, Maqbool Khan, Qiang Ni, andWanchun Dou. Game theory based correlated privacy preserving analysis in big data. IEEE Transactions on Big Data,
2017.
[63] Yonghui Xiao and Li Xiong. Protecting locations with differential privacy under temporal correlations. In Proceedingsof the 22nd ACM SIGSAC Conference on Computer andCommunications Security, pages 1298–1309. ACM, 2015.
[64] Bin Yang, Issei Sato, and Hiroshi Nakagawa. Bayesian differential privacy on correlated data. In Proceedings of the 2015
ACM SIGMOD international conference on Management of
Data, pages 747–762. ACM, 2015.
[65] Tianqing Zhu, Ping Xiong, Gang Li, and Wanlei Zhou. Correlated differential privacy: Hiding information in non-iid
dataset. Information Forensics and Security, IEEE Transactions on, 2013.

10 Appendix
10.1 Proof for Theorem 2
Proof. Achieve the minimal PF A under a given
level of PT D : For a given false alarm rate PF A , themaximal true detection rate PT D can be achieved according to the Neyman-Pearson criterion (Definition 3).
Furthermore, note that the maximal PT D is not decreasing with the increasing of PF A . Thus, under a given levelof the true detection rate PT D = P (D̂ = D|D = D) =P (D̂ = D, D = D)/P (D = D), the adversary implementing the Neyman-Pearson criterion can achieve theminimal false alarm rate PF A = P (D̂ = D|D = D′ ) =P (D̂ = D, D = D′ )/P (D = D′ ). As a direct result of
this, we obtain a minimal P (D̂ = D, D = D′ ) under afixed P (D̂ = D, D = D).
Achieve the maximal precision under a given
level of recall: Since both PT D and recall correspondto P (D̂ = D|D = D), we know that a given level ofrecall is equivalent to the same level of PT D . Therefore,
under a given level of recall (i.e., PT D ), the precision
can be computed as P (D = D|D̂ = D) = P (D̂ = D, D =D)/ P (D̂ = D, D = D) + P (D̂ = D, D = D′ ) , which is
maximized under the Neyman-Pearson criterion (witha minimal P (D̂ = D, D = D′ ) under a fixed P (D̂ =D, D = D)).
Therefore, the Neyman-Pearson criterion canachieve the maximal precision under any given level ofrecall, thus characterizing the optimal adversary that
can achieve the best PR-relation.

10.2 Proof for Corollary 1
Proof. This optimality is generally applicable for adversaries implementing the Neyman-Pearson criterion,
under any distribution of the input data. This is because the proof in Theorem 2 demonstrates the inherent relationship among these quantification metrics (i.e.,the maximization of PT D under a given level of PF A is
equivalent to maximizing precision under a given level ofrecall), regardless of the distribution of the data. Therefore, the optimality of Neyman-Pearson criterion (maximizing PT D under a given level of PF A ) to achieve thebest PR-relation holds for correlated records. where thecorrelation relationships are naturally incorporated in
the likelihood ratio detection process of the NeymanPearson criterion.

∗
for Unbounded DP
10.3 Fβscore

According to the definition of Fβscore , we knowthat maximizing Fβscore is equivalent to minimizing
GSR+β 2RSR

1since Fβscore =

1+β 2
2 .
1+ GSR+βRSR21+ (1+β 2β)recall(1+β 2 )precision
2

GSR+β
RSR

Then, we define f ==and ana-lyze f by considering three different intervals of θ in(−∞, Q(D′ )], (Q(D′ ), Q(D)), [Q(D), +∞), respectively.
1) For the first interval of (−∞, Q(D′ )], we havef = GSR+βRSR2

θ−Q(D ′ )ǫ∆Q2

= 1+β −0.5e
θ−Q(D)∆Q

1−0.5eǫ. Then, we take thederivative of f with respect to θ as0.5ǫ

− ∆Q e
∂f
=
∂θ

+

0.5ǫ
e
∆Q

θ−Q(D ′ )ǫ∆Q

(1 − 0.5e(1 − 0.5e

θ−Q(D)ǫ∆Q

θ−Q(D)ǫ∆Q=

θ−Q(D ′ )
ǫ
∆Q

)

)2

(1 + β 2 − 0.5e

(1 − 0.5e

0.5ǫ
e
∆Q

θ−Q(D)ǫ∆Q

θ−Q(D)ǫ∆Q

θ−Q(D ′ )
ǫ
∆Q

)

(26)

)2

((1 + β 2 )e−ǫ − 1)

(1 − 0.5e

θ−Q(D)ǫ∆Q)2

Therefore, we have ∂f∂θ θ=Q(D ′ ) > 0, i.e., the function
f increases monotonically with θ ∈ (−∞, Q(D′ )], if ǫ <log(1 + β 2 ). Otherwise, it decreases monotonically.
2) For the second interval of (Q(D′ ), Q(D)), we have−θ−Q(D ′ )

ǫ

2
∆Q
+β 2
= 0.5e. We then compute thef = GSR+βθ−Q(D)RSRǫ
1−0.5e ∆Q

252

Investigating Statistical Privacy Frameworks from the Perspective of Hypothesis Testingin Eq. 4 asderivative of f with respect to θ as
0.5ǫ −− ∆Q e
∂f
=
∂θ

+

0.5ǫ
e
∆Q

θ−Q(D ′ )ǫ∆Q

(1 − 0.5e

θ−Q(D)ǫ∆Q

θ−Q(D)
ǫ
∆Q

−

(0.5e

(1 − 0.5e=(1 − 0.5e−
0.5ǫ −ǫ(e − e∆Q

θ−Q(D ′ )∆Qǫ)Λ(o) =)2

θ−Q(D ′ )ǫ∆Qθ−Q(D)
ǫ∆Q(1 − 0.5e

θ−Q(D)
ǫ
∆Q

=

+ β2)

(27)

)2

+ β2e

θ−Q(D)ǫ∆Q

θ−Q(D)
ǫ∆Q>

0. When θ

=

)

)2

Q(D′ ), we have∂f0.5ǫ2 −ǫ − 1). Therefore, we know∂θ θ=Q(D ′ ) = ∆Q ((1 + β )ethat ∂f∂θ θ=Q(D ′ ) > 0. i.e., the function f increases monotonically with ǫ ∈ [Q(D′ ), Q(D)], if ǫ < log(1 + β 2 ).

Otherwise, it decreases and then increases thus there isa mininum within this interval. To solve for this minθ−Q(D ′ )− ∆Q ǫ
+inum, we set the derivative to 0, i.e., e−ǫ − e√
θ−Q(D)−1+

1+4β 2 eǫ+
β 2 e ∆Q ǫ = 0 to obtain θ = ∆Q
ǫ log
2β 2
Q(D′ ). The corresponding minimum value
forF
βscore√(1+β 2 )(1+4β 2 eǫ −can be computed as

1+4β 2 eǫ )(1+β 2 )(1+4β 2 eǫ )−(1−β 2 )√1+4β 2 eǫ.

3) For the third interval [Q(D), +∞), we have f =−(θ−Q(D ′ )ǫ)2∆Q
GSR+β 2
= 0.5e −(θ−Q(D)ǫ)+β . We then take the derivaRSR∆Q
0.5e

tive of f with respect to θ as2−

θ−Q(D ′ )ǫ −θ−Q(D)∆Q∆Qe− 0.25ǫe∂f∆Q=
θ−Q(D)∂θ− ∆Q ǫ 2
)
(0.5e

+

0.5ǫ −e∆Q

θ−Q(D)
ǫ
∆Q

−

(0.5e

θ−Q(D)− ∆Q ǫ

(0.5e=

0.5β 2 ǫ −
e
∆Q
−

(0.5e

ǫ

θ−Q(D ′ )
ǫ
∆Q

+ β2)

(28)

)2

θ−Q(D)ǫ∆Q

θ−Q(D)
ǫ
∆Q

√

1
exp
2 log(1.25/δ)∆Q/ǫ

√

1
exp
2 log(1.25/δ)∆Q/ǫ= exp

0.5ǫ −ǫ−
When θ = Q(D), we have ∂f∂θ θ=Q(D) = ∆Q (ee−ǫ + β 2 )L(o|h1 )P(A(D) = o)=L(o|h0 )P(A(D′ ) = o))2Therefore, we know that f increases monotonically withθ ∈ [Q(D), +∞). Combining all the three intervals 1)-3),
we obtain the highest Fβscore as in Eq. 12.

(o−Q(D))2− 4 log(1.25/δ)∆Q/ǫ
(o−Q(D ′ ))2− 4 log(1.25/δ)∆Q/ǫ

∆Q(2o − Q(D) − Q(D′ ))4 log(1.25/δ)∆Q/ǫ






(29)

Then, we can compute the false alarm rateR∞
α according to 1 − θ P(A(D′ ) = o)do = 1 −R∞(o−Q(D ′ ))2
1
√
1
−
exp
−
4 log(1.25/δ)∆Q/ǫ do,θ
2 log(1.25/δ)∆Q/ǫ

′which is 1 − Φ( √ θ−Q(D )), i.e., θ = Φ−1 (1 −2 log(1.25/δ)∆Q/ǫpα) 2 log(1.25/δ)∆Q/ǫ + Q(D′ ), where Φ(·) is the
cumulative distribution probability (CDF) of thestandard normal distribution. Then, the threshold λ for the likelihood ratio can be computed′))
as exp ∆Q(2θ−Q(D)−Q(Dand the true detection
4 log(1.25/δ)∆Q/ǫ
rate can be computed according to PT D = 1 −R∞
P(A(D) = o)do = 1 − Φ( √ θ−Q(D)).
θ
2 log(1.25/δ)∆Q/ǫ

For a given false alarm rate α, we can uniquelydetermine the threshold of the likelihood ratio λ, thethreshold of the output θ and the true detection rate
PT D . Since θ can be any possible value of the private
query result, we know that the Neyman-Pearson criterion is equivalent to setting a threshold θ for the Gaussian mechanism which is of a simpler formulation.

∗
under Auxiliary Information
10.5 Fβscore∗
10.5.1 Fβscoreunder Prior Distribution

Consider an adversary with access to the prior distribution of the input database. Since Fβscore =121+ (1+β 2β)recall(1+β 2 )precision

=

1+β 2
(1−ρp )GSR+β 2
1+
RSR, we knowthat maximizing Fβscore is equivalent to minimizing(1−ρp )GSR+β 2(1−ρp )GSR+β 2. Next, we define f =
RSR
RSR

and

10.4 Proof for Theorem 6

analyze its property under three intervals.
1) For the first interval of (−∞, Q(D′ )], we have f =Proof. According to the Neyman-Pearson Lemma [46],the likelihood ratio test [49, 57] can be utilized toachieve the Neyman-Pearson criterion. For an adversary with access to the noisy scalar output o = A(D) =Q(D)+N (2 log(1.25/δ)∆Q/ǫ), we can compute the likelihood ratio corresponding to the two hypotheses defined(1−ρp )GSR+β 2
RSR=

1−ρp +β 2 −0.5(1−ρp )e1−0.5eθ−Q(D ′ )ǫ∆Qθ−Q(D)
ǫ∆Q. Next, weInvestigating Statistical Privacy Frameworks from the Perspective of Hypothesis Testingtake the derivative of f as

take the derivative of f as
−
∂f
=
∂θ

+

=

0.5(1−ρp )ǫ
e∆Q

θ−Q(D ′ )ǫ∆Q

(1 − 0.5e

0.5ǫ
e
∆Q

0.5ǫ
e
∆Q

θ−Q(D)
ǫ∆Q(1 − 0.5e

θ−Q(D)ǫ∆Q

θ−Q(D)
ǫ
∆Q

−
∂f
=
∂θ

)

)2

(1 − ρp + β 2 − 0.5(1 − ρp )eθ−Q(D ′ )ǫ∆Q

(1 − 0.5e

θ−Q(D)ǫ∆Q

θ−Q(D ′ )ǫ∆Q)θ−Q(D)
ǫ
∆Q

=

−

=

take the derivative of f as
−
∂f
=
∂θ

+

0.5(1−ρp )ǫ −
e
∆Q

0.5ǫ
e
∆Q

(1 − 0.5e

θ−Q(D)
ǫ∆Q−(0.5(1 − ρp )e0.5(1−ρp )ǫ −ǫ
−(e − e∆Q

θ−Q(D)
ǫ∆Q(1 − 0.5e

θ−Q(D)
ǫ∆Q(1 − 0.5e=

1−0.5eθ−Q(D ′ )ǫ∆Qθ−Q(D ′ )
ǫ
∆Q
+β 2

−

θ−Q(D ′ )∆Q

θ−Q(D)ǫ∆Q

θ−Q(D ′ )
ǫ
∆Q

)

2

θ−Q(D)ǫ∆Q))2

0.5(1−ρp )ǫ −ǫ
(e −
∆Q
2
∂f
β
e−ǫ + 1−ρp ) > 0. For θ = Q(D′ ), we have ∂θ θ=Q(D′ ) =0.5(1−ρp )ǫ
β2((1 + 1−ρ)e−ǫ − 1). Therefore, we have∆Qp∂f∂θ θ=Q(D ′ ) > 0, i.e., the function f increases monotonically for ǫ ∈ (Q(D′ ), Q(D)), if ǫ < log(1 +For θ = Q(D), we have ∂f∂θ θ=Q(D) =β21−ρp ). Otherwise, it decreases and then increases thus

there is a mininum within this interval. To solve forthe mininum, we set the derivative to 0, i.e., e−ǫ −e−

θ−Q(D ′ )ǫ∆Qθ−Q(D)2β· e ∆Q ǫ = 0 to obtain θ =+ 1−ρ
q p 2 ǫ
1−ρp
∆Q
4β e
′
ǫ log( 2β 2 ( 1 + 1−ρp −1))+Q(D ). The correspondq(1+β 2 )(ing Fβscore =(1+β 2 )

q

2 ǫ

e
1+ 4β
1−ρp −1)
2 ǫ

.

e
2
1+ 4β
1−ρp −1+β3) For the third interval of [Q(D′ ), +∞, we have f =(1−ρp )GSR+β 2
RSR=0.5(1−ρp )e
0.5e

+ β2)

(32)

)2

θ−Q(D)ǫ∆Q

θ−Q(D)ǫ∆Q)2

Therefore, f increases monotonically for θ ∈(−∞, Q(D′ )]. Combining the analysis for all the three∗intervals, we can achieve Fβscoreas in Eq. 12.
∗
10.5.2 Fβscoreunder Record Correlation∗
10.5.3 Fβscoreunder Temporal Correlation

β
e
+ 1−ρ

θ−Q(D)ǫ∆Q

θ−Q(D ′ )
ǫ
∆Q

(31)

)2

ǫ

−

(0.5(1 − ρp )e

The computation of the highest Fβscore for adversaries
under record correlation is similar to that of adversaries with prior distribution. By comparing Eq. 17 andEq. 20, we can also simply replace ρp in Eq. 18 with
ρp + ρc (2 − ρp ) to obtain Eq. 21.

+ β2)

p

(1 − 0.5e. Next, we)2

θ−Q(D)
ǫ∆Q

0.5β 2 ǫ −e∆Q

θ−Q(D)ǫ∆Q)2

θ−Q(D)− ∆Q ǫ

(0.5e

)2
(30)

0.5(1−ρp )e

0.5ǫ
e
∆Q

θ−Q(D)
ǫ
∆Q

−

e

(0.5e

Therefore, we have ∂f∂θ θ=Q(D ′ ) > 0, i.e., the function
f increases monotonically for θ ∈ (−∞, Q(D′ )], if ǫ <β2
log(1 + 1−ρ). Otherwise, it decreases monotonically.
p2) For the second interval of (Q(D′ ), Q(D)), we have(1−ρp )GSR+β 2
f =
RSR

−

(0.5e
θ−Q(D)− ∆Q ǫ

+θ−Q(D ′ )ǫ∆Q

0.25(1−ρp )ǫ2 −
e
∆Q

)2

((1 − ρp + β 2 )e−ǫ − (1 − ρp ))(1 − 0.5e253−(θ−Q(D ′ )ǫ)∆Q+β 2−(θ−Q(D)ǫ)∆Q. Then, we

The computation of the highest Fβscore for adversaries
under temporal correlation is similar to that of adversaries with prior distribution and record correlation. By
comparing Eq. 17 with Eq. 23, we can also simply replace ρp in Eq. 18 with ρp + (2 − ρp )(ρc + ρt (1 − ρc )) to
obtain Eq. 24.

10.6 Proof for Theorem 7
Proof. The Blowfish framework [28], which is a subclass of the Pufferfish framework, allows user to specify
adversarial knowledge about the database in the formof deterministic policy constraints. In the presence ofgeneral deterministic constraints, pairs of neighboring
databases can differ in any number of tuples. The neighboring databases of dependent differential privacy differ
in L tuples caused by one direct modification of one tuple. Therefore, under the same performance achieved by
the adversary’s hypothesis testing (the same amount of
perturbation), we know that ǫDDP (ht) ≤ ǫBP (ht).
From the definition of inferential privacy, we(D=D|A(D)=o)(D=D)≤ eǫ PP(D=D⇐⇒have maxD,D′ PP(D=D′ |A(D)=o)′)′|A(D)=o)≤ eǫ P (D=D
maxD,D′ P (D=D|A(D)=o)
P (D=D)P (D=D ′ )P (D=D,A(D)=o)
maxD,D′ A(D)=o),P(D=D)

maxD,D′ P (A(D) = o)′⇐⇒

P (D=D ,A(D)=o)≤ eǫ A(D)=o),P⇐⇒(D=D ′ )ǫ≤ e P (A(D′ ) = o), which is

Investigating Statistical Privacy Frameworks from the Perspective of Hypothesis Testing

equivalent to dependent differential privacy that re(A(D)=o)ǫ
quires maxD,D′ PP(A(D′ )=o) ≤ e . Therefore, we haveǫDDP (ht) = ǫIP (ht) under the same hypothesis testing
performance achieved by the adversary.
Since the neighboring databases in DP only differ
in one tuple, we know that ǫDP (ht) ≤ ǫDDP (ht) under
the same hypothesis testing achieved by the adversary.
Next, we consider membership privacy whose mathematical form is different from other privacy metrics.
Membership privacy does not consider two neighboring databases, but only bounds the ratio between theposterior probability and the prior probability for any
data record. Based on the definition of membership privacy and inferential privacy, we know that the membership privacy satisfying exp(−ǫ) ≤ P (D=D|A(D)=o)≤
P (D=D)
P (Di =di1 |A(D)=o)exp(ǫ) would lead to maxdi1 ,di2 P(Di =di2 |A(D)=o) ≤P (Di =di1 )exp(2ǫ) P(Di =di2 ) in inferential privacy (and thus dependent differential privacy). That is to say, ǫ-membershipprivacy would lead to 2ǫ-dependent differential privacy.
Therefore, we have ǫDDP (ht) ≤ 2ǫM P (ht) under thesame performance of the adversary’s hypothesis testing.
Furthermore, membership privacy considers theworst-case difference between posterior probability andprior probability, and the mutual information based differential privacy considers the average difference between posterior probability and prior probability. Therefore, we have that ǫ-membership privacy would lead to ǫmutual information based differential privacy. Under thesame performance of the adversary’s hypothesis testing,
we have ǫM IDP (ht) ≤ ǫM P (ht).

254