2
$\begingroup$

For adjacent database $D,D'$, a randomized algorithm $A$ is $\varepsilon$-differential private when the following satisfies

$$\frac{\Pr(A(D) \in S)}{\Pr(A(D') \in S)} \leq e^\varepsilon,$$ where $S$ is any range of A.

Why is the exponential function is used for the upper bounding?

Is that related to Chernoff's inequality? Since most of the textbooks that I have ever seen do not explain why the exponential is used, I have no idea about that.

$\endgroup$
8
$\begingroup$

This answer may be disappointing, but working on a log scale really mostly just makes the formulas nicer. The definition, as written, has the following important properties:

  • Composition: If $A(\cdot)$ is an $\varepsilon$-DP algorithm, and for any $a$ in the range of $A$, $A'(\cdot, a)$ is an $\varepsilon'$-DP algorithm, then the composed algorithm $A' \circ A$, defined by $A'\circ A(D) = A'(D, A(D))$, is $(\varepsilon + \varepsilon')$-DP.

  • Group Privacy: If $A$ is $\varepsilon$-DP, then it satisfies $k\varepsilon$-DP on pairs of data sets that differ in at most $k$ data points.

It may be more natural to define $\varepsilon$-DP with $(1+\varepsilon)$ in place of $e^\varepsilon$, but then the formulas above would be far less nice. There is no real connection with Chernoff bounds here.

Another reason is that this definition makes it more clear how the differential privacy definition is related to divergences between distributions. To see what I mean, let me define the privacy loss of an output $a$ of an algorithm $A$ (with respect to datasets $D$ and $D'$) as $$ \ell_{D, D'}(a) = \log\left( \frac{\Pr[A(D) = a]}{\Pr[A(D') = a]}\right). $$ Then, the expectation $\mathbb{E}[\ell_{D, D'}(A(D))]$ is simply the KL-divergence between $A(D)$ and $A(D')$. The differential privacy condition asks that this KL-divergence is bounded by $\varepsilon$, but in fact it asks much more: that the random variable $\ell_{D, D'}(A(D))$ is bounded by $\varepsilon$ everywhere in its support. There are also intermediate definitions which put bounds on moments of $\ell_{D, D'}(A(D))$, and correspond to bounding Renyi divergences between $A(D)$ and $A(D')$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.