Sensibilité à la confidentialité différentielle

Question

Je souhaite vérifier ma connaissance de la sensibilité. Donc dans$\epsilon$-différentielle de confidentialité, le bruit est ajouté avec le mécanisme de Laplace en fonction de la sensibilité et du paramètre de perte de confidentialité. Laplace prend en compte la sensibilité globale et le bruit est mis à l'échelle sur la norme L1, ιn$\epsilon-\delta$confidentialité différentielle le bruit est ajouté avec un mécanisme gaussien qui considère la sensibilité locale et utilise la norme L2 comme une métrique, ai-je raison ou ai-je manqué quelque chose? Je pense que j'ai peut-être confondu les concepts.

Answer 1

Le livre de confidentialité différentielle est la référence typique pour la région, et il est très utile ici. Puisque cette réponse revient essentiellement à citer ce livre, je vais vous expliquer comment trouver les bonnes choses à citer.

Ctrl + F-ing "Laplace", on trouve le Théorème 3.6, qui stipule que le mécanisme de Laplace est $(\epsilon,0)$-différentiellement privé. Ce mécanisme ajoute iid$\mathsf{Lap}(\Delta f/\epsilon)$ bruit à la sortie, où (comme vous le mentionnez): $$\Delta f = \max_{\substack{x, y\in\mathbb{N}^{|\mathcal{X}|}\\\lVert x - y\rVert_1 = 1}} \lVert f(x) - f(y)\rVert_1$$ Donc c'est le $\ell_1$ version de la sensibilité.

Ctrl + F-ing "Gaussian", on voit que cela fonctionne pour la sensibilité définie 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$$ C'est un $\ell_2$ notion de sensibilité (mais notez que les "jeux de données voisins" $x, y$ sont toujours à moins de 1 l'un de l'autre dans le $\ell_1$norme, ce qui signifie qu’ils diffèrent toujours sur au plus une ligne). Le théorème 3.22 montre alors que pour être$(\epsilon, \delta)$ différentiellement privé, le mécanisme gaussien ajoute du bruit iid $\mathcal{N}(0, 2\ln(1.25/\delta) \Delta_2(f)^2/\epsilon^2)$ à la sortie de la fonction.