Confidențialitate diferențială

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 15 februarie 2022; verificările necesită 2 modificări .

Confidențialitatea diferențială este un set de metode care oferă cele mai precise interogări unei baze de date statistice , reducând în același timp posibilitatea de a identifica înregistrările individuale din aceasta.

Introducere

Confidențialitatea diferențială este definiția matematică a pierderii datelor sensibile ale persoanelor atunci când informațiile lor personale sunt folosite pentru a crea un produs. Termenul a fost inventat de Cynthia Dwork în 2006 [1] , dar este folosit și într-o publicație anterioară a lui Dwork, Frank McSherry , Kobe Nissim și Adam D. Smith [2] . Lucrarea se bazează în special pe cercetările lui Nissim și Irit Dinur [3] [4] care au arătat că este imposibil să se publice informații dintr-o bază de date statică privată fără a expune o parte din informațiile private și că întreaga bază de date poate fi dezvăluită. prin publicarea rezultatelor unui număr destul de mic de cereri [4] .

În urma studiului, a devenit clar că este imposibil să se asigure confidențialitatea în bazele de date statistice folosind metodele existente și, ca urmare, a fost nevoie de altele noi care să limiteze riscurile asociate cu pierderea informațiilor private conținute în datele statistice. Bază de date. Drept urmare, au fost create noi metode care permit, în majoritatea cazurilor, furnizarea de statistici precise din baza de date, oferind în același timp un nivel ridicat de confidențialitate [5] [6] .

Principiu și ilustrație

Confidențialitatea diferențială se bazează pe introducerea aleatoriei în date.

Un exemplu simplu dezvoltat în științele sociale [7] este acela de a cere unei persoane să răspundă la întrebarea „Ai atributul A?” conform următoarei proceduri:

dă cu banul
Dacă apar capetele, răspundeți sincer la întrebare.
În caz contrar, aruncați din nou, dacă iese capete, răspundeți „Da”, dacă este cozi - „Nu”

Confidențialitatea apare deoarece este imposibil să știi cu siguranță din răspuns dacă o persoană are un anumit atribut. Cu toate acestea, aceste date sunt semnificative, deoarece răspunsurile pozitive provin de la un sfert dintre persoanele care nu au acest atribut și trei sferturi dintre cei care îl au efectiv. Astfel, dacă p este proporția reală a persoanelor cu A, atunci ne așteptăm să obținem (1/4) (1- p) + (3/4) p = (1/4) + p / 2 răspunsuri pozitive. Prin urmare, se poate estima R.

Definiție formală și exemplu de utilizare

Fie ε un număr real pozitiv și A un algoritm probabilist care ia ca intrare un set de date (reprezintă acțiunile unei părți de încredere care are datele). Notați imaginea lui A prin im A . Algoritmul A este ε - diferențial privat dacă pentru toate seturile de date și care diferă cu un element (adică datele unei persoane), precum și toate submulțimile S ale mulțimii im A : $D_{1}$ $D_{2}$

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

unde P este probabilitatea.

Conform acestei definiții, confidențialitatea diferențială este o condiție a mecanismului de publicare a datelor (adică determinată de partea de încredere care eliberează informații despre setul de date), nu setul de date în sine. Intuitiv, aceasta înseamnă că pentru oricare două seturi de date similare, algoritmul privat diferenţial se va comporta aproximativ la fel pe ambele seturi de date. Definiția oferă, de asemenea, o garanție puternică că prezența sau absența unui individ nu va afecta rezultatul final al algoritmului.

De exemplu, să presupunem că avem o bază de date de înregistrări medicale în care fiecare înregistrare este o pereche de ( Nume , X ) unde este zero sau unu indicând dacă persoana are sau nu gastrită: $D_{1}$ $X$

Nume	Prezența gastritei (X)
Ivan	unu
Petru	0
Vasilisa	unu
Mihai	unu
Maria	0

Acum să presupunem că un utilizator rău intenționat (denumit adesea atacator) dorește să afle dacă Mikhail are gastrită sau nu. Să presupunem, de asemenea, că el știe ce rând conține informații despre Mihail în baza de date. Acum să presupunem că unui atacator i se permite doar să folosească o formă specifică de interogare care returnează o sumă parțială a primelor rânduri ale unei coloane din baza de date. Pentru a afla dacă Mihail are gastrită, atacatorul execută interogări: și , apoi calculează diferența lor. În acest exemplu, , și , deci diferența lor este . Aceasta înseamnă că câmpul „Prezența gastritei” din linia lui Mihail ar trebui să fie egal cu . Acest exemplu arată cum informațiile individuale pot fi compromise chiar și fără o solicitare explicită pentru datele unei anumite persoane. $Q_{i}$ $i$ $X$ $Q_{4}(D_{1})$ $Q_{3}(D_{1})$ $Q_{4}(D_{1})=3$ $Q_{3}(D_{1})=2$ $unu$ $unu$

Continuând cu acest exemplu, dacă construim setul de date prin înlocuirea (Mikhail, 1) cu (Mikhail, 0), atunci atacatorul va putea distinge de prin calcul pentru fiecare set de date. Dacă un atacator ar obține valori printr-un algoritm privat ε-diferențial, pentru un ε suficient de mic, atunci nu ar putea distinge între cele două seturi de date. $D_{2}$ $D_{2}$ $D_{1}$ ${\displaystyle Q_{4}-Q_{3))$ $Q_{i}$

Exemplul de monedă descris mai sus este -diferențial privat [8] . $(\ln 3)$

Cazuri limită

Cazul în care ε = 0 este ideal pentru menținerea confidențialității, deoarece prezența sau absența oricărei informații despre orice persoană în baza de date nu afectează rezultatul algoritmului, totuși, un astfel de algoritm este lipsit de sens în ceea ce privește informațiile utile, deoarece chiar și cu un număr zero de persoane va da același rezultat sau similar.

Dacă ε tinde spre infinit, atunci orice algoritm probabilist se va potrivi definiției, deoarece inegalitatea este întotdeauna satisfăcută. $P[{\mathcal {A}}(D_{1})\in S]\leq \infty \times P[{\mathcal {A}}(D_{2})\in S],$

Sensibilitate

Fie un număr întreg pozitiv, un set de date și o funcție. Sensibilitatea [9] a funcției, notată cu , este determinată de formula $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},

peste toate perechile de seturi de date și în , care diferă cu cel mult un element și unde denotă norma . $D_{1}$ $D_{2}$ $\mathcal{D}$ $\lVert \cdot \rVert _{1)$ $\ell _{1}$

În exemplul de mai sus al unei baze de date medicale, dacă luăm în considerare sensibilitatea funcției , atunci aceasta este egală cu , deoarece modificarea oricăreia dintre înregistrările din baza de date duce la ceva care fie se modifică, fie nu se schimbă. $d$ $Q_{i}$ $unu$ $Q_{i}$ $unu$

mecanism Laplace

Datorită faptului că confidențialitatea diferențială este un concept probabilist, oricare dintre metodele sale are în mod necesar o componentă aleatorie. Unele dintre ele, precum metoda lui Laplace, folosesc adăugarea de zgomot controlat la funcția de calculat.

Metoda Laplace adaugă zgomotul Laplace, adică zgomotul din distribuția Laplace , care poate fi exprimat ca funcție de densitate de probabilitate și care are medie zero și abatere standard . Să definim funcția de ieșire ca o funcție cu valoare reală în forma unde , și este interogarea pe care am plănuit să o executăm în baza de date. Astfel, poate fi considerată o variabilă aleatoare continuă , unde ${\text{zgomot}}(y)\propto \exp(-|y|/\lambda )\,\!$ ${\sqrt {2}}\lambda \,\!$ ${\mathcal {A}}\,\!$ ${\mathcal {T}}_{\mathcal {A}}(x)=f(x)+Y\,\!$ $Y\sim {\text{Lap}}(\lambda )\,\!\,\!$ $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}}(tf(D_{1})) }{{\text{zgomot}}(tf(D_{2})))}}\,\!

care nu este mai mare de (pdf - funcția de densitate de probabilitate sau funcție de densitate de probabilitate). În acest caz, putem desemna factorul de confidențialitate ε. Astfel, conform definiției, este ε-diferențial privat. Dacă încercăm să folosim acest concept în exemplul de mai sus despre prezența gastritei, atunci pentru a fi o funcție privată ε-diferențială, trebuie să țină , deoarece ). $e^{\frac {|f(D_{1})-f(D_{2})|}{\lambda }}\leq e^{\frac {\Delta (f)}{\lambda } }\,\!$ ${\frac {\Delta (f)}{\lambda }}\,\!$ ${\mathcal {T}}\,\!$ ${\mathcal {A}}\,\!$ $\lambda =1/\epsilon$ $\Delta (f)=1$

Pe lângă zgomotul Laplace, pot fi folosite și alte tipuri de zgomot (de exemplu, gaussian), dar pot necesita o ușoară relaxare a definiției confidențialității diferențiale [10] .

Compoziție

Aplicație consistentă

Dacă executăm o interogare de ε- timp de siguranță diferențial, iar zgomotul aleator introdus este independent pentru fiecare interogare, atunci confidențialitatea totală va fi (εt)-diferențială. Mai general, dacă există mecanisme independente: , ale căror garanții de confidențialitate sunt , respectiv, egale, atunci orice funcție va fi -diferențial privată [11] . $T$ $N$ ${\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{n}$ $\epsilon _{1},\dots,\epsilon _{n)$ $g({\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{n})$ $(\sum \limits _{i=1}^{n}\epsilon _{i})$

Compoziție paralelă

De asemenea, dacă interogările sunt executate pe subseturi nesuprapuse ale bazei de date, atunci funcția ar fi -diferențial private [11] . $g$ $(\max _{i}{\epsilon }_{i})$

Confidențialitatea grupului

În general, confidențialitatea diferențială este concepută pentru a proteja confidențialitatea între bazele de date care diferă doar cu o singură linie. Aceasta înseamnă că niciun adversar cu informații auxiliare arbitrare nu poate ști dacă un participant individual și-a furnizat informațiile. Totuși, acest concept poate fi extins la un grup dacă dorim să protejăm bazele de date care diferă în funcție de rânduri, astfel încât un atacator cu informații de sprijin arbitrare să nu știe dacă membrii individuali și-au furnizat informațiile. Acest lucru se poate realiza dacă formula din definiție este înlocuită cu [12] , atunci pentru D 1 și D 2 care diferă prin rânduri $c$ $c$ $\exp(\epsilon )$ $\exp(\epsilon c)$ $c$

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

Astfel, utilizarea parametrului (ε/c) în loc de ε vă permite să obțineți rezultatul dorit și să protejați șirurile. Cu alte cuvinte, în loc ca fiecare element să fie ε-diferențial privat, acum fiecare grup de elemente este ε-diferențial privat și fiecare element este (ε/c)-diferențial privat. $c$ $c$

Aplicarea confidențialității diferențiale aplicațiilor din lumea reală

Până în prezent, există mai multe utilizări pentru confidențialitatea diferențială:

Biroul de recensământ al SUA când se afișează statistici [13]
Google RAPPOR pentru a colecta statistici despre software-ul nedorit care încalcă preferințele utilizatorului [14] ( implementarea open source a RAPPOR )
Google , pentru partajarea statisticilor privind istoricul traficului [15] .
Pe 13 iunie 2016, Apple și-a anunțat intenția de a folosi confidențialitatea diferențială în iOS 10 pentru a-și îmbunătăți suportul inteligent și ofertele tehnologice [16]

Note

↑ Dwork Cynthia, 2006 , p. opt.
↑ Cynthia Dwork, Frank McSherry, Kobbi Nissim și Adam Smith=. Calibrarea zgomotului la sensibilitate în analiza datelor private // Proceedings of the Third Conference on Theory of Cryptography (TCC'06), Shai Halevi și Tal Rabin (eds.). - Springer-Verlag, Berlin, Heidelberg, 2006. - P. 266 . - doi : 10.1007/11681878_14 .
↑ Dwork Cynthia, 2006 , p. 12.
↑ 12 Nissim et al, 2003 , pp. 202-206.
↑ HILTON, MICHAEL. Confidențialitate diferențială: un studiu istoric (nedeterminat) . , p.1
↑ Dwork, 2008 , pp. 3-13.
↑ Roth et al, 2014 , p. cincisprezece.
↑ Roth et al, 2014 , p. treizeci.
↑ Dwork et al, 2006 , pp. 271-272.
↑ Dwork, 2008 , p. 16.
↑ 12 McSherry , 2009 , p. 6.
↑ Dwork Cynthia, 2006 , p. 9.
↑ Machanavajjhala et al, 2008 , p. unu.
↑ Erlingsson et al, 2014 , p. unu.
↑ Tackling Urban Mobility with Technology de Andrew Eland . Politica Google Europa Blog . Data accesului: 19 decembrie 2017. Arhivat din original pe 10 decembrie 2017. (nedefinit)
↑ Apple - Informații de presă - Apple previzualizează iOS 10, cea mai mare lansare iOS vreodată . Apple . Data accesului: 16 iunie 2016. Arhivat din original pe 29 aprilie 2017. (nedefinit)

Literatură

Ashwin Machanavajjhala, Daniel Kifer, John M. Abowd, Johannes Gehrke, Lars Vilhuber. Confidențialitate: Teoria se întâlnește cu practica pe hartă // În lucrările celei de-a 24-a Conferințe Internaționale privind Ingineria Datelor, (ICDE). — 2008.
Úlfar Erlingsson, Vasyl Pihur, Aleksandra Korolova. RAPPOR: Răspuns ordinal de păstrare a confidențialității agregabile aleatorie // Proceedings of the 21st ACM Conference on Computer and Communications Security (CCS). — 2014.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, Adam Smith. Calibrarea zgomotului la sensibilitate în analiza datelor private // Theory of Cryptography Conference (TCC). - Springer, 2006. - doi : 10.1007/11681878_14 .
Frank D. McSherry. Interogări integrate de confidențialitate: o platformă extensibilă pentru analiza datelor care păstrează confidențialitatea // Proceedings of the 35th SIGMOD International Conference on Management of Data (SIGMOD). - 2009. - doi : 10.1145/1559845.1559850 .
Cynthia Dwork, Aaron Roth. Fundamentele algoritmice ale confidențialității diferențiale // Fundamente și tendințe în informatica teoretică. - 2014. - August (vol. 9). - doi : 10.1561/0400000042 .
Dwork, Cynthia. Confidențialitate diferențială: un sondaj de rezultate // Agrawal, Manindra; Du, Dingzhu; Duan, Zhenhua; Li, Teoria Angsheng și aplicațiile modelelor de calcul. Note de curs în informatică. - Springer Berlin Heidelberg, 2008. - 25 aprilie. doi : 10.1145 / 773153.773173 .
Dwork, Cynthia. Confidențialitate diferențială . - Colocviul Internațional de Automate, Limbaje și Programare (ICALP), 2006. - doi : 10.1007/11787006_1 .
Irit Dinur, Kobbi Nissim. Dezvăluirea informațiilor în timp ce protejează confidențialitatea // Proceedings of the two22 second ACM SIGMOD-SIGACT-SIGART simpozion on Principles of database systems (PODS '03). - ACM, New York, NY, SUA, 2003. - doi : 10.1145/773153.773173 .