Historical background

Official statistics organizations are charged with collecting information from individuals or establishments, and publishing aggregate data to serve the public interest. For example, the 1790 United States Census collected information about individuals living in the United States and published tabulations based on sex, age, race, and condition of servitude.^[4] Census records were originally posted, but started with the 1840 Census they were collected under a promise of confidentiality that the information provided will be used for statistical purposes, but that the publications will not produce information that can be traced back to a specific individual or establishment.

To accomplish the goal of confidentiality, statistical organizations have long suppressed information in their publications. For example, in a table presenting the sales of each business in a town grouped by business category, a cell that has information from only one company might be suppressed, in order to maintain the confidentiality of that company's specific sales.

The adoption of electronic information processing systems by statistical agencies in the 1950s and 1960s dramatically increased the number of tables that a statistical organization could produce and, in so doing, significantly increased the potential for an improper disclosure of confidential information. For example, if a business that had its sales numbers suppressed also had those numbers appear in the total sales of a region, then it might be possible to determine the suppressed value by subtracting the other sales from that total. But there might also be combinations of additions and subtractions that might cause the private information to be revealed. The number of combinations that needed to be checked increases exponentially with the number of publications, and it is potentially unbounded if data users are able to make queries of the statistical database using an interactive query system.

Definition of ε-differential privacy

Let ε be a positive real number and ${\displaystyle {\mathcal {A}}}$ be a randomized algorithm that takes a dataset as input (representing the actions of the trusted party holding the data).

Let ${\displaystyle {\textrm {im}}\ {\mathcal {A}}}$ denote the image of ${\displaystyle {\mathcal {A}}}$.

The algorithm ${\displaystyle {\mathcal {A}}}$ is said to provide ε-differential privacy if, for all datasets ${\displaystyle D_{1}}$ and ${\displaystyle D_{2}}$ that differ on a single element (i.e., the data of one person), and all subsets ${\displaystyle S}$ of ${\displaystyle {\textrm {im}}\ {\mathcal {A}}}$:

$${\displaystyle {\frac {\Pr[{\mathcal {A}}(D_{1})\in S]}{\Pr[{\mathcal {A}}(D_{2})\in S]}}\leq e^{\varepsilon },}$$

where the probability is taken over the randomness used by the algorithm.^[11]

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.

Composability

(Self-)composability refers to the fact that the joint distribution of the outputs of (possibly adaptively chosen) differentially private mechanisms satisfies differential privacy.

Sequential composition. If we query an ε-differential privacy mechanism ${\displaystyle t}$ times, and the randomization of the mechanism is independent for each query, then the result would be ${\displaystyle \varepsilon t}$-differentially private. In the more general case, if there are ${\displaystyle n}$ independent mechanisms: ${\displaystyle {\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{n}}$, whose privacy guarantees are ${\displaystyle \varepsilon _{1},\dots ,\varepsilon _{n}}$ differential privacy, respectively, then any function ${\displaystyle g}$ of them: ${\displaystyle g({\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{n})}$ is ${\displaystyle \left(\sum \limits _{i=1}^{n}\varepsilon _{i}\right)}$-differentially private.^[12]

Parallel composition. If the previous mechanisms are computed on disjoint subsets of the private database then the function ${\displaystyle g}$ would be ${\displaystyle (\max _{i}\varepsilon _{i})}$-differentially private instead.^[12]

Robustness to post-processing

For any deterministic or randomized function ${\displaystyle F}$ defined over the image of the mechanism ${\displaystyle {\mathcal {A}}}$, if ${\displaystyle {\mathcal {A}}}$ satisfies ε-differential privacy, so does ${\displaystyle F({\mathcal {A}})}$.

Together, composability and robustness to post-processing permit modular construction and analysis of differentially private mechanisms and motivate 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.

Group privacy

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 his information. However this is also extendable. We may want to protect databases differing in ${\displaystyle c}$ rows, which amounts to an adversary with arbitrary auxiliary information knowing if ${\displaystyle c}$ particular participants submitted their information. This can be achieved because if ${\displaystyle c}$ items change, the probability dilation is bounded by ${\displaystyle \exp(\varepsilon c)}$ instead of ${\displaystyle \exp(\varepsilon )}$,^[13] i.e., for D₁ and D₂ differing on ${\displaystyle c}$ items:

$${\displaystyle \Pr[{\mathcal {A}}(D_{1})\in S]\leq \exp(\varepsilon c)\cdot \Pr[{\mathcal {A}}(D_{2})\in S]\,\!}$$

Thus setting ε instead to ${\displaystyle \varepsilon /c}$ achieves the desired result (protection of ${\displaystyle c}$ items). In other words, instead of having each item ε-differentially private protected, now every group of ${\displaystyle c}$ items is ε-differentially private protected (and each item is ${\displaystyle (\varepsilon /c)}$-differentially private protected).

Sensitivity

Let ${\displaystyle d}$ be a positive integer, ${\displaystyle {\mathcal {D}}}$ be a collection of datasets, and ${\displaystyle f\colon {\mathcal {D}}\rightarrow \mathbb {R} ^{d}}$ be a function. The sensitivity ^[3] of a function, denoted ${\displaystyle \Delta f}$, is defined by

$${\displaystyle \Delta f=\max \lVert f(D_{1})-f(D_{2})\rVert _{1},}$$

where the maximum is over all pairs of datasets ${\displaystyle D_{1}}$ and ${\displaystyle D_{2}}$ in ${\displaystyle {\mathcal {D}}}$ differing in at most one element and ${\displaystyle \lVert \cdot \rVert _{1}}$ denotes the ${\displaystyle \ell _{1}}$ norm.

In the example of the medical database below, if we consider ${\displaystyle f}$ to be the function ${\displaystyle 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.

There are techniques (which are described below) using which we can create a differentially private algorithm for functions with low sensitivity.

The Laplace mechanism

The Laplace mechanism adds Laplace noise (i.e. noise from the Laplace distribution, which can be expressed by probability density function ${\displaystyle {\text{noise}}(y)\propto \exp(-|y|/\lambda )\,\!}$, which has mean zero and standard deviation ${\displaystyle {\sqrt {2}}\lambda \,\!}$). Now in our case we define the output function of ${\displaystyle {\mathcal {A}}\,\!}$ as a real valued function (called as the transcript output by ${\displaystyle {\mathcal {A}}\,\!}$) as ${\displaystyle {\mathcal {T}}_{\mathcal {A}}(x)=f(x)+Y\,\!}$ where ${\displaystyle Y\sim {\text{Lap}}(\lambda )\,\!\,\!}$ and ${\displaystyle f\,\!}$ is the original real valued query/function we planned to execute on the database. Now clearly ${\displaystyle {\mathcal {T}}_{\mathcal {A}}(x)\,\!}$ can be considered to be a continuous random variable, where

$${\displaystyle {\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 ${\displaystyle e^{\frac {|f(D_{1})-f(D_{2})|}{\lambda }}\leq e^{\frac {\Delta (f)}{\lambda }}\,\!}$. We can consider ${\displaystyle {\frac {\Delta (f)}{\lambda }}\,\!}$ to be the privacy factor ${\displaystyle \varepsilon \,\!}$. Thus ${\displaystyle {\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 ${\displaystyle {\mathcal {A}}\,\!}$ as the ${\displaystyle \varepsilon \,\!}$-differential private algorithm we need to have ${\displaystyle \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.^[13]

According to this definition, differential privacy is a condition on the release mechanism (i.e., the trusted party releasing information about the dataset) and not on the dataset itself. Intuitively, this means that for any two datasets that are similar, a given differentially private algorithm will behave approximately the same on both datasets. The definition gives a strong guarantee that presence or absence of an individual will not affect the final output of the algorithm significantly.

For example, assume we have a database of medical records ${\displaystyle D_{1}}$ where each record is a pair (Name, X), where ${\displaystyle X}$ is a Boolean denoting whether a person has diabetes or not. For example:

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 ${\displaystyle Q_{i}}$ that returns the partial sum of the first ${\displaystyle i}$ rows of column ${\displaystyle X}$ in the database. In order to find Chandler's diabetes status the adversary executes ${\displaystyle Q_{5}(D_{1})}$ and ${\displaystyle Q_{4}(D_{1})}$, then computes their difference. In this example, ${\displaystyle Q_{5}(D_{1})=3}$ and ${\displaystyle 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 ${\displaystyle D_{2}}$ by replacing (Chandler, 1) with (Chandler, 0) then this malicious adversary will be able to distinguish ${\displaystyle D_{2}}$ from ${\displaystyle D_{1}}$ by computing ${\displaystyle Q_{5}-Q_{4}}$ for each dataset. If the adversary were required to receive the values ${\displaystyle Q_{i}}$ via an ${\displaystyle \varepsilon }$-differentially private algorithm, for a sufficiently small ${\displaystyle \varepsilon }$, then he or she would be unable to distinguish between the two datasets.

Randomized response

A simple example, especially developed in the social sciences,^[16] is to ask a person to answer the question "Do you own the attribute A?", according to the following procedure:

1. Toss a coin.
2. If heads, then toss the coin again (ignoring the outcome), and answer the question honestly.
3. If tails, then toss the coin again and answer "Yes" if heads, "No" if tails.

(The seemingly redundant extra toss in the first case is needed in situations where just the act of tossing a coin may be observed by others, even if the actual result stays hidden.) The confidentiality then arises from the refutability of the individual responses.

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.^[17][18]

Stable transformations

A transformation ${\displaystyle T}$ is ${\displaystyle c}$-stable if the Hamming distance between ${\displaystyle T(A)}$ and ${\displaystyle T(B)}$ is at most ${\displaystyle c}$-times the Hamming distance between ${\displaystyle A}$ and ${\displaystyle B}$ for any two databases ${\displaystyle A,B}$. Theorem 2 in ^[12] asserts that if there is a mechanism ${\displaystyle M}$ that is ${\displaystyle \varepsilon }$-differentially private, then the composite mechanism ${\displaystyle M\circ T}$ is ${\displaystyle (\varepsilon \times c)}$-differentially private.

This could be generalized to group privacy, as the group size could be thought of as the Hamming distance ${\displaystyle h}$ between ${\displaystyle A}$ and ${\displaystyle B}$ (where ${\displaystyle A}$ contains the group and ${\displaystyle B}$ does not). In this case ${\displaystyle M\circ T}$ is ${\displaystyle (\varepsilon \times c\times h)}$-differentially private.

Publications

• Calibrating noise to sensitivity in private data analysis, Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. In Proceedings of the Third conference on Theory of Cryptography (TCC'06). Springer-Verlag, Berlin, Heidelberg, 265–284. https://doi.org/10.1007/11681878_14 (This is the original publication of Differential Privacy, and not the eponymous article by Dwork that was published the same year.)
• 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). https://doi.org/10.21428/2c646de5.7ec6ab93.

Tutorials

• A Practical Beginner's Guide To Differential Privacy by Christine Task, Purdue University, April 2012