Диференційна приватність

Наприклад, у жовтні 2006 Netflix запропонував приз у 1 мільйон доларів США за покращення власної системи формування рекомендацій на 10%. Netflix також випустив тренувальний масив даних для змагання розробників. При випуску цього масиву даних Netflix зазначив, що для захисту приватності користувачів уся персональна інформація, що ідентифікує користувачів, та усі ідентифікатори користувачів замінені на випадкові ідентифікатори.

Netflix - не єдиний портал оцінювання кінофільмів у мережі, існують і інші, зокрема IMDb. На IMDb користувачі можуть реєструватись і оцінювати фільми без анонімізації. Arvind Narayanan та Vitaly Shmatikov, дослідники у University of Texas at Austin, поєднали анонімізований масив даних Netflix з базою даних IMDb (використовуючи дату оцінювання) і частково деанонімізували масив даних Netflix, скомпрометувавши ідентичність деяких користувачів[1].

Latanya Sweeney з Carnegie Mellon University поєднала анонімізовану базу даних (у якій зберігалися дата народження, стать та поштовий індекс кожного пацієнта) з записами виборців, і змогла визначити медичний запис губернатора штату Массачусетс[2].

De Montjoye та інші з MIT ввели поняття унікальності і показали, що 4 просторово-часових відмітки з приблизними моментами часу і просторовими координатами достатньо, щоб ідентифікувати 95% з 1,5 млн. людей з бази даних мобільних операторів[3] . Подальше дослідження показує, що ці обмеження мають місце навіть тоді, коли роздільна здатність набору даних є низькою, що означає, що навіть грубий або розмитий набір даних мобільних операторів та метадані забезпечують малу анонімність.

Диференційна приватність - це процес, який вносить випадковість у дані.

Простим прикладом, розробленим у соціальних науках,[6] є опитування осіб "Ви володієте атрибутом A?", за наступною процедурою:

1. Підкинути монетку.
2. Якщо випав аверс - відповісти чесно.
3. Якщо випав герб - підкинути монетку ще раз і відповісти "Так", якщо випав аверс, або "Ні", якщо випав герб.

Приватність забезпечується через забезпечення відмовності щодо індивідуальних відповідей.

Хоча ці дані з багатьма відповідями є значимими, позитивні відповіді дали чверть осіб, які не мали атрибута A і три чверті осіб, які володіють атрибутом A.

Якщо p справжня частка осіб з A, тоді буде отримано (1/4)(1-p) + (3/4)p = (1/4) + p/2 позитивних відповідей. Звідси можна обчислити p.

PS: зокрема, якщо володіння атрибутом A є синонімом незаконних дій, відповідь "Так" не є зізнанням у злочині, оскільки існує ненульова імовірність хибнопозитивної відповіді "Так".

Нехай ${\displaystyle d}$ є позитивним цілим, ${\displaystyle {\mathcal {D}}}$ є колекцією наборів даних, і ${\displaystyle f\colon {\mathcal {D}}\rightarrow \mathbb {R} ^{d}}$ є функцією. Чутливість [7] функції, позначена ${\displaystyle \Delta f}$, визначається як

${\displaystyle \Delta f=\max \lVert f(D_{1})-f(D_{2})\rVert _{1},}$ де максимум по усім парам наборів даних ${\displaystyle D_{1}}$ та ${\displaystyle D_{2}}$ у ${\displaystyle {\mathcal {D}}}$ , які відрізняються щонайменш у одному елементі і ${\displaystyle \lVert \cdot \rVert _{1}}$ позначається ${\displaystyle \ell _{1}}$ нормою.

У прикладі медичної бази даних вище, якщо ми приймемо ${\displaystyle f}$ є функцією ${\displaystyle Q_{i}}$, тоді чутливість функції дорівнює одиниці, оскільки зміна одного запису у базі даних призводить до зміни значення функції на нуль або одиницю.

Існують методи (описані нижче), використання яких дозволяє створювати диференційно приватний алгоритм для функцій з низькою чутливістю.

Компроміс між точністю статистики, отриманої із дотриманням приватності, і приватністю описується параметром ε.[8][9][10][11]

Для деяких застосувань властивість диференційної приватності є занадто суворою, тому запропоновані слабші версії властивостей приватності. Вони включають (ε, δ)-диференційну приватність,[12] рандомізовану диференційну приватність,[13] і приватність з метрикою.[14]

Багато диференційно приватних методів додають контрольований шум до функцій з низькою чутливістю.[7] Механізм Лапласа додає шум Лапласа (шум з розподілом Лапласа), який може бути виражений функцією щільності імовірності ${\displaystyle {\text{noise}}(y)\propto \exp(-|y|/\lambda )\,\!}$, яка має математичне сподівання, що дорівнює нулю, і стандартне відхилення ${\displaystyle \lambda \,\!}$). У нашому випадку визначено вихідну функцію від ${\displaystyle {\mathcal {A}}\,\!}$ як функцію з дійсними значеннями як ${\displaystyle {\mathcal {T}}_{\mathcal {A}}(x)=f(x)+Y\,\!}$ де ${\displaystyle Y\sim {\text{Lap}}(\lambda )\,\!\,\!}$ and ${\displaystyle f\,\!}$ є оригінальною функцією з дійсними значеннями, яку планувалося виконати над базою даних. Звідси ${\displaystyle {\mathcal {T}}_{\mathcal {A}}(x)\,\!}$ може бути представлена як неперервну випадкову змінну, де

${\displaystyle {\frac {\mathrm {pdf} ({\mathcal {T}}_{{\mathcal {A}},D_{1}}(x)=t)}{\mathrm {pdf} ({\mathcal {T}}_{{\mathcal {A}},D_{2}}(x)=t)}}={\frac {{\text{noise}}(t-f(D_{1}))}{{\text{noise}}(t-f(D_{2}))}}\,\!}$

де щонайменше ${\displaystyle e^{\frac {|f(D_{1})-f(D_{2})|}{\lambda }}\leq e^{\frac {\Delta (f)}{\lambda }}\,\!}$. Можна представити ${\displaystyle {\frac {\Delta (f)}{\lambda }}\,\!}$ як фактор приватності ${\displaystyle \epsilon \,\!}$. Таким чином ${\displaystyle {\mathcal {T}}\,\!}$ відповідає визначенню диференційно приватного механізму. Якщо застосувати цю концепцію до нашого прикладу з хворими на діабет, тоді це слідує з факту, що ${\displaystyle {\mathcal {A}}\,\!}$ як ${\displaystyle \epsilon \,\!}$-диференційно приватний алгоритм повинен мати ${\displaystyle \lambda =1/\epsilon \,\!}$. Хоча було використано шум Лапласа, можуть бути використані шуми з іншим розподілом (наприклад нормальним розподілом), але для цього потрібне деяке послаблення визначення диференційної приватності.[2]

Якщо запитати ε-диверенційно приватний механізм ${\displaystyle t}$ разів, і рандомізація механізму є незалежною для кожного запиту, тоді результат буде ${\displaystyle \epsilon t}$-диференційно приватним. У загальному випадку, якщо наявні ${\displaystyle n}$ незалежних механізмів: ${\displaystyle {\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{n}}$, чиї гарантії приватності є ${\displaystyle \epsilon _{1},\dots ,\epsilon _{n}}$ диференційно приватними, відповідно, тоді будь-яка функція ${\displaystyle g}$ від: ${\displaystyle g({\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{n})}$ є ${\displaystyle (\sum \limits _{i=1}^{n}\epsilon _{i})}$-диференційно приватною.[17]

Більш того, якщо попередні механізми обчислені над підмножинами, що не перетинаються, приватної бази даних, тоді функція ${\displaystyle g}$ є ${\displaystyle (\max _{i}\epsilon _{i})}$-диференційно приватною.[17]

Перетворення ${\displaystyle T}$ є ${\displaystyle c}$-стабільним, якщо відстань Геммінга між ${\displaystyle T(A)}$ та ${\displaystyle T(B)}$ є не більше ${\displaystyle c}$-разів відстані Геммінга між ${\displaystyle A}$ та ${\displaystyle B}$ для двох довільних баз даних ${\displaystyle A,B}$. Теорема 2 у [17] стверджує, що якщо існує механізм ${\displaystyle M}$ такий, що є ${\displaystyle \epsilon }$-диверенційно приватним, тоді складений механізм ${\displaystyle M\circ T}$ є ${\displaystyle (\epsilon \times c)}$-диференційно приватним.

Це може бути узагальнене для групової приватності, оскільки розмір групи може бути розглянуте як відстань Геммінга ${\displaystyle h}$ між ${\displaystyle A}$ та ${\displaystyle B}$ (де ${\displaystyle A}$ містить групу та ${\displaystyle B}$ не містить). У цьому випадку ${\displaystyle M\circ T}$ є ${\displaystyle (\epsilon \times c\times h)}$-диференційно приватним.