Sensitivitas pada privasi diferensial

Question

Saya ingin memverifikasi pengetahuan saya tentang kepekaan. Jadi masuk$\epsilon$privasi -differential, kebisingan ditambahkan dengan mekanisme Laplace tergantung pada sensitivitas dan parameter hilangnya privasi. Laplace memperhitungkan sensitivitas global dan kebisingan diskalakan pada norma L1, ιn$\epsilon-\delta$privasi diferensial kebisingan ditambahkan dengan mekanisme Gaussian yang mempertimbangkan sensitivitas lokal dan menggunakan norma-L2 sebagai metrik apakah saya benar atau apakah saya melewatkan sesuatu? Saya pikir mungkin saya bingung entah bagaimana konsepnya.

Answer 1

The book privasi diferensial adalah referensi khas untuk wilayah, dan cukup berguna di sini. Karena jawaban ini pada dasarnya sama dengan mengutip dari buku itu, saya akan menjelaskan cara menemukan hal yang tepat untuk dikutip.

Ctrl + F-ing "Laplace", kita temukan Teorema 3.6, yang menyatakan bahwa mekanisme Laplace adalah $(\epsilon,0)$-differentially private. Mekanisme ini menambahkan iid$\mathsf{Lap}(\Delta f/\epsilon)$ kebisingan ke output, di mana (seperti yang Anda sebutkan): $$\Delta f = \max_{\substack{x, y\in\mathbb{N}^{|\mathcal{X}|}\\\lVert x - y\rVert_1 = 1}} \lVert f(x) - f(y)\rVert_1$$ Jadi ini $\ell_1$ versi sensitivitas.

Ctrl + F-ing "Gaussian", kita melihat bahwa itu bekerja untuk sensitivitas yang ditentukan melalui: $$\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$$ Ini adalah sebuah $\ell_2$ pengertian tentang sensitivitas (meskipun perhatikan bahwa "set data tetangga" $x, y$ masih dalam 1 dari satu sama lain di $\ell_1$norma, artinya mereka masih berbeda paling banyak satu baris). Teorema 3.22 kemudian menunjukkan bahwa menjadi$(\epsilon, \delta)$ privat yang berbeda, mekanisme Gaussian menambahkan derau iid $\mathcal{N}(0, 2\ln(1.25/\delta) \Delta_2(f)^2/\epsilon^2)$ ke keluaran fungsi.