Propose-Test-Release

Let $(\mathcal{X}, d)$ be a metric space and $q : \mathcal{X} \rightarrow \mathbb{R}$ be a function defined on $\mathcal{X}$. The metric $d: \mathcal{X} \rightarrow \mathbb{N}$ takes only integer values. For an $x \in \mathcal{X}$, it neighbors an $x' \in \mathcal{X}$, termed $x \sim x'$, if $d(x, x') = 1$.

Further, define the global sensitivity $\Delta$ of $q$ as:

The Laplace mechanism $M$ of $q$ adds random noise $N \sim \mathbb{Lap}(\frac{\Delta}{\varepsilon})$ to the output of $q$:

where $\mathbb{Lap}(\frac{\Delta}{\varepsilon})$ is the Laplacian distribution with parameter $\frac{\Delta}{\varepsilon}$. It guarantees that if $x \sim x'$, the output distributions of $M(x)$ and $M(x')$ are indistinguishable in the sense that for all $S \subset \mathbb{R}$, s.t. $S$ is measurable, it holds that

The value of $\Delta$ could be large and is independent of an $x \in \mathcal{X}$. We would like to investigate the possibility of adding a smaller noise than $\mathbb{Lap}(\frac{\Delta}{\varepsilon})$.

For a fixed $x$, we can define the local sensitivity with respect to $x$ as

Here the maximum is over the neighbors of a fixed $x$. The value between $\Delta$ and $\delta(x)$ is quite different.

Example. Let

• $\mathcal{X} \doteq [0, 100]^3$.
• $d(x, x')\doteq \#\text{ different values between } x \text{ and } x'$.
• $q(x) \doteq \min_{1 \le i < j \le 3} |x_i - x_j|$, where $x_i$ is the $i$-dimension of $x$.

Then for the point $x = (0, 0, 0) \in [0, 100]^3$, if $x' \sim x$, $x'$ contains at least two zeros in some of its dimensions. Therefore, $q(x') = 0$ and $\delta(x) = 0$. But for $x = (0, 0, 100)$, it has a neighbor $x' = (0, 50, 100)$. Now $q(x) = 0$ but $q(x') = 50$. So $\Delta \ge \delta(x) \ge 50$.

We are interested in whether adding smaller noise $N \sim \mathbb{Lap}(\frac{\delta(x) }{\varepsilon})$ to the output of $q(x)$ would preserve privacy:

However, this approach is not private. In the previous example, $(0, 0, 0)$ and $(0, 0, 100)$ are neighbors. But for the former we add noise $N \sim \mathbb{Lap}(0)$ and for the latter we add noise $N \sim \mathbb{Lap}(\frac{50}{\varepsilon})$. So the output distributions of them are very different and this would violate privacy protection.

Perhaps, we should propose some fixed parameter $\beta > 0$ (which could be much smaller than $\Delta$), and add a noise $N \sim \mathbb{Lap}(\frac{\beta}{\varepsilon})$ for whatever $x \in \mathcal{X}$. For a pair of neighboring $x, x'$, when $|q(x) - q(x')| \le \beta$, then the distributions of $q(x) + N$ and $q(x') + N$ are indeed $(\varepsilon, 0)$ indistinguishable. The only concern is for the case where $|q(x) - q(x')| > \beta$ and adding a noise $N \sim \mathbb{Lap}(\frac{\beta}{\varepsilon})$ fails to protect the privacy.

One simple remedy is simply to refuse to output $q(x) + N$ (or $q(x) + N'$). This should be done in a differentially private manner. Let

be the set of points with local sensitivity greater than $\beta$. For a fixed $x$, define $d(x, \{ y : \delta(y) > \beta \})$ be its distance to the set. It follows that for $x \sim x'$,

This motivates the following propose-test-release algorithm.

1. Propose a bound $\beta$ on local sensitivity.
2. Compute $\hat d \doteq d(x, \{ y \in \mathcal{X} : \delta(y) > \beta \}) + \mathbb{Lap}(1 / \varepsilon)$.
3. If $\hat d \le \frac{1}{\varepsilon} \ln \frac{1}{\gamma}$ then
   $\qquad$ output $\bot$.
4. Else
   $\qquad$ output $q(x) + \mathbb{Lap}(\beta / \varepsilon)$.

Theorem. The algorithm is $(2\varepsilon, \gamma / 2)$ differentially private.

Proof.

First observe that for two neighboring $x, x'$, their probabilities of outputting $\bot$ are similar.

Now consider a measurable set $S \subset \mathbb{R}$. $M(x) \in S$ is only possible when $\hat d > \frac{1}{\varepsilon} \ln \frac{1}{\gamma}$:

We consider two cases.

• Case 1. When $\delta(x) > \beta$, then $d(x, \{ y \in \mathcal{X} : \delta(y) > \beta \}) = 0$. It follows that

  $$\Pr[M(x) \in S] \le \Pr[M(x) \neq \bot ] \le \frac{\gamma}{2}$$

• Case 2. When $\delta(x) \le \beta$, it holds that $|q(x) - q(x') |\le \beta$ and

  $$\Pr[ M(x) \in S \mid M(x) \neq \bot ] \le e^\varepsilon \cdot \Pr[ M(x') \in S \mid M(x') \neq \bot ]$$

  Therefore,

  $$\begin{aligned} \Pr[M(x) \in S] &= \Pr[ M(x) \in S \mid M(x) \neq \bot ] \cdot \Pr[ M(x) \neq \bot] \\ &\le \Pr[ M(x) \in S \mid M(x) \neq \bot ] \cdot e^\varepsilon \cdot \Pr[ M(x') \neq \bot] \\ &\le e^\varepsilon \cdot \Pr[ M(x') \in S \mid M(x') \neq \bot ] \cdot e^\varepsilon \cdot \Pr[ M(x') \neq \bot] \\ &= e^{2\varepsilon} \Pr[ M(x') \in S]. \end{aligned}$$

$\blacksquare$

Reference

[1] S. Vadhan, “The Complexity of Differential Privacy,” in Tutorials on the Foundations of Cryptography, Y. Lindell, Ed. Cham: Springer International Publishing, 2017, pp. 347–450.