Adding the same noise to all element of a vector is Differential privacy

Question

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?

Answer 1

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.