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

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

Мотивація

Нехай існує довірена сторона, яка володіє масивом чутливих персональних даних (наприклад медичні записи, відомості щодо перегляду кіно або використання електронної пошти) і бажає надавати узагальнену статистичну інформацію про ці дані. Така система називається статистичною базою даних. Однак надання узагальненої статистичної інформації про дані може розкрити деяку інформацію щодо осіб. Дійсно, різноманітні 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 є синонімом незаконних дій, відповідь «Так» не є зізнанням у злочині, оскільки існує ненульова імовірність хибнопозитивної відповіді «Так».

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

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

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

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

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

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

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

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

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

Чутливість

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

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

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

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

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

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

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

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

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

Багато диференційно приватних методів додають контрольований шум до функцій з низькою чутливістю. Механізм Лапласа додає шум Лапласа (шум з розподілом Лапласа), який може бути виражений функцією щільності імовірності ${\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 \,\!}$. Хоча було використано шум Лапласа, можуть бути використані шуми з іншим розподілом (наприклад нормальним розподілом), але для цього потрібне деяке послаблення визначення диференційної приватності.

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

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

Якщо запитати ε-диверенційно приватний механізм ${\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})}$-диференційно приватною.

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

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

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

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

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

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

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

Перетворення ${\displaystyle T}$ є ${\displaystyle c}$-стабільним, якщо відстань Геммінга між ${\displaystyle T(A)}$ та ${\displaystyle T(B)}$ є не більше ${\displaystyle c}$-разів відстані Геммінга між ${\displaystyle A}$ та ${\displaystyle B}$ для двох довільних баз даних ${\displaystyle A,B}$. Теорема 2 у стверджує, що якщо існує механізм ${\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)}$-диференційно приватним.

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

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

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

Посилання

1. , (2008). (PDF). . с. 111—125. Архів оригіналу (PDF) за 26 січня 2021. Процитовано 4 листопада 2017.
2. Differential Privacy by Cynthia Dwork, International Colloquium on Automata, Languages and Programming (ICALP) 2006, p. 1–12. DOI=10.1007/11787006_1
3. de Montjoye, Yves-Alexandre; César A. Hidalgo; Michel Verleysen; Vincent D. Blondel (25 березня 2013). . Nature srep. doi:10.1038/srep01376. Архів оригіналу за 11 серпня 2015. Процитовано 12 квітня 2013.
4. HILTON, MICHAEL. (PDF). Архів оригіналу (PDF) за 1 березня 2017. Процитовано 4 листопада 2017.
5. Dwork, Cynthia (25 квітня 2008). . У Agrawal, Manindra; Du, Dingzhu; Duan, Zhenhua; Li, Angsheng (ред.). Theory and Applications of Models of Computation. Lecture Notes in Computer Science (англ.). Springer Berlin Heidelberg. с. 1—19. doi:10.1007/978-3-540-79228-4_1. ISBN . Архів оригіналу за 27 лютого 2021. Процитовано 4 листопада 2017.
6. The Algorithmic Foundations of Differential Privacy by Cynthia Dwork and Aaron Roth. Foundations and Trends in Theoretical Computer Science. Vol. 9, no. 3–4, pp. 211‐407, Aug. 2014. DOI=10.1561/0400000042
7. Calibrating Noise to Sensitivity in Private Data Analysis by Cynthia Dwork, Frank McSherry, Kobbi Nissim, Adam Smith In Theory of Cryptography Conference (TCC), Springer, 2006. DOI=10.1007/11681878_14
8. A. Ghosh, T. Roughgarden, and M. Sundararajan. Universally utility-maximizing privacy mechanisms. In Proceedings of the 41st annual ACM Symposium on Theory of Computing, pages 351–360. ACM New York, NY, USA, 2009.
9. H. Brenner and K. Nissim. Impossibility of Differentially Private Universally Optimal Mechanisms. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2010.
10. R. Chen, N. Mohammed, B. C. M. Fung, B. C. Desai, and L. Xiong. Publishing set-valued data via differential privacy. The Proceedings of the VLDB Endowment (PVLDB), 4(11):1087-1098, August 2011. VLDB Endowment.
11. N. Mohammed, R. Chen, B. C. M. Fung, and P. S. Yu. Differentially private data release for data mining. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD), pages 493-501, San Diego, CA: ACM Press, August 2011.
12. Dwork, Cynthia, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. "Our data, ourselves: Privacy via distributed noise generation." In Advances in Cryptology-EUROCRYPT 2006, pp. 486-503. Springer Berlin Heidelberg, 2006.
13. Hall, Rob, Alessandro Rinaldo, and Larry Wasserman. "Random differential privacy." arXiv preprint arXiv:1112.2680 (2011).
14. Chatzikokolakis, Konstantinos, Miguel E. Andrés, Nicolás Emilio Bordenabe, and Catuscia Palamidessi. "Broadening the scope of Differential Privacy using metrics." In Privacy Enhancing Technologies, pp. 82-102. Springer Berlin Heidelberg, 2013.
15. (PDF). Архів оригіналу (PDF) за 7 березня 2016. Процитовано 28 січня 2018.
16. . Архів оригіналу за 16 листопада 2017. Процитовано 28 січня 2018.
17. Privacy integrated queries: an extensible platform for privacy-preserving data analysis by Frank D. McSherry. In Proceedings of the 35th SIGMOD International Conference on Management of Data (SIGMOD), 2009. DOI=10.1145/1559845.1559850
18. Ashwin Machanavajjhala, Daniel Kifer, John M. Abowd, Johannes Gehrke, and Lars Vilhuber. "Privacy: Theory meets Practice on the Map". In Proceedings of the 24th International Conference on Data Engineering, (ICDE) 2008.
19. Úlfar Erlingsson, Vasyl Pihur, Aleksandra Korolova. "RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response". In Proceedings of the 21st ACM Conference on Computer and Communications Security (CCS), 2014.
20. Tackling Urban Mobility with Technology by Andrew Eland. Google Policy Europe Blog, Nov 18, 2015.
21. . Apple. Архів оригіналу за 15 червня 2016. Процитовано 16 червня 2016.
22. Fletcher, Sam; Islam, Md Zahidul (July 2017). Differentially private random decision forests using smooth sensitivity. Expert Systems with Applications. 78: 16—31. doi:10.1016/j.eswa.2017.01.034.

Посилання

• 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 , 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