I want to verify my knowledge of sensitivity. So in $\epsilon$-differential privacy, the noise is added with the Laplace mechanism depending on the sensitivity and the privacy loss parameter. Laplace takes into account the global sensitivity and the noise is scaled on the L1-norm, ιn $\epsilon-\delta$ differential privacy the noise is added with Gaussian mechanism which considers the local sensitivity and uses the L2-norm as a metric am I right or did I miss something? I think that maybe I have confused somehow the concepts.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The differential privacy book is the typical reference for the area, and it is quite useful here. Since this answer essentially amounts to quoting from that book, I'll walk through how to find the right things to quote.
Ctrl+F-ing "Laplace", we find Theorem 3.6, which states that the Laplace mechanism is $(\epsilon,0)$-differentially private. This mechanism adds i.i.d. $\mathsf{Lap}(\Delta f/\epsilon)$ noise to the output, where (as you mention): $$\Delta f = \max_{\substack{x, y\in\mathbb{N}^{|\mathcal{X}|}\\\lVert x - y\rVert_1 = 1}} \lVert f(x) - f(y)\rVert_1$$ So this is the $\ell_1$ version of sensitivity.
Ctrl+F-ing "Gaussian", we see that it works for sensitivity defined via: $$\Delta_2 f = \max_{\substack{x, y\in\mathbb{N}^{|\mathcal{X}|}\\\lVert x - y\rVert_1 = 1}} \lVert f(x) - f(y)\rVert_2$$ This is an $\ell_2$ notion of sensitivity (although note that "neighboring datasets" $x, y$ are still within 1 of eachother in the $\ell_1$ norm, meaning they still differ in at most one row). Theorem 3.22 then shows that to be $(\epsilon, \delta)$ differentially private, the Gaussian mechanism adds i.i.d. noise $\mathcal{N}(0, 2\ln(1.25/\delta) \Delta_2(f)^2/\epsilon^2)$ to the output of the function.
