differential-privacy: show $\epsilon$ -differentially privacy

Question

In this problem we consider a sensitive dataset $x \in \{−1, 1\}^n$. We consider the bounded setting where neighboring n-dimensional datasets differ in one coordinate. $A$ mechanism is available that supports statistical queries on x. Specifically, for a query $q \in \{−1, 1\}^n$ the mechanism computes the dot product $\langle x, q \rangle = \sum_{i=1}^n x_iq_i$ and releases $\langle x, q \rangle + z$ where $z \sim Lap(\lambda)$ is Laplace-distributed noise added to protect the privacy of individual entries of x.

My thoughts are that the $\langle x,q \rangle$ will differ between $-1$ and $1$, so we have $\{-1,1\}^n+z$ where $z \sim Lap(\lambda)$. Therefore when considering two databases $x_1, ..., x_n$ and $x_1, ..., x'_n$, we get that: $$ \begin{array}[ccc] \;\frac{P(m(x_1, \dots, x_n) = t)}{P(m(x_1, \dots, x'_n) = t)} & \leq & \exp(2/\lambda)\\ & = &\exp(\varepsilon) \end{array} $$ But I'm not sure if it correct? Especially not the inequality, why it should hold? Can anyone help?

Answer 1

You are indeed correct. What you describe is a more restricted case of the proof that a "Laplace mechanism" is $\varepsilon$-differentially private. Just so that we're all on the same page, here's a simplified definition of $\varepsilon$-differentially private (adapted from Dwork and Roth, The Algorithmic Foundations of Differential Privacy, Definition 2.4):

"A randomized algorithm $\mathcal{M}$ with domain $\mathbb{N}^{|\mathcal{X}|}$ is $\varepsilon$-differentially private if for all $\mathcal{S} \subseteq \text{Im}(\mathcal{M})$ and all $x, x' \in \mathbb{N}^{|\mathcal{X}|}$ where $\lVert x - x' \rVert_1 \leq 1$, $$\frac{P(\mathcal{M}(x) \in \mathcal{S})}{P(\mathcal{M}(x') \in \mathcal{S})} \leq \exp(\varepsilon)."$$

Intuitively, for a pair of datasets $x, x'$ of size $|\mathcal{X}|$ containing categorical data that differ in at most one location, "running" $\mathcal{X}$ on each dataset does not leak "too much information" (i.e., bounded above as a function of $\varepsilon$) about the difference between the two datasets. To check your intuition, consider what $\varepsilon$ would be if $x = x'$, and/or what it means for the LHS of the inequality to be large.

So, we know that $\mathcal{M}(x) \triangleq \langle q, x \rangle + z$ where $z$ is drawn from a mean-zero Laplace distribution with parameter $\lambda$. Choose any $q$ (conforming to your problem constraints). Using the Laplace PDF, we can write the LHS of the differential privacy definition (where $z$ is some realized value of a Laplace RV) as $$\frac{p_x(z)}{p_{x'}(z)} = \frac{(2\lambda)^{-1}\exp(-\lambda^{-1}|z - \langle q, x \rangle|)}{(2\lambda)^{-1}\exp(-\lambda^{-1}|z - \langle q, x' \rangle|)} = \exp\left(\lambda^{-1}(|z - \langle q, x' \rangle|-|z - \langle q, x \rangle|)\right).$$

After simplification, you will be able to bound this value from above by $\exp(2 / \lambda)$, which yields your desired result. I'd like to leave that as an exercise (it is mostly algebra), but feel free to ask for hints.

If you are still stuck, the solution (for a slightly more general version of your problem) can be found in Theorem 3.6 in Dwork and Roth. For further reading, I would consult the Dwork and Roth textbook.