In Differential privacy, if we add a $N$-dimension private vector with $N$-dimension Laplace or Gauss noise, we obtain differential privacy. However, if we only generate a 1-dimension noise to add it to all element of private vector, can we obtain differential privacy?


This cannot possibly be differentially private. Recall than a randomized algorithm $\mathcal{A}$ is $\epsilon$-differentially private if, for all datasets $D_1$ and $D_2$ that differ in a single entry, and all subsets $S\subseteq\mathsf{im}(\mathcal{A})$, that: $$\Pr[\mathcal{A}(D_1)\in S] \leq \exp(\epsilon)\Pr[\mathcal{A}(D_2)]$$

Let $\mathcal{A}$ be your proposed mechanism, which samples $e\sim \mathcal{D}$ for some distribution $\mathcal{D}$, then maps $v \mapsto v + e(1,1,\dots,1)$. Let $S = \{v\in\mathbb{R}^n \mid v_1 = v_2\}$ be the set of all vectors such that their first two coordinates are equal (any pair of coordinates suffices).

Identify datasets with vectors in $\mathbb{R}^n$, as this seems to be your use case. Let $D_2 = (v_1, v_2,\dots, v_n)$, and let $D_1 = (v_1, v_1, v_3,\dots, v_n)$. Note that these differ in a single entry (their second entry).

We have that $\Pr[\mathcal{A}(D_1)\in S] = 1$, but $\Pr[\mathcal{A}(D_2)\in S] = 0$, so the inequality cannot hold.

Note that the above makes no restrictions on the entries of your datasets (a prior answer had them in $\{0,1\}^n$), nor does it make any restrictions on the error distribution $\mathcal{D}$. So your optimization cannot ever be differentially private.

| improve this answer | |
  • $\begingroup$ Thank you very much. But i do not know clearly why $e=M-m$. I think this case is very similar to Caesar-like ciphers with many-time-pad random key $e$, but i'm not sure about its security. $\endgroup$ – eclipse140790 Apr 12 at 7:32
  • $\begingroup$ This is because of the assumption that $v\in\{0,1\}^n$ (try writing out a particular choice of $v$ if you're still confused). $\endgroup$ – Mark Apr 12 at 7:49
  • $\begingroup$ There are similarities with the OTP under key re-use (in particular, releasing statistics via the mechanism $v \mapsto v + e(1,1,\dots,1)$ leaves the function $f(i,j) = \delta_{v_i = v_j}$ invariant in both cases, which causes issues in both cases). But the similarities are not exact --- key to the proof that the OTP is perfectly secret is the fact that the message space is finite. No such restrictions are generally made in differential privacy, and moreover you don't want a "perfect" notion of security (if the input is "perfect"ly kept private you cannot compute useful statistics). $\endgroup$ – Mark Apr 12 at 7:53
  • $\begingroup$ Oh, I got it. But what about if $v \in \mathcal{D}\subseteq \mathbb{R}^n$ and also $e \in[c,d]\subseteq \mathbb{R}$. In my problem i need not to recover any statistics property of $v$. I only want it to be secure? Can i do as above? If can, how can i prove that? $\endgroup$ – eclipse140790 Apr 12 at 8:02
  • $\begingroup$ If you only want it to be "secure", map every $v\in\mathcal{D}$ to $0$. If this solution doesn't work for your application (which I doubt it will), you do need to recover some statistical properties of $v$ (as this is the entire reason for using differential privacy in the first place). If you truly don't need to, using differential privacy gains you nothing in practice. $\endgroup$ – Mark Apr 12 at 8:40

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.