(\(\epsilon\),\(\delta\))-Differential Privacy

In brief

A relaxed version of Differential Privacy, named (\(\epsilon\),\(\delta\))-Differential Privacy, allows a little privacy loss (\(\delta\)) due to a variation in the output distribution for the privacy mechanism.

More in Detail

Relaxing \(\epsilon\)-Differential Privacy

The (\(\epsilon\),\(\delta\))-differential privacy model is a common relaxation of \(\epsilon\)-differential privacy. Under the \(\epsilon\)-differential privacy model, the probabilities that the function \(\mathtt{f}\) outputs the same output when computed over neighboring datasets are allowed to diverge up to an \(e^\epsilon\) factor. The (\(\epsilon\),\(\delta\))-differential privacy model additionally tolerates the two probabilities to diverge by a small additional quantity, denoted \(\delta\).

This leads to revisiting the formal definition of \(\epsilon\)-differential privacy as follows. A random function \(\mathtt{f}\) with range \(\mathcal{O}\) satisfies (\(\epsilon\), \(\delta\))-differential privacy if and only if for all possible pairs of datasets (\(\mathcal{D}\), \(\mathcal{D}'\)) such that \(\mathcal{D}'\) is \(\mathcal{D}\) with one record more or one record less, and for all \(\mathcal{S} \subseteq \mathcal{O}\), then it holds that: \(\mathtt{Pr} [ \mathtt{f} ( \mathcal{D} ) \in \mathcal{S} ] \leq e^\mathbf{\epsilon} \times \mathtt{Pr} [ \mathtt{f} ( \mathcal{D}' ) \in \mathcal{S} ] + \delta\) where \(\epsilon>0\) and \(\delta \geq 0\) are the privacy parameters. When \(\delta>0\), (\(\epsilon\),\(\delta\))-differential privacy is also called approximate differential privacy.

Bibliography

The (\(\epsilon\),\(\delta\))-differential privacy model is introduced in [1] and thoroughly studied in [2].

1

Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: privacy via distributed noise generation. In EUROCRYPT. 2006.

2

Sebastian Meiser. Approximate and probabilistic differential privacy definitions. IACR Cryptol. ePrint Arch., 2018:277, 2018.

This entry was written by Tristan Allard.