Differensielt personvern sprang fra forskningsartikler til tekniske nyhetsoverskrifter i fjor da Apples VP For Engineering Craig Federighi kunngjorde Apples bruk Av konseptet for å beskytte brukerens personvern i iOS.Det var den siste forekomsten av en generell trend: brukere og ingeniører våkner til viktigheten av personvern i programvare. Høyprofilerte personvernbrudd som Ubers «Gudmodus» har vist i sterk grad hvor enkelt ansatte i et selskap kan misbruke sensitive data samlet inn fra sine kunder.

mengden sensitive data som registreres digitalt, øker raskt. Folk stoler nå på digitale tjenester for mer av sine betalinger, transport, navigasjon, shopping og helse enn noensinne. Denne nye datainnsamlingen skaper stadig flere måter å krenke personvernet på.Men det skaper også spennende muligheter-for å forbedre transportnettverket, for å redusere kriminalitet, for å kurere sykdom—hvis det gjøres tilgjengelig for de rette datavitenskaperne og forskerne. Det er en naturlig spenning mellom å beskytte personvernet til enkeltpersoner i datasettet og muliggjøre analyser som kan føre til en bedre verden.Differensielt private algoritmer er en lovende teknisk løsning som kan lette denne spenningen, slik at analytikere kan utføre godartet aggregatanalyse samtidig som de garanterer meningsfull beskyttelse av hver enkelt persons personvern.

dette utviklingsfeltet av teknologi er verdt å vurdere i ethvert system som søker å analysere sensitive data. Selv om differensial personvern garanti ble unnfanget av bare ti år siden, det har vært vellykket i akademia og industri. Forskere oppdager raskt og forbedrer differensielt private algoritmer, hvorav noen har blitt vedtatt i Både Apples iOS og Googles Chrome.denne artikkelen diskuterer de historiske faktorene som fører til differensielt personvern i sin nåværende form, sammen med en definisjon av differensielt personvern og eksempel differensielt private algoritmer. Det ser da på noen nyere høyprofilerte implementeringer av differensielt private algoritmer Av Google, Apple og andre.

Bakgrunn

Differensielt private algoritmer er det siste innen et tiår gammelt felt av teknologier for personvernbevarende dataanalyse. To tidligere konsepter påvirket direkte differensielt personvern:

1. Minimumsspørringsstørrelse
2. Dalenius ‘ statistiske avsløringsdefinisjon.

vi vil forklare disse først som de gir nyttig bakgrunn for differensial personvern.Det første konseptet er en minimumsspørringsstørrelse, som – som differensielt private algoritmer-tar sikte på å sikre sikkerheten til aggregerte spørringer. Samlingsspørringer er de der den returnerte verdien beregnes på tvers av et delsett av poster i datasettet, for eksempel antall, gjennomsnitt eller summer. Det kan være nyttig å tenke på aggregerte spørringer SOM SQL-spørringer som begynner med «SELECT SUM», «SELECT COUNT»eller» SELECT AVG». Andre typer aggregerte spørringer inkluderer beredskapstabeller og histogrammer.

en minste spørringsstørrelse er en begrensning som søker å sikre at aggregerte spørringer ikke kan lekke informasjon om enkeltpersoner. Gitt noen konfigurerte terskelnummer T, sikrer det at hver aggregatspørring utføres på et sett med Minst T-poster. En minimumsspørringsstørrelse ville blokkere aggregerte spørringer som målrettet færre enn T-personer. For Eksempel, Hvis T=2, ville det blokkere følgende:

«VELG AVG (lønn) DER name = ‘Troy Brown’;».

fordi denne spørringen vil føre et gjennomsnitt over en post (vi antar at Det bare Er En Troy Brown).

bruk av minimumsspørringsstørrelser forhindrer visse angrep, men kommer ikke med en personverngaranti og kan i praksis omgås av dyktige angripere. For eksempel kan angriperen utføre angrepet ovenfor med:

» VELG SUM (lønn);».

» VELG SUM (lønn) HVOR navn != ‘Troy Brown’;».

Eller til Og Med, hvis Vi kjenner Troy Browns alder (45) og posisjon (WR) unikt identifisere ham:

«VELG SUM (lønn) HVOR posisjon = ‘WR’;».

«VELG SUM (lønn) DER posisjon =’ WR ‘ og alder != 45;

slike angrep kalles trackerangrep, og de kan ikke stoppes av en minimumsbegrensning for spørring. På grunn av disse angrepene ble minimumsspørringsstørrelser ansett som et utilstrekkelig forsvar for å beskytte spørringssystemer (se Dennings arbeid). Noe bedre, med en garanti, var nødvendig for å sikre personvern.

Dalenius ‘ statistiske definisjon

i 1977 foreslo statistikeren Tore Dalenius en streng definisjon av personvern: at angriperen ikke skulle lære noe om en person som de ikke visste før de brukte det sensitive datasettet. Selv om denne garantien mislyktes (og vi vil se hvorfor), er det viktig å forstå hvorfor differensielt personvern er konstruert slik det er.Dalenius ‘ definisjon mislyktes fordi datavitenskapsmann Cynthia Dwork i 2006 beviste at denne garantien var umulig å gi – med andre ord, enhver tilgang til sensitive data ville krenke denne definisjonen av personvern. Problemet hun fant var at visse typer bakgrunnsinformasjon alltid kunne føre til en ny konklusjon om en person. Hennes bevis er illustrert i følgende anekdote: Jeg vet At Alice er to inches høyere enn gjennomsnittet litauisk kvinne. Da jeg samhandle med et datasett av litauiske kvinner og beregne gjennomsnittlig høyde, som jeg ikke visste før. Jeg vet Nå Alices høyde nøyaktig, selv om hun ikke var i datasettet. Det er umulig å redegjøre for alle typer bakgrunnsinformasjon som kan føre til en ny konklusjon om en person fra bruk av et datasett.

Dwork, etter å ha bevist det ovenfor, foreslo en ny definisjon: differensielt personvern.

hva er differensial personvern?

Differensiell personvern garanterer følgende: at angriperen kan lære nesten ingenting mer om et individ enn de ville lære om personens rekord var fraværende fra datasettet. Mens svakere Enn Dalenius definisjon av personvern, er garantien sterk nok fordi den samsvarer med virkelige insentiver—enkeltpersoner har ingen incitament til ikke å delta i et datasett, fordi analytikerne til datasettet vil trekke de samme konklusjonene om den enkelte om personen inkluderer seg selv i datasettet eller ikke. Siden deres sensitive personlige opplysninger er nesten irrelevante i systemets utganger, kan brukerne være sikre på at organisasjonen som håndterer dataene deres ikke bryter med personvernet.Analytikere som lærer «nesten ingenting mer om et individ» betyr at De er begrenset til en ubetydelig liten endring i troen på et individ. (Her og under refererer «endring» til endringen mellom å bruke et datasett og bruke samme datasett minus en persons rekord. Omfanget av denne endringen styres av en parameter kjent som ϵ, som setter grensen for endringen i sannsynlighet for et hvilket som helst utfall. En lav verdi av ϵ, for eksempel 0,1, betyr at svært lite kan endre troen på et individ. En høy verdi av ϵ, for eksempel 50, betyr at troen kan endres vesentlig mer. Den formelle definisjonen er som følger.

en algoritme A er ϵ-differensielt privat hvis og bare hvis:

pr ≤ e^ϵ * Pr

for alle x Og For alle datasettpar D, D ‘Hvor D’ er D med en hvilken som helst post—det vil si en persons data—mangler. Symbolet e refererer til den matematiske konstanten. Merk at denne definisjonen bare gir mening for randomiserte algoritmer. En algoritme som gir deterministisk utgang er ikke en kandidat for differensielt personvern.

den primære appellen til differensiell personverngaranti er dens begrensning på beløpet som enhver analytiker kan lære om en person. I tillegg har den følgende nyttige egenskaper:

• Composability: hvis to spørsmål blir besvart med differensielle personverngarantier for nivå ϵ1 og ϵ2, er de to spørsmålene dekket av en garanti for nivå (ϵ1 + ϵ2). Husk at en høyere verdi av ϵ betyr en svakere garanti.
• Styrke mot vilkårlig bakgrunnsinformasjon: garantien er ikke avhengig av hvilken bakgrunnsinformasjon angriperen vet. Denne egenskapen er en av hovedgrunnene til at differensielt personvern er sterkere enn en tidligere personverngaranti, k-anonymitet.
• Sikkerhet under etterbehandling: det er ingen begrensninger på hva som kan gjøres med et differensielt privat resultat – uansett hva det kombineres med eller hvordan det forvandles, er det fortsatt differensielt privat.

hvordan oppnås denne garantien i programvare? Differensielt private algoritmer er randomiserte algoritmer som legger til støy på viktige punkter i algoritmen. En av de enkleste algoritmene er Laplace-mekanismen, som kan etterbehandle resultater av aggregerte spørringer (f. eks. teller, summer og midler) for å gjøre dem differensielt private. Nedenfor er eksempel Java-kode For Laplace-mekanismen som er spesifikk for å telle spørringer:

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

de viktigste delene av denne funksjonen Er

1. Instansiere En Laplace-sannsynlighetsfordeling (Se Figur 1) sentrert på 0 og skalert med 1 / ϵ. Vi bruker Apache Commons-implementeringen, «LaplaceDistribution», som er konstruert med to argumenter: gjennomsnittet av distribusjonen og omfanget av distribusjonen. Legg merke til at lavere epsilon (mer personvern) fører til større skala og dermed en bredere distribusjon og mer støy.
2. Tegn en tilfeldig prøve fra denne fordelingen. Denne eksempelfunksjonen() tar et tilfeldig tall mellom 0 og 1 og bruker Laplace-distribusjonens inverse kumulative distribusjonsfunksjon (CDF) til dette tallet. Denne prosessen resulterer i et tilfeldig tall slik at sannsynligheten for å være en bestemt verdi samsvarer med fordelingen. Som en alternativ måte å tenke på det, hvis denne prøvefunksjonen ble påkalt en million ganger for å få en million prøver, ville formen på histogrammet til disse prøvene tett matche Formen På Laplace-distribusjonen.
3. Perturb den virkelige verdien ved å legge til tilfeldig verdi fra trinn 2.

la oss vurdere hvorfor denne algoritmen er differensielt privat ved å ta synspunktet til en angriper som heter Eve. Si at datasettet er psykisk helsedata, Og Eve har tenkt på et sporingsangrep (se ovenfor) som vil avsløre om hennes mål, Bob, mottar rådgivning for alkoholisme eller ikke. Hvis spørringen resultat er 48, Eve vet At Bob mottar rådgivning; hvis det er 47, Eve vet det motsatte.

om svaret er 47 eller 48, Vil Laplace-mekanismen returnere et støyende resultat et sted rundt 47 eller 48. Det kan returnere 49, 46, eller til og med, med mindre sannsynlighet, 44 eller 51 (Se figur 2 for et histogram). I praksis Er Det umulig For Eve å være veldig sikker på om det sanne svaret var 47 eller 48, og dermed vil hennes tro på Om Bob er i rådgivning for alkoholisme eller nå ikke endres meningsfylt.

Figur 1: Laplace-distribusjonen sentrert ved 0 med skala på 1. Bildet er sannsynlighetstetthetsfunksjonen (PDF) av fordelingen—y-aksen er den relative sannsynligheten for at variabelen vil ta verdien på x-aksen.

Figur 2: de sannsynlige resultatene av tellespørringen for de to scenariene, hvor det virkelige svaret er 47 og når det er 48. Et lite antall utganger ville ikke være nok til å skille hvilken distribusjon de kom fra. Epsilon er satt til 0,67.

Du har kanskje observert på dette punktet At Eve kunne kutte gjennom støyen ved å gjenta spørringen mange ganger, og se om svarene klynger seg rundt 47 eller 48. For å forhindre denne taktikken må differensielt private systemer ha et «personvernbudsjett», et tak på summen av den ϵ som brukes i hver spørring. Denne hetten fungerer på grunn av differensial personvernsegenskapen som er beskrevet ovenfor. De kan spørre noen relativt lav støy spørringer, eller mange hundre høy støy spørringer, men uansett, de vil ikke være i stand til å trygt fastslå om det sanne svaret er 47 eller 48.

Til Slutt, merk at Laplace-mekanismen for teller bare er en enkel differensielt privat algoritme. Laplace-mekanismen kan utvides til å fungere for summer og andre aggregerte spørringer. Videre er det fundamentalt forskjellige algoritmer som har vist seg å tilfredsstille differensiell personverngaranti. Noen få verdt å utforske Er Den Private Multiplikative Vektalgoritmen, Multiplikativ Vekt Eksponentiell Mekanisme og DualQuery.

Differensial personvern i aksjon

i juni 2016 annonserte Apple At Det ville begynne å bruke differensielt private algoritmer for å samle atferdsstatistikk fra iPhones. Denne kunngjøringen, i tillegg til å forårsake en stor økning i differensiell personverninteresse, viste at differensielt personvern kan hjelpe store organisasjoner til å få ny verdi fra data som de tidligere ikke rørte på grunn av personvernhensyn.Selv Om Apple hittil har gjort få detaljer offentlig, virker algoritmen som brukes i iPhone, lik Googles RAPPORT-prosjekt. Google implementerte En Funksjon I Chrome som samler atferdsstatistikk fra Chrome-nettlesere gjennom en differensielt privat randomisert responsalgoritme.

i randomisert respons legges tilfeldig støy til statistikk før de sendes til samleren. For eksempel, hvis den virkelige statistikken er 0, vil nettleseren med en viss sannsynlighet erstatte 0 med en tilfeldig valgt 0 eller 1. Hver bruker har en stor grad av deniability om verdien som deres programvare rapporter, fordi det kan være en tilfeldig verdi. Men samlet sett skiller signalet seg ut over den tilfeldige støyen, og organisasjonen som samler statistikken (Dvs. Google eller Apple) kan nøyaktig observere trender.

Interessant nok har Verken Google Eller Apple, så vidt vi vet, avslørt verdien av ϵ som følger med deres differensielle personverngaranti. Vi trenger denne verdien for å forstå beskyttelsen som tilbys av garantien. Hvis de bruker en høy nok verdi av ϵ, kan analytikere fortsatt lære sensitive fakta om brukere med høy tillit. En lav verdi av ϵ er nødvendig for meningsfylt personvern.Ulike private algoritmer har også blitt implementert i personvernbevarende analyseprodukter, for eksempel de som er utviklet av min arbeidsgiver Privitar. Disse produktene tillater selskaper som arbeider med verdifulle, sensitive data å innlemme differensielt private algoritmer i deres dataarkitektur, og gir personverngarantier til brukerne mens de fortsatt utfører meningsfull analyse av dataene.

Ser fremover

både ingeniør-og forskningsmiljøene har veier fremover med differensielt personvern. For ingeniører er oppgaven å bli utdannet på differensielt personvern og sikre at det brukes der det er hensiktsmessig for brukerens personvern. For forskere er det å finne flere og bedre differensielt private algoritmer, forbedre verktøysettet som vi kan aktivere personvernbevarende dataanalyse.

vi står alle for å tjene på etablering av personverngarantier og suksessene til dataanalyse. Av begge grunner ser vi frem til flere organisasjoner som omfavner differensielt personvern. Charlie Cabot er senior datavitenskapsmann ved Privitar, en oppstart av datasikkerhet som bygger programvare med høy ytelse for data anonymisering, inkludert forstyrrelser og generaliseringsalgoritmer og differensielt private mekanismer, for å lette sikker bruk av sensitive datasett. Charlie fokuserer på bevisbare personverngarantier og den statistiske virkningen av anonymisering på analyse og datavitenskap. Tidligere jobbet Han med cybersikkerhet og utviklet maskinlæringsdrevne tilnærminger til deteksjon av skadelig programvare og modellerte cyberangrep på datanettverk.