Introduction

Let’s start introducing the mathematical definition of ε-differential privacy:

Definition (ε-differential privacy).

A randomized algorithm \(\mathcal{M}\), with domain \(\mathcal{D}\) and range \(\mathcal{R}\), satisfies ε-differential privacy if for any two adjacent inputs \(Y, Y' \in \mathcal{D}\) and for any subset of outputs \(S \subseteq \mathcal{R}\) it holds that

\[\mathbb{P}[\mathcal{M}(Y)\in S] \leq e^{\epsilon}\,\mathbb{P}[\mathcal{M}(Y')\in S],\]

with \(\epsilon \geq 0\).

Definition (ε-differential privacy).

A randomized algorithm \(\mathcal{M}\), with domain \(\mathcal{D}\) and range \(\mathcal{R}\), satisfies ε-differential privacy if for any two adjacent inputs \(Y, Y' \in \mathcal{D}\) and for any subset of outputs \(S \subseteq \mathcal{R}\) it holds that

\[\mathbb{P}[\mathcal{M}(Y)\in S] \leq e^{\epsilon}\,\mathbb{P}[\mathcal{M}(Y')\in S],\]

with \(\epsilon \geq 0\).

In this definition the value of \(\epsilon\) is the privacy budget, which is the parameter used to control the level of privacy.

Then, we can introduce the definition of (ε, δ)-differential privacy), which incoporated a parameter \(\delta\) that represents the probability of exceeding the privacy budget:

Definition ((ε, δ)-differential privacy).

Let \(\mathcal{M}\) be a randomized algorithm with domain \(\mathcal{D}\) and range \(\mathcal{R}\). It satisfies (ε, δ)-differential privacy if for any two adjacent inputs \(Y, Y' \in \mathcal{D}\) and for any subset of outputs \(S \subseteq \mathcal{R}\) it holds that

\[\mathbb{P}[\mathcal{M}(Y)\in S] \leq e^{\epsilon}\,\mathbb{P}[\mathcal{M}(Y')\in S] + \delta,\]

with \(\epsilon \geq 0\) and \(\delta \in [0,1]\).