Theorem. Let q:X→Rq : \mathcal{X} \rightarrow \mathbb{R} be a real-valued query and M:X→YM : \mathcal{X} \rightarrow Y be an (ε,δ)(\varepsilon, \delta )-differentially private mechanism. Then

  1. For every x0∼x1∈Xx_0 ∼ x_1 \in \mathcal{X}, at least one of the following holds
Pr⁡[∣M(x0)−q(x0)∣<∣q(x0)−q(x1)∣2]≤1+δ1+e−ε=12+O(δ+ε). \Pr\left[ |M(x_0) − q(x_0)| < \frac{|q(x_0) − q(x_1)|}{2} \right] \le \frac{1 + \delta} {1 + e^{−\varepsilon}} = \frac{1}{2} + O( \delta + \varepsilon). Pr⁡[∣M(x1)−q(x1)∣<∣q(x0)−q(x1)∣2]≤1+δ1+e−ε=12+O(δ+ε). \Pr\left[ |M(x_1) − q(x_1)| < \frac{|q(x_0) − q(x_1)|}{2} \right] \le \frac{1 + \delta} {1 + e^{−\varepsilon}} = \frac{1}{2} + O( \delta + \varepsilon). \\

Corollary. For every x∈Xx \in \mathcal{X}, there is some x′x' at Hamming distance at most 11 from xx such that

Pr⁡[∣M(x′)−q(x′)∣<LSq(x)2]≤1+δ1+e−ε=12+O(δ+ε). \Pr\left[ |M(x') − q(x')| < \frac{LS_q(x)}{2} \right] \le \frac{1 + \delta} {1 + e^{−\varepsilon}} = \frac{1}{2} + O( \delta + \varepsilon). \\

Proof. Let

Gb={y∈R:∣y−q(xb)∣<∣q(x0)−q(x1)∣},∀b∈{0,1},p=min⁡{Pr⁡[M(x0)∈G0],Pr⁡[M(x1)∈G1]}. \begin{align*} G_b &= \left\{ y \in \mathbb{R} : |y − q(x_b)| < |q(x_0) − q(x_1)| \right\}, \quad \forall b \in \{0, 1\}, \\ p &= \min \{ \Pr[ M(x_0) \in G_0 ], \Pr[ M(x_1) \in G_1 ] \}. \end{align*}

To shed light on the final inequality, assume first that M(x0)M(x_0) and M(x1)M(x_1) have identical distributions. Then M(x0)∈G0M(x_0) \in G_0 and M(x1)∈G1M(x_1) \in G_1 are mutually disjoint events, and therefore at least one of them has probability at most 1/21 / 2.

In general, since M(x0)M(x_0) and M(x1)M(x_1) have similar distributions, we should expect similar results. We present two ways of deriving it.

First,

2⋅p≤Pr⁡[M(x0)∈G0]+Pr⁡[M(x1)∈G1]≤Pr⁡[M(x0)∈G0]+eεPr⁡[M(x0)∈G1]+δ≤Pr⁡[M(x0)∈G0]+eε(1−Pr⁡[M(x0)∈G0])+δ=eε+δ+(1−eε)⋅Pr⁡[M(x0)∈G0]. \begin{align*} 2 \cdot p &\le \Pr[ M(x_0) \in G_0 ] + \Pr[ M(x_1) \in G_1 ] \\ &\le \Pr[ M(x_0) \in G_0 ] + e^\varepsilon \Pr[ M(x_0) \in G_1 ] + \delta \\ &\le \Pr[ M(x_0) \in G_0 ] + e^\varepsilon \big(1 - \Pr[ M(x_0) \in G_0 ]\big) + \delta \\ &= e^\varepsilon + \delta + (1 - e^\varepsilon) \cdot \Pr[ M(x_0) \in G_0 ]. \end{align*}

Similarly, we have 2⋅p≤eε+δ+(1−eε)⋅Pr⁡[M(x1)∈G1]2 \cdot p \le e^\varepsilon + \delta + (1 - e^\varepsilon) \cdot \Pr[ M(x_1) \in G_1 ]. It follows that

2⋅p≤eε+δ+(1−eε)⋅p⟺p≤eε+δeε+1. 2 \cdot p \le e^\varepsilon + \delta + (1 - e^\varepsilon) \cdot p \Longleftrightarrow p \le \frac{e^\varepsilon + \delta}{e^\varepsilon + 1}.

Second Proof:

1−p≥Pr⁡[M(x0)∉G0]≥Pr⁡[M(x0)∈G1]≥e−ε⋅Pr⁡[M(x1)∈G1]−δ≥e−ε⋅p−δ. \begin{align*} 1 − p &\ge \Pr[ M(x_0) \notin G_0 ] \\ &\ge \Pr[ M(x_0) \in G_1] \\ &\ge e^{− \varepsilon} \cdot \Pr[ M(x_1) \in G_1 ] − \delta \\ &\ge e^{− \varepsilon} \cdot p − \delta. \end{align*}

Solving, we deduce that p≤(1+δ)/(1+e−ε)p \le (1 + \delta ) / (1 + e^{−\varepsilon}).

Third Proof: there is an alternative proof, which is quite close the proof of packing lower bound.

1≥Pr⁡[M(x0)∈G0]+Pr⁡[M(x0)∈G1]≥Pr⁡[M(x0)∈G0]+e−ε⋅(Pr⁡[M(x1)∈G1]−δ)≥(1+e−ε)⋅p−e−ε⋅δ. \begin{aligned} 1 &\ge \Pr[ M(x_0) \in G_0 ] + \Pr[ M(x_0) \in G_1]\\ &\ge \Pr[ M(x_0) \in G_0 ] + e^{− \varepsilon} \cdot (\Pr[ M(x_1) \in G_1 ] − \delta)\\ &\ge (1 + e^{− \varepsilon}) \cdot p − e^{− \varepsilon} \cdot \delta. \end{aligned}

It concludes that

p≤eε+δeε+1. p \le \frac{e^\varepsilon + \delta}{e^\varepsilon + 1}.

■\blacksquare

Reference

  1. Vadhan, Salil. “The Complexity of Differential Privacy.” 2017. https://doi.org/10.1007/978-3-319-57048-8_7.