Диференційна приватність — це формальна теорія забезпечення конфіденційності персональних даних при публікації статистичних аналізів або моделей машинного навчання, обчислених на базі персональних даних. Диференційна приватність гарантує те, що персональні дані неможливо точно відновити з результатів обчислень за рахунок контрольованого додавання випадкових значень в процес обчислень.
Мотивація
Нехай існує довірена сторона, яка володіє масивом чутливих персональних даних (наприклад медичні записи, відомості щодо перегляду кіно або використання електронної пошти) і бажає надавати узагальнену статистичну інформацію про ці дані. Така система називається статистичною базою даних. Однак надання узагальненої статистичної інформації про дані може розкрити деяку інформацію щодо осіб. Дійсно, різноманітні 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?», за наступною процедурою:
- Підкинути монетку.
- Якщо випав аверс — відповісти чесно.
- Якщо випав герб — підкинути монетку ще раз і відповісти «Так», якщо випав аверс, або «Ні», якщо випав герб.
Приватність забезпечується через забезпечення відмовності щодо індивідуальних відповідей.
Хоча ці дані з багатьма відповідями є значимими, позитивні відповіді дали чверть осіб, які не мали атрибута A і три чверті осіб, які володіють атрибутом A.
Якщо p справжня частка осіб з A, тоді буде отримано (1/4)(1-p) + (3/4)p = (1/4) + p/2 позитивних відповідей. Звідси можна обчислити p.
PS: зокрема, якщо володіння атрибутом A є синонімом незаконних дій, відповідь «Так» не є зізнанням у злочині, оскільки існує ненульова імовірність хибнопозитивної відповіді «Так».
Формальне визначення та приклад застосування
Нехай позитивне дійсне число і
є увипадковленим алгоритмом, який приймає набір даних на вході, що представляє дії довіреної сторони, яка розпоряджається даними. Нехай
є образом відображення
. Алгоритм
є
-диференційно приватним, якщо для всіх наборів даних
та
, які відрізняються у єдиному елементі (даних щодо однієї особи), для всіх підмножин
з
,
де імовірність отримана з випадковості, яку використовує алгоритм.
У відповідності до цього визначення диференційна приватність є умовою роботи механізму публікації (довіреної сторони, яка публікує інформацію щодо набору даних), а не самого набору даних. Інтуітивно це означає, що для двох довільних схожих наборів даних диференційно приватний алгоритм буде праціювати схоже для обох наборів даних. Визначення гарантує, що присутність або відсутність особи не значно вплине на фінальний результат.
Наприклад представимо, що ми маємо базу баних медичних записів де кожен запис є парою (Ім'я, X), де
є булевою змінною, яка позначає наявність діабету у особи. Наприклад:
Ім'я | Наявність діабету (X) |
---|---|
Рос | 1 |
Моніка | 1 |
Джої | 0 |
Фібі | 0 |
Чендлер | 1 |
Тепер припустимо, що зловимсний користувач (порушник) бажає визначити наявність діабету у Чендлера. Також припустимо, що порушник також знає у якому рядку бази даних розміщено запис Чендлера. Тепер припустимо, що порушнику дозволено використовуати тільки часткову форму запиту , яка повертає часткову суму перших
рядків ствопчика
у базі даних. Зазвичай, щоб визначити наявність діабету у Чендлера порушник виконує запити
та
, потім обчислює їх різницю. У цьому прикладі
, а
, тому різниця дорівнює 1. Це означає, що у полі рядка Чендлера знаходиться 1. Це приклад показує, як може бути скомпрометована інформація про особу навіть без точного запиту щодо особи.
Продовжуючи цей приклад, якщо ми сконструюємо базу даних заміною (Чендлер, 1) на (Чендлер, 0), то порушник матиме можливість відрізнити
від
обчисленням
для кожного набору даних. Якщо порушнику знадобиться отримати значення
використовуючи
-диференційно приватний алгоритм, для достатньо малого
, то він не зможе розрізнити два набори даних.
Чутливість
Нехай є позитивним цілим,
є колекцією наборів даних, і
є функцією. Чутливість функції, позначена
, визначається як
де максимум по усім парам наборів даних
та
у
, які відрізняються щонайменш у одному елементі і
позначається
нормою.
У прикладі медичної бази даних вище, якщо ми приймемо є функцією
, тоді чутливість функції дорівнює одиниці, оскільки зміна одного запису у базі даних призводить до зміни значення функції на нуль або одиницю.
Існують методи (описані нижче), використання яких дозволяє створювати диференційно приватний алгоритм для функцій з низькою чутливістю.
Компроміс між корисністю та приватністю
Компроміс між точністю статистики, отриманої із дотриманням приватності, і приватністю описується параметром ε.
Інші нотації диференційної приватності
Для деяких застосувань властивість диференційної приватності є занадто суворою, тому запропоновані слабші версії властивостей приватності. Вони включають (ε, δ)-диференційну приватність, рандомізовану диференційну приватність, і приватність з метрикою.
Диференційно приватні механізми
Оскільки диференційна приватність є імовірнісною концепцією, будь-який диференційно приватний механізм обов'язково є рандомізованим. Деякі з них, як механізм Лапласа, описаний нижче, покладаються на додавання контрольованого шуму до функції, яку потрібно обчислити. Інші, як [en] використовують післявибірку замість залежних від галузі використання розподілів.
Механізм Лапласа
Багато диференційно приватних методів додають контрольований шум до функцій з низькою чутливістю. Механізм Лапласа додає шум Лапласа (шум з розподілом Лапласа), який може бути виражений функцією щільності імовірності , яка має математичне сподівання, що дорівнює нулю, і стандартне відхилення
). У нашому випадку визначено вихідну функцію від
як функцію з дійсними значеннями як
де
and
є оригінальною функцією з дійсними значеннями, яку планувалося виконати над базою даних. Звідси
може бути представлена як неперервну випадкову змінну, де
де щонайменше . Можна представити
як фактор приватності
. Таким чином
відповідає визначенню диференційно приватного механізму. Якщо застосувати цю концепцію до нашого прикладу з хворими на діабет, тоді це слідує з факту, що
як
-диференційно приватний алгоритм повинен мати
. Хоча було використано шум Лапласа, можуть бути використані шуми з іншим розподілом (наприклад нормальним розподілом), але для цього потрібне деяке послаблення визначення диференційної приватності.
Поєднуваність
Послідовне поєднання
Якщо запитати ε-диверенційно приватний механізм разів, і рандомізація механізму є незалежною для кожного запиту, тоді результат буде
-диференційно приватним. У загальному випадку, якщо наявні
незалежних механізмів:
, чиї гарантії приватності є
диференційно приватними, відповідно, тоді будь-яка функція
від:
є
-диференційно приватною.
Паралельне поєднання
Більш того, якщо попередні механізми обчислені над підмножинами, що не перетинаються, приватної бази даних, тоді функція є
-диференційно приватною.
Групова приватність
У загальному випадку ε-диверенційна приватність створена для захисту приватності між базами даних, які відрізняються лише у одному рядку. Це означає, що жоден порушник із довільною допоміжною інформацією не може знати, чи один конкретний учасник надав свою інформацію. Тим не менше це також може бути поширене для потреби захисту баз даних, які відрізняються у рядках, де порушник із довільною допоміжною інформацією має можливість знати, що
часткових учасників надали інформацію. Це може бути досягнуто тому що у випадку коли
значень змінюються, ймовірність розширення обмежена
замість
, тобто для D1 та D2, які відрізняються у
значеннях:
Таким чином встановлення ε замість досягає бажаного результату (захисту
значень). Іншими словами, замість ε-диференційно приватного захисту кожного значення, тепер група з
значень є захищеною з параметром ε-диференційної приватності (і кожне значення є захищеним з параметром
-диференційної приватності).
Стабільні перетворення
Перетворення є
-стабільним, якщо відстань Геммінга між
та
є не більше
-разів відстані Геммінга між
та
для двох довільних баз даних
. Теорема 2 у стверджує, що якщо існує механізм
такий, що є
-диверенційно приватним, тоді складений механізм
є
-диференційно приватним.
Це може бути узагальнене для групової приватності, оскільки розмір групи може бути розглянуте як відстань Геммінга між
та
(де
містить групу та
не містить). У цьому випадку
є
-диференційно приватним.
Використання
Деякі використання, відомі на сьогодні:
- Бюро перепису населення США, для демонстрації шаблонів взаємодії,
- Google RAPPOR, для телеметрії та вивчення статистики щодо небажаного програмного забезпечення, яке перехоплює налаштування користувача (RAPPOR's open-source implementation [ 14 січня 2021 у Wayback Machine.]),
- Google, для поширення історичної статистики трафіку,
- 13 червня 2016 Apple оголосила про намір використовувати диференційну приватність у iOS 10 щоб покращити власну технологію персонального помічника,
- Виконані деякі початкові дослідження щодо практичної реалізації диференційної приватності у моделях дата-майнингу.
Посилання
- , (2008). (PDF). . с. 111—125. Архів оригіналу (PDF) за 26 січня 2021. Процитовано 4 листопада 2017.
- Differential Privacy by Cynthia Dwork, International Colloquium on Automata, Languages and Programming (ICALP) 2006, p. 1–12. DOI=10.1007/11787006_1
- 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.
- HILTON, MICHAEL. (PDF). Архів оригіналу (PDF) за 1 березня 2017. Процитовано 4 листопада 2017.
- 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.
- 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
- 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
- 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.
- 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.
- 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.
- 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.
- 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.
- Hall, Rob, Alessandro Rinaldo, and Larry Wasserman. "Random differential privacy." arXiv preprint arXiv:1112.2680 (2011).
- 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.
- (PDF). Архів оригіналу (PDF) за 7 березня 2016. Процитовано 28 січня 2018.
- . Архів оригіналу за 16 листопада 2017. Процитовано 28 січня 2018.
- 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
- Ú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.
- Tackling Urban Mobility with Technology by Andrew Eland. Google Policy Europe Blog, Nov 18, 2015.
- . Apple. Архів оригіналу за 15 червня 2016. Процитовано 16 червня 2016.
- 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
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Diferencijna privatnist ce formalna teoriya zabezpechennya konfidencijnosti personalnih danih pri publikaciyi statistichnih analiziv abo modelej mashinnogo navchannya obchislenih na bazi personalnih danih Diferencijna privatnist garantuye te sho personalni dani nemozhlivo tochno vidnoviti z rezultativ obchislen za rahunok kontrolovanogo dodavannya vipadkovih znachen v proces obchislen MotivaciyaNehaj isnuye dovirena storona yaka volodiye masivom chutlivih personalnih danih napriklad medichni zapisi vidomosti shodo pereglyadu kino abo vikoristannya elektronnoyi poshti i bazhaye nadavati uzagalnenu statistichnu informaciyu pro ci dani Taka sistema nazivayetsya statistichnoyu bazoyu danih Odnak nadannya uzagalnenoyi statistichnoyi informaciyi pro dani mozhe rozkriti deyaku informaciyu shodo osib Dijsno riznomanitni ad hoc pidhodi do anonimizaciyi opublikovanih zapisiv buli podolani koli doslidniki poyednuvali vmist dvoh abo bilshe okremih baz danih Diferencijna privatnist ce pidhid dlya formalizaciyi privatnosti u statistichnih bazah danih zaproponovanij dlya zahistu vid podibnih metodiv deanonimizaciyi Priz Netflix Napriklad u zhovtni 2006 Netflix zaproponuvav priz u 1 miljon dolariv SShA za pokrashennya vlasnoyi sistemi formuvannya rekomendacij na 10 Netflix takozh vipustiv trenuvalnij masiv danih dlya zmagannya rozrobnikiv Pri vipusku cogo masivu danih Netflix zaznachiv sho dlya zahistu privatnosti koristuvachiv usya personalna informaciya sho identifikuye koristuvachiv ta usi identifikatori koristuvachiv zamineni na vipadkovi identifikatori Netflix ne yedinij portal ocinyuvannya kinofilmiv u merezhi isnuyut i inshi zokrema IMDb Na IMDb koristuvachi mozhut reyestruvatis i ocinyuvati filmi bez anonimizaciyi Arvind Narayanan ta Vitaly Shmatikov doslidniki u University of Texas at Austin poyednali anonimizovanij masiv danih Netflix z bazoyu danih IMDb vikoristovuyuchi datu ocinyuvannya i chastkovo deanonimizuvali masiv danih Netflix skomprometuvavshi identichnist deyakih koristuvachiv Baza danih medichnih vipadkiv Komisiyi z grupovogo strahuvannya shtatu Massachusets Latanya Sweeney z Carnegie Mellon University poyednala anonimizovanu bazu danih u yakij zberigalisya data narodzhennya stat ta poshtovij indeks kozhnogo paciyenta z zapisami viborciv i zmogla viznachiti medichnij zapis gubernatora shtatu Massachusets Metadani ta bazi danih mobilnih operatoriv De Montjoye ta inshi z MIT vveli ponyattya unikalnosti i pokazali sho 4 prostorovo chasovih vidmitki z pribliznimi momentami chasu i prostorovimi koordinatami dostatno shob identifikuvati 95 z 1 5 mln lyudej z bazi danih mobilnih operatoriv Podalshe doslidzhennya pokazuye sho ci obmezhennya mayut misce navit todi koli rozdilna zdatnist naboru danih ye nizkoyu sho oznachaye sho navit grubij abo rozmitij nabir danih mobilnih operatoriv ta metadani zabezpechuyut malu anonimnist OglyadU 2006 Cynthia Dwork viznachila galuz diferencijnoyi privatnosti z vikoristannyam rezultativ roboti pochatoyi u 2003 U cij roboti pokazano nemozhlivist dosyagti semantichnih cilej bezpeki sho vidnosyatsya do roboti Tore Dalenius z 1970 h i viznacheno novi metodi dlya obmezhennya zrostayuchogo riziku dlya personalnih danih vid yih vklyuchennya do statistichnoyi bazi danih Ce dozvolyaye u bagatoh vipadkah nadati duzhe tochnu statistiku na pidstavi bazi danih iz zabezpechennyam visokogo rivnya privatnosti Princip ta ilyustraciya Diferencijna privatnist ce proces yakij vnosit vipadkovist u dani Prostim prikladom rozroblenim u socialnih naukah ye opituvannya osib Vi volodiyete atributom A za nastupnoyu proceduroyu Pidkinuti monetku Yaksho vipav avers vidpovisti chesno Yaksho vipav gerb pidkinuti monetku she raz i vidpovisti Tak yaksho vipav avers abo Ni yaksho vipav gerb Privatnist zabezpechuyetsya cherez zabezpechennya vidmovnosti shodo individualnih vidpovidej Hocha ci dani z bagatma vidpovidyami ye znachimimi pozitivni vidpovidi dali chvert osib yaki ne mali atributa A i tri chverti osib yaki volodiyut atributom A Yaksho p spravzhnya chastka osib z A todi bude otrimano 1 4 1 p 3 4 p 1 4 p 2 pozitivnih vidpovidej Zvidsi mozhna obchisliti p PS zokrema yaksho volodinnya atributom A ye sinonimom nezakonnih dij vidpovid Tak ne ye ziznannyam u zlochini oskilki isnuye nenulova imovirnist hibnopozitivnoyi vidpovidi Tak Formalne viznachennya ta priklad zastosuvannyaNehaj ϵ displaystyle epsilon pozitivne dijsne chislo i A displaystyle mathcal A ye uvipadkovlenim algoritmom yakij prijmaye nabir danih na vhodi sho predstavlyaye diyi dovirenoyi storoni yaka rozporyadzhayetsya danimi Nehaj imA displaystyle textrm im mathcal A ye obrazom vidobrazhennya A displaystyle mathcal A Algoritm A displaystyle mathcal A ye ϵ displaystyle epsilon diferencijno privatnim yaksho dlya vsih naboriv danih D1 displaystyle D 1 ta D2 displaystyle D 2 yaki vidriznyayutsya u yedinomu elementi danih shodo odniyeyi osobi dlya vsih pidmnozhin S displaystyle S z imA displaystyle textrm im mathcal A Pr A D1 S eϵ Pr A D2 S displaystyle Pr mathcal A D 1 in S leq e epsilon times Pr mathcal A D 2 in S de imovirnist otrimana z vipadkovosti yaku vikoristovuye algoritm U vidpovidnosti do cogo viznachennya diferencijna privatnist ye umovoyu roboti mehanizmu publikaciyi dovirenoyi storoni yaka publikuye informaciyu shodo naboru danih a ne samogo naboru danih Intuitivno ce oznachaye sho dlya dvoh dovilnih shozhih naboriv danih diferencijno privatnij algoritm bude praciyuvati shozhe dlya oboh naboriv danih Viznachennya garantuye sho prisutnist abo vidsutnist osobi ne znachno vpline na finalnij rezultat Napriklad predstavimo sho mi mayemo bazu banih medichnih zapisiv D1 displaystyle D 1 de kozhen zapis ye paroyu Im ya X de X displaystyle X ye bulevoyu zminnoyu yaka poznachaye nayavnist diabetu u osobi Napriklad Im ya Nayavnist diabetu X Ros 1Monika 1Dzhoyi 0Fibi 0Chendler 1 Teper pripustimo sho zlovimsnij koristuvach porushnik bazhaye viznachiti nayavnist diabetu u Chendlera Takozh pripustimo sho porushnik takozh znaye u yakomu ryadku bazi danih rozmisheno zapis Chendlera Teper pripustimo sho porushniku dozvoleno vikoristovuati tilki chastkovu formu zapitu Qi displaystyle Q i yaka povertaye chastkovu sumu pershih i displaystyle i ryadkiv stvopchika X displaystyle X u bazi danih Zazvichaj shob viznachiti nayavnist diabetu u Chendlera porushnik vikonuye zapiti Q5 D1 displaystyle Q 5 D 1 ta Q4 D1 displaystyle Q 4 D 1 potim obchislyuye yih riznicyu U comu prikladi Q5 D1 3 displaystyle Q 5 D 1 3 a Q4 D1 2 displaystyle Q 4 D 1 2 tomu riznicya dorivnyuye 1 Ce oznachaye sho u poli ryadka Chendlera znahoditsya 1 Ce priklad pokazuye yak mozhe buti skomprometovana informaciya pro osobu navit bez tochnogo zapitu shodo osobi Prodovzhuyuchi cej priklad yaksho mi skonstruyuyemo bazu danih D2 displaystyle D 2 zaminoyu Chendler 1 na Chendler 0 to porushnik matime mozhlivist vidrizniti D2 displaystyle D 2 vid D1 displaystyle D 1 obchislennyam Q5 Q4 displaystyle Q 5 Q 4 dlya kozhnogo naboru danih Yaksho porushniku znadobitsya otrimati znachennya Qi displaystyle Q i vikoristovuyuchi ϵ displaystyle epsilon diferencijno privatnij algoritm dlya dostatno malogo ϵ displaystyle epsilon to vin ne zmozhe rozrizniti dva nabori danih Chutlivist Nehaj d displaystyle d ye pozitivnim cilim D displaystyle mathcal D ye kolekciyeyu naboriv danih i f D Rd displaystyle f colon mathcal D rightarrow mathbb R d ye funkciyeyu Chutlivist funkciyi poznachena Df displaystyle Delta f viznachayetsya yak Df max f D1 f D2 1 displaystyle Delta f max lVert f D 1 f D 2 rVert 1 de maksimum po usim param naboriv danih D1 displaystyle D 1 ta D2 displaystyle D 2 u D displaystyle mathcal D yaki vidriznyayutsya shonajmensh u odnomu elementi i 1 displaystyle lVert cdot rVert 1 poznachayetsya ℓ1 displaystyle ell 1 normoyu U prikladi medichnoyi bazi danih vishe yaksho mi prijmemo f displaystyle f ye funkciyeyu Qi displaystyle Q i todi chutlivist funkciyi dorivnyuye odinici oskilki zmina odnogo zapisu u bazi danih prizvodit do zmini znachennya funkciyi na nul abo odinicyu Isnuyut metodi opisani nizhche vikoristannya yakih dozvolyaye stvoryuvati diferencijno privatnij algoritm dlya funkcij z nizkoyu chutlivistyu Kompromis mizh korisnistyu ta privatnistyu Kompromis mizh tochnistyu statistiki otrimanoyi iz dotrimannyam privatnosti i privatnistyu opisuyetsya parametrom e Inshi notaciyi diferencijnoyi privatnosti Dlya deyakih zastosuvan vlastivist diferencijnoyi privatnosti ye zanadto suvoroyu tomu zaproponovani slabshi versiyi vlastivostej privatnosti Voni vklyuchayut e d diferencijnu privatnist randomizovanu diferencijnu privatnist i privatnist z metrikoyu Diferencijno privatni mehanizmiOskilki diferencijna privatnist ye imovirnisnoyu koncepciyeyu bud yakij diferencijno privatnij mehanizm obov yazkovo ye randomizovanim Deyaki z nih yak mehanizm Laplasa opisanij nizhche pokladayutsya na dodavannya kontrolovanogo shumu do funkciyi yaku potribno obchisliti Inshi yak en vikoristovuyut pislyavibirku zamist zalezhnih vid galuzi vikoristannya rozpodiliv Mehanizm Laplasa Bagato diferencijno privatnih metodiv dodayut kontrolovanij shum do funkcij z nizkoyu chutlivistyu Mehanizm Laplasa dodaye shum Laplasa shum z rozpodilom Laplasa yakij mozhe buti virazhenij funkciyeyu shilnosti imovirnosti noise y exp y l displaystyle text noise y propto exp y lambda yaka maye matematichne spodivannya sho dorivnyuye nulyu i standartne vidhilennya l displaystyle lambda U nashomu vipadku viznacheno vihidnu funkciyu vid A displaystyle mathcal A yak funkciyu z dijsnimi znachennyami yak TA x f x Y displaystyle mathcal T mathcal A x f x Y de Y Lap l displaystyle Y sim text Lap lambda and f displaystyle f ye originalnoyu funkciyeyu z dijsnimi znachennyami yaku planuvalosya vikonati nad bazoyu danih Zvidsi TA x displaystyle mathcal T mathcal A x mozhe buti predstavlena yak neperervnu vipadkovu zminnu de pdf TA D1 x t pdf TA D2 x t noise t f D1 noise t f D2 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 de shonajmenshe e f D1 f D2 l eD f l displaystyle e frac f D 1 f D 2 lambda leq e frac Delta f lambda Mozhna predstaviti D f l displaystyle frac Delta f lambda yak faktor privatnosti ϵ displaystyle epsilon Takim chinom T displaystyle mathcal T vidpovidaye viznachennyu diferencijno privatnogo mehanizmu Yaksho zastosuvati cyu koncepciyu do nashogo prikladu z hvorimi na diabet todi ce sliduye z faktu sho A displaystyle mathcal A yak ϵ displaystyle epsilon diferencijno privatnij algoritm povinen mati l 1 ϵ displaystyle lambda 1 epsilon Hocha bulo vikoristano shum Laplasa mozhut buti vikoristani shumi z inshim rozpodilom napriklad normalnim rozpodilom ale dlya cogo potribne deyake poslablennya viznachennya diferencijnoyi privatnosti PoyednuvanistPoslidovne poyednannya Yaksho zapitati e diverencijno privatnij mehanizm t displaystyle t raziv i randomizaciya mehanizmu ye nezalezhnoyu dlya kozhnogo zapitu todi rezultat bude ϵt displaystyle epsilon t diferencijno privatnim U zagalnomu vipadku yaksho nayavni n displaystyle n nezalezhnih mehanizmiv M1 Mn displaystyle mathcal M 1 dots mathcal M n chiyi garantiyi privatnosti ye ϵ1 ϵn displaystyle epsilon 1 dots epsilon n diferencijno privatnimi vidpovidno todi bud yaka funkciya g displaystyle g vid g M1 Mn displaystyle g mathcal M 1 dots mathcal M n ye i 1nϵi displaystyle sum limits i 1 n epsilon i diferencijno privatnoyu Paralelne poyednannya Bilsh togo yaksho poperedni mehanizmi obchisleni nad pidmnozhinami sho ne peretinayutsya privatnoyi bazi danih todi funkciya g displaystyle g ye maxiϵi displaystyle max i epsilon i diferencijno privatnoyu Grupova privatnistU zagalnomu vipadku e diverencijna privatnist stvorena dlya zahistu privatnosti mizh bazami danih yaki vidriznyayutsya lishe u odnomu ryadku Ce oznachaye sho zhoden porushnik iz dovilnoyu dopomizhnoyu informaciyeyu ne mozhe znati chi odin konkretnij uchasnik nadav svoyu informaciyu Tim ne menshe ce takozh mozhe buti poshirene dlya potrebi zahistu baz danih yaki vidriznyayutsya u c displaystyle c ryadkah de porushnik iz dovilnoyu dopomizhnoyu informaciyeyu maye mozhlivist znati sho c displaystyle c chastkovih uchasnikiv nadali informaciyu Ce mozhe buti dosyagnuto tomu sho u vipadku koli c displaystyle c znachen zminyuyutsya jmovirnist rozshirennya obmezhena exp ϵc displaystyle exp epsilon c zamist exp ϵ displaystyle exp epsilon tobto dlya D1 ta D2 yaki vidriznyayutsya u c displaystyle c znachennyah Pr A D1 S exp ϵc Pr A D2 S displaystyle Pr mathcal A D 1 in S leq exp epsilon c times Pr mathcal A D 2 in S Takim chinom vstanovlennya e zamist ϵ c displaystyle epsilon c dosyagaye bazhanogo rezultatu zahistu c displaystyle c znachen Inshimi slovami zamist e diferencijno privatnogo zahistu kozhnogo znachennya teper grupa z c displaystyle c znachen ye zahishenoyu z parametrom e diferencijnoyi privatnosti i kozhne znachennya ye zahishenim z parametrom ϵ c displaystyle epsilon c diferencijnoyi privatnosti Stabilni peretvorennya Peretvorennya T displaystyle T ye c displaystyle c stabilnim yaksho vidstan Gemminga mizh T A displaystyle T A ta T B displaystyle T B ye ne bilshe c displaystyle c raziv vidstani Gemminga mizh A displaystyle A ta B displaystyle B dlya dvoh dovilnih baz danih A B displaystyle A B Teorema 2 u stverdzhuye sho yaksho isnuye mehanizm M displaystyle M takij sho ye ϵ displaystyle epsilon diverencijno privatnim todi skladenij mehanizm M T displaystyle M circ T ye ϵ c displaystyle epsilon times c diferencijno privatnim Ce mozhe buti uzagalnene dlya grupovoyi privatnosti oskilki rozmir grupi mozhe buti rozglyanute yak vidstan Gemminga h displaystyle h mizh A displaystyle A ta B displaystyle B de A displaystyle A mistit grupu ta B displaystyle B ne mistit U comu vipadku M T displaystyle M circ T ye ϵ c h displaystyle epsilon times c times h diferencijno privatnim VikoristannyaDeyaki vikoristannya vidomi na sogodni Byuro perepisu naselennya SShA dlya demonstraciyi shabloniv vzayemodiyi Google RAPPOR dlya telemetriyi ta vivchennya statistiki shodo nebazhanogo programnogo zabezpechennya yake perehoplyuye nalashtuvannya koristuvacha RAPPOR s open source implementation 14 sichnya 2021 u Wayback Machine Google dlya poshirennya istorichnoyi statistiki trafiku 13 chervnya 2016 Apple ogolosila pro namir vikoristovuvati diferencijnu privatnist u iOS 10 shob pokrashiti vlasnu tehnologiyu personalnogo pomichnika Vikonani deyaki pochatkovi doslidzhennya shodo praktichnoyi realizaciyi diferencijnoyi privatnosti u modelyah data majningu Posilannya 2008 PDF s 111 125 Arhiv originalu PDF za 26 sichnya 2021 Procitovano 4 listopada 2017 Differential Privacy by Cynthia Dwork International Colloquium on Automata Languages and Programming ICALP 2006 p 1 12 DOI 10 1007 11787006 1 de Montjoye Yves Alexandre Cesar A Hidalgo Michel Verleysen Vincent D Blondel 25 bereznya 2013 Nature srep doi 10 1038 srep01376 Arhiv originalu za 11 serpnya 2015 Procitovano 12 kvitnya 2013 HILTON MICHAEL PDF Arhiv originalu PDF za 1 bereznya 2017 Procitovano 4 listopada 2017 Dwork Cynthia 25 kvitnya 2008 U Agrawal Manindra Du Dingzhu Duan Zhenhua Li Angsheng red Theory and Applications of Models of Computation Lecture Notes in Computer Science angl Springer Berlin Heidelberg s 1 19 doi 10 1007 978 3 540 79228 4 1 ISBN 9783540792277 Arhiv originalu za 27 lyutogo 2021 Procitovano 4 listopada 2017 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 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 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 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 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 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 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 Hall Rob Alessandro Rinaldo and Larry Wasserman Random differential privacy arXiv preprint arXiv 1112 2680 2011 Chatzikokolakis Konstantinos Miguel E Andres Nicolas Emilio Bordenabe and Catuscia Palamidessi Broadening the scope of Differential Privacy using metrics In Privacy Enhancing Technologies pp 82 102 Springer Berlin Heidelberg 2013 PDF Arhiv originalu PDF za 7 bereznya 2016 Procitovano 28 sichnya 2018 Arhiv originalu za 16 listopada 2017 Procitovano 28 sichnya 2018 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 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 Ulfar 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 Tackling Urban Mobility with Technology by Andrew Eland Google Policy Europe Blog Nov 18 2015 Apple Arhiv originalu za 15 chervnya 2016 Procitovano 16 chervnya 2016 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 PosilannyaDifferential Privacy 1 sichnya 2021 u Wayback Machine by Cynthia Dwork ICALP July 2006 The Algorithmic Foundations of Differential Privacy 18 zhovtnya 2014 u Wayback Machine by Cynthia Dwork and Aaron Roth 2014 Differential Privacy A Survey of Results 5 bereznya 2010 u Wayback Machine by Cynthia Dwork Microsoft Research April 2008 Privacy of Dynamic Data Continual Observation and Pan Privacy 9 chervnya 2010 u Wayback Machine by Moni Naor Institute for Advanced Study November 2009 Tutorial on Differential Privacy 14 lipnya 2014 u Wayback Machine by California Institute of Technology December 2013 A Practical Beginner s Guide To Differential Privacy 8 travnya 2012 u Wayback Machine by Christine Task Purdue University April 2012 Private Map Maker v0 2 3 grudnya 2012 u Wayback Machine on the Common Data Project blog Learning Statistics with Privacy aided by the Flip of a Coin 11 bereznya 2018 u Wayback Machine by Ulfar Erlingsson Google Research Blog October 2014