Erotettu yksityisyys

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 15. helmikuuta 2022 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Differentiaalinen yksityisyys on joukko menetelmiä, jotka tarjoavat tarkimmat kyselyt tilastotietokantaan minimoiden samalla mahdollisuuden tunnistaa yksittäisiä tietueita siinä.

Johdanto

Differentiaalinen yksityisyys on matemaattinen määritelmä yksilöiden arkaluonteisten tietojen menettämisestä, kun heidän henkilökohtaisia tietojaan käytetään tuotteen luomiseen. Termin loi Cynthia Dwork vuonna 2006 [1] , mutta sitä käytetään myös Dworkin, Frank McSherryn , Kobe Nissim ja Adam D. Smithin 2] aikaisemmassa julkaisussa . Työ perustuu erityisesti Nissim ja Irit Dinur [3] [4] tutkimukseen, joka osoitti, että yksityisestä staattisesta tietokannasta on mahdotonta julkaista tietoja paljastamatta joitakin yksityisiä tietoja ja että koko tietokanta voidaan paljastaa. julkaisemalla tulokset melko pienestä määrästä pyyntöjä [4] .

Selvityksen jälkeen kävi selväksi, että tilastotietokantojen luottamuksellisuuden varmistaminen olemassa olevilla menetelmillä oli mahdotonta, minkä seurauksena tarvitaan uusia, jotka rajoittaisivat tilastotietoihin sisältyvien yksityisten tietojen katoamiseen liittyviä riskejä. tietokanta. Tämän seurauksena on luotu uusia menetelmiä, joiden avulla voidaan useimmissa tapauksissa tuottaa tarkkoja tilastoja tietokannasta samalla kun ne tarjoavat korkean luottamuksellisuuden tason [5] [6] .

Periaate ja kuva

Differentiaalinen yksityisyys perustuu satunnaisuuden tuomiseen tietoihin.

Yksinkertainen yhteiskuntatieteissä kehitetty esimerkki [7] on pyytää henkilöä vastaamaan kysymykseen "Onko sinulla attribuutti A?" seuraavan menettelyn mukaisesti:

heitä kolikkoa
Jos päät heräävät, vastaa kysymykseen rehellisesti.
Muussa tapauksessa heitä uudelleen, jos se nousee päähän, vastaa "Kyllä", jos se on häntää - "Ei"

Luottamuksellisuus syntyy, koska vastauksesta on mahdotonta tietää varmasti, onko henkilöllä tietty ominaisuus. Nämä tiedot ovat kuitenkin merkittäviä, sillä myönteisiä vastauksia antaa neljäsosa ihmisistä, joilla ei ole tätä ominaisuutta, ja kolme neljäsosaa niistä, joilla se todella on. Jos p on A:n omaavien ihmisten todellinen osuus, odotamme saavamme (1/4) (1- p) + (3/4) p = (1/4) + p / 2 positiivista vastausta. Siksi voidaan arvioida R.

Muodollinen määritelmä ja käyttöesimerkki

Olkoon ε positiivinen reaaliluku ja A todennäköisyyspohjainen algoritmi , joka ottaa syötteeksi joukon dataa (edustaa luotettavan osapuolen toimia, jolla on tiedot). Merkitse A:n kuvaa im A : lla . Algoritmi A on ε - differentiaalisesti yksityinen , jos kaikille tietojoukoille ja jotka eroavat yhdellä elementillä (eli yhden henkilön tiedoilla), samoin kuin kaikki joukon im A osajoukot S : $D_{1}$ $D_{2}$

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

missä P on todennäköisyys.

Tämän määritelmän mukaan differentiaalinen yksityisyys on tiedon julkaisumekanismin ehto (eli sen määrittää tietojoukosta tietoa luovuttava luotettava osapuoli), ei itse tietojoukko. Intuitiivisesti tämä tarkoittaa, että kahdelle samanlaiselle tietojoukolle differentiaalinen yksityinen algoritmi käyttäytyy suunnilleen samalla tavalla molemmissa tietojoukoissa. Määritelmä antaa myös vahvan takuun siitä, että yksilön läsnäolo tai poissaolo ei vaikuta algoritmin lopulliseen tuottoon.

Oletetaan esimerkiksi, että meillä on potilastietojen tietokanta, jossa jokainen tietue on pari ( Nimi , X ), jossa on nolla tai yksi , joka ilmaisee, onko henkilöllä gastriitti vai ei: $D_{1}$ $X$

Nimi	Gastriitti (X)
Ivan	yksi
Peter	0
Vasilisa	yksi
Michael	yksi
Maria	0

Oletetaan nyt, että pahantahtoinen käyttäjä (jota kutsutaan usein hyökkääjäksi) haluaa selvittää, onko Mikhaililla gastriitti vai ei. Oletetaan myös, että hän tietää, millä rivillä on tietoa Mikhailista tietokannassa. Oletetaan nyt, että hyökkääjä saa käyttää vain tiettyä kyselymuotoa , joka palauttaa osittaisen summan tietokannan sarakkeen ensimmäisistä riveistä . Selvittääkseen, onko Mikhaililla gastriitti, hyökkääjä suorittaa kyselyt: ja ja laskee sitten niiden eron. Tässä esimerkissä , ja , joten niiden ero on . Tämä tarkoittaa, että "Gastriitin esiintyminen" -kentän Mihailin rivillä tulee olla yhtä suuri kuin . Tämä esimerkki osoittaa, kuinka yksittäisiä tietoja voidaan vaarantaa jopa ilman nimenomaista pyyntöä tietyn henkilön tiedoista. $Q_{i}$ $i$ $X$ $Q_{4}(D_{1})$ $Q_{3}(D_{1})$ $Q_{4}(D_{1})=3$ $Q_{3}(D_{1})=2$ $yksi$ $yksi$

Jatkamme tätä esimerkkiä, jos luomme tietojoukon korvaamalla (Mihail, 1) arvolla (Mihail, 0), hyökkääjä pystyy erottamaan tiedot laskemalla jokaiselle tietojoukolle. Jos hyökkääjä hankkisi arvoja ε-differentiaalisen yksityisen algoritmin avulla riittävän pienelle ε:lle, hän ei pystyisi erottamaan kahta tietojoukkoa. $D_{2}$ $D_{2}$ $D_{1}$ ${\displaystyle Q_{4}-Q_{3))$ $Q_{i}$

Yllä kuvattu kolikon esimerkki on -differentiaalisesti yksityinen [8] . $(\ln 3)$

Rajatapaukset

Tapaus, jossa ε = 0 on ihanteellinen luottamuksellisuuden säilyttämiseen, koska tietokannassa olevien henkilöiden tietojen läsnäolo tai puuttuminen ei vaikuta algoritmin tulokseen, mutta tällainen algoritmi on hyödyllisen tiedon kannalta merkityksetön, koska jopa nollalla ihmismäärällä se antaa saman tai samanlaisen tuloksen.

Jos ε pyrkii äärettömyyteen, niin mikä tahansa todennäköisyysalgoritmi sopii määritelmään, koska epäyhtälö täyttyy aina. $P[{\mathcal {A}}(D_{1})\in S]\leq \infty \times P[{\mathcal {A}}(D_{2})\in S],$

Herkkyys

Antaa olla positiivinen kokonaisluku, tietojoukko ja funktio. Funktion herkkyys [9] , jota merkitään , määritetään kaavalla $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},

kaikissa tietojoukkopareissa ja in , jotka eroavat enintään yhdellä elementillä ja missä tarkoittaa normia . $D_{1}$ $D_{2}$ $\mathcal{D}$ ${\displaystyle \lVert \cdot \rVert _{1))$ $\ell _{1}$

Yllä olevassa esimerkissä lääketieteellisestä tietokannasta, jos otamme huomioon funktion herkkyyden , se on yhtä suuri kuin , koska minkä tahansa tietokannan tietueen muuttaminen johtaa johonkin, joka joko muuttuu tai ei muutu. $d$ $Q_{i}$ $yksi$ $Q_{i}$ $yksi$

Laplace-mekanismi

Koska differentiaalinen yksityisyys on todennäköisyyskäsite, kaikilla sen menetelmillä on välttämättä satunnainen komponentti. Jotkut niistä, kuten Laplacen menetelmä, käyttävät ohjatun kohinan lisäystä laskettavaan funktioon.

Laplace-menetelmä lisää Laplace-kohinaa eli Laplace-jakauman kohinan , joka voidaan ilmaista todennäköisyystiheysfunktiona ja jolla on nollakeskiarvo ja keskihajonta . Määritellään tulosfunktio reaaliarvoiseksi funktioksi muodossa , jossa , ja on kysely, jonka suunnittelimme suorittavamme tietokannassa. Siten sitä voidaan pitää jatkuvana satunnaismuuttujana , missä ${\text{noise}}(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{kohina}}(tf(D_{1})) }{{\text{noise}}(tf(D_{2})))}}\,\!

joka on enintään (pdf - todennäköisyystiheysfunktio tai todennäköisyystiheysfunktio). Tässä tapauksessa voimme merkitä yksityisyystekijää ε. Siten määritelmän mukaan ε-differentiaalisesti yksityinen. Jos yritämme käyttää tätä käsitettä yllä olevassa esimerkissä gastriitin esiintymisestä, niin, jotta se olisi ε-differentiaalinen yksityinen funktio, sen on oltava , koska ). $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$

Laplace-kohinan lisäksi voidaan käyttää myös muun tyyppistä melua (esim. Gaussia), mutta ne saattavat vaatia hieman lievennettyä differentiaalisen yksityisyyden määritelmää [10] .

Koostumus

Johdonmukainen sovellus

Jos suoritamme kyselyn ε-differentiaalisesti suojattuja aikoja ja tuotettu satunnainen kohina on riippumaton jokaiselle kyselylle, niin kokonaistietosuoja on (εt)-differentiaali. Yleisemmin sanottuna, jos on olemassa itsenäisiä mekanismeja: , joiden yksityisyyden takuut ovat vastaavasti samat, mikä tahansa toiminto on -differentiaalisesti yksityinen [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})$

Rinnakkaiskokoonpano

Lisäksi, jos kyselyt suoritetaan ei-päällekkäisille tietokannan osajoukoille, funktio olisi -differentiaalisesti yksityinen [11] . $g$ $(\max _{i}{\epsilon }_{i})$

Ryhmän tietosuoja

Differentiaalinen yksityisyys yleensä on suunniteltu suojaamaan yksityisyyttä tietokantojen välillä, jotka eroavat vain yhdellä rivillä. Tämä tarkoittaa, että yksikään vastustaja, jolla on mielivaltaisia aputietoja, ei voi tietää, onko joku yksittäinen osallistuja antanut tietonsa. Tämä käsite voidaan kuitenkin laajentaa ryhmään, jos haluamme suojata riveittäin erilaisia tietokantoja siten, että mielivaltaisen tukitiedon omaava hyökkääjä ei voi tietää, ovatko yksittäiset jäsenet toimittaneet tietonsa. Tämä voidaan saavuttaa, jos määritelmän kaava korvataan [ 12] :lla , jolloin D 1 ja D 2 eroavat riveillä $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}) \in S]\,\!

Siten käyttämällä parametria (ε/c) ε:n sijasta voit saavuttaa halutun tuloksen ja suojata merkkijonoja. Toisin sanoen, sen sijaan, että jokainen elementti olisi ε-differentiaalisesti yksityinen, nyt jokainen elementtiryhmä on ε-differentiaalisesti yksityinen ja jokainen elementti on (ε/c)-differentiaalisesti yksityinen. $c$ $c$

Erillisen yksityisyyden soveltaminen tosielämän sovelluksiin

Toistaiseksi erilaiselle yksityisyydelle on useita käyttötapoja:

US Census Bureau tilastojen näyttämisen yhteydessä [13]
Google RAPPOR kerää tilastoja ei-toivotuista ohjelmistoista, jotka loukkaavat käyttäjien asetuksia [14] ( RAPPORin avoimen lähdekoodin toteutus )
Google , liikennehistoriatilastojen jakamiseen [15] .
Apple ilmoitti 13. kesäkuuta 2016 aikovansa käyttää erotettua yksityisyyttä iOS 10 :ssä älykkään tuki- ja teknologiatarjonnan parantamiseksi [16]

Muistiinpanot

↑ Dwork Cynthia, 2006 , s. kahdeksan.
↑ Cynthia Dwork, Frank McSherry, Kobbi Nissim ja Adam Smith=. Kohinan kalibrointi herkkyyteen yksityisessä data-analyysissä // Kolmannen kryptografiateorian konferenssin julkaisut (TCC'06), Shai Halevi ja Tal Rabin (Toim.). - Springer-Verlag, Berliini, Heidelberg, 2006. - S. 266 . - doi : 10.1007/11681878_14 .
↑ Dwork Cynthia, 2006 , s. 12.
↑ 12 Nissim et al, 2003 , s. 202-206.
↑ HILTON, MICHAEL. Erotettu yksityisyys: Historiallinen tutkimus (määrittelemätön) . , s.1
↑ Dwork, 2008 , s. 3-13.
↑ Roth et al, 2014 , s. viisitoista.
↑ Roth et al, 2014 , s. kolmekymmentä.
↑ 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. yksi.
↑ Erlingsson et al, 2014 , s. yksi.
↑ Tackling Urban Mobility with Technology Andrew Eland . Google Policy Europe -blogi . Käyttöpäivä: 19. joulukuuta 2017. Arkistoitu alkuperäisestä 10. joulukuuta 2017. (määrätön)
↑ Apple - Lehdistötiedot - Apple esikatselee iOS 10:tä, kaikkien aikojen suurinta iOS-julkaisua . Apple . Käyttöpäivä: 16. kesäkuuta 2016. Arkistoitu alkuperäisestä 29. huhtikuuta 2017. (määrätön)

Kirjallisuus

Ashwin Machanavajjhala, Daniel Kifer, John M. Abowd, Johannes Gehrke, Lars Vilhuber. Yksityisyys: teoria kohtaa käytännön kartalla // 24. kansainvälisen tietotekniikan konferenssin (ICDE) julkaisussa. – 2008.
Úlfar Erlingsson, Vasyl Pihur, Aleksandra Korolova. RAPPOR: Randomized Aggregatable Privacy Preserving Ordinal Response // Proceedings of 21st ACM Conference on Computer and Communications Security (CCS). – 2014.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, Adam Smith. Kohinan kalibrointi herkkyyteen yksityisten tietojen analyysissä // Theory of Cryptography Conference (TCC). - Springer, 2006. - doi : 10.1007/11681878_14 .
Frank D. McSherry. Yksityisyyden suojan integroidut kyselyt: laajennettava alusta yksityisyyttä säilyttävään tietojen analysointiin // Proceedings of the 35th SIGMOD International Conference on Management of Data (SIGMOD). - 2009. - doi : 10.1145/1559845.1559850 .
Cynthia Dwork, Aaron Roth. Differentiaalisen yksityisyyden algoritmiset perusteet // Tietojenkäsittelyteorian perusteet ja suuntaukset. - 2014. - elokuu (nide 9). - doi : 10.1561/0400000042 .
Dwork, Cynthia. Erotettu yksityisyys: tulostutkimus // Agrawal, Manindra; Du, Dingzhu; Duan, Zhenhua; Li, Angsheng Theory and Applications of Models of Computation. Tietojenkäsittelytieteen luentomuistiinpanot. - Springer Berlin Heidelberg, 2008. - 25. huhtikuuta. doi : 10.1145 / 773153.773173 .
Dwork, Cynthia. Erotettu yksityisyys . - Automaattien, kielten ja ohjelmoinnin kansainvälinen kollokviumi (ICALP), 2006. - doi : 10.1007/11787006_1 .
Irit Dinur, Kobbi Nissim. Tietojen paljastaminen yksityisyyttä suojaamalla // Tietokantajärjestelmien periaatteita käsittelevän 22. ACM SIGMOD-SIGACT-SIGART -symposiumin (PODS '03) julkaisu. - ACM, New York, NY, USA, 2003. - doi : 10.1145/773153.773173 .