Differential privacy

Differential privacy (DP) is a mathematically rigorous framework for releasing statistical information about datasets while protecting the privacy of individual data subjects.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 13 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Differential privacy (DP) is a mathematically rigorous framework for releasing statistical information about datasets while protecting the privacy of individual data subjects. It enables a data holder to share aggregate patterns of the group while limiting information that singles out specific individuals.

This is done by injecting carefully calibrated noise into statistical computations such that the utility of the statistic is preserved while provably limiting what can be inferred about any individual in the dataset. Another way to describe differential privacy is as a constraint on the algorithms used to publish aggregate information about a statistical database which limits the disclosure of private information of records in the database.

For example, differentially private algorithms are used by some government agencies to publish demographic information or other statistical aggregates while ensuring confidentiality of survey responses, and by companies to collect information about user behavior while controlling what is visible even to internal analysts. Roughly, an algorithm is differentially private if an observer seeing its output cannot tell whether a particular individual's information was used in the computation.

Differential privacy is often discussed in the context of identifying individuals whose information may be in a database.…

Differential privacy (DP) is a mathematically rigorous framework for releasing statistical information about datasets while protecting the privacy of individual data subjects. It enables a data holder to share aggregate patterns of the group while limiting information that singles out specific individuals.

This is done by injecting carefully calibrated noise into statistical computations such that the utility of the statistic is preserved while provably limiting what can be inferred about any individual in the dataset. Another way to describe differential privacy is as a constraint on the algorithms used to publish aggregate information about a statistical database which limits the disclosure of private information of records in the database.

For example, differentially private algorithms are used by some government agencies to publish demographic information or other statistical aggregates while ensuring confidentiality of survey responses, and by companies to collect information about user behavior while controlling what is visible even to internal analysts. Roughly, an algorithm is differentially private if an observer seeing its output cannot tell whether a particular individual's information was used in the computation.

Differential privacy is often discussed in the context of identifying individuals whose information may be in a database. Although it does not directly refer to identification and reidentification attacks, differentially private algorithms provably resist such attacks. where the probability is taken over the randomness used by the algorithm.

This definition is sometimes called "approximate differential privacy", with "pure differential privacy" being a special case when \delta = 0 . In the latter case, the algorithm is commonly said to satisfy ε-differential privacy (i.e., omitting \delta = 0 ).

Differential privacy offers strong and robust guarantees that facilitate modular design and analysis of differentially private mechanisms due to its composability, robustness to post-processing, and graceful degradation in the presence of correlated data. Now suppose a malicious user (often termed an adversary) wants to find whether Chandler has diabetes or not.

Suppose he also knows in which row of the database Chandler resides. Now suppose the adversary is only allowed to use a particular form of query Q_i that returns the partial sum of the first i rows of column X in the database. In order to find Chandler's diabetes status the adversary executes Q_5(D_1) and Q_4(D_1) , then computes their difference.

In this example, Q_5(D_1) = 3 and Q_4(D_1) = 2 , so their difference is 1. This indicates that the "Has Diabetes" field in Chandler's row must be 1. This example highlights how individual information can be compromised even without explicitly querying for the information of a specific individual.

Continuing this example, if we construct D_2 by replacing (Chandler, 1) with (Chandler, 0) then this malicious adversary will be able to distinguish D_2 from D_1 by computing Q_5 - Q_4 for each dataset. If the adversary were required to receive the values Q_i via an \varepsilon -differentially private algorithm, for a sufficiently small \varepsilon , then they would be unable to distinguish between the two datasets.

Sequential composition. If we query an ε-differential privacy mechanism t times, and the randomization of the mechanism is independent for each query, then the result would be \varepsilon t -differentially private.

In the more general case, if there are n independent mechanisms: \mathcal{M}_1,\dots,\mathcal{M}_n , whose privacy guarantees are \varepsilon_1,\dots,\varepsilon_n differential privacy, respectively, then any function g of them: g(\mathcal{M}_1,\dots,\mathcal{M}_n) is \left(\sum\limits_{i=1}^{n} \varepsilon_i\right) -differentially private. Parallel composition.

If the previous mechanisms are computed on disjoint subsets of the private database then the function g would be (\max_i \varepsilon_i) -differentially private instead. The other important property for modular use of differential privacy is robustness to post processing.

This is defined to mean that for any deterministic or randomized function F defined over the image of the mechanism \mathcal{A} , if \mathcal{A} satisfies ε-differential privacy, so does F(\mathcal{A}) . The property of composition permits modular construction and analysis of differentially private mechanisms and motivates the concept of the privacy loss budget.

If all elements that access sensitive data of a complex mechanisms are separately differentially private, so will be their combination, followed by arbitrary post-processing. In general, ε-differential privacy is designed to protect the privacy between neighboring databases which differ only in one row.

This means that no adversary with arbitrary auxiliary information can know if one particular participant submitted their information. However this is also extendable. We may want to protect databases differing in c rows, which amounts to an adversary with arbitrary auxiliary information knowing if c particular participants submitted their information.

This can be achieved because if c items change, the probability dilation is bounded by \exp ( \varepsilon c ) instead of \exp ( \varepsilon ) , i.e., for D 1 and D 2 differing on c items: \Pr[\mathcal{A}(D_{1})\in S]\leq \exp(\varepsilon c)\cdot\Pr[\mathcal{A}(D_{2})\in S]\,\! Thus setting ε instead to \varepsilon/c achieves the desired result (protection of c items).

In other words, instead of having each item ε-differentially private protected, now every group of c items is ε-differentially private protected (and each item is (\varepsilon/c) -differentially private protected). False Positive Rate (FPR): P_\text{FP} = \Pr[\text{Adversary guesses } H_1 \mid H_0 \text{ is true}].

False Negative Rate (FNR): P_\text{FN} = \Pr[\text{Adversary guesses } H_0 \mid H_1 \text{ is true}]. Ideal protection would imply that both error rates are equal, but for a fixed (ε, δ) setting, an attacker can achieve the following rates: \{(P_\text{FP}, P_\text{FN}) \mid P_\text{FP} + e^\varepsilon P_\text{FN} \geq 1 - \delta, \ e^\varepsilon P_\text{FP} + P_\text{FN} \geq 1 - \delta \} An important definition with respect to ε-differentially private mechanisms is sensitivity.

Let d be a positive integer, \mathcal{D} be a collection of datasets, and f \colon \mathcal{D} \rightarrow \mathbb{R}^d be a function. One definition of the sensitivity of a function, denoted \Delta f , can be defined by: \Delta f=\max \lVert f(D_1)-f(D_2) \rVert_1, where the maximum is over all pairs of datasets D_1 and D_2 in \mathcal{D} differing in at most one element and \lVert \cdot \rVert_1 denotes the L1 norm.

In the example of the medical database above, if we consider f to be the function Q_i , then the sensitivity of the function is one, since changing any one of the entries in the database causes the output of the function to change by either zero or one. This can be generalized to other metric spaces (measures of distance), and must be to make certain differentially private algorithms work, including adding noise from the Gaussian distribution (which requires the L2 norm) instead of the Laplace distribution.

There are techniques (which are described below) using which we can create a differentially private algorithm for functions, with parameters that vary depending on their sensitivity. The Laplace mechanism adds Laplace noise (i.e. noise from the Laplace distribution, which can be expressed by probability density function \text{noise}(y)\propto \exp(-|y|/\lambda)\,\! , which has mean zero and standard deviation \sqrt{2} \lambda\,\! ).

Now in our case we define the output function of \mathcal{A}\,\! as a real valued function (called as the transcript output by \mathcal{A}\,\! ) as \mathcal{T}_{\mathcal{A}}(x)=f(x)+Y\,\! where Y \sim \text{Lap}(\lambda)\,\!\,\! and f\,\! is the original real valued query/function we planned to execute on the database. Now clearly \mathcal{T}_{\mathcal{A}}(x)\,\! can be considered to be a continuous random variable, where \frac{\mathrm{pdf}(\mathcal{T}_{\mathcal{A},D_1}(x)=t)}{\mathrm{pdf}(\mathcal{T}_{\mathcal{A},D_2}(x)=t)}=\frac{\text{noise}(t-f(D_1))}{\text{noise}(t-f(D_2))}\,\! which is at most e^{\frac {\lambda}}\leq e^{\frac{\Delta(f)}{\lambda}}\,\! .

We can consider \frac{\Delta(f)}{\lambda}\,\! to be the privacy factor \varepsilon\,\! . Thus \mathcal{T}\,\! follows a differentially private mechanism (as can be seen from the definition above).

If we try to use this concept in our diabetes example then it follows from the above derived fact that in order to have \mathcal{A}\,\! as the \varepsilon\,\! -differential private algorithm we need to have \lambda=1/\varepsilon\,\! . Though we have used Laplace noise here, other forms of noise, such as the Gaussian Noise, can be employed, but they may require a slight relaxation of the definition of differential privacy.

But, overall, these data with many responses are significant, since positive responses are given to a quarter by people who do not have the attribute A and three-quarters by people who actually possess it. Thus, if p is the true proportion of people with A, then we expect to obtain (1/4)(1-p) + (3/4)p = (1/4) + p/2 positive responses.

Hence it is possible to estimate p. In particular, if the attribute A is synonymous with illegal behavior, then answering "Yes" is not incriminating, insofar as the person has a probability of a "Yes" response, whatever it may be. Although this example, inspired by randomized response, might be applicable to microdata (i.e., releasing datasets with each individual response), by definition differential privacy excludes microdata releases and is only applicable to queries (i.e., aggregating individual responses into one result) as this would violate the requirements, more specifically the plausible deniability that a subject participated or not.

Differentially-private voting rules

Because the outcome of an election is a function of the votes cast, publishing the winner of a close contest can leak information about how individual voters chose; for example, if the preferences of all voters but one are already known, the published winner reveals exactly how the remaining voter cast their ballot, which can in turn facilitate coercion and bribery. This concern has motivated a growing body of work applying DP, and especially local DP, to voting and social choice.

One strand of this research applies local DP directly to the collection of ballots, so that each voter's true preference is randomized before it leaves their device and no central tallying authority ever observes it in the clear. David, Giustolisi, Mortensen and Pedersen empirically evaluated five local DP mechanisms — randomized response, the Laplace and Gaussian mechanisms, RAPPOR, and local hashing — on synthetic ballots in a binary first-past-the-post setting and on a multi-option setting modelled on the first round of a two-round election, testing the latter against vote shares from the 2019 Danish general election.

They found that randomized response preserved the correct binary outcome for population sizes of 100,000 or more with privacy parameters between 0.1 and 1, while a One-Time RAPPOR mechanism performed best in the multi-option setting for populations of a million or more. Since no mechanism could reliably call the outcome of a near-tied vote, they proposed a threshold variant of randomized response that abstains from declaring a result when the estimated tally falls within a chosen margin of the tie point, which avoided incorrect outcomes but at the cost of occasionally rejecting a close vote outright.

A second strand treats privacy as inseparable from the normative axioms used to evaluate voting rules, rather than as an add-on to an existing rule. Mohsin, Liu, Chen, Rossi and Xia introduced a notion of group fairness alongside local DP, showed that existing voting rules trade off economic efficiency against fairness and privacy, and proposed both a machine-learning approach and a constrained-optimization approach for designing new voting rules that balance the three properties.

For multiwinner approval voting, Li, Guo, Xia, Cao and Wang showed that DP is fundamentally incompatible with several standard proportionality and efficiency axioms, including justified representation, extended justified representation, Pareto efficiency, and the Condorcet criterion. They derived matching upper and lower bounds on the trade-off between a rule's privacy budget and its approximate satisfaction of each axiom.

Related work has connected differential privacy to robustness properties of committee voting rules more broadly. Kehne, Schmidt-Kraepelin and Sornat designed randomized multiwinner approval voting rules that are algorithmically stable — meaning the distribution over winning committees changes only slightly when a single voter's ballot changes — and noted that a stronger version of this stability property coincides with DP, suggesting such rules could be applied in privacy-sensitive settings.

Differential Privacy: A Survey of Results by Cynthia Dwork, Microsoft Research, April 2008 (Presents what was discovered during the first two years of research on differential privacy.) Differential Privacy: A Primer for a Non-Technical Audience, Alexandra Wood, Micah Altman, Aaron Bembenek, Mark Bun, Marco Gaboardi, et al, Vanderbilt Journal of Entertainment & Technology LawVanderbilt Journal of Entertainment, Volume 21, Issue 1, Fall 2018.

(A good introductory document, but definitely *not* for non-technical audiences!) Technology Factsheet: Differential Privacy by Raina Gandhi and Amritha Jayanti, Belfer Center for Science and International Affairs, Fall 2020 Differential Privacy and the 2020 US Census, MIT Case Studies in Social and Ethical Responsibilities of Computing, no. Winter 2022 (January).

Differential Privacy and the 2020 US Census. Bowen, Claire McKay and Simson Garfinkel, The Philosophy of Differential Privacy, AMS Notices, November 2021.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1375131673 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

31 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.