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

Диференційна приватність — здатність забезпечувати максимальну точність запитів із статистичних баз даних при мінімізації імовірності ідентифікації їх записів.

Мотивація

Нехай існує довірена сторона, яка володіє масивом чутливих персональних даних (наприклад медичні записи, відомості щодо перегляду кіно або використання електронної пошти) і бажає надавати узагальнену статистичну інформацію про ці дані. Така система називається статистичною базою даних. Однак надання узагальненої статистичної інформації про дані може розкрити деяку інформацію щодо осіб. Дійсно, різноманітні ad-hoc підходи до анонімізації опублікованих записів були подолані, коли дослідники поєднували вміст двох або більше окремих баз даних. Диференційна приватність — це підхід для формалізації приватності у статистичних базах даних, запропонований для захисту від подібних методів деанонімізації.

Приз Netflix

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

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

База даних медичних випадків Комісії з групового страхування штату Массачусетс

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

Метадані та бази даних мобільних операторів

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

Огляд

У 2006, Cynthia Dwork визначила галузь диференційної приватності з використанням результатів роботи, початої у 2003. У цій роботі показано неможливість досягти семантичних цілей безпеки, що відносяться до роботи Tore Dalenius з 1970-х, і визначено нові методи для обмеження зростаючого ризику для персональних даних від їх включення до статистичної бази даних. Це дозволяє у багатьох випадках надати дуже точну статистику на підставі бази даних із забезпеченням високого рівня приватності.

Принцип та ілюстрація

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

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

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

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

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

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

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

Формальне визначення та приклад застосування

Нехай $\epsilon$ позитивне дійсне число і ${\mathcal {A}}$ є увипадковленим алгоритмом, який приймає набір даних на вході, що представляє дії довіреної сторони, яка розпоряджається даними. Нехай ${\textrm {im}}{\mathcal {A}}$ є образом відображення ${\mathcal {A}}$. Алгоритм ${\mathcal {A}}$ є $\epsilon$-диференційно приватним, якщо для всіх наборів даних $D_{1}$ та $D_{2}$, які відрізняються у єдиному елементі (даних щодо однієї особи), для всіх підмножин $S$ з ${\textrm {im}}{\mathcal {A}}$,

$\Pr[{\mathcal {A}}(D_{1})\in S]\leq e^{\epsilon }\times \Pr[{\mathcal {A}}(D_{2})\in S],$

де імовірність отримана з випадковості, яку використовує алгоритм.

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

Наприклад представимо, що ми маємо базу баних медичних записів $D_{1}$ де кожен запис є парою (Ім'я, X), де $X$ є булевою змінною, яка позначає наявність діабету у особи. Наприклад:

Ім'я	Наявність діабету (X)
Рос	1
Моніка	1
Джої	0
Фібі	0
Чендлер	1

Тепер припустимо, що зловимсний користувач (порушник) бажає визначити наявність діабету у Чендлера. Також припустимо, що порушник також знає у якому рядку бази даних розміщено запис Чендлера. Тепер припустимо, що порушнику дозволено використовуати тільки часткову форму запиту $Q_{i}$, яка повертає часткову суму перших $i$ рядків ствопчика $X$ у базі даних. Зазвичай, щоб визначити наявність діабету у Чендлера порушник виконує запити $Q_{5}(D_{1})$ та $Q_{4}(D_{1})$, потім обчислює їх різницю. У цьому прикладі $Q_{5}(D_{1})=3$, а $Q_{4}(D_{1})=2$, тому різниця дорівнює 1. Це означає, що у полі рядка Чендлера знаходиться 1. Це приклад показує, як може бути скомпрометована інформація про особу навіть без точного запиту щодо особи.

Продовжуючи цей приклад, якщо ми сконструюємо базу даних $D_{2}$ заміною (Чендлер, 1) на (Чендлер, 0), то порушник матиме можливість відрізнити $D_{2}$ від $D_{1}$ обчисленням $Q_{5}-Q_{4}$ для кожного набору даних. Якщо порушнику знадобиться отримати значення $Q_{i}$ використовуючи $\epsilon$-диференційно приватний алгоритм, для достатньо малого $\epsilon$, то він не зможе розрізнити два набори даних.

Чутливість

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

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

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

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

Компроміс між корисністю та приватністю

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

Інші нотації диференційної приватності

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

Диференційно приватні механізми

Оскільки диференційна приватність є імовірнісною концепцією, будь-який диференційно приватний механізм обов'язково є рандомізованим. Деякі з них, як механізм Лапласа, описаний нижче, покладаються на додавання контрольованого шуму до функції, яку потрібно обчислити. Інші, як еспоненційний механізм використовують післявибірку замість залежних від галузі використання розподілів.

Механізм Лапласа

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

${\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}))}}\,\!$

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

Поєднуваність

Послідовне поєднання

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

Паралельне поєднання

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

Групова приватність

У загальному випадку ε-диверенційна приватність створена для захисту приватності між базами даних, які відрізняються лише у одному рядку. Це означає, що жоден порушник із довільною допоміжною інформацією не може знати, чи один конкретний учасник надав свою інформацію. Тим не менше це також може бути поширене для потреби захисту баз даних, які відрізняються у $c$ рядках, де порушник із довільною допоміжною інформацією має можливість знати, що $c$ часткових учасників надали інформацію. Це може бути досягнуто тому що у випадку коли $c$ значень змінюються, ймовірність розширення обмежена $\exp(\epsilon c)$ замість $\exp(\epsilon )$, тобто для D₁ та D₂, які відрізняються у $c$ значеннях:

$\Pr[{\mathcal {A}}(D_{1})\in S]\leq \exp(\epsilon c)\times \Pr[{\mathcal {A}}(D_{2})\in S]\,\!$

Таким чином встановлення ε замість $\epsilon /c$ досягає бажаного результату (захисту $c$ значень). Іншими словами, замість ε-диференційно приватного захисту кожного значення, тепер група з $c$ значень є захищеною з параметром ε-диференційної приватності (і кожне значення є захищеним з параметром $(\epsilon /c)$-диференційної приватності).

Стабільні перетворення

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

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

Використання

Деякі використання, відомі на сьогодні:

• Бюро перепису населення США, для демонстрації шаблонів взаємодії,
• Google RAPPOR, для телеметрії та вивчення статистики щодо небажаного програмного забезпечення, яке перехоплює налаштування користувача (RAPPOR's open-source implementation [Архівовано 14 січня 2021 у Wayback Machine.]),
• Google, для поширення історичної статистики трафіку,
• 13 червня 2016 Apple оголосила про намір використовувати диференційну приватність у iOS 10 щоб покращити власну технологію персонального помічника,
• Виконані деякі початкові дослідження щодо практичної реалізації диференційної приватності у моделях дата-майнингу.

Посилання

• Differential Privacy [Архівовано 1 січня 2021 у Wayback Machine.] by Cynthia Dwork, ICALP July 2006.
• The Algorithmic Foundations of Differential Privacy [Архівовано 18 жовтня 2014 у Wayback Machine.] by Cynthia Dwork and Aaron Roth, 2014.
• Differential Privacy: A Survey of Results [Архівовано 5 березня 2010 у Wayback Machine.] by Cynthia Dwork, Microsoft Research, April 2008
• Privacy of Dynamic Data: Continual Observation and Pan Privacy [Архівовано 9 червня 2010 у Wayback Machine.] by Moni Naor, Institute for Advanced Study, November 2009
• Tutorial on Differential Privacy [Архівовано 14 липня 2014 у Wayback Machine.] by Katrina Ligett, California Institute of Technology, December 2013
• A Practical Beginner's Guide To Differential Privacy [Архівовано 8 травня 2012 у Wayback Machine.] by Christine Task, Purdue University, April 2012
• Private Map Maker v0.2 [Архівовано 3 грудня 2012 у Wayback Machine.] on the Common Data Project blog
• Learning Statistics with Privacy, aided by the Flip of a Coin [Архівовано 11 березня 2018 у Wayback Machine.] by Úlfar Erlingsson, Google Research Blog, October 2014