PaperlayerView exact revision on arXiv

Source-linked AI summary

SoK: Differential Privacies

Damien Desfontaines, Balázs Pejó

arXiv:1906.01337v6cs.CR

TL;DR

Many differential privacy definitions modify several aspects at once, making a comprehensive taxonomy difficult. This paper classifies variants by dimensions and compares their relationships and properties, showing that definitions from different dimensions can be combined into meaningful notions.

  • Problem

    A comprehensive taxonomy is difficult because many privacy definitions modify several aspects at once and cannot be placed neatly in a single category.

    Source: §2.2 · p. 6

  • Method

    The paper classifies DP variants and extensions by dimensions, compares definitions within dimensions, and examines their relative strength and properties.

    Source: §2.4 · p. 10, §12 · p. 47

  • Results

    The classification shows that definitions from different dimensions can be combined into meaningful new notions, while unifying and simplifying notions proposed in the literature.

    Source: §12 · p. 47

  • Takeaways & Limitations

    The taxonomy is intended to help practitioners judge whether an alternative definition suits their use case and, if so, which one.

    Source: §1 · p. 3

    Definitions in the multidimensional section mostly appear in theoretical research and do not seem to be used in practical applications, apart from hypothesis-testing reformulations.

    Source: §7.4 · p. 32

Abstract

from arXiv · show

Shortly after it was first introduced in 2006, differential privacy became the flagship data privacy definition. Since then, numerous variants and extensions were proposed to adapt it to different scenarios and attacker models. In this work, we propose a systematic taxonomy of these variants and extensions. We list all data privacy definitions based on differential privacy, and partition them into seven categories, depending on which aspect of the original definition is modified. These categories act like dimensions: variants from the same category cannot be combined, but variants from different categories can be combined to form new definitions. We also establish a partial ordering of relative strength between these notions by summarizing existing results. Furthermore, we list which of these definitions satisfy some desirable properties, like composition, post-processing, and convexity by either providing a novel proof or collecting existing ones.

1 Introduction

The paper systematizes differential-privacy variants and extensions in a taxonomy intended to clarify their use cases and relationships. It compares their relative strength and summarizes whether they satisfy key privacy properties and composition.

1 Introduction

  • Differential privacy shifted anonymity from a property of a released dataset to a property of the process, following shortcomings of dataset-based approaches.Earlier approaches such as k-anonymity could still leak sensitive information; differential privacy was introduced in.Source: §1 · p. 3
  • Many DP variants address contexts where its noise is too large, its risk model is unsuitable, or stronger statements about information revealed are needed.The proliferation of definitions makes it difficult for practitioners to choose an appropriate notion and for experts to compare related definitions.Source: §1 · p. 3

Contributions and organization

  • The survey organizes its review into seven sections on the dimensions and their definitions, followed by a summary table of properties and known relations.It also describes its methodology and scope and reviews related literature.Source: Contributions and organization · p. 4

2 Differential Privacy

The section defines differential privacy through indistinguishability on neighboring datasets and develops a framework for classifying variants, evaluating their properties, and comparing their strength. It introduces seven modification dimensions, privacy axioms and composition, and relations between definitions.

2.1 The original version

  • A mechanism is ε-DP when its outputs on any datasets differing in one record are ε-indistinguishable.ε-indistinguishability requires event probabilities in either direction to differ by at most a factor of e^ε.Source: §2.1 · p. 6

Mechanisms

  • Noise can be added to inputs, outputs, or mechanisms; Laplace and exponential noise yield ε-DP, while Gaussian noise yields the weaker (ε, δ)-DP guarantee.Mechanism perturbation includes adding noise to a loss function or gradient.Source: Mechanisms · p. 6

2.2 Dimensions

  • The taxonomy uses seven dimensions because definitions may change several aspects at once; different dimensions are compatible, while choices within one dimension are mutually exclusive.The dimensions are motivated and presented as understandable choices for users selecting definitions.Source: §2.2 · pp. 6–7

Privacy Axioms

  • Most DP variants, including original DP, satisfy the post-processing and convexity privacy axioms, though some do not.Post-processing permits applying a probabilistic function to a mechanism’s output; convexity permits random selection between two mechanisms satisfying the definition.Source: Privacy Axioms · p. 8

Composition

  • Sequential composition of ε1-DP and ε2-DP mechanisms is (ε1 + ε2)-DP, while parallel composition on disjoint datasets is max(ε1, ε2)-DP.Sequential composition remains valid when the second mechanism depends on the first mechanism’s output; the paper focuses on sequential composition.Source: Composition · p. 9

2.4 Relations between definitions

  • An extension makes one definition a special case of another through a parameter mapping, while relative strength defines a partial ordering between definitions.Equivalent definitions may differ by a parameter change, and a weaker extension combines extension with weaker relative strength.Source: §2.4 · pp. 9–10

3 Quantification of privacy loss (Q)

This section groups differential-privacy relaxations by how they quantify privacy loss: permitting rare violations, averaging loss, or controlling its tail, with extensions that generalize divergence bounds and parameterization. These alternatives address risk models beyond worst-case bounds and can support better composition properties.

3 Quantification of privacy loss (Q)

  • Differential privacy bounds the maximum privacy loss over neighboring datasets and outputs, while these relaxations allow rare errors, average loss, or describe its distribution more finely.The worst-case framing can exclude events with vanishingly small probability and mechanisms such as the Gaussian mechanism.Source: §3 · p. 10

3.1 Allowing a small probability of error

  • Approximate DP permits a δ probability allowance beyond the ε bound, whereas probabilistic DP bounds the probability of outputs violating that bound; ProDP is stronger at unchanged parameters.The probability-of-violation intuition applies to ProDP, not approximate DP; the two definitions can be combined as relaxed DP.Source: §3.1 · pp. 10–11

3.2 Averaging the privacy loss

  • KL privacy bounds the arithmetic mean of privacy loss, while Rényi DP bounds its αth moment, with larger α assigning greater weight to worst-case events.Rényi DP extends continuously to ε-KL privacy at α = 1 and ε-DP at α = ∞; the moments accountant tracks privacy-loss moments during composition [ACG+16].Source: §3.2 · pp. 11–12

3.3 Controlling the tail distribution of the privacy loss

  • Concentrated-DP variants control the privacy-loss tail more tightly than approximate DP, including zCoDP’s concentration around zero and truncated or approximate variants.Mean-concentrated DP does not satisfy post-processing; zero-concentrated DP was proposed as an alternative [BS16]. Variants restrict the probability mass or range of Rényi orders [BS16].Source: §3.3 · pp. 12–13

3.4 Extension

  • Divergence DP generalizes privacy bounds by making the divergence function a parameter; capacity-bounded DP restricts the supremum to a selected family of queries.For approximate DP, probabilistic DP, and Rényi DP, the tightest parameter family for a mechanism specifies its privacy-loss behavior entirely.Source: §3.4 · p. 14

3.5 Multidimensional definitions

  • Approximate DP and Rényi privacy have standalone uses, while most other variants in this section serve as technical tools for composition or privacy amplification.Examples include posterior sampling, resistance to adversarial machine-learning inputs [PYGPA19], and technical uses.Source: §3.5 · p. 14

4 Neighborhood definition (N)

The section treats neighborhood choice as the dimension that determines which data changes are protected, allowing DP to adapt to different sensitive properties. This dimension can also be combined with changes to the privacy-loss risk model.

4 Neighborhood definition (N)

  • The standard neighborhood relates datasets differing in one record, either by changing its value or by adding or removing it; together, these protect properties of an individual.Source: §4 · pp. 14–15

4.1 Changing the sensitive property

  • Changing which dataset pairs must be indistinguishable changes the protected sensitive property.Source: §4.1 · p. 15, §4 · p. 15

Weaker relaxations

  • Bounded and unbounded DP formalize record replacement versus addition or removal, while attribute and bit DP narrow the change within a record.ε-unbounded DP implies 2ε-bounded DP, and the original ε-DP is the conjunction of the two; one-sided DP uses a sensitive-record policy and is asymmetric, becoming bounded DP when P = T.Source: Weaker relaxations · p. 15

Stronger notions

  • Stronger neighborhood variants protect multiple contributions or elements that reveal user information; group privacy protects multiple individuals across datasets differing in several records and can be interpreted as accounting for correlations, while DP under correlation tracks influence [ADJ19].Dependent DP specifies a dependence relation R and dependence size c, comparing datasets after one record and at most c − 1 related records change. When R is empty or c = 1, it is equivalent to bounded DP.Source: Stronger notions · p. 16

4.2 Limiting the scope of the definition

  • Individual DP compares one fixed dataset only with its neighbors, with conditioned DP an equivalent definition.A further restriction fixes a record as well as the dataset.Source: §4.2 · p. 17

4.3 Applying the definition to other types of input

  • Applications redefine neighbors for locations, graph data [HLMJ09], streams, RAM/PIR, and text or images [LDX+21].These variants define protected changes over domain-specific inputs, such as graph nodes or edges, event sequences, memory requests, and words or images.Source: §4.3 · pp. 17–18

4.4 Extensions

  • Generic DP allows an arbitrary dataset relation, while other extensions use predicate pairs, private functions, distances, or policy graphs and constraints.Generic DP is symmetric but can be adapted to asymmetric definitions; bounded DP is equivalent to blowfish privacy with a complete policy graph and datasets of fixed size.Source: §4.4 · p. 19

4.5 Multidimensional definitions

  • Neighborhood changes are orthogonal to privacy-loss risk-model changes, so they can be combined, including with a δ parameter or an arbitrary divergence function.Examples include adjacency relation divergence DP and node-Rényi DP [DMS+21]; local mechanisms such as RAPPOR implicitly use bounded DP, while dataset- or user-specific scope variants provide few formal guarantees and are not commonly used in practice.Source: §4.5 · p. 20

5 Variation of privacy loss (V)

This section describes differential privacy variants that vary protection across inputs or randomize which cases must satisfy privacy, and explains how these approaches combine with changes to neighborhoods and privacy metrics.

5.1 Varying the privacy level across inputs

  • Personalized DP (PerDP) assigns user-specific ε levels; related notions include heterogeneous DP [AGK16] and personalized location DP.The assigned privacy level is not considered sensitive and cannot depend on the data itself.Source: §5.1 · p. 20
  • Uniform Ψ(i)=ε PerDP follows from ε-DP, while Ψ-PerDP implies ε-DP for ε=max_i Ψ(i).Source: §5.1 · p. 21
  • TaiDP makes privacy depend on the whole dataset and differing record; input-discriminative DP uses ε values for both datasets.Source: §5.1 · p. 21
  • Other variants tailor protection to outlierness or make ε grow linearly with distance between r-neighbor datasets in geo-indistinguishability.Source: §5.1 · p. 21

5.2 Randomizing the variation of privacy levels

  • Random DP allows a fraction γ of input cases not to satisfy ε-indistinguishability; unlike probabilistic DP, its failure probability is over inputs, and it does not satisfy convexity.The authors suggest approximate DP- or Rényi DP-like tools as a possible way to address the convexity issue.Source: §5.2 · pp. 21–22

5.3 Multidimensional definitions

  • Varying privacy levels or limiting considered datasets can be combined with other dimensions of differential privacy.Source: §5.3 · p. 22

Combination with N

  • dD-privacy uses a dataset-distance function to specify maximal privacy loss and neighborhood, and smooth DP and earth mover’s privacy are particular instantiations for specific distance functions.Source: Combination with N · pp. 22–23

Combination with Q

  • Endogenous DP combines (ε, δ)-DP with personalized DP, while pseudo-metric DP [DNM+13] combines dD-privacy with (ε, δ)-DP and extended divergence DP with divergence DP.Source: Combination with Q · p. 23

6 Background knowledge (B)

Differential privacy’s full-background-knowledge assumption can be relaxed by modeling attacker uncertainty with a distribution over input data. The resulting definitions distinguish whether a sensitive property conditions data generation or is changed after data generation, and can be combined with other privacy dimensions.

6 Background knowledge (B)

  • Limited-background-knowledge definitions model attacker uncertainty with a data-generating distribution; associative and causal views differ in whether the sensitive property conditions data generation or changes afterward.Less attacker knowledge can motivate using significantly less mechanism noise.Source: §6 · p. 24

6.1 Conditioning the output on the sensitive property

  • Noiseless privacy (NPr), introduced in and formalized in, expresses indistinguishability by conditioning the input distribution on a sensitive property.NPr follows the associative view, and its uncertainty model can vary; DP under sampling is one instance.Source: §6.1 · pp. 24–25

6.2 Removing the effect of correlations in the data

  • Causal DP avoids correlation effects by changing a record after data generation; it is equivalent to noiseless privacy when records are independent [DMKB19].Distributional DP conditions the data-generating distribution on a target-record value, but correlations can make noiseless privacy too strong and impede learning global properties; causal DP [DMKB19] was introduced to avoid definitional issues with background knowledge.Source: §6.2 · p. 25

6.3 Multidimensional definitions

  • Limiting background knowledge is orthogonal to earlier dimensions, so it can be combined with changes to the risk model, neighborhood definition, or privacy parameters.Source: §6.3 · p. 26

Combination with Q

  • Under a risk model similar to (ε, δ)-DP, APKDP quantifies over all possible background-knowledge values, whereas strictly weaker PPKDP models a passive attacker unable to choose that knowledge, with δ also applying to its value.Noiseless privacy was first introduced in and reformulated in [DMKB19] to clarify its implicit active-attacker assumption.Source: Combination with Q · pp. 26–27

Combination with N

  • Pufferfish privacy [KM12] compares distributions conditioned on sensitive attributes, encompassing noiseless privacy and other notions; its assumptions about limited attacker knowledge can make guarantees fragile.Distribution privacy is an equivalent pair-of-distributions formalism; further combinations include probabilistic and divergence distribution privacy.Source: Combination with N · pp. 27–28

7 Change in formalism (F)

The section organizes alternative differential privacy formalisms around hypothesis testing and Bayesian views of attackers’ beliefs. These definitions clarify DP’s guarantees, and hypothesis-testing reformulations can improve composition and amplification results, though most are theoretical rather than practical.

7.4 Multidimensional definitions

  • These definitions deepen understanding of DP guarantees, but apart from hypothesis-testing variants that can improve composition and amplification, they mostly appear in theoretical work rather than practical applications.The section notes that this formalism dimension can combine with other dimensions, and that some definitions span multiple dimensions.Source: §7 · p. 28, §7.4 · pp. 31–32

7.1 Hypothesis testing

  • Hypothesis testing interprets DP through type I false-alarm and type II missed-detection errors, with ε-DP characterized by bounds on both errors.The test asks whether a mechanism’s output came from D1 or D2.Source: §7.1 · pp. 28–29
  • f-DP uses this testing view to avoid divergence-based relaxations, offers lossless composition and tractable privacy-loss approximation, and is dual to infinitely many (ε, δ)-DP guarantees.Gaussian DP is an f-DP instance; weak and strong federated f-DP describe guarantees against individual and group adversaries, respectively.Source: §7.1 · p. 29

7.2 Changing the shape of the prior-posterior bounds

  • Indistinguishable privacy restates DP as bounding a Bayesian attacker’s posterior certainty from its prior, while positive membership privacy limits posterior increases under restricted background knowledge.The posterior bound has a symmetric lower counterpart; positive membership privacy itself is asymmetric.Source: §7.2 · p. 29
  • Membership privacy [LQS+13] combines positive and negative membership bounds, whereas adversarial privacy adds δ to a positive bound and aposteriori noiseless privacy is another related variant.Positive membership privacy bounds only from above; negative membership privacy supplies the symmetric lower bound.Source: §7.2 · p. 30

7.3 Comparing two posteriors

  • Semantic privacy bounds the statistical distance between posterior beliefs for different datasets and, like DP, quantifies over arbitrary attacker priors.Inferential privacy reformulates noiseless privacy, while range-bounded privacy compares possible privacy-loss values and serves as a composition proof tool.Source: §7.3 · pp. 30–31

7.4 Multidimensional definitions

  • Bayesian definitions can combine with other dimensions: identity DP [WXH17] reformulates noiseless privacy, and information privacy [dPCF12] considers knowledge about dataset groups and implies 2ε-DP when Θ contains a full-support distribution.Semantic privacy also combines with probabilistic DP, and definitions can use different neighborhood relations.Source: §7.4 · pp. 31–32

8 Relativization of the knowledge gain (R)

These variants relativize differential privacy by accounting for auxiliary leakage or limiting what a mechanism reveals relative to safe aggregate information. Some also combine controls on background knowledge, protected attributes, and other aspects of privacy definitions.

8.1 Taking into account auxiliary leakage function

  • BLDP conditions mechanism-output probabilities on shared-randomness leakage outputs, reverting to (ε, δ)-DP for constant leakage and remaining post-processing closed and composable.When the mechanism is independent of the leakage function, BLDP is strictly weaker than differential privacy.Source: §8.1 · p. 32

8.2 Borrowing concepts from zero-knowledge proofs

  • Zero-knowledge privacy requires the mechanism’s output to be simulatable from aggregate information about the dataset without the target individual, and it implies 2ε-DP.Conversely, ε-DP implies (Agg, ε)-ZKPr when Agg contains the identity function. Subspace DP [GGY21] instead requires a projection f(M(D)) to be DP, with induced subspace DP ensuring external linear constraints.Source: §8.2 · p. 33

8.3 Multidimensional definitions

  • Coupled-worlds privacy uses distributions and protected-attribute functions to express what information is protected relative to aggregate information.Distributional DP is a special case in which priv captures one record and agg returns the others. The framework combines aspects from N, B, and R, and its inference-based form integrates Q and F using Bayesian reformulation; the paper also introduces inference-based distributional DP.Source: §8.3 · pp. 33–34
  • Typical stability [BF16] combines random DP with approximate DP by comparing mechanism output to a simulator that knows only the data-generating distribution.The guarantee holds with probability at least 1−γ over D∼θ, and the paper finds no evidence that these section’s variants are used outside theoretical work.Source: §8.3 · p. 34

9 Computational power (C)

Computational privacy variants weaken differential privacy’s information-theoretic attacker assumption by bounding the attacker’s power. IndCDP bounds output distinguishers, while SimCDP requires a mechanism to resemble a differentially private one to a bounded distinguisher.

9 Computational power (C)

  • Bounding the attacker’s computation weakens privacy definitions that otherwise assume infinite computing power; formalizes this through bounded distinguishers or mechanisms that resemble truly differentially private ones.These are the output-based and mechanism-based approaches, respectively.Source: §9 · p. 34

Using a polynomial distinguisher on the output

  • IndCDP requires that no non-uniform probabilistic polynomial-time distinguisher can distinguish outputs on neighboring datasets beyond an εκ multiplicative bound plus negligible slack.The guarantee applies to sufficiently large security parameter κ and datasets of polynomially bounded size differing in one record; the slack vanishes faster than the reciprocal of any polynomial.Source: Using a polynomial distinguisher on… · p. 35

Using a polynomial distinguisher on the mechanism

  • SimCDP requires a mechanism to be indistinguishable to polynomial-time observers from a family of mechanisms satisfying εκ-DP.Its definition includes negligible slack that vanishes faster than the reciprocal of any polynomial.Source: Using a polynomial distinguisher on… · p. 35

9.1 Multidimensional definitions

  • Computational privacy extends to multidimensional and other settings: OCDP allows party-specific parameters and function-defined neighborhoods, while DPRL protects non-matching records in private record linkage.Computational zero-knowledge privacy bounds the simulator, and the paper notes that SimCDP’s approach could in principle adapt other definitions, though this has not been done in existing literature. Computational limits may offer little benefit for many client-server queries, so existing work focuses on multi-party settings.Source: §9.1 · pp. 35–36

10 Summarizing table

This section summarizes known relations and properties of differential privacy variants, including their dimensions, post-processing, convexity, composability, and privacy axioms. It also notes that data-dependent randomness prevents adapting the proof of Proposition 7 because the relevant probabilities become dependent.

10 Summarizing table

  • Table 3 catalogs variants by name, parameters, dimensions, axioms, composability, and relations, excluding definitions differing only by input type and geolocation-specific definitions.The table presents main options for combinations of dimensions.Source: §10 · p. 36, Table 3 · p. 39

10.1.1 Axioms

  • All DivDP instantiations satisfy both privacy axioms, including approximate DP, MIDP, KLPr, RenDP, and zCoDP; dD-Pr, EDivDP, MPr, AdvPr, ANPr, and InfPr also satisfy both.InfPr follows as a direct corollary of the result for MPr, AdvPr, and ANPr variants.Source: §10.1.1 · p. 40
  • ProDP, ACoDP, and RanDP do not satisfy the convexity axiom.Source: §10.1.1 · p. 40
  • Both CDP versions satisfy both axioms with post-processing limited to probabilistic polynomial-time functions, and CZKPr satisfies both axioms.Source: §10.1.1 · p. 41

10.1.2 Composition

  • Most definitions can also be combined with dD-privacy, with composition proofs adapted accordingly.Source: §10.1.2 · p. 42
  • Definitions that assume the adversary has limited background knowledge generally do not compose.Source: §10.1.2 · p. 42
  • With limited background knowledge, combining individually private query mechanisms can reveal information about a particular user because their probabilities are no longer independent.For example, the queries may count records satisfying a property and records satisfying it with an ID different from 4217.Source: §10.1.2 · p. 42

11 Scope and related work

The section defines inclusion criteria for the survey, explains why related definitions and technical notions are excluded, and situates the work among local-model variants and prior surveys. It distinguishes changes to DP’s formal property from changes of context, such as the local model.

11.1 Methodology

  • The survey includes definitions with explicit attacker capabilities and protected properties, and manually filters a broad literature search for new definitions or DP settings.The search used BASE24 and Google Scholar, and all papers defining a DP variant or extension are cited in the work.Source: §11.1 · pp. 42–43

11.2 Out of scope definitions

  • The survey excludes definitions lacking clear semantic privacy guarantees or used only to prove links between existing definitions; ε-privacy conditions the output, not the mechanism, and thus lacks strong semantic guarantees.Source: Lack of semantic guarantees · p. 43

Lack of semantic guarantees

  • ε-privacy and relaxed indistinguishability are excluded because their guarantees are unclear against Bayesian adversaries or do not protect against them.ε-privacy constrains outputs, not the mechanism; relaxed indistinguishability requires at least l tuples to have ε-indistinguishability.Source: Lack of semantic guarantees · p. 43
  • Other exclusions include membership privacy, posteriori DP, and noiseless privacy and measure of privacy, whose guarantees or attacker models are unclear.Differential identifiability does not compare probabilities between alternatives, while weak DP [WSMD20] guarantees privacy only for the average of possible outputs.Source: Lack of semantic guarantees · p. 44

Variants of sensitivity

  • Sensitivity variants, from local and smooth sensitivity to per-instance sensitivity, are excluded because they do not modify DP’s definition.The paper treats sensitivity as a technical tool for designing DP mechanisms.Source: Variants of sensitivity · p. 45

11.3 Local model and other contexts

  • Local DP and other contexts retain the formal definition; the local model randomizes each person’s data before aggregation, while the shuffled model applies DP to the shuffler’s output [BEM+17].Distributed DP corresponds to local DP with only a portion of participants assumed honest.Source: §11.3 · p. 45

11.4 Related work

  • Prior surveys cover DP fundamentals, applications, privacy metrics, correlation, location privacy, and parameter selection; this taxonomy extends an earlier classification of privacy metrics.That classification placed eight DP variants in its “Indistinguishability” category, while classifying Rényi DP and mutual-information DP elsewhere.Source: §11.4 · pp. 46–47

12 Conclusion

The paper organizes differential-privacy variants and extensions into dimensions, comparing notions within dimensions and showing how notions from different dimensions can be combined. It also unifies definitions and summarizes their properties and relative relationships.

12 Conclusion

  • The authors classify differential-privacy variants by dimensions, compare definitions within dimensions, and show that variants from different dimensions can form new definitions.They estimate that even three possible changes for each of seven dimensions would yield 3^7 = 2187 definitions, while Figure 1 shows approximately 225 existing definitions.Source: §12 · p. 47
  • The work unifies and simplifies notions from the literature, collecting existing results or proving properties such as composability and satisfaction of privacy axioms.It also shows relative relationships between notions where possible.Source: §12 · p. 47

Related papers

Loading 1906.01337v6…