nøgle grillbarer

• Differential privacy kan opnås ved at tilføje randomiseret “støj” til et samlet forespørgselsresultat for at beskytte individuelle poster uden at ændre resultatet væsentligt.
• differentielt private algoritmer garanterer, at angriberen næsten ikke kan lære mere om en person, end de ville lære, hvis personens rekord var fraværende i datasættet.
• en af de enkleste algoritmer er Laplace-mekanismen, som kan efterbehandle resultater af aggregerede forespørgsler.
• både Apple og Google bruger forskellige privatlivsteknikker i henholdsvis iOS og Chrome. Differentielt private algoritmer er også blevet implementeret i analyseprodukter til beskyttelse af personlige oplysninger, såsom dem, der er udviklet af Privitar.
• differentielt private algoritmer er stadig et aktivt forskningsfelt.Differential privacy sprang fra forskningsartikler til tekniske nyhedsoverskrifter sidste år, da Apple VP of Engineering Craig Federighi annoncerede Apples brug af konceptet til beskyttelse af brugernes privatliv i iOS.

  det var den seneste forekomst af en generel tendens: brugere og ingeniører, der vågnede op til vigtigheden af beskyttelse af privatlivets fred i programmer. Højt profilerede krænkelser af privatlivets fred som Ubers “God mode” har vist i skarpe vendinger, hvor let medarbejdere i en virksomhed kan misbruge følsomme data indsamlet fra deres kunder.

  mængden af følsomme data, der registreres digitalt, stiger hurtigt. Folk stoler nu på digitale tjenester for flere af deres betalinger, transport, navigation, shopping og sundhed end nogensinde. Denne nye dataindsamling skaber stadigt stigende måder at krænke privatlivets fred på.

  men det skaber også spændende muligheder—at forbedre transportnetværk, reducere kriminalitet, helbrede sygdomme—hvis de stilles til rådighed for de rigtige dataforskere og forskere. Der er en naturlig spænding mellem at beskytte privatlivets fred for enkeltpersoner i datasættet og muliggøre analyser, der kan føre til en bedre verden.differentielt private algoritmer er en lovende teknisk løsning, der kan lette denne spænding, så analytikere kan udføre godartet aggregatanalyse, samtidig med at de garanterer meningsfuld beskyttelse af den enkeltes privatliv.

  dette teknologiske udviklingsområde er værd at overveje i ethvert system, der søger at analysere følsomme data. Selvom den differentierede privatlivsgaranti blev udtænkt for kun ti år siden, har den haft succes i den akademiske verden og industrien. Forskere opfinder og forbedrer hurtigt differentielt private algoritmer, hvoraf nogle er blevet vedtaget i både Apples iOS og Googles Chrome.

  denne artikel diskuterer de historiske faktorer, der fører til differentieret privatliv i sin nuværende form, sammen med en definition af differentieret privatliv og eksempel differentielt private algoritmer. Det ser derefter på nogle nylige højt profilerede implementeringer af differentielt private algoritmer af Google, Apple og andre.

  baggrund

  differentielt private algoritmer er de seneste i et årtier gammelt felt af teknologier til beskyttelse af privatlivets fred dataanalyse. To tidligere begreber påvirkede direkte differentieret privatliv:

  1. mindste forespørgselssætstørrelse
  2. Dalenius ‘ s definition af statistisk afsløring.

  Vi forklarer disse først, da de giver nyttig baggrund for differentieret privatliv.

  minimum forespørgsel sæt størrelse det første koncept er en minimum forespørgsel sæt størrelse, som—ligesom differentielt private algoritmer—har til formål at sikre sikkerheden af aggregerede forespørgsler. Samlede forespørgsler er dem, hvor den returnerede værdi beregnes på tværs af en delmængde af poster i datasættet, f.eks. Det kan være nyttigt at tænke på samlede forespørgsler som forespørgsler, der begynder med “Vælg SUM”, “Vælg antal” eller “vælg gennemsnit”. Andre typer af samlede forespørgsler omfatter beredskabstabeller og histogrammer.

  en minimum forespørgselssætstørrelse er en begrænsning, der søger at sikre, at samlede forespørgsler ikke kan lække oplysninger om enkeltpersoner. Givet nogle konfigureret tærskel nummer T, Det sikrer, at hver samlet forespørgsel udføres på et sæt af mindst T poster. En mindste forespørgselssætstørrelse ville blokere samlede forespørgsler, der målrettede færre end T-individer. For eksempel, hvis T=2, ville det blokere følgende:

  “vælg AVG(løn) hvor name = ‘Troy brun’;”.

  fordi denne forespørgsel ville foretage et gennemsnit over en post (vi antager, at der kun er en Troy brun).

  brug af minimale forespørgselssætstørrelser forhindrer visse angreb, men leveres ikke med en privatlivsgaranti og kan i praksis omgås af dygtige angribere. For eksempel kunne angriberen udføre ovenstående angreb med:

  “vælg SUM(løn);”.

  ” vælg SUM (løn) Hvor navn != ‘Troy Brun’;”.

  eller endda, hvis vi kender Troy brun Alder (45) og position (VR) entydigt identificere ham:

  “vælg SUM(løn) hvor position = ‘VR’;”.

  “vælg SUM (løn) hvor position =’ VR ‘ og alder != 45;

  sådanne angreb kaldes tracker angreb, og de kan ikke stoppes af en minimum forespørgsel sæt størrelse begrænsning. På grund af disse angreb blev minimale forespørgselssætstørrelser betragtet som et utilstrækkeligt forsvar til beskyttelse af forespørgselssystemer (se Dennings arbejde). Noget bedre, med en garanti, var nødvendigt for at sikre privatlivets fred.

  Dalenius ‘ s definition af statistisk afsløring

  i 1977 foreslog statistikeren Tore Dalenius en streng definition af Databeskyttelse: at angriberen ikke skulle lære noget om en person, som de ikke vidste, før de brugte det følsomme datasæt. Selvom denne garanti mislykkedes (og vi vil se hvorfor), er det vigtigt at forstå, hvorfor differentieret privatliv er konstrueret som det er.Dalenius ‘ definition mislykkedes, fordi computerforsker Cynthia i 2006 beviste, at denne garanti var umulig at give—med andre ord ville enhver adgang til følsomme data krænke denne definition af privatlivets fred. Problemet, hun fandt, var, at visse typer baggrundsinformation altid kunne føre til en ny konklusion om et individ. Hendes bevis er illustreret i følgende anekdote: Jeg ved, at Alice er to inches højere end den gennemsnitlige litauiske kvinde. Så interagerer jeg med et datasæt af litauiske kvinder og beregner den gennemsnitlige højde, som jeg ikke vidste før. Jeg kender nu Alice ‘ s højde nøjagtigt, selvom hun ikke var i datasættet. Det er umuligt at redegøre for alle typer baggrundsoplysninger, der kan føre til en ny konklusion om en person fra brug af et datasæt.

  Darbejde, efter at have bevist ovenstående, foreslog en ny definition: differentieret privatliv.

  hvad er differentieret privatliv?

  Differential privacy garanterer følgende: at angriberen kan lære næsten intet mere om en person, end de ville lære, hvis personens rekord var fraværende fra datasættet. Selvom den er svagere end Dalenius ‘ definition af privatlivets fred, er garantien stærk nok, fordi den er i overensstemmelse med den virkelige verdens incitamenter—enkeltpersoner har intet incitament til ikke at deltage i et datasæt, fordi analytikerne af dette datasæt vil drage de samme konklusioner om den enkelte, uanset om personen inkluderer sig selv i datasættet eller ej. Da deres følsomme personlige oplysninger næsten er irrelevante i systemets output, kan brugerne være sikre på, at den organisation, der håndterer deres data, ikke krænker deres privatliv.analytikere, der lærer “næsten intet mere om et individ” betyder, at de er begrænset til en ubetydelig lille ændring i troen på ethvert individ. (Her og nedenfor henviser “ændring” til ændringen mellem at bruge et datasæt og bruge det samme datasæt minus en persons post.) Omfanget af denne ændring styres af en parameter kendt som kur, som sætter grænsen for ændringen i sandsynligheden for ethvert resultat. 0,1, betyder, at meget lidt kan ændre sig i troen på ethvert individ. En høj værdi af Kristus, såsom 50, betyder, at tro kan ændre sig væsentligt mere. Den formelle definition er som følger.

  en algoritme A er Prip-differentielt privat, hvis og kun hvis:

  Pr Prip e^Prip * Pr

  for alle K og for alle par datasæt D, D’ hvor D’ er D med en hvilken som helst post—dvs.en persons data—mangler. Symbolet E henviser til den matematiske konstant. Bemærk, at denne definition kun giver mening for randomiserede algoritmer. En algoritme, der giver deterministisk output, er ikke en kandidat til differentieret privatliv.

  den primære appel af den differentierede privatlivsgaranti er dens begrænsning af det beløb, som enhver analytiker kan lære om en person. Derudover har den følgende nyttige egenskaber:

  • Composability: hvis to forespørgsler besvares med differentierede privatlivsgarantier for niveau lus1 og lus2, dækkes paret af en garanti for niveau (lus1 + lus2). Husk på, at en højere værdi af kursist betyder en svagere garanti.
  • styrke mod vilkårlig baggrundsinformation: garantien er ikke på nogen måde afhængig af, hvilke baggrundsoplysninger angriberen kender. Denne ejendom er en af hovedårsagerne til, at differentieret privatliv er stærkere end en tidligere privatlivsgaranti, k-anonymitet.
  • sikkerhed under efterbehandling: der er ingen begrænsninger for, hvad der kan gøres med et differentielt privat resultat – uanset hvad det kombineres med, eller hvordan det transformeres, er det stadig differentielt privat.

  hvordan opnås denne garanti i programmer? Differentielt private algoritmer er randomiserede algoritmer, der tilføjer støj på nøglepunkter i algoritmen. En af de enkleste algoritmer er Laplace-mekanismen, som kan efterbehandle resultater af samlede forespørgsler (f.eks. Nedenfor er Eksempel Java-kode til Laplace-mekanismen, der er specifik for at tælle forespørgsler:

  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 vigtigste dele af denne funktion er

  1. instantiere en Laplace sandsynlighedsfordeling (se figur 1) centreret ved 0 og skaleret med 1/list. Vi bruger Apache Commons implementering,” LaplaceDistribution”, som er konstrueret med to argumenter: middelværdien af fordelingen, og omfanget af fordelingen. Bemærk, at lavere epsilon (mere privatliv) fører til en større skala og dermed en bredere distribution og mere støj.
  2. Tegn en tilfældig prøve fra denne fordeling. Denne prøve () – funktion tager et tilfældigt tal mellem 0 og 1 og anvender Laplace-distributionens inverse kumulative fordelingsfunktion (CDF) på dette tal. Denne proces resulterer i et tilfældigt tal, således at dets sandsynlighed for at være en bestemt værdi svarer til fordelingen. Som en alternativ måde at tænke over det på, hvis denne prøvefunktion blev påberåbt en million gange for at få en million prøver, ville formen på histogrammet for disse prøver nøje matche formen på Laplace-fordelingen.
  3. forstyrrer den reelle værdi ved at tilføje den tilfældige værdi fra trin 2.

  lad os overveje, hvorfor denne algoritme er differentielt privat ved at tage synspunktet fra en angriber ved navn Eve. Sig datasættet er mentale sundhedsdata, og Eve har udtænkt et trackerangreb (se ovenfor), der vil afsløre, om hendes mål, Bob, modtager rådgivning for alkoholisme eller ej. Hvis forespørgslens resultat er 48, Eva ved, at Bob modtager rådgivning; hvis det er 47, Eva ved det modsatte.

  uanset om svaret er 47 eller 48, vil Laplace-mekanismen returnere et støjende resultat et sted omkring 47 eller 48. Det kan returnere 49, 46 eller endda med mindre sandsynlighed 44 eller 51 (se figur 2 for et histogram). I praksis er det umuligt for Eva at være meget sikker på, om det sande svar var 47 eller 48, og dermed vil hendes tro på, om Bob er i rådgivning for alkoholisme eller nu, ikke ændre sig meningsfuldt.

  

  Figur 1: Laplace-fordelingen centreret ved 0 med skala på 1. På billedet er sandsynlighedsdensitetsfunktionen (PDF) for fordelingen—y-aksen er den relative sandsynlighed for, at variablen vil tage værdien på h-aksen.

  

  figur 2: de sandsynlige resultater af tælleforespørgslen for de to scenarier, hvor det virkelige svar er 47 og når det er 48. Et lille antal output ville ikke være nok til at skelne, hvilken distribution de kom fra. Epsilon er indstillet til 0,67.

  Du har måske observeret på dette tidspunkt, at Eve kunne skære igennem støjen ved at gentage forespørgslen mange gange og se, om svarene klynger sig omkring 47 eller 48. For at forhindre denne taktik skal differentielt private systemer have et “privatlivsbudget”, et loft på summen af de kraner, der bruges i hver forespørgsel. Denne hætte fungerer på grund af differential privacy ‘ s composability-egenskab beskrevet ovenfor. De kan stille et par relativt støjsvage forespørgsler eller mange hundreder af støjsvage forespørgsler, men uanset hvad vil de ikke være i stand til med sikkerhed at fastslå, om det sande svar er 47 eller 48.

  endelig bemærk, at Laplace-mekanismen for tællinger kun er en simpel differentielt privat algoritme. Laplace-mekanismen kan udvides til at arbejde for summer og andre samlede forespørgsler. Derudover er der grundlæggende forskellige algoritmer, der har vist sig at tilfredsstille den differentierede privatlivsgaranti. Et par værd at udforske er den private multiplikative Vægtalgoritme, den multiplikative vægt eksponentiel mekanisme og Dualforespørgsel.

  Differential privacy in action

  i Juni 2016 meddelte Apple, at det ville begynde at bruge differentielt private algoritmer til at indsamle adfærdsstatistikker fra iPhones. Denne meddelelse, udover at forårsage en enorm stigning i differentieret privatlivsinteresse, viste, at differentieret privatliv kan hjælpe store organisationer med at få ny værdi fra data, som de tidligere ikke rørte ved på grund af privatlivets fred.

  selvom Apple hidtil har offentliggjort få detaljer, ligner algoritmen, der bruges i iPhone, Googles rapport-projekt. Google implementerede en funktion i Chrome, der indsamler adfærdsstatistikker fra Chrome gennem en differentielt privat randomiseret responsalgoritme.

  i randomiseret respons tilføjes tilfældig støj til statistikker, før de sendes til samleren. For eksempel, hvis den reelle statistik er 0, vil bro.ser med en vis sandsynlighed erstatte 0 med en tilfældigt valgt 0 eller 1. Hver bruger har en stor grad af benægtelse af den værdi, som deres program rapporterer, fordi det kan være en tilfældig værdi. Men samlet set skiller signalet sig ud over den tilfældige støj, og organisationen, der indsamler statistikken (dvs.Google eller Apple), kan nøjagtigt observere tendenser.

  interessant nok har hverken Google eller Apple, så vidt vi ved, afsløret værdien af karrus, der følger med deres differentierede privatlivsgaranti. Vi har brug for denne værdi for at forstå den beskyttelse, der tilbydes af garantien. Hvis de bruger en høj nok værdi af Kurt, kan analytikere stadig lære følsomme fakta om brugere med stor tillid. Der kræves en lav værdi af krop for meningsfuld beskyttelse af privatlivets fred.

  differentielt private algoritmer er også blevet implementeret i privatlivsbeskyttende analyseprodukter, såsom dem, der er udviklet af min arbejdsgiver Privitar. Disse produkter giver virksomheder, der arbejder med værdifulde, følsomme data, mulighed for at inkorporere differentielt private algoritmer i deres dataarkitektur, hvilket giver privatlivsgarantier til deres brugere, mens de stadig udfører meningsfuld analyse af dataene.

  ser fremad

  både ingeniør-og forskningsmiljøerne har veje fremad med differentieret privatliv. For ingeniører er opgaven at blive uddannet i differentieret privatliv og sikre, at det bruges, hvor det er relevant til beskyttelse af brugernes privatliv. For forskere er det at finde flere og bedre differentielt private algoritmer og forbedre det værktøjssæt, som vi kan aktivere privatlivsbevarende dataanalyse med.

  Vi kan alle drage fordel af etableringen af privatlivsgarantier og succeserne med dataanalyse. Af begge grunde ser vi frem til, at flere organisationer omfavner differentieret privatliv.

  om forfatteren

  Charlie Cabot er senior Data scientist hos Privitar, en datasikkerhedsstart, der bygger højtydende programmer til data anonymisering, herunder forstyrrelser og generaliseringsalgoritmer og differentielt private mekanismer, for at lette sikker brug af følsomme datasæt. Charlie fokuserer på beviselige privatlivsgarantier og den statistiske indvirkning af anonymisering på analyse og datalogi. Tidligere arbejdede han med cybersikkerhed og konstruerede machine learning-drevne tilgange til afsløring af ondsindede programmer og modellerede cyberangreb på computernetværk.