Problem Setting

When distributing some data calculated from a dataset publicly, we need to ensure that any malicious party cannot recover from the released data any information about personal data in the original dataset. Mathematically speaking, we need to ensure that our algorithm has Differential Privacy.

First, we need to define a special pair of sets called neighbouring set:

Definition 1 (Neighbouring Sets) Two sets $S,S^{\prime }$ are neighbouring sets iff there exists $\pi :[|S|]\to S,{\pi }^{\prime }:[|S^{\prime }|]\to S^{\prime }$ such that $\mathrm{\exists }!n\pi (n)\ne {\pi }^{\prime }(n)$, or that $S$ and $S^{\prime }$ differs only by one element.

With this definition, we could define DP:

Definition 1 (Differential Privacy) Let A be a randomized algorithm, $A:X^n\to R$, with input $D$, we say $A$ satisfies $ϵ$-differential privacy if for all neighboring sets $D,D\prime \in X^n$, and all set $S\subseteq A(X^n)$, we have $$\begin{array}{}\text{(1)}& \underset{x\in D}{P}(A(x)\in S)\le e^{ϵ}\underset{x\in D^{\prime }}{P}(A(x)\in S)\end{array}$$