Differential privacy loikkasi tutkimuspapereista tech-uutisotsikoihin viime vuonna, kun WWDC: n pääpuheenvuorossa Apple VP of Engineering Craig Federighi ilmoitti Applen käyttävän konseptia suojaamaan käyttäjän yksityisyyttä iOS: ssä.

se oli viimeisin esimerkki yleisestä suuntauksesta: käyttäjät ja insinöörit heräsivät yksityisyyden suojan tärkeyteen ohjelmistoissa. Korkean profiilin yksityisyyden loukkaukset, kuten Uberin ”God mode”, ovat osoittaneet karulla tavalla, miten helposti yrityksen työntekijät voivat käyttää asiakkailtaan kerättyjä arkaluonteisia tietoja väärin.

digitaalisesti tallennettavan arkaluonteisen tiedon määrä kasvaa nopeasti. Ihmiset luottavat nyt digitaalisiin palveluihin maksuissa, kuljetuksissa, navigoinnissa, ostoksilla ja terveydessä enemmän kuin koskaan. Tämä uusi tiedonkeruu luo yhä uusia tapoja rikkoa yksityisyyttä.

mutta se luo myös jännittäviä mahdollisuuksia—parantaa liikenneverkkoja, vähentää rikollisuutta, parantaa sairauksia—jos se annetaan oikeiden tiedemiesten ja tutkijoiden käyttöön. Tietoaineistossa olevien henkilöiden yksityisyyden suojaamisen ja parempaan maailmaan johtavan analytiikan mahdollistamisen välillä on luonnollinen jännite.

toisistaan poikkeavat Yksityiset algoritmit ovat lupaava tekninen ratkaisu, joka voisi helpottaa tätä jännitettä, jolloin analyytikot voivat tehdä hyvänlaatuisia kokonaisanalyysejä ja taata samalla mielekkään suojan jokaisen yksilön yksityisyydelle.

tämä kehittyvä tekniikan ala kannattaa ottaa huomioon missä tahansa järjestelmässä, joka pyrkii analysoimaan arkaluonteisia tietoja. Vaikka erillisyksityisyystakuu keksittiin vasta kymmenen vuotta sitten, se on menestynyt yliopistomaailmassa ja teollisuudessa. Tutkijat keksivät ja parantavat nopeasti erilaisia yksityisiä algoritmeja, joista osa on otettu käyttöön sekä Applen iOS: ssä että Googlen Chromessa.

tässä artikkelissa käsitellään historiallisia tekijöitä, jotka johtavat differentiaaliseen yksityisyyteen sen nykyisessä muodossa, sekä differentiaalisen yksityisyyden määritelmää ja erilaisia yksityisiä algoritmeja. Sen jälkeen tarkastellaan joitakin viime korkean profiilin toteutuksia eri yksityisten algoritmien Google, Apple, ja muut.

Tausta

toisistaan poikkeavat Yksityiset algoritmit ovat uusimpia vuosikymmeniä vanhalla tietosuojaa säilyttävän data-analyysin teknologioiden alalla. Kaksi aikaisempaa käsitettä vaikuttivat suoraan differentiaaliseen yksityisyyteen:

1. Vähimmäiskyselyjoukon koko
2. Daleniuksen tilastollinen ilmaisumääritelmä.

selitämme nämä ensin, koska ne tarjoavat hyödyllistä taustaa differentiaaliselle yksityisyydelle.

vähimmäiskyselyjoukon koko ensimmäinen käsite on vähimmäiskyselyjoukon koko, joka—kuten erilaiset yksityiset algoritmit—pyrkii varmistamaan kokonaiskyselyiden turvallisuuden. Yhteenlasketut kyselyt ovat niitä, joissa palautettu arvo lasketaan datajoukon tietueiden osajoukosta, kuten laskuista, keskiarvoista tai summista. Se voi olla hyödyllistä ajatella yhteenlaskettu kyselyt SQL kyselyt, jotka alkavat ”Valitse summa”, ”valitse määrä”, tai ”valitse AVG”. Muita aggregaattikyselyjä ovat varataulukot ja histogrammit.

vähimmäiskyselyjoukon koko on rajoitus, jolla pyritään varmistamaan, että yhteenlasketut kyselyt eivät voi vuotaa tietoja yksilöistä. Koska jokin määritetty kynnysarvo t, se varmistaa, että jokainen yhteenlaskettu kysely suoritetaan joukolla vähintään t tietueita. Vähimmäiskyselykoko estäisi yhteenlasketut kyselyt, jotka kohdistuivat harvempiin kuin T-yksilöihin. Esimerkiksi, jos T=2, se estäisi seuraavat:

”SELECT AVG(salary) WHERE name = ”Troy Brown”;”.

koska tämä kysely johtaisi keskiarvon yli yhden levyn (oletamme, että on vain yksi Troy Brown).

vähimmäiskyselykokoisten käyttäminen estää tietyt hyökkäykset, mutta ei sisällä tietosuojatakuuta ja käytännössä taitavat hyökkääjät voivat kiertää ne. Hyökkääjä saattoi esimerkiksi suorittaa edellä mainitun hyökkäyksen:

”Valitse summa(palkka);”.

”Valitse summa(palkka) missä nimi != ”Troy Brown”;”.

tai jopa, jos tiedämme Troy Brownin iän (45) ja aseman (WR) yksiselitteisesti tunnistaa hänet:

”SELECT SUM(salary) WHERE position = ”WR”;”.

”SELECT SUM (salary) WHERE position =” WR ” AND age != 45;

tällaisia hyökkäyksiä kutsutaan seurantahyökkäyksiksi, eikä niitä voi pysäyttää kyselyjoukon vähimmäiskokorajoituksella. Näiden hyökkäysten vuoksi minimikyselyjoukkojen kokoa pidettiin riittämättömänä puolustuksena kyselyjärjestelmien suojaamiseen (katso Denningin teos). Yksityisyydensuojan takaamiseksi tarvittiin jotain parempaa.

Daleniuksen tilastollinen tiedonjulkistamismääritelmä

vuonna 1977 tilastotieteilijä Tore Dalenius ehdotti tiukkaa tietosuojan määritelmää: hyökkääjän ei tulisi oppia yksilöstä mitään, mitä ei olisi tiennyt ennen arkaluontoisen aineiston käyttöä. Vaikka tämä takuu epäonnistui (ja näemme miksi), on tärkeää ymmärtää, miksi differentiaalinen yksityisyys on rakennettu niin kuin se on.

Daleniuksen määritelmä epäonnistui, koska tietojenkäsittelytieteilijä Cynthia Dwork todisti vuonna 2006, että tätä takuuta oli mahdotonta antaa—toisin sanoen kaikki pääsy arkaluonteisiin tietoihin rikkoisi tätä yksityisyyden määritelmää. Ongelmana hän piti sitä, että tietyntyyppiset taustatiedot voivat aina johtaa uuteen johtopäätökseen yksilöstä. Hänen todistuksensa on esitetty seuraavassa anekdootissa: Tiedän, että Alice on viisi senttiä pidempi kuin keskimääräinen Liettualainen nainen. Sitten olen vuorovaikutuksessa dataset Liettuan naisten ja laskea keskimääräinen korkeus, jota en tiennyt ennen. Nyt tiedän tarkalleen Alicen pituuden, vaikka hän ei ollut aineistossa. On mahdotonta ottaa huomioon kaikentyyppisiä taustatietoja, jotka voisivat johtaa uuteen johtopäätökseen henkilöstä aineiston käytöstä.

dwork esitti edellä todennettuaan uuden määritelmän: differentiaalinen Yksityisyys.

mitä on differentiaalinen Yksityisyys?

differentiaalinen Yksityisyys takaa seuraavat: että hyökkääjä voi oppia käytännössä mitään muuta yksilöstä kuin he oppisivat, jos kyseisen henkilön tiedot olisivat poissa aineistosta. Vaikka takuu on heikompi kuin Daleniuksen yksityisyyden määritelmä, se on riittävän vahva, koska se vastaa reaalimaailman kannustimia—yksilöillä ei ole kannustinta olla osallistumatta aineistoon, koska kyseisen aineiston analyytikot tekevät samat johtopäätökset kyseisestä yksilöstä riippumatta siitä, sisältyykö yksilö aineistoon vai ei. Koska heidän arkaluonteiset henkilötietonsa ovat lähes merkityksettömiä järjestelmän tuotoksissa, käyttäjät voivat olla varmoja siitä, että heidän tietojaan käsittelevä organisaatio ei loukkaa heidän yksityisyyttään.

analyytikot, jotka oppivat ”käytännöllisesti katsoen mitään muuta yksilöstä”, merkitsevät sitä, että he rajoittuvat vain vähäpätöiseen muutokseen uskomuksessa kenestäkään yksilöstä. (Tässä ja alla ”muutos” tarkoittaa muutosta tietokokonaisuuden ja saman tietokokonaisuuden käytön välillä vähennettynä yhden henkilön tiedoilla.) Tämän muutoksen laajuutta säätelee parametri nimeltä ϵ, joka asettaa sidonnaisuuden minkä tahansa lopputuloksen todennäköisyyden muutokseen. Alhainen arvo ϵ, kuten 0,1, tarkoittaa, että hyvin vähän voi muuttaa uskomuksia kenestäkään yksilöstä. Suuri arvo ϵ, kuten 50, tarkoittaa, että uskomukset voivat muuttua huomattavasti enemmän. Muodollinen määritelmä on seuraava.

algoritmi A on ϵ-differentiaalisesti yksityinen, jos ja vain jos:

PR ≤ e^ϵ * Pr

kaikille x: lle ja kaikille datajoukkojen D: lle, D ”missä D” on d minkä tahansa yhden tietueen—eli yhden henkilön datan—ollessa kateissa. Symboli e viittaa matemaattiseen vakioon. Huomaa, että tämä määritelmä on järkevä vain satunnaistetuille algoritmeille. Deterministisen ulostulon antava algoritmi ei ole ehdokas differentiaaliselle yksityisyydelle.

differentiaalisen yksityisyyden takuun ensisijainen vetovoima on sen rajoittaminen määrään, jonka kuka tahansa analyytikko voi oppia yksilöstä. Lisäksi sillä on seuraavat hyödylliset ominaisuudet:

• Kompositivuus: jos kahteen Kyselyyn vastataan tasojen ϵ1 ja ϵ2 differentiaalisella tietosuojatakuulla, tiedustelupari kuuluu tasojen takuun piiriin (ϵ1 + ϵ2). Muista, että korkeampi arvo ϵ tarkoittaa heikompaa takuuta.
• vahvuus mielivaltaista taustatietoa vastaan: takuu ei perustu millään tavalla siihen, mitä taustatietoja hyökkääjä tietää. Tämä ominaisuus on yksi tärkeimmistä syistä siihen, että differentiaalinen yksityisyys on vahvempi kuin aikaisempi yksityisyystakuu, k-anonymiteetti.
• jälkikäsittelyn turva: ei ole rajoituksia sille, mitä voidaan tehdä erilaisella yksityisellä tuloksella-riippumatta siitä, mihin se yhdistetään tai miten se muutetaan, se on silti eri tavoin yksityinen.

miten tämä takuu saavutetaan ohjelmistoissa? Eri tavoin Yksityiset algoritmit ovat satunnaistettuja algoritmeja, jotka lisäävät kohinaa algoritmin keskeisissä kohdissa. Yksi yksinkertaisimmista algoritmeista on Laplace-mekanismi, joka voi jälkikäsitellä yhteenlaskettujen kyselyiden tuloksia (esim.laskuja, summia ja keinoja), jotta ne eroavat toisistaan yksityisesti. Alla on esimerkki Java-koodi Laplace mekanismi erityisiä count kyselyt:

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;}

tämän funktion keskeiset osat ovat

1. Instantiaatti Laplace-todennäköisyysjakauma (KS.Kuva 1), jonka keskipisteenä on 0 ja skaalattuna 1 / ϵ. Käytämme Apache Commons-toteutusta, ”LaplaceDistribution”, joka on rakennettu kahdella argumentilla: jakauman keskiarvolla ja jakauman mittakaavalla. Huomaa, että alempi epsilon (enemmän yksityisyyttä) johtaa laajempaan mittakaavaan ja siten laajempaan jakeluun ja enemmän melua.
2. piirtää tästä jakaumasta yhden satunnaisotoksen. Tämä otos () – funktio ottaa satunnaisluvun väliltä 0-1 ja soveltaa Laplace-jakauman käänteistä kumulatiivista jakaumafunktiota (CDF) tähän lukuun. Tämä prosessi johtaa satunnaislukuun siten, että sen todennäköisyys olla jokin tietty arvo vastaa jakaumaa. Vaihtoehtoisena ajatustapana on, että jos tähän näytefunktioon vedottaisiin miljoona kertaa miljoonan näytteen saamiseksi, näiden näytteiden histogrammin muoto vastaisi läheisesti Laplace-jakauman muotoa.
3. Perturboi reaaliarvoa lisäämällä satunnaisarvo vaiheesta 2.

Pohditaanpa, miksi tämä algoritmi on eri tavoin Yksityinen, kun otetaan Eeva-nimisen hyökkääjän näkökulma. Sano, että tietokokonaisuus on mielenterveystietoa, ja Eve on keksinyt seurantahyökkäyksen (KS.yllä), joka paljastaa, saako hänen kohteensa Bob neuvontaa alkoholismiin vai ei. Jos kyselyn tulos on 48, Eve tietää, että Bob saa terapiaa; jos se on 47, Eve tietää päinvastaista.

olipa vastaus 47 tai 48, Laplace-mekanismi palauttaa äänekkään tuloksen jonnekin 47 tai 48 tienoille. Se voi palata 49, 46, tai jopa, pienemmällä todennäköisyydellä, 44 tai 51 (katso kuva 2 varten histogrammi). Käytännössä Eevan on mahdotonta olla kovin varma siitä, oliko oikea vastaus 47 vai 48, ja siksi hänen käsityksensä siitä, onko Bob alkoholismin takia terapiassa vai nyt, eivät tule merkityksellisesti muuttumaan.

kuva 1: Laplace-jakauma keskitetty 0: een asteikolla 1. Kuvassa on jakauman todennäköisyystiheysfunktio (PDF)-y-akseli on suhteellinen todennäköisyys sille, että muuttuja ottaa arvon x-akselilla.

kuva 2: laskukyselyn todennäköiset tulokset kahdelle skenaariolle, joissa todellinen vastaus on 47 ja kun se on 48. Pieni määrä lähtöjä ei riittäisi erottamaan, mistä jakaumasta ne tulevat. Epsilonin arvo on 0,67.

olet saattanut huomata tässä vaiheessa, että Eeva pystyi leikkaamaan kohinan läpi toistamalla kyselyn monta kertaa ja katsomalla, ryhmittyvätkö vastaukset 47: n vai 48: n tienoille. Tämän taktiikan estämiseksi eri yksityisissä järjestelmissä on oltava ”yksityisyysbudjetti”, joka on yläraja kussakin kyselyssä käytettyjen ϵ-kirjainten summalle. Tämä korkki toimii, koska differential privacy n kompostoitavuus ominaisuus kuvattu edellä. He voivat kysyä muutamia suhteellisen hiljainen kyselyitä, tai useita satoja korkean melun kyselyjä, mutta joka tapauksessa, he eivät voi luottavaisesti määrittää, onko todellinen vastaus on 47 tai 48.

huomaa lopuksi, että laskujen Laplace-mekanismi on vain yksi yksinkertainen eroava yksityinen algoritmi. Laplace mekanismi voidaan laajentaa työtä summia ja muita yhteenlaskettu kyselyt. Lisäksi on olemassa perustavanlaatuisesti erilaisia algoritmeja, joiden on osoitettu täyttävän differentiaalisen yksityisyyden takuun. Muutamia tutkimisen arvoisia ovat yksityinen Multiplicative painot algoritmi, Multiplicative painot eksponentiaalinen mekanismi, ja DualQuery.

Differential privacy in action

kesäkuussa 2016 Apple ilmoitti alkavansa käyttää erilaisia yksityisiä algoritmeja kerätäkseen käyttäytymistilastoja iPhoneista. Tämä ilmoitus, paitsi aiheuttaa valtava piikki ero yksityisyyden kiinnostusta, osoitti, että ero Yksityisyys voi auttaa suuria organisaatioita saamaan uutta arvoa tiedoista, jotka he aiemmin eivät koskeneet, koska yksityisyyden huolenaiheita.

vaikka Apple on toistaiseksi julkistanut muutamia yksityiskohtia, iPhonessa käytetty algoritmi näyttää samanlaiselta kuin Googlen RAPPOR-projektissa. Google toteutti Chromeen ominaisuuden, joka kerää käyttäytymistilastoja Chrome-selaimista poikkeavasti yksityisen satunnaistetun vastausalgoritmin avulla.

satunnaistetussa vastauksessa satunnaiskohina lisätään tilastoihin ennen niiden toimittamista kerääjälle. Esimerkiksi jos todellinen tilasto on 0, selain korvaa jollain todennäköisyydellä 0: n satunnaisesti valitulla 0: lla tai 1: llä. Jokaisella käyttäjällä on suuri kiistettävyys arvosta, jonka heidän ohjelmistonsa raportoi, koska se voi olla satunnainen arvo. Mutta kollektiivisesti signaali erottuu satunnaisesta kohinasta ja tilastoja keräävä organisaatio (eli Google tai Apple) voi tarkasti tarkkailla trendejä.

mielenkiintoista on, ettei Google eikä Apple ole tietojemme mukaan paljastanut ϵ: n arvoa, joka kuuluu niiden erilliseen yksityisyystakuuseen. Tarvitsemme tätä arvoa ymmärtääksemme takuun tarjoaman suojan. Jos he käyttävät tarpeeksi korkeaa arvoa ϵ, analyytikot voivat silti oppia arkaluonteisia tietoja käyttäjistä suurella luottamuksella. Mielekäs Yksityisyyden suoja edellyttää pientä arvoa ϵ.

toisistaan poikkeavia yksityisiä algoritmeja on toteutettu myös yksityisyyttä säilyttävissä analytiikkatuotteissa, kuten työnantajani Privitarin kehittämissä. Näiden tuotteiden avulla yritykset, jotka työskentelevät arvokkaiden, arkaluonteisten tietojen kanssa, voivat sisällyttää eri tavoin yksityisiä algoritmeja tietoarkkitehtuuriinsa ja tarjota käyttäjille tietosuojatakuita samalla, kun he suorittavat tietojen mielekästä analysointia.

tulevaisuuteen katsova

sekä insinööri-että tutkimusyhteisöillä on polkuja eteenpäin differentiaalisen yksityisyyden kanssa. Insinöörien tehtävänä on kouluttautua erilaiseen yksityisyyteen ja varmistaa, että sitä käytetään silloin, kun se on tarkoituksenmukaista käyttäjien yksityisyyden suojaamiseksi. Tutkijoille se on löytää enemmän ja paremmin erilaisia yksityisiä algoritmeja, parantaa työkalusarja, jolla voimme mahdollistaa yksityisyyttä säilyttävän data analytics.

me kaikki hyödymme tietosuojatakuiden käyttöönotosta ja data-analytiikan menestyksestä. Molemmista syistä, odotamme enemmän organisaatioita omaksuvat ero yksityisyyden.

tekijästä

Charlie Cabot on vanhempi datatieteilijä privitarissa, tietosuojaa tarjoavassa startup-yrityksessä, joka rakentaa korkean suorituskyvyn ohjelmistoja tietojen anonymisointiin, mukaan lukien häiriö-ja yleistysalgoritmit ja erilaiset yksityiset mekanismit, helpottaakseen arkaluonteisten tietokokonaisuuksien turvallista käyttöä. Charlie keskittyy todistettavissa oleviin yksityisyyden takuisiin ja anonymisoinnin tilastolliseen vaikutukseen analytiikkaan ja datatieteeseen. Aiemmin kyberturvallisuuden parissa työskennellyt Charlie suunnitteli koneoppimispohjaisia lähestymistapoja haittaohjelmien havaitsemiseen ja mallinsi tietoverkkoihin kohdistuvia kyberhyökkäyksiä.