<p>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:</p>

<ul>
<li><p><strong>Composition</strong>: If <span class="math-container">$A(\cdot)$</span> is an <span class="math-container">$\varepsilon$</span>-DP algorithm, and for any <span class="math-container">$a$</span> in the range of <span class="math-container">$A$</span>, <span class="math-container">$A'(\cdot, a)$</span> is an <span class="math-container">$\varepsilon'$</span>-DP algorithm, then the composed algorithm <span class="math-container">$A' \circ A$</span>, defined by <span class="math-container">$A'\circ A(D) = A'(D, A(D))$</span>, is <span class="math-container">$(\varepsilon + \varepsilon')$</span>-DP. </p></li>
<li><p><strong>Group Privacy</strong>: If <span class="math-container">$A$</span> is <span class="math-container">$\varepsilon$</span>-DP, then it satisfies <span class="math-container">$k\varepsilon$</span>-DP on pairs of data sets that differ in at most <span class="math-container">$k$</span> data points.</p></li>
</ul>

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

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

CC BY-SA 4.0
2019-09-09T18:04:37.013Z
2019-09-09T18:04:37.013Z
Sasho Nikolov
<p>For adjacent database <span class="math-container">$D,D'$</span>, a randomized algorithm <span class="math-container">$A$</span> is <span class="math-container">$\varepsilon$</span>-differential private when the following satisfies</p>

<p><span class="math-container">$$\frac{\Pr(A(D) \in S)}{\Pr(A(D') \in S)} \leq e^\varepsilon,$$</span> where <span class="math-container">$S$</span> is any range of A.</p>

<p>Why is the exponential function is used for the upper bounding?</p>

<p>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.</p>

<pr.probability><definitions><privacy>
Why is differential privacy defined over the exponential function?
user9414424
# Why is differential privacy defined over the exponential function?

(Asked by: username_0 on 2019-09-09)

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.

**Tags:** pr.probability, definitions, privacy


---

## 1 answers

### Answer by username_1 on 2019-09-09. Score: 11 | Accepted answer

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](https://arxiv.org/abs/1702.07476) [definitions](https://arxiv.org/abs/1605.02065) which put bounds on moments of $\ell\_{D, D'}(A(D))$, and correspond to bounding Renyi divergences between $A(D)$ and $A(D')$.


---

