Differential Privacy

For two datasets D and D' that differ in at most one element, a randomized algorithm $M$ guarantees \emph{$(\epsilon, \delta)$-differential privacy} for any subset of the output $S$ if $M$ satisfies: \begin{equation} Pr[M(D) \in S] \leq exp(\epsilon)*Pr[M(D') \in S] + \delta \end{equation} Furthermore, when $\delta = 0$ an algorithm M is said to guarantee \emph{$\epsilon$-differential privacy}

Differential privacy is a method for measuring how much information the output of a computation reveals about an individual. It is based on the randomised injection of "noise". Noise is a random alteration of data in a dataset so that values such as direct or indirect identifiers of individuals are harder to reveal. An important aspect of differential privacy is the concept of “epsilon” or ɛ, which determines the level of added noise. Epsilon is also known as the “privacy budget” or “privacy parameter”.