Introduction to Differential Privacy
Table of Contents
Differential privacy is widely regarded as the gold standard for privacy protection in statistical analysis and dataset releases. Its strength lies in providing a formal and mathematical definition of privacy, offering precise and provable guarantees.
1. Desiderata for Strong Privacy Definition
- Compositionality. A good privacy definition should ensure that its protection gradually degrade when applied multiple times, instead of drastically collapse.
- Post-processing immunity. After data has been privatized with a privacy-preserving mechanism, any further data analysis should not degrade its privacy guarantees.
- Group privacy. The privacy mechanism does not arbitrarily fail to protect privacy beyond the individual level when data from multiple users is combined.
- Quantifiable privacy-accuracy trade-offs.
2. Definition of DP
A more precise requirement: information obtained from dataset with individual data, cannot be more than information from dataset without individual data. (There shouldn’t be much new information gained from joining new individual data). DP is more like an requirement for privacy, rather than some algorithm.
2.1. Distributed or Central Models for DP
In centralized models, all data collection, storage and processing happen at a single and central location by a trusted data curator. The assumption is that the data curator will faithfully protect individual privacy and handle data responsibly.
The centralized settings trade trust for data utility and algorithmic flexibility, since the center has access to the raw data.
In distributed (local) models, data are kept de-centralized at each client. Privacy-preserving algorithms are executed locally and only privatized data will be communicated to the central authority.
The distributed settings are, however, the contrast that introduces additional complexity in implementing privacy-preserving protocols. In addition, the aggregated results may suffer from accuracy-reduced individual data due to accumulation of noise.
2.2. Formal Definition, Techniques and Properties
DP is a mathematical framework for measuring and bounding the individuals’ privacy risks in a computation. A mechanism is considered differentially private if the probability of any outcome occurring is nearly the same for any two datasets that differ in only one record.
- Dataset
- A dataset \(D\) is a multiset of elements in the data universe \(\mathcal{U}\). The set of every possible dataset is denoted \(\mathcal{D}\). The data universe \(\mathcal{U}\) is a cross product of multiple attributes \(U_1,U_2, \dots, U_{n}\) and has dimension \(n\).
- Numeric Query
- A numeric query is a function \(f:\mathcal{D}\mapsto\mathcal{R},\mathcal{R}\subseteq \mathbb{R}^{r}\) that maps a dataset in some real vector space. For example, the function could be an SQL statement that counts the individuals.
2.2.1. Adjacency
The concept of adjacency is fundamental in DP. It frames the unit of change that DP seeks to protect against, ensuring that the presence or absense of any single individual’s data does not significantly alter the outcomes of data analysis. There 2 common ways to define adjacency in the context of DP:
- Add (remove) adjacency
- Two datasets \(D,D'\) are said adjacent under the add/remove notion, denoted as \(D\sim D'\), if \(|D\Delta D'|=1\) where \(\Delta\) is the symmetric difference of two sets.
- Exchange adjacency
- Two datasets \(D,D'\) are said adjacent under exchange notion, denoted as \(D\sim_{\leftrightarrows}D'\), if \(D'\) is obtained from \(D\) by successively removing one record and adding a (possibly different) record. That is, there exist elements \(d\in D\) and \(d'\in \mathcal{U}\) such that \(D' = (D-\set{d})\cup \set{d'}\). This implies that \(|D| = |D'|\) and \(|D\Delta D'| = 2\)
2.2.2. Gloval Sensitivity
The choice of add/remove or exchange adjacency has implications for how DP is applied, as it directly addects the computation of global sensitivity, which measures the *maximum change in the output of a function for adjacent datasets.
- Global Sensitivity
- The impact of a single individual’s data on the overall analysis is measured through the concept of global sensitivity. Formally, the global sensitivity of a function \(f:\mathcal{D}\mapsto \mathcal{R}\) is defined as the maximum difference in the output over \(f\) over all pairs of adjacent datasets \(D\sim D'\in \mathcal{D}\), measured w.r.t. to \(\ell_{p}\) norm
\[ \Delta_{p} f = \max_{D\sim D'} \Vert f(D)-f(D') \Vert_{p} \]
In simpler terms, it measures how much the output of a function can change when an individual’s data is added or removed from the dataset. This measurement provides a basis for determining the amount of noise that needs to be added to the function’s output to achieve privacy.
2.2.3. Mathematical Definition of DP
The sensitivity measurement tells us how much the output of the target function need to be adjusted to protect an individual’s privacy. DP achieves this by adding noise to the function’s output by an amount calibrated to the function sensitivity.
- Differential Privacy
- A randomized mechanism \(\mathcal{M}:\mathcal{D}\mapsto\mathcal{R}\) with domain \(\mathcal{D}\) and range \(\mathcal{R}\) is \((\epsilon,\delta)\)-differentially private if for any event \(S \subseteq \mathcal{R}\) and any pair \(D,D'\in\mathcal{D}\) of adjacent datasets:
A DP mechanism maps a dataset to a distribution over the possible outputs. The released DP output is a single random sample drawn from this distribution. The level of privacy is controlled by \(\epsilon\), called privacy loss, with values close to \(0\) denoting strong privacy. The secondary \(\delta\) can be loosely interpreted as a margin of error.
In DP, \((\epsilon,0)\)-DP is satisfied for any pair \(D,D'\).
With the definition of DP, we can prove that this DP satisfies compositionality, group privacy, post-processing.
2.3. Approximate DP
DP with \(\delta=0\) is called pure DP, while \(\delta\gt 0\) is called approximate DP. Examples include [BROKEN LINK: 0230d137-15b1-407f-b805-6212d4378d9d].