Differentiell integritet

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 15 februari 2022; kontroller kräver 2 redigeringar .

Differentiell integritet är en uppsättning metoder som ger de mest exakta frågorna till en statistisk databas samtidigt som möjligheten att identifiera enskilda poster i den minimeras.

Inledning

Differentiell integritet är den matematiska definitionen av förlust av individers känsliga data när deras personliga information används för att skapa en produkt. Termen myntades av Cynthia Dwork 2006 [1] men används också i en tidigare publikation av Dwork, Frank McSherry , Kobe Nissim och Adam D. Smith [2] . Arbetet baseras särskilt på forskning av Nissim och Irit Dinur [3] [4] som visade att det är omöjligt att publicera information från en privat statisk databas utan att exponera en del av den privata informationen, och att hela databasen kan lämnas ut. genom att publicera resultaten av ett ganska litet antal förfrågningar [4] .

Efter studien stod det klart att det var omöjligt att säkerställa konfidentialitet i statistiska databaser med hjälp av befintliga metoder, och som ett resultat av detta fanns ett behov av nya som skulle begränsa riskerna förknippade med förlust av privat information i statistiken. databas. Som ett resultat av detta har nya metoder skapats som i de flesta fall gör det möjligt att tillhandahålla korrekt statistik från databasen, samtidigt som det ger en hög nivå av konfidentialitet [5] [6] .

Princip och illustration

Differentiell integritet bygger på att införa slumpmässighet i data.

Ett enkelt exempel utvecklat inom samhällsvetenskapen [7] är att be en person svara på frågan "Har du attribut A?" enligt följande procedur:

slå ett mynt
Om huvuden kommer upp, svara ärligt på frågan.
Annars, kasta igen, om det kommer upp huvuden, svara "Ja", om det är svansar - "Nej"

Sekretess uppstår eftersom det är omöjligt att med säkerhet veta från svaret om en person har en given egenskap. Ändå är dessa uppgifter betydande, eftersom positiva svar kommer från en fjärdedel av de människor som inte har denna egenskap och tre fjärdedelar av dem som faktiskt har den. Således, om p är den sanna andelen personer med A, förväntar vi oss att få (1/4) (1- p) + (3/4) p = (1/4) + p / 2 positiva svar. Därför kan man uppskatta R.

Formell definition och användningsexempel

Låt ε vara ett positivt reellt tal och A vara en probabilistisk algoritm som tar en uppsättning data som indata (representerar handlingar av en betrodd part som har datan). Beteckna bilden av A av im A . Algoritm A är ε - differentiellt privat om för alla datamängder och som skiljer sig åt med ett element (d.v.s. data för en person), såväl som alla delmängder S av uppsättningen im A : $D_{1}$ $D_{2}$

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

där P är sannolikheten.

Enligt denna definition är differentiell integritet ett villkor för datapubliceringsmekanismen (det vill säga bestäms av den betrodda part som släpper information om datamängden), inte själva datamängden. Intuitivt betyder detta att för två liknande datauppsättningar kommer den differentiella privata algoritmen att bete sig ungefär likadant på båda datauppsättningarna. Definitionen ger också en stark garanti för att närvaron eller frånvaron av en individ inte kommer att påverka den slutliga utmatningen av algoritmen.

Anta till exempel att vi har en databas med medicinska journaler där varje journal är ett par av ( Namn , X ) där är noll eller en som anger om personen har gastrit eller inte: $D_{1}$ $X$

namn	Förekomst av gastrit (X)
Ivan	ett
Peter	0
Vasilisa	ett
Michael	ett
Maria	0

Anta nu att en illvillig användare (ofta kallad en angripare) vill ta reda på om Mikhail har gastrit eller inte. Låt oss också anta att han vet vilken rad som innehåller information om Mikhail i databasen. Anta nu att en angripare endast tillåts använda en specifik form av fråga som returnerar en delsumma av de första raderna i en kolumn i databasen. För att ta reda på om Mikhail har gastrit, utför angriparen frågor: och , beräknar sedan deras skillnad. I det här exemplet är , och , så skillnaden är . Detta betyder att fältet "Närvaro av gastrit" i Mikhails linje bör vara lika med . Detta exempel visar hur individuell information kan äventyras även utan en uttrycklig begäran om en specifik persons uppgifter. $Q_{i}$ $i$ $X$ $Q_{4}(D_{1})$ $Q_{3}(D_{1})$ $Q_{4}(D_{1})=3$ $Q_{3}(D_{1})=2$ $ett$ $ett$

Om vi fortsätter med detta exempel, om vi bygger datamängden genom att ersätta (Mikhail, 1) med (Mikhail, 0), kommer angriparen att kunna skilja från genom att beräkna för varje datamängd. Om en angripare skulle få värden via en ε-differentiell privat algoritm, för en tillräckligt liten ε, skulle han inte kunna skilja mellan de två datamängderna. $D_{2}$ $D_{2}$ $D_{1}$ ${\displaystyle Q_{4}-Q_{3))$ $Q_{i}$

Myntexemplet som beskrivs ovan är -differentiellt privat [8] . $(\ln 3)$

Gränsfall

Fallet när ε = 0 är idealiskt för att upprätthålla konfidentialitet, eftersom närvaron eller frånvaron av någon information om någon person i databasen inte påverkar resultatet av algoritmen, men en sådan algoritm är meningslös när det gäller användbar information, eftersom även med noll antal personer kommer det att ge samma eller liknande resultat.

Om ε tenderar till oändlighet, så kommer vilken sannolikhetsalgoritm som helst att passa definitionen, eftersom ojämlikheten alltid är uppfylld. $P[{\mathcal {A}}(D_{1})\in S]\leq \infty \times P[{\mathcal {A}}(D_{2})\in S],$

Känslighet

Låt vara ett positivt heltal, vara en datamängd och vara en funktion. Känsligheten [9] för funktionen, betecknad med , bestäms av formeln $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},

över alla par av datamängder och in , som inte skiljer sig åt med mer än ett element och där anger normen . $D_{1}$ $D_{2}$ $\mathcal{D}$ ${\displaystyle \lVert \cdot \rVert _{1))$ $\ell _{1}$

I exemplet ovan på en medicinsk databas, om vi tar hänsyn till känsligheten för funktionen , då är den lika med , eftersom att ändra någon av posterna i databasen leder till något som antingen ändras till eller inte ändras. $d$ $Q_{i}$ $ett$ $Q_{i}$ $ett$

Laplace mekanism

På grund av det faktum att differentiell integritet är ett probabilistiskt koncept, har alla dess metoder nödvändigtvis en slumpmässig komponent. Vissa av dem använder, som Laplaces metod, tillägg av kontrollerat brus till funktionen som ska beräknas.

Laplacemetoden lägger till Laplace-brus, det vill säga bruset från Laplace-fördelningen , som kan uttryckas som en sannolikhetstäthetsfunktion och som har noll medelvärde och standardavvikelse . Låt oss definiera utdatafunktionen som en verkligt värderad funktion i formen där , och är frågan som vi planerade att köra i databasen. Det kan alltså betraktas som en kontinuerlig slumpvariabel , där ${\text{brus}}(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{brus}}(tf(D_{1})) }{{\text{brus}}(tf(D_{2})))}}\,\!

som inte är mer än (pdf - sannolikhetstäthetsfunktion eller sannolikhetstäthetsfunktion). I det här fallet kan vi beteckna integritetsfaktorn ε. Är alltså enligt definitionen ε-differentiellt privat. Om vi försöker använda detta begrepp i exemplet ovan om närvaron av gastrit, måste det för att vara en ε-differentiell privat funktion hålla , eftersom ). $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$

Förutom Laplace-buller kan andra typer av buller (till exempel Gaussiskt) också användas, men de kan kräva en liten uppmjukning av definitionen av differentiell integritet [10] .

Komposition

Konsekvent applikation

Om vi kör en fråga ε-differentiellt säkra gånger, och det slumpmässiga bruset som introduceras är oberoende för varje fråga, så kommer den totala integriteten att vara (εt)-differentiell. Mer generellt, om det finns oberoende mekanismer: , vars integritetsgarantier är likvärdiga respektive, kommer alla funktioner att vara -differentiellt privata [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})$

Parallell komposition

Dessutom, om frågor exekveras på icke-överlappande delmängder av databasen, så skulle funktionen vara -differentiellt privat [11] . $g$ $(\max _{i}{\epsilon }_{i})$

Gruppens integritet

Differentiell integritet i allmänhet är utformad för att skydda integriteten mellan databaser som skiljer sig bara en rad. Detta innebär att ingen motståndare med godtycklig hjälpinformation kan veta om någon enskild deltagare har lämnat sin information. Detta koncept kan dock utvidgas till en grupp om vi vill skydda databaser som skiljer sig åt efter rader så att en angripare med godtycklig stödinformation inte kan veta om enskilda medlemmar har lämnat sin information. Detta kan uppnås om formeln från definitionen ersätts med [12] , då för D 1 och D 2 som skiljer sig åt med rader $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]\,\!

Genom att använda parametern (ε/c) istället för ε kan du alltså uppnå önskat resultat och skydda strängarna. Med andra ord, istället för att varje element är ε-differentiellt privat, nu är varje grupp av element ε-differentiellt privat, och varje element är (ε/c)-differentiellt privat. $c$ $c$

Tillämpa differentiell integritet på verkliga applikationer

Hittills finns det flera användningsområden för differentiell integritet:

US Census Bureau när man visar statistik [13]
Google RAPPOR för att samla in statistik om oönskad programvara som gör intrång i användarpreferenser [14] ( öppen källkod implementering av RAPPOR )
Google , för att dela trafikhistorikstatistik [15] .
Den 13 juni 2016 tillkännagav Apple sin avsikt att använda differentiell integritet i iOS 10 för att förbättra sina smarta support- och teknologierbjudanden [16]

Anteckningar

↑ Dwork Cynthia, 2006 , sid. åtta.
↑ Cynthia Dwork, Frank McSherry, Kobbi Nissim och Adam Smith=. Kalibrering av brus för känslighet i privat dataanalys // Proceedings of the Third conference on Theory of Cryptography (TCC'06), Shai Halevi och Tal Rabin (Eds.). - Springer-Verlag, Berlin, Heidelberg, 2006. - S. 266 . - doi : 10.1007/11681878_14 .
↑ Dwork Cynthia, 2006 , sid. 12.
↑ 12 Nissim et al, 2003 , s. 202-206.
↑ HILTON, MICHAEL. Differential Privacy: A Historical Survey (obestämd tid) . , s.1
↑ Dwork, 2008 , s. 3-13.
↑ Roth et al, 2014 , sid. femton.
↑ Roth et al, 2014 , sid. trettio.
↑ Dwork et al, 2006 , s. 271-272.
↑ Dwork, 2008 , sid. 16.
↑ 12 McSherry , 2009 , sid. 6.
↑ Dwork Cynthia, 2006 , sid. 9.
↑ Machanavajjhala et al, 2008 , sid. ett.
↑ Erlingsson et al, 2014 , sid. ett.
↑ Att tackla stadsrörlighet med teknologi av Andrew Eland . Google Policy Europe Blog . Datum för åtkomst: 19 december 2017. Arkiverad från originalet 10 december 2017. (obestämd)
↑ Apple - Pressinformation - Apple förhandsgranskar iOS 10, den största iOS-versionen någonsin . Apple . Tillträdesdatum: 16 juni 2016. Arkiverad från originalet 29 april 2017. (obestämd)

Litteratur

Ashwin Machanavajjhala, Daniel Kifer, John M. Abowd, Johannes Gehrke, Lars Vilhuber. Sekretess: 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 av brus mot känslighet i privat dataanalys // Theory of Cryptography Conference (TCC). - Springer, 2006. - doi : 10.1007/11681878_14 .
Frank D. McSherry. Integrerade frågor om integritet: en utbyggbar plattform för dataanalys som bevarar integritet // 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 // Foundations and Trends in Theoretical Computer Science. - 2014. - Augusti (bd 9). - doi : 10.1561/0400000042 .
Dwork, Cynthia. Differential Privacy: A Survey of Results // Agrawal, Manindra; Du, Dingzhu; Duan, Zhenhua; Li, Angsheng Teori och tillämpningar av beräkningsmodeller. Föreläsningsanteckningar i datavetenskap. - Springer Berlin Heidelberg, 2008. - 25 april. doi : 10.1145 / 773153.773173 .
Dwork, Cynthia. Differentiell integritet . - International Colloquium on Automata, Languages and Programming (ICALP), 2006. - doi : 10.1007/11787006_1 .
Irit Dinur, Kobbi Nissim. Avslöjande av information samtidigt som integritetsskyddet skyddas // Förfaranden från det tjugoandra ACM SIGMOD-SIGACT-SIGART-symposiet om principer för databassystem (PODS '03). - ACM, New York, NY, USA, 2003. - doi : 10.1145/773153.773173 .