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

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

Мотивація

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

Приз Netflix

Наприклад, у жовтні 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] . Подальше дослідження показує, що ці обмеження мають місце навіть тоді, коли роздільна здатність набору даних є низькою, що означає, що навіть грубий або розмитий набір даних мобільних операторів та метадані забезпечують малу анонімність.

Огляд

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Продовжуючи цей приклад, якщо ми сконструюємо базу даних заміною (Чендлер, 1) на (Чендлер, 0), то порушник матиме можливість відрізнити від обчисленням для кожного набору даних. Якщо порушнику знадобиться отримати значення використовуючи -диференційно приватний алгоритм, для достатньо малого , то він не зможе розрізнити два набори даних.

Чутливість

Нехай є позитивним цілим, є колекцією наборів даних, і є функцією. Чутливість [7] функції, позначена , визначається як

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

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

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


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

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

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

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

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

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

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

Багато диференційно приватних методів додають контрольований шум до функцій з низькою чутливістю.[7] Механізм Лапласа додає шум Лапласа (шум з розподілом Лапласа), який може бути виражений функцією щільності імовірності , яка має математичне сподівання, що дорівнює нулю, і стандартне відхилення ). У нашому випадку визначено вихідну функцію від як функцію з дійсними значеннями як де and є оригінальною функцією з дійсними значеннями, яку планувалося виконати над базою даних. Звідси може бути представлена як неперервну випадкову змінну, де

де щонайменше . Можна представити як фактор приватності . Таким чином відповідає визначенню диференційно приватного механізму. Якщо застосувати цю концепцію до нашого прикладу з хворими на діабет, тоді це слідує з факту, що як -диференційно приватний алгоритм повинен мати . Хоча було використано шум Лапласа, можуть бути використані шуми з іншим розподілом (наприклад нормальним розподілом), але для цього потрібне деяке послаблення визначення диференційної приватності.[2]

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

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

Якщо запитати ε-диверенційно приватний механізм разів, і рандомізація механізму є незалежною для кожного запиту, тоді результат буде -диференційно приватним. У загальному випадку, якщо наявні незалежних механізмів: , чиї гарантії приватності є диференційно приватними, відповідно, тоді будь-яка функція від: є -диференційно приватною.[17]

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

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

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

У загальному випадку ε-диверенційна приватність створена для захисту приватності між базами даних, які відрізняються лише у одному рядку. Це означає, що жоден порушник із довільною допоміжною інформацією не може знати, чи один конкретний учасник надав свою інформацію. Тим не менше це також може бути поширене для потреби захисту баз даних, які відрізняються у рядках, де порушник із довільною допоміжною інформацією має можливість знати, що часткових учасників надали інформацію. Це може бути досягнуто тому що у випадку коли значень змінюються, ймовірність розширення обмежена замість ,[2] тобто для D1 та D2, які відрізняються у значеннях:

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

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

Перетворення є -стабільним, якщо відстань Геммінга між та є не більше -разів відстані Геммінга між та для двох довільних баз даних . Теорема 2 у [17] стверджує, що якщо існує механізм такий, що є -диверенційно приватним, тоді складений механізм є -диференційно приватним.

Це може бути узагальнене для групової приватності, оскільки розмір групи може бути розглянуте як відстань Геммінга між та (де містить групу та не містить). У цьому випадку є -диференційно приватним.

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

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

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

Посилання

  1. Arvind Narayanan, Vitaly Shmatikov (2008). Robust De-anonymization of Large Sparse Datasets IEEE Symposium on Security and Privacy. с. 111–125.
  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). Unique in the Crowd: The privacy bounds of human mobility. Nature srep. doi:10.1038/srep01376. Процитовано 12 квітня 2013.
  4. HILTON, MICHAEL. Differential Privacy: A Historical Survey.
  5. Dwork, Cynthia (25 квітня 2008). Differential Privacy: A Survey of Results. У Agrawal, Manindra; Du, Dingzhu; Duan, Zhenhua та ін. Theory and Applications of Models of Computation. Lecture Notes in Computer Science (англ.). Springer Berlin Heidelberg. с. 1–19. ISBN 9783540792277. doi:10.1007/978-3-540-79228-4_1.
  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. F.McSherry and K.Talwar. Mechasim Design via Differential Privacy. Proceedings of the 48th Annual Symposium of Foundations of Computer Science, 2007.
  16. Christos Dimitrakakis, Blaine Nelson, Aikaterini Mitrokotsa, Benjamin Rubinstein. Robust and Private Bayesian Inference. Algorithmic Learning Theory 2014
  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 - Press Info - Apple Previews iOS 10, the Biggest iOS Release Ever. Apple. Процитовано 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.

Зовнішні посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.