Differentiel privatliv

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 15. februar 2022; checks kræver 2 redigeringer .

Differentielt privatliv er et sæt metoder, der giver de mest nøjagtige forespørgsler til en statistisk database, samtidig med at muligheden for at identificere individuelle poster i den minimeres.

Introduktion

Differentiel privatliv er den matematiske definition af tab af enkeltpersoners følsomme data, når deres personlige oplysninger bruges til at skabe et produkt. Udtrykket blev opfundet af Cynthia Dwork i 2006 [1] men er også brugt i en tidligere publikation af Dwork, Frank McSherry , Kobe Nissim og Adam D. Smith [2] . Arbejdet er især baseret på forskning fra Nissim og Irit Dinur [3] [4] , som viste, at det er umuligt at offentliggøre oplysninger fra en privat statisk database uden at blotlægge nogle af de private oplysninger, og at hele databasen kan videregives ved at offentliggøre resultaterne af et ret lille antal anmodninger [4] .

Efter undersøgelsen blev det klart, at det var umuligt at sikre fortrolighed i statistiske databaser ved hjælp af eksisterende metoder, og som følge heraf var der behov for nye, der ville begrænse risiciene forbundet med tab af private oplysninger indeholdt i statistikkerne. database. Som følge heraf er der blevet skabt nye metoder, der i de fleste tilfælde gør det muligt at levere nøjagtige statistikker fra databasen, samtidig med at de giver et højt niveau af fortrolighed [5] [6] .

Princip og illustration

Differentieret privatliv er baseret på at indføre tilfældighed i dataene.

Et simpelt eksempel udviklet inden for samfundsvidenskab [7] er at bede en person om at besvare spørgsmålet "Har du attribut A?" efter følgende procedure:

plat eller krone
Hvis der kommer hoveder op, så svar ærligt på spørgsmålet.
Ellers smid igen, hvis det kommer op i hovedet, svar "Ja", hvis det er haler - "Nej"

Fortrolighed opstår, fordi det er umuligt at vide med sikkerhed ud fra svaret, om en person har en given egenskab. Ikke desto mindre er disse data signifikante, da positive svar kommer fra en fjerdedel af de mennesker, der ikke har denne egenskab, og tre fjerdedele af dem, der faktisk har den. Således, hvis p er den sande andel af personer med A, så forventer vi at få (1/4) (1- p) + (3/4) p = (1/4) + p / 2 positive svar. Derfor kan man estimere R.

Formel definition og brugseksempel

Lad ε være et positivt reelt tal, og A være en sandsynlighedsalgoritme , der tager et sæt data som input (repræsenterer handlingerne fra en betroet part, der har dataene). Betegn billedet af A ved im A . Algoritme A er ε - forskelligt privat , hvis for alle datasæt, og som adskiller sig med ét element (dvs. data fra én person), såvel som alle delmængder S af sættet im A : $D_{1}$ $D_{2}$

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

hvor P er sandsynligheden.

Ifølge denne definition er differentieret privatliv en betingelse for datapubliceringsmekanismen (det vil sige bestemt af den betroede part, der frigiver oplysninger om datasættet), ikke selve datasættet. Intuitivt betyder dette, at for alle to ens datasæt vil den differentielle private algoritme opføre sig omtrent det samme på begge datasæt. Definitionen giver også en stærk garanti for, at tilstedeværelsen eller fraværet af en person ikke vil påvirke det endelige output af algoritmen.

Antag for eksempel, at vi har en database med medicinske journaler, hvor hver journal er et par af ( Navn , X ), hvor er nul eller én, der angiver, om personen har gastritis eller ej: $D_{1}$ $x$

Navn	Tilstedeværelse af gastritis (X)
Ivan	en
Peter	0
Vasilisa	en
Michael	en
Maria	0

Antag nu, at en ondsindet bruger (ofte omtalt som en angriber) ønsker at finde ud af, om Mikhail har gastritis eller ej. Lad os også antage, at han ved, hvilken række der indeholder oplysninger om Mikhail i databasen. Antag nu, at en angriber kun har tilladelse til at bruge en specifik form for forespørgsel , der returnerer en delvis sum af de første rækker i en kolonne i databasen. For at finde ud af, om Mikhail har gastritis, udfører angriberen forespørgsler: og beregner derefter deres forskel. I dette eksempel er , og , så deres forskel er . Dette betyder, at feltet "Tilstedeværelse af gastritis" i Mikhails linje skal være lig med . Dette eksempel viser, hvordan individuelle oplysninger kan kompromitteres, selv uden en eksplicit anmodning om en specifik persons data. $Q_{i}$ $jeg$ $x$ $Q_{4}(D_{1})$ $Q_{3}(D_{1})$ $Q_{4}(D_{1})=3$ $Q_{3}(D_{1})=2$ $en$ $en$

Hvis vi fortsætter med dette eksempel, hvis vi bygger datasættet ved at erstatte (Mikhail, 1) med (Mikhail, 0), så vil angriberen være i stand til at skelne fra ved at beregne for hvert datasæt. Hvis en angriber skulle opnå værdier via en ε-differentiel privat algoritme, for en tilstrækkelig lille ε, så ville han ikke være i stand til at skelne mellem de to datasæt. $D_{2}$ $D_{2}$ $D_{1}$ ${\displaystyle Q_{4}-Q_{3))$ $Q_{i}$

Mønteksemplet beskrevet ovenfor er -differentiel privat [8] . $(\ln 3)$

Grænsetilfælde

Tilfældet, hvor ε = 0 er ideel til at opretholde fortrolighed, da tilstedeværelsen eller fraværet af nogen information om nogen person i databasen ikke påvirker resultatet af algoritmen, men en sådan algoritme er meningsløs med hensyn til nyttig information, da selv med nul antal personer vil det give det samme eller lignende resultat.

Hvis ε har en tendens til uendelig, vil enhver sandsynlighedsalgoritme passe til definitionen, da uligheden altid er opfyldt. $P[{\mathcal {A}}(D_{1})\in S]\leq \infty \times P[{\mathcal {A}}(D_{2})\in S],$

Følsomhed

Lad være et positivt heltal, være et datasæt og være en funktion. Følsomheden [9] af funktionen, betegnet med , bestemmes af formlen $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},

over alle par af datasæt og i , der ikke adskiller sig med mere end ét element, og hvor angiver normen . $D_{1}$ $D_{2}$ $\mathcal{D}$ ${\displaystyle \lVert \cdot \rVert _{1))$ $\ell _{1}$

I ovenstående eksempel på en medicinsk database, hvis vi overvejer følsomheden af funktionen , så er den lig med , da ændring af nogen af posterne i databasen fører til noget, der enten ændres til eller ikke ændres. $d$ $Q_{i}$ $en$ $Q_{i}$ $en$

Laplace mekanisme

På grund af det faktum, at differentieret privatliv er et probabilistisk begreb, har enhver af dens metoder nødvendigvis en tilfældig komponent. Nogle af dem bruger, ligesom Laplaces metode, tilføjelsen af kontrolleret støj til den funktion, der skal beregnes.

Laplace-metoden tilføjer Laplace-støj, det vil sige støjen fra Laplace-fordelingen , som kan udtrykkes som en sandsynlighedstæthedsfunktion, og som har nul middelværdi og standardafvigelse . Lad os definere outputfunktionen som en funktion med reel værdi i formen hvor , og er den forespørgsel, som vi planlagde at udføre i databasen. Det kan således betragtes som en kontinuert stokastisk variabel , hvor ${\tekst{støj}}(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{støj}}(tf(D_{1})) }{{\text{støj}}(tf(D_{2})))}}\,\!

som ikke er mere end (pdf - sandsynlighedstæthedsfunktion eller sandsynlighedstæthedsfunktion). I dette tilfælde kan vi betegne privatlivsfaktoren ε. Er således ifølge definitionen ε-differentiel privat. Hvis vi forsøger at bruge dette koncept i ovenstående eksempel om tilstedeværelsen af gastritis, så for at være en ε-differentiel privat funktion, skal holde , siden ). $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$

Ud over Laplace-støj kan andre typer støj (for eksempel Gaussisk) også bruges, men de kan kræve en lille lempelse af definitionen af differentieret privatliv [10] .

Sammensætning

Konsekvent applikation

Hvis vi udfører en forespørgsel ε-differentielt sikre gange, og den introducerede tilfældige støj er uafhængig for hver forespørgsel, så vil det totale privatliv være (εt)-differentiel. Mere generelt, hvis der er uafhængige mekanismer: , hvis privatlivsgarantier er henholdsvis lige store, så vil enhver funktion være -differentiel privat [11] . $T$ $N$ ${\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{n}$ ${\displaystyle \epsilon _{1},\dots ,\epsilon _{n))$ $g({\mathcal {M}}_{1},\dots,{\mathcal {M}}_{n})$ $(\sum \limits _{i=1}^{n}\epsilon _{i})$

Parallel komposition

Desuden, hvis forespørgsler udføres på ikke-overlappende undersæt af databasen, vil funktionen være -differentiel privat [11] . $g$ $(\max _{i}{\epsilon }_{i})$

Gruppens privatliv

Differentiel privatliv er generelt designet til at beskytte privatlivets fred mellem databaser, der kun adskiller sig med én linje. Det betyder, at ingen modstander med vilkårlige hjælpeoplysninger kan vide, om en enkelt deltager har givet sine oplysninger. Dette koncept kan dog udvides til en gruppe, hvis vi ønsker at beskytte databaser, der adskiller sig efter rækker, så en angriber med vilkårlig understøttende information ikke kan vide, om individuelle medlemmer har givet deres oplysninger. Dette kan opnås, hvis formlen fra definitionen erstattes af [12] , så for D 1 og D 2 , der er forskellige med rækker $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}) \i S]\,\!

Ved at bruge parameteren (ε/c) i stedet for ε kan du således opnå det ønskede resultat og beskytte strengene. Med andre ord, i stedet for at hvert element er ε-differentiel privat, nu er hver gruppe af elementer ε-differentiel privat, og hvert element er (ε/c)-differentiel privat. $c$ $c$

Anvendelse af differentieret privatliv til applikationer i den virkelige verden

Til dato er der flere anvendelser for differentieret privatliv:

US Census Bureau ved visning af statistik [13]
Google RAPPOR til at indsamle statistik om uønsket software, der krænker brugerpræferencer [14] ( open source implementering af RAPPOR )
Google , til deling af trafikhistorikstatistikker [15] .
Den 13. juni 2016 annoncerede Apple sin hensigt om at bruge differentieret privatliv i iOS 10 for at forbedre sine smarte support- og teknologitilbud [16]

Noter

↑ Dwork Cynthia, 2006 , s. otte.
↑ Cynthia Dwork, Frank McSherry, Kobbi Nissim og Adam Smith=. Kalibrering af støj til følsomhed i privat dataanalyse // Proceedings of the Third conference on Theory of Cryptography (TCC'06), Shai Halevi og Tal Rabin (red.). - Springer-Verlag, Berlin, Heidelberg, 2006. - S. 266 . - doi : 10.1007/11681878_14 .
↑ Dwork Cynthia, 2006 , s. 12.
↑ 12 Nissim et al., 2003 , s. 202-206.
↑ HILTON, MICHAEL. Differentiel privatliv: En historisk undersøgelse (ubestemt) . , s.1
↑ Dwork, 2008 , s. 3-13.
↑ Roth et al, 2014 , s. femten.
↑ Roth et al, 2014 , s. tredive.
↑ Dwork et al, 2006 , s. 271-272.
↑ Dwork, 2008 , s. 16.
↑ 12 McSherry , 2009 , s. 6.
↑ Dwork Cynthia, 2006 , s. 9.
↑ Machanavajjhala et al., 2008 , s. en.
↑ Erlingsson et al, 2014 , s. en.
↑ Takling af urban mobilitet med teknologi af Andrew Eland . Google Politik Europa-blog . Dato for adgang: 19. december 2017. Arkiveret fra originalen 10. december 2017. (ubestemt)
↑ Apple - Presseinfo - Apple forhåndsviser iOS 10, den største iOS-udgivelse nogensinde . Æble . Dato for adgang: 16. juni 2016. Arkiveret fra originalen 29. april 2017. (ubestemt)

Litteratur

Ashwin Machanavajjhala, Daniel Kifer, John M. Abowd, Johannes Gehrke, Lars Vilhuber. Privatliv: Theory meets Practice on the Map // In Proceedings of the 24th International Conference on Data Engineering, (ICDE). – 2008.
Úlfar Erlingsson, Vasyl Pihur, Aleksandra Korolova. RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response // Proceedings of the 21st ACM Conference on Computer and Communications Security (CCS). – 2014.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, Adam Smith. Kalibrering af støj til følsomhed i privat dataanalyse // Theory of Cryptography Conference (TCC). - Springer, 2006. - doi : 10.1007/11681878_14 .
Frank D. McSherry. Integrerede forespørgsler om beskyttelse af personlige oplysninger: en platform, der kan udvides til dataanalyse, der beskytter privatlivets fred // Proceedings of the 35th SIGMOD International Conference on Management of Data (SIGMOD). - 2009. - doi : 10.1145/1559845.1559850 .
Cynthia Dwork, Aaron Roth. The Algorithmic Foundations of Differential Privacy // Fundamenter og tendenser inden for teoretisk datalogi. - 2014. - August (bd. 9). - doi : 10.1561/0400000042 .
Dwork, Cynthia. Differentiel privatliv: En undersøgelse af resultater // Agrawal, Manindra; Du, Dingzhu; Duan, Zhenhua; Li, Angsheng teori og anvendelser af beregningsmodeller. Forelæsningsnotater i datalogi. - Springer Berlin Heidelberg, 2008. - 25. april. doi : 10.1145 / 773153.773173 .
Dwork, Cynthia. Differentiel privatliv . - International Colloquium on Automata, Languages and Programming (ICALP), 2006. - doi : 10.1007/11787006_1 .
Irit Dinur, Kobbi Nissim. Afsløring af information, mens privatlivets fred beskyttes // Proceedings af det 22. ACM SIGMOD-SIGACT-SIGART symposium om principper for databasesystemer (PODS '03). - ACM, New York, NY, USA, 2003. - doi : 10.1145/773153.773173 .