SoK: Differential Privacies

Damien Desfontaines; Balázs Pejó

Source-linked AI summary

SoK: Differential Privacies

Damien Desfontaines, Balázs Pejó

arXiv:1906.01337v6Jun 4, 2019cs.CR

TL;DR

Differential privacy has accumulated many variants and extensions for different contexts and assumptions, making the research landscape difficult to understand and compare. The paper systematizes these definitions into seven dimensions, relates their strengths, and catalogs key properties. It concludes that the dimensions unify existing notions while leaving a much larger space of possible definitions, with some variants remaining mainly theoretical or facing specific property limitations.

Problem
The many DP variants and extensions are difficult to understand, compare, and select because related notions may overlap, be independently named, or lack comparisons.
Method
The paper proposes a taxonomy that groups DP variants and extensions into seven dimensions, compares their relative strength, and records properties such as composition, post-processing, convexity, and privacy axioms.
Results
The taxonomy unifies and simplifies existing notions, shows that definitions from different dimensions can be combined, and summarizes their known relations and properties.
Takeaways & Limitations
The dimension-based view helps identify appropriate alternative definitions and exposes a broader space of possible privacy notions than those currently proposed.
Takeaways & Limitations
Some definitions appear mainly in theoretical research and do not seem to be used in practical applications, while random DP does not satisfy the convexity axiom.

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

Differential privacy shifted anonymization from a dataset property to a process property, but its growing family of variants has made the field difficult to navigate. This work addresses that problem with a taxonomy of DP definitions, their relationships, and their basic properties.

Motivation: Differential privacy defines anonymity as a property of the data-generating process rather than the sanitized dataset, addressing leakage possible under dataset-based approaches.Earlier notions such as k-anonymity treated anonymity as a dataset property, which could allow arbitrary information leakage without assumptions about data generation.
Motivation: Variants and extensions adapt DP to settings where its noise, risk model, or privacy statement is unsuitable, enabling guarantees beyond the original definition's coverage.The motivation includes excessive noise, inappropriate risk models, and contexts requiring stronger statements about disclosed information.
Motivation: The field's expansion creates practical difficulties because similar definitions may be independently introduced, differently named, or presented without comparison to related notions.The paper identifies these problems as affecting both new practitioners and experts.
Contributions and organization: The authors organize differential privacy variants and extensions into seven dimensions, comparing definitions within dimensions and identifying combinations across dimensions.The taxonomy is intended to simplify understanding of existing notions and their relationships.
Contributions and organization: The taxonomy records intuition, use cases, relative strength, and whether definitions satisfy privacy axioms, post-processing, convexity, and composition.The survey compares definitions and establishes partial orderings when possible, while summarizing properties in a final table.

2 Differential Privacy

Differential privacy defines anonymity as a property of a randomized mechanism, and its variants modify different aspects of the original guarantee to fit different contexts. This section introduces seven dimensions for organizing these modifications, their compatibility conditions, and properties used to compare them.

Original Definition: Differential privacy requires mechanisms on neighboring datasets to produce ε-indistinguishable output distributions.ε-indistinguishability bounds event probabilities in both directions by a multiplicative factor e^ε.
Original Definition: Unlike dataset-based anonymity, differential privacy defines privacy as a property of the process rather than the released dataset.Earlier dataset properties could permit arbitrary leakage without assumptions about dataset generation.
Dimensions: Definitions from different dimensions can be combined, whereas definitions within one dimension are mutually exclusive but may remain comparable.These are the dimensions’ mutual-compatibility and inner-exclusivity requirements.
Dimensions: Variants modify different dimensions of the guarantee, including attacker knowledge, computation, protected information, failure behavior, and affected users.The paper represents each definition as a point in a multidimensional space and highlights seven aspects in an attacker-oriented reformulation.
Privacy Axioms: The paper evaluates variants against core properties including composition, post-processing, and convexity, finding that most satisfy these axioms.The results are summarized in a later table, with some exceptions noted.
Relations between Definitions: The taxonomy compares privacy definitions using relations such as extension, relative strength, and equivalence, which together induce a partial ordering.Equivalent definitions may differ by parameter transformations rather than being syntactically identical.

3 Quantification of privacy loss (Q)

This dimension modifies how privacy loss is quantified, replacing DP’s worst-case bound with probabilistic, average-case, or tail-sensitive controls. These alternatives can improve composition or support mechanisms such as the Gaussian mechanism, while differing in strength and practical use.

3 Quantification of privacy loss (Q): Relaxed privacy definitions replace DP’s maximum privacy-loss bound with probability allowances, averages, or finer descriptions of the loss distribution.Approximate DP permits a small probability mass where the ε bound fails; KL and Rényi privacy average privacy loss; concentrated definitions control its tail.
3.1 Allowing a small probability of error: (ε, δ)-DP allows an additional probability density δ on which the upper ε-indistinguishability bound need not hold.It is the most commonly used relaxation in the scientific literature.
3.1 Allowing a small probability of error: Probabilistic DP instead bounds an exceptional output set with probability at most δ, and is stronger than (ε, δ)-DP without changing parameters.A reverse implication holds with a parameter change, and both definitions can be expressed using privacy loss.
3.2 Averaging the privacy loss: Rényi DP controls the αth moment of privacy loss, interpolating between KL privacy at α = 1 and standard DP at α = ∞.Larger α assigns more weight to worst-case events, creating an ordered family of relaxations.
3 Quantification of privacy loss (Q): These definitions are standalone in some applications, but most variants are used as technical tools for improved composition or privacy amplification.Rényi privacy appears in posterior sampling and resistance to adversarial machine-learning inputs.

4 Neighborhood definition (N)

This dimension changes which dataset differences count as neighbors, thereby changing the sensitive property protected by DP. The taxonomy covers record-level, attribute-level, one-sided, group, correlation-aware, constrained, and dataset-specific neighborhoods.

4 Neighborhood definition (N): Changing DP’s neighborhood relation changes the protected sensitive property, allowing definitions to protect attributes, groups, correlations, or other dataset-specific properties.The original neighboring relation concerns one individual, but alternative relations target different forms of change.
4 Neighborhood definition (N): Unbounded DP allows adding or removing one record, bounded DP changes exactly one record, attribute DP changes one attribute, and bit DP changes one bit.Unbounded DP implies 2ε-bounded DP, while standard ε-DP combines unbounded and bounded protection.
4 Neighborhood definition (N): One-sided DP replaces a sensitive record with any other record, and becomes equivalent to bounded DP when every record is considered sensitive.Asymmetric DP extends the idea to an unbounded neighborhood, while sensitive privacy determines sensitivity from the data and a normality property.
4 Neighborhood definition (N): Group and correlation-aware definitions model changes affecting multiple records, with dependent DP using a dependence relation and a dependence-size parameter.Group privacy can represent multiple-individual protection, whereas correlated definitions account for records influenced by one individual’s change.
4 Neighborhood definition (N): Neighborhood restrictions also yield stronger or narrower notions, including free lunch privacy, individual DP, and constrained induced DP.Free lunch privacy compares arbitrary datasets and has near-total utility loss; individual DP compares one fixed dataset with its neighbors.

5 Variation of privacy loss (V)

This section organizes definitions that vary privacy protection across inputs, including personalized, tailored, randomized, and distance-based variants. It also describes combinations with other differential-privacy dimensions and summarizes representative strength relations and limitations.

5.1 Varying the privacy level across inputs: Personalized differential privacy varies ε by the differing user or record, while tailored variants can depend on the entire dataset and differing record.Equivalent formulations include heterogeneous DP and personalized location DP; tailored DP generalizes input-dependent privacy levels.
5.1 Varying the privacy level across inputs: ε-DP implies Ψ-PerDP when every Ψ(i)=ε, while Ψ-PerDP implies ε-DP for ε=max_i Ψ(i).
5.2 Randomizing the variation of privacy levels: Random DP protects randomly generated neighboring datasets with probability at least 1−γ, allowing a small fraction of inputs to fall outside the guarantee.The data-generating distribution may use parameters such as θ rather than i.i.d. records.
5.2 Randomizing the variation of privacy levels: Random DP differs from probabilistic DP because its exceptional probability ranges over mechanism inputs, whereas probabilistic DP ranges over outputs.The text also reports that random DP does not satisfy convexity.
5.3 Combining dimensions: Privacy-level variation can combine with neighborhood, risk-model, and background-knowledge dimensions, producing definitions such as EndDP, PsDP, and EDivDP.The framework treats these modifications as distinct dimensions that can be combined.
5.3 Combining dimensions: dD-privacy uses a dataset-distance function to specify both neighborhood structure and input-dependent privacy levels, recovering ε-DP for proportional Hamiltonian distance.The distance may be infinite for non-neighboring datasets and need not remain symmetric in generalized forms.
5.4 Distributional privacy: Distributional privacy compares mechanisms on randomly generated datasets and captures protection of particular samples while permitting learning properties of the generating distribution.If γ=o(1/n^2), the cited result states that (ε,γ)-distributional privacy also implies ε-DP.

6 Background knowledge (B)

This section adapts privacy definitions to attackers with limited background knowledge by modeling inputs through probability distributions and distinguishing associative from causal changes. It also develops active and passive partial-knowledge variants, while noting their dependence on modeling assumptions.

6.1 Modeling limited background knowledge: Background-knowledge variants model attacker uncertainty by generating datasets from probability distributions rather than comparing only fixed neighboring datasets.Noiseless privacy conditions mechanism outputs after conditioning the data-generating distribution on a sensitive record value.
6.2 Removing the effect of correlations in the data: Causal differential privacy changes one record after dataset generation, preventing dependence relationships from propagating that change; it equals noiseless privacy under record independence.The changed dataset is denoted D_i→t′.
6.2 Removing the effect of correlations in the data: Causal and noiseless privacy differ only in how dependence relationships among records are treated, with causal DP severing those relationships before mechanism evaluation.
6.4 Combining dimensions: These background-knowledge restrictions are orthogonal to risk models, neighborhood definitions, and input-dependent privacy levels, so they can be combined with them.Examples include DP under sampling, inherit DP, and empirical DP.
6.3 Active and passive attackers: Partial-knowledge privacy uses a privacy-loss random variable that explicitly incorporates auxiliary background knowledge alongside the generated dataset.
6.3 Active and passive attackers: Active partial-knowledge DP quantifies over all possible background-knowledge values, whereas passive partial-knowledge DP models an attacker who cannot choose that knowledge.Under passive partial knowledge, δ applies both to mechanism outputs and background-knowledge values.

7 Change in formalism (F)

This section reformulates differential privacy through hypothesis testing and Bayesian posterior relationships, then compares posterior-to-posterior guarantees. These formalisms clarify privacy guarantees and can yield tighter composition or amplification analyses, but are used mainly theoretically outside hypothesis-testing reformulations.

7 Change in formalism (F): The section’s formalisms deepen understanding of differential-privacy guarantees, and hypothesis-testing versions can improve composition and amplification results.Most other definitions in this section appear primarily in theoretical research rather than practical applications.
7.1 Hypothesis testing: Hypothesis-testing reformulations express ε-DP and (ε,δ)-DP through type I and type II errors for distinguishing neighboring datasets.The resulting f-DP framework uses a trade-off function and has a lossless composition theorem with a duality to collections of (ε,δ)-DP guarantees.
7.1 Hypothesis testing: f-DP defines privacy through a convex, continuous, non-increasing trade-off function, with Gaussian DP as a notable instance.The trade-off function captures the hardness of distinguishing mechanism outputs from shifted Gaussian distributions in Gaussian DP.
7.2 Changing the shape of the prior-posterior bounds: Differential privacy bounds a Bayesian attacker’s posterior as a function of the prior, while positive membership privacy directly requires an upper posterior-to-prior bound under limited background knowledge.Membership privacy combines positive and negative membership privacy to obtain symmetric bounds.
7.3 Comparing two posteriors: Semantic privacy compares two posterior belief distributions conditioned on outputs from datasets that differ in one record, rather than comparing posterior and prior beliefs.
7.4 Multidimensional definitions: If Θ contains a distribution supported on all datasets, (Θ,ε)-information privacy implies 2ε-DP.

8 Relativization of the knowledge gain (R)

This section organizes DP variants that relativize the knowledge gain protected, including auxiliary leakage, correlated data, simulators, and attacker background knowledge.

8 Relativization of the knowledge gain (R): The section covers DP variants that modify what information is protected or what auxiliary knowledge and leakage the attacker may use.Examples address side-channel leakage, correlated datasets, simulators, and explicitly modeled background knowledge.
8 Relativization of the knowledge gain (R): Bounded leakage DP conditions mechanism outputs on shared leakage and reduces to (ε, δ)-DP when the leakage function is constant.It is closed under post-processing and composition, but is strictly weaker than DP when the mechanism and leakage are independent.
8 Relativization of the knowledge gain (R): Zero-knowledge privacy uses a simulator based on aggregate information, and (Agg, ε)-ZKPr implies 2ε-DP while ε-DP implies ZKPr when identity is allowed.This formalizes protection against attackers with full background knowledge through simulation rather than direct neighboring-output comparison.
8 Relativization of the knowledge gain (R): Coupled-worlds privacy combines multiple modified dimensions, while inference-based coupled-worlds privacy adds Bayesian reformulation and approximate indistinguishability.Typical stability similarly combines random DP with approximate DP using a simulator informed by the data-generating distribution.
8 Relativization of the knowledge gain (R): The surveyed variants in this section were not found to be used outside theoretical papers studying their guarantees.This scope observation is reported for the section’s variants and extensions.

9 Computational power (C)

This section adapts differential privacy to computationally bounded attackers by replacing unbounded distinguishers or simulators with probabilistic polynomial-time ones.

9 Computational power (C): Computational DP models the attacker as a probabilistic polynomial-time distinguisher, yielding weaker privacy definitions than information-theoretic DP.The section presents indistinguishability-based and simulation-based approaches.
9 Computational power (C): IndCDP bounds a polynomial-time distinguisher’s probability of identifying which neighboring dataset produced a mechanism output, up to a negligible term.The definition applies to sufficiently large security parameters and polynomially bounded dataset sizes.
9 Computational power (C): SimCDP requires a mechanism to be computationally indistinguishable from a genuinely εκ-DP mechanism for polynomial-time distinguishers.This simulation-based idea can in principle be adapted to other privacy definitions.
9 Computational power (C): Computational restrictions extend to settings such as two-party computation, record linkage, computational zero-knowledge privacy, and potentially coupled-worlds privacy.These adaptations impose computational bounds on distinguishers or simulators.
9 Computational power (C): Computationally bounded attackers offer limited benefits over classical DP for many queries in typical client-server settings, so existing work focuses on multi-party settings.This is the section’s stated practical scope boundary.

10 Summarizing table

The summarizing table consolidates DP variants by dimensions, axioms, composability, and relative strength, alongside propositions establishing selected properties and relations.

10 Summarizing table: Most DP variants and extensions satisfy the privacy axioms, but the table highlights exceptions and cases with unknown status.The paper summarizes these properties using references or novel proofs.
10 Summarizing table: The table presents a partial ordering among notions, including examples where one definition is weaker, stronger, equivalent, or incomparable in the listed relations.Examples include ε-KL privacy between approximate DP and ε-DP, and Renyi DP related to both ε-KL privacy and ε-DP.
10 Summarizing table: Table 3 records each definition’s name, parameters, dimensions, post-processing and convexity axioms, composability, and relations to other DP notions.The table excludes definitions differing only in input type or geolocation-specific applications.
10.1 Axioms: Random DP, probabilistic DP, and approximate concentrated DP provide explicit counterexamples or relations showing that convexity and axiom behavior vary across definitions.In particular, ProDP, ACoDP, and RanDP do not satisfy convexity, while several divergence-based notions satisfy both axioms.
10.1.2 Composition: Most definitions can be combined with dD-privacy, but definitions assuming limited adversarial background knowledge generally do not compose.The table and propositions distinguish combinability across dimensions from composition guarantees.

11 Scope and related work

The paper defines a scope for its survey, uses a repeated literature-review process to identify DP variants, and excludes notions lacking clear semantic privacy guarantees or fitting the formal criteria.

11 Scope and related work: The survey includes definitions with clearly specified attackers that prevent attackers from learning protected properties, while excluding output-only and context-only differences.Technical notions such as sensitivity variants are also excluded from the taxonomy.
11.1 Methodology: The authors searched BASE24 and Google Scholar using repeated queries from 2018 through 2021, then manually filtered papers for new definitions or new DP settings.All papers defining a DP variant or extension were cited in the work.
11 Scope and related work: Other exclusions provide limited or unclear protection against Bayesian adversaries, including differential identifiability, crowd-blending privacy, and (k, ε)-anonymity.The stated concern is that their semantic guarantees are unclear or do not bound the relevant probability changes.
11 Scope and related work: Several excluded notions lack clear semantic guarantees because they constrain outputs, average mechanism behavior, or omit an explicit attacker model.Examples include membership privacy, posteriori DP, weak DP, error-preserving privacy, and the first ε-privacy definition.
11 Scope and related work: The work focuses on the global model, while local-model differential privacy is treated as a separate context without formally changing the definition.The local model has each individual randomize data before sending it to an aggregator.

12 Conclusion

The paper classifies differential-privacy variants and extensions into dimensions, enabling combinations across dimensions and comparisons within them. It also organizes their properties and relative relationships to make the field easier to navigate.

The dimension-based classification unifies differential-privacy variants and extensions while showing that definitions from different dimensions can combine into new notions.The paper illustrates the potential space with 3^7 = 2187 possible definitions, compared with approximately 225 existing definitions.
The work compares definitions, summarizes or proves properties such as composability and privacy axioms, and reports relative relations where possible.