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?
1 Answer
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.
-
$\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$ Apr 12, 2020 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$– MarkApr 12, 2020 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$– MarkApr 12, 2020 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$ Apr 12, 2020 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$– MarkApr 12, 2020 at 8:40