confidențialitatea diferențială a sărit de la lucrări de cercetare la titluri de știri tehnologice anul trecut, când, în nota principală WWDC, vicepreședintele Apple al ingineriei Craig Federighi a anunțat utilizarea de către Apple a conceptului pentru a proteja confidențialitatea utilizatorilor în iOS.

a fost ultima instanță a unei tendințe generale: utilizatorii și inginerii care se trezesc la importanța protecției vieții private în software. Încălcări importante ale confidențialității, cum ar fi „Modul Dumnezeu” al Uber, au demonstrat în termeni duri ușurința cu care angajații unei companii pot folosi în mod abuziv datele sensibile colectate de la clienții lor.

cantitatea de date sensibile care este înregistrată digital crește rapid. Oamenii se bazează acum pe serviciile digitale pentru mai multe plăți, transport, navigație, cumpărături și sănătate decât oricând. Această nouă colecție de date creează modalități din ce în ce mai mari de a încălca confidențialitatea.

dar creează, de asemenea, oportunități interesante—de a îmbunătăți rețelele de transport, de a reduce criminalitatea, de a vindeca bolile—dacă sunt puse la dispoziția oamenilor de știință și cercetătorilor potriviți. Există o tensiune naturală între protejarea confidențialității persoanelor din setul de date și activarea analizelor care ar putea duce la o lume mai bună.algoritmii diferențiali privați sunt o soluție tehnică promițătoare care ar putea ușura această tensiune, permițând analiștilor să efectueze analize agregate benigne, garantând în același timp o protecție semnificativă a vieții private a fiecărui individ.

acest domeniu tehnologic în curs de dezvoltare merită luat în considerare în orice sistem care încearcă să analizeze date sensibile. Deși garanția diferențială de Confidențialitate a fost concepută în urmă cu doar zece ani, a avut succes în mediul academic și industrie. Cercetătorii inventează și îmbunătățesc rapid algoritmi privați diferențiați, dintre care unii au fost adoptați atât în iOS-ul Apple, cât și în Chrome-ul Google.

Acest articol discută factorii istorici care conduc la confidențialitatea diferențială în forma sa actuală, împreună cu o definiție a confidențialității diferențiale și un exemplu de algoritmi diferențiali privați. Apoi se uită la unele implementări recente de profil înalt ale algoritmilor diferențiați privați de către Google, Apple și alții.

Background

algoritmii diferențiați privați sunt cei mai recenți dintr-un domeniu vechi de zeci de ani de tehnologii pentru analiza datelor care păstrează confidențialitatea. Două concepte anterioare au influențat direct confidențialitatea diferențială:

1. dimensiunea minimă a setului de interogare
2. definiția dezvăluirii statistice a lui Dalenius.

le vom explica mai întâi, deoarece oferă un fundal util pentru confidențialitatea diferențială.

dimensiunea minimă a setului de interogări primul concept este o dimensiune minimă a setului de interogări, care—la fel ca algoritmii diferențiați privați—își propune să asigure siguranța interogărilor agregate. Interogările agregate sunt cele în care valoarea returnată este calculată într-un subset de înregistrări din setul de date, cum ar fi numărări, medii sau sume. Poate fi util să vă gândiți la interogările agregate ca interogări SQL care încep cu „selectați suma”, „selectați numărul” sau „selectați AVG”. Alte tipuri de interogări agregate includ tabele de urgență și histograme.

o dimensiune minimă a setului de interogări este o constrângere care urmărește să se asigure că interogările agregate nu pot scurge informații despre indivizi. Având în vedere un număr de prag configurat T, se asigură că fiecare interogare agregată este efectuată pe un set de cel puțin t înregistrări. O dimensiune minimă a setului de interogări ar bloca interogările agregate care vizează mai puține persoane decât T. De exemplu, dacă T = 2, ar bloca următoarele:

„selectați AVG(salariu) unde name = ‘Troy Brown’;”.

deoarece această interogare ar efectua o medie pe o înregistrare (presupunem că există doar un singur Troy Brown).

utilizarea dimensiunilor minime ale seturilor de interogare previne anumite atacuri, dar nu vine cu o garanție de confidențialitate și, în practică, poate fi eludată de atacatori calificați. De exemplu, atacatorul ar putea realiza atacul de mai sus cu:

„selectați suma(salariul);”.

„selectați suma(salariul) unde numele != „Troy Brown”;”.

sau chiar, dacă știm că vârsta lui Troy Brown (45) și poziția (WR) îl identifică în mod unic:

„selectați suma(salariul) unde poziția = ‘WR’;”.

„selectați suma (salariul) unde poziția = ‘WR’ și vârsta != 45;

astfel de atacuri se numesc atacuri tracker și nu pot fi oprite printr-o constrângere minimă de dimensiune a setării interogării. Din cauza acestor atacuri, dimensiunile minime ale seturilor de interogări au fost considerate o apărare inadecvată pentru protejarea sistemelor de interogare (a se vedea lucrarea lui Denning). Era nevoie de ceva mai bun, cu garanție, pentru a asigura confidențialitatea.în 1977, statisticianul Tore Dalenius a propus o definiție strictă a confidențialității datelor: atacatorul nu ar trebui să învețe nimic despre o persoană pe care nu o cunoștea înainte de a utiliza setul de date sensibile. Deși această garanție a eșuat (și vom vedea de ce), este important să înțelegem de ce confidențialitatea diferențială este construită așa cum este.definiția lui Dalenius a eșuat deoarece, în 2006, informaticianul Cynthia Dwork a dovedit că această garanție era imposibil de oferit—cu alte cuvinte, orice acces la date sensibile ar încălca această definiție a confidențialității. Problema pe care a găsit-o a fost că anumite tipuri de informații de fond ar putea duce întotdeauna la o nouă concluzie despre un individ. Dovada ei este ilustrată în următoarea anecdotă: Știu că Alice e cu doi centimetri mai înaltă decât o Lituaniană obișnuită. Apoi interacționez cu un set de date de femei lituaniene și calculez înălțimea medie, pe care nu o știam înainte. Acum știu exact înălțimea lui Alice, chiar dacă nu era în setul de date. Este imposibil să se țină cont de toate tipurile de informații de fond care ar putea duce la o nouă concluzie despre o persoană din utilizarea unui set de date.

Dwork, după ce a demonstrat cele de mai sus, a propus o nouă definiție: confidențialitate diferențială.

ce este confidențialitatea diferențială?

confidențialitatea diferențială garantează următoarele: că atacatorul nu poate învăța practic nimic mai mult despre un individ decât ar învăța dacă dosarul acelei persoane ar lipsi din setul de date. Deși este mai slabă decât definiția vieții private a lui Dalenius, garanția este suficient de puternică pentru că se aliniază cu stimulentele din lumea reală—indivizii nu au niciun stimulent să nu participe la un set de date, deoarece analiștii acelui set de date vor trage aceleași concluzii despre acel individ dacă individul se include sau nu în setul de date. Deoarece informațiile lor personale sensibile sunt aproape irelevante în rezultatele sistemului, utilizatorii pot fi siguri că organizația care le gestionează datele nu le încalcă confidențialitatea.

analiștii care învață „practic nimic mai mult despre un individ” înseamnă că sunt limitați la o schimbare nesemnificativă de mică în credința despre orice individ. (Aici și mai jos,” modificare ” se referă la schimbarea dintre utilizarea unui set de date și utilizarea aceluiași set de date minus înregistrarea oricărei persoane.) Amploarea acestei modificări este controlată de un parametru cunoscut sub numele de XV, care stabilește limita de modificare a probabilității oricărui rezultat. O valoare scăzută de 0,1, cum ar fi 0,1, înseamnă că foarte puțin se poate schimba în credințele despre orice individ. O valoare ridicată de 50, cum ar fi 50, înseamnă că credințele se pot schimba substanțial mai mult. Definiția formală este următoarea.

un algoritm a este de tip A, în mod diferențiat privat, dacă și numai dacă:

pr, e^ * PR,

pentru toate X și pentru toate perechile de seturi de date D, D’ unde D’ este D cu o singură înregistrare-adică datele unei persoane—lipsă. Simbolul e se referă la Constanta matematică. Rețineți că această definiție are sens doar pentru algoritmii randomizați. Un algoritm care dă rezultate deterministe nu este un candidat pentru confidențialitate diferențială.apelul principal al garanției diferențiale de confidențialitate este limitarea sumei pe care orice analist o poate afla despre o persoană. În plus, acesta are următoarele proprietăți utile:

• Composability: dacă două întrebări au răspuns cu diferențial de confidențialitate garanții de nivel ϵ1 și ϵ2, o pereche de interogări este acoperit de o garanție de nivel (ϵ1 + ϵ2). Amintiți-vă că o valoare mai mare a lui hectar înseamnă o garanție mai slabă.
• rezistență împotriva informațiilor de fond arbitrare: garanția nu se bazează în niciun fel pe informațiile de fond pe care le cunoaște atacatorul. Această proprietate este unul dintre principalele motive pentru care confidențialitatea diferențiată este mai puternică decât o garanție anterioară de confidențialitate, k-anonimatul.
• securitate în post-procesare: nu există restricții cu privire la ceea ce se poate face cu un rezultat privat diferențiat – indiferent cu ce este combinat sau cum este transformat, este încă privat diferențiat.

cum se realizează această garanție în software? Algoritmii privați diferențiați sunt algoritmi randomizați care adaugă zgomot în punctele cheie din algoritm. Unul dintre cei mai simpli algoritmi este mecanismul Laplace, care poate post-procesa rezultatele interogărilor agregate (de exemplu, numărări, sume și mijloace) pentru a le face diferențiat private. Mai jos este un exemplu de cod Java pentru mecanismul Laplace specific numărării interogărilor:

import org.apache.commons.math3.distribution.LaplaceDistribution;double laplaceMechanismCount(long realCountResult, double epsilon) { LaplaceDistribution ld = new LaplaceDistribution(0, 1 / epsilon); double noise = ld.sample(); return realCountResult + noise;}

părțile cheie ale acestei funcții sunt

1. instanțiază o distribuție de probabilitate Laplace (a se vedea Figura 1) centrată la 0 și scalată la 1 / inkt. Folosim implementarea Apache Commons, „LaplaceDistribution”, care este construită cu două argumente: media distribuției și scara distribuției. Rețineți că Epsilon mai mic (mai multă confidențialitate) duce la o scară mai mare și, astfel, la o distribuție mai largă și la mai mult zgomot.
2. desenați un eșantion aleatoriu din această distribuție. Această funcție sample () ia un număr aleatoriu între 0 și 1 și aplică funcția de distribuție inversă cumulativă (CDF) a distribuției Laplace la acest număr. Acest proces are ca rezultat un număr aleatoriu, astfel încât probabilitatea sa de a fi orice valoare specifică se potrivește cu distribuția. Ca o modalitate alternativă de a gândi la asta, dacă această funcție a eșantionului ar fi invocată de un milion de ori pentru a obține un milion de eșantioane, forma histogramei acestor eșantioane s-ar potrivi îndeaproape cu forma distribuției Laplace.
3. perturbați valoarea reală adăugând valoarea aleatorie de la Pasul 2.

să luăm în considerare de ce acest algoritm este diferit Privat, Luând punctul de vedere al unui atacator numit Eve. Spuneți că setul de date este de date de sănătate mintală, iar Eve a conceput un atac de urmărire (Vezi mai sus) care va dezvălui dacă ținta ei, Bob, primește consiliere pentru alcoolism sau nu. Dacă rezultatul interogării este 48, Eva știe că Bob primește consiliere; dacă este 47, Eva știe contrariul.

Dacă răspunsul este 47 sau 48, mecanismul Laplace va returna un rezultat zgomotos undeva în jurul valorii de 47 sau 48. Poate returna 49, 46 sau chiar, cu probabilitate mai mică, 44 sau 51 (vezi Figura 2 pentru o histogramă). În practică, este imposibil ca Eva să fie foarte sigură dacă răspunsul adevărat a fost de 47 sau 48 de ani și, astfel, credințele ei despre faptul dacă Bob este în consiliere pentru alcoolism sau acum nu se vor schimba în mod semnificativ.

Figura 1: distribuția Laplace centrată la 0 cu scara 1. În imagine este funcția de densitate a probabilității (PDF) a distribuției—axa y este probabilitatea relativă ca variabila să ia valoarea pe axa X.

Figura 2: rezultatele probabile ale interogării de numărare pentru cele două scenarii, unde răspunsul real este 47 și când este 48. Un număr mic de ieșiri nu ar fi suficient pentru a distinge din ce distribuție provin. Epsilon este setat la 0,67.

este posibil să fi observat prin acest punct că Eva ar putea reduce zgomotul repetând interogarea de mai multe ori și văzând dacă răspunsurile se grupează în jurul valorii de 47 sau 48. Pentru a preveni această tactică, sistemele private diferențiate trebuie să aibă un „buget de Confidențialitate”, un plafon pentru suma celor de la 7XT utilizate în fiecare interogare. Acest plafon funcționează din cauza proprietății de compozabilitate a confidențialității diferențiale descrise mai sus. Ei pot cere câteva interogări relativ cu zgomot redus sau multe sute de interogări cu zgomot ridicat, dar oricum, nu vor putea stabili cu încredere dacă răspunsul adevărat este 47 sau 48.

în cele din urmă, rețineți că mecanismul Laplace pentru numărători este doar un algoritm simplu diferențiat privat. Mecanismul Laplace poate fi extins pentru a lucra pentru sume și alte interogări agregate. În plus, există algoritmi fundamental diferiți care s-au dovedit a satisface garanția diferențială de confidențialitate. Câteva merită explorate sunt algoritmul privat de greutăți Multiplicative, mecanismul exponențial de greutăți Multiplicative și DualQuery.

Confidențialitate diferențială în acțiune

În iunie 2016, Apple a anunțat că va începe să utilizeze algoritmi diferențiați privați pentru a colecta statistici comportamentale de pe iPhone. Acest anunț, pe lângă faptul că a provocat o creștere uriașă a interesului diferențial pentru confidențialitate, a arătat că confidențialitatea diferențiată poate ajuta organizațiile majore să obțină o nouă valoare din datele pe care anterior nu le-au atins din cauza preocupărilor de confidențialitate.

deși Apple a făcut până acum puține detalii publice, algoritmul folosit în iPhone pare similar cu proiectul RAPPOR al Google. Google a implementat o caracteristică în Chrome care colectează statistici comportamentale din browserele Chrome printr-un algoritm de răspuns randomizat privat diferențiat.

în răspunsul randomizat, zgomotul aleatoriu este adăugat la statistici înainte ca acestea să fie transmise colectorului. De exemplu, dacă statistica reală este 0, browserul va înlocui cu o anumită probabilitate 0 cu un 0 sau 1 selectat aleatoriu. Fiecare utilizator are un grad mare de negare a valorii pe care o raportează software-ul său, deoarece ar putea fi o valoare aleatorie. Dar, în mod colectiv, semnalul iese în evidență peste zgomotul aleatoriu, iar organizația care colectează statisticile (adică Google sau Apple) poate observa cu exactitate tendințele.

interesant este că nici Google, nici Apple, din cunoștințele noastre, nu au dezvăluit valoarea de la XV care merge cu garanția lor diferențială de confidențialitate. Avem nevoie de această valoare pentru a înțelege protecția oferită de garanție. Dacă folosesc o valoare suficient de mare a lui hectolixt, analiștii pot afla în continuare fapte sensibile despre utilizatori cu încredere ridicată. Pentru o protecție semnificativă a vieții private, este necesară o valoare scăzută a produsului.

algoritmi diferențiați privați au fost, de asemenea, implementați în produsele de analiză care păstrează confidențialitatea, cum ar fi cele dezvoltate de angajatorul meu Privitar. Aceste produse permit companiilor care lucrează cu date valoroase și sensibile să încorporeze algoritmi privați diferențiat în arhitectura lor de date, oferind garanții de confidențialitate utilizatorilor lor, în timp ce efectuează în continuare analize semnificative asupra datelor.

Privind înainte

atât comunitățile de inginerie, cât și cele de cercetare au căi înainte cu Confidențialitate diferențiată. Pentru ingineri, sarcina este de a deveni educați cu privire la confidențialitatea diferențială și de a se asigura că este utilizată acolo unde este cazul pentru protecția confidențialității utilizatorilor. Pentru cercetători, este de a găsi algoritmi mai diferiți și mai buni, îmbunătățind setul de instrumente cu care putem permite analiza datelor care păstrează confidențialitatea.

cu toții avem de câștigat din stabilirea garanțiilor de confidențialitate și a succeselor analizei datelor. Din ambele motive, așteptăm cu nerăbdare ca mai multe organizații să adopte confidențialitatea diferențiată.

despre autor

Charlie Cabot este un om de știință de date senior la Privitar, un startup de Confidențialitate a datelor care construiește software de înaltă performanță pentru anonimizarea datelor, inclusiv algoritmi de perturbare și generalizare și mecanisme diferențiat private, pentru a facilita utilizarea în siguranță a seturilor de date sensibile. Charlie se concentrează pe garanțiile de confidențialitate demonstrabile și pe impactul statistic al anonimizării asupra analizei și științei datelor. Anterior, lucrând în domeniul securității cibernetice, Charlie a proiectat abordări bazate pe învățarea automată a detectării malware-ului și a modelat atacuri cibernetice asupra rețelelor de calculatoare.