Differential privacy hoppade från forskningsrapporter till tech nyhetsrubriker förra året när, i WWDC keynote, Apple VP of Engineering Craig Federighi meddelade Apples användning av konceptet för att skydda användarnas integritet i iOS.

det var den senaste förekomsten av en allmän trend: användare och ingenjörer uppvaknande till vikten av integritetsskydd i programvara. Högprofilerade integritetsbrott som Ubers ”God mode” har visat i skarpa termer hur lätt anställda i ett företag kan missbruka känslig data som samlats in från sina kunder.

mängden känslig data som registreras digitalt ökar snabbt. Människor litar nu på digitala tjänster för mer av sina betalningar, transport, navigering, shopping och hälsa än någonsin. Denna nya datainsamling skapar ständigt ökande sätt att kränka integriteten.

men det skapar också spännande möjligheter-att förbättra transportnäten, att minska brottsligheten, att bota sjukdomar – om de görs tillgängliga för rätt Dataforskare och forskare. Det finns en naturlig spänning mellan att skydda privatlivet för individer i datasetet och möjliggöra analyser som kan leda till en bättre värld.

differentiellt privata algoritmer är en lovande teknisk lösning som kan lindra denna spänning, vilket gör det möjligt för analytiker att utföra godartad aggregerad analys samtidigt som man garanterar meningsfullt skydd för varje individs integritet.

detta utvecklingsområde är värt att överväga i alla system som syftar till att analysera känsliga data. Även om den differentiella integritetsgarantin utformades för bara tio år sedan har den varit framgångsrik inom akademin och industrin. Forskare uppfinner snabbt och förbättrar differentiellt privata algoritmer, av vilka några har antagits i både Apples iOS och Googles Chrome.

den här artikeln diskuterar de historiska faktorer som leder till differentiell integritet i sin nuvarande form, tillsammans med en definition av differentiell integritet och exempel differentiellt privata algoritmer. Det tittar sedan på några nyligen högprofilerade implementeringar av differentiellt privata algoritmer av Google, Apple och andra.

Bakgrund

differentiellt privata algoritmer är det senaste inom ett decennier gammalt teknikområde för integritetsbevarande dataanalys. Två tidigare begrepp påverkade direkt differentiell integritet:

1. minsta frågeställningsstorlek
2. Dalenius definition av statistisk information.

vi förklarar dessa först eftersom de ger användbar bakgrund för differentiell integritet.

minsta frågeuppsättningsstorlek det första konceptet är en minsta frågeuppsättningsstorlek, som—som differentiellt privata algoritmer-syftar till att säkerställa säkerheten för aggregerade frågor. Aggregerade frågor är de där det returnerade värdet beräknas över en delmängd av poster i datauppsättningen, till exempel räkningar, medelvärden eller summor. Det kan vara bra att tänka på aggregerade frågor som SQL-frågor som börjar med ”välj summa”, ”välj antal” eller ”välj AVG”. Andra typer av aggregerade frågor inkluderar beredskapstabeller och histogram.

en minsta frågestorlek är en begränsning som syftar till att säkerställa att aggregerade frågor inte kan läcka information om individer. Med tanke på vissa konfigurerade tröskelnummer T säkerställer det att varje aggregerad fråga utförs på en uppsättning av minst T-poster. En minsta frågestorlek skulle blockera aggregerade frågor som riktade sig till färre än t-individer. Till exempel, om T=2, skulle det blockera följande:

”välj AVG(lön) där name = ’Troy Brown’;”.

eftersom den här frågan skulle göra ett genomsnitt över en post (Vi antar att det bara finns en Troy Brown).

att använda minsta frågeuppsättningsstorlekar förhindrar vissa attacker, men kommer inte med en integritetsgaranti och kan i praktiken kringgås av skickliga angripare. Till exempel kan angriparen utföra ovanstående attack med:

”välj summa(lön);”.

”välj summa (lön) där namn != ’Troy Brown’;”.

eller till och med, om vi vet Troy Browns ålder (45) och position (WR) identifierar honom unikt:

”välj summa(lön) där position = ’WR’;”.

”välj summa (lön) där position = ’WR’ och ålder != 45;

sådana attacker kallas spårningsattacker, och de kan inte stoppas av en begränsning av minsta fråga. På grund av dessa attacker ansågs minsta frågeuppsättningsstorlekar vara ett otillräckligt försvar för att skydda frågesystem (se Dennings arbete). Något bättre, med en garanti, behövdes för att säkerställa integriteten.

Dalenius ’ s statistical disclosure definition

1977 föreslog statistikern Tore Dalenius en strikt definition av datasekretess: att angriparen inte skulle lära sig något om en individ som de inte visste innan de använde den känsliga datamängden. Även om denna garanti misslyckades (och vi kommer att se varför) är det viktigt att förstå varför differentiell integritet är konstruerad som den är.

Dalenius definition misslyckades eftersom datavetenskapsmannen Cynthia Dwork 2006 visade att denna garanti var omöjlig att ge—med andra ord skulle All tillgång till känsliga uppgifter bryta mot denna definition av integritet. Problemet hon fann var att vissa typer av bakgrundsinformation alltid kan leda till en ny slutsats om en individ. Hennes bevis illustreras i följande anekdot: Jag vet att Alice är två inches högre än den genomsnittliga Litauiska kvinnan. Sedan interagerar jag med en dataset av Litauiska kvinnor och beräknar den genomsnittliga höjden, som jag inte visste förut. Jag vet nu Alices höjd exakt, även om hon inte var i datasetet. Det är omöjligt att redogöra för alla typer av bakgrundsinformation som kan leda till en ny slutsats om en individ från användning av en dataset.

Dwork, efter att ha bevisat ovanstående, föreslog en ny definition: differentiell integritet.

vad är differentiell integritet?

differentiell integritet garanterar följande: att angriparen kan lära sig nästan ingenting mer om en individ än de skulle lära sig om den personens rekord var frånvarande från datasetet. Medan svagare än Dalenius definition av integritet, är garantin stark nog eftersom den ligger i linje med verkliga incitament—individer har inget incitament att inte delta i en dataset, eftersom analytikerna i det dataset kommer att dra samma slutsatser om den individen om individen inkluderar sig själv i dataset eller inte. Eftersom deras känsliga personuppgifter är nästan irrelevanta i systemets resultat kan användarna vara säkra på att organisationen som hanterar deras data inte bryter mot deras integritet.

analytiker som lär sig ”praktiskt taget ingenting mer om en individ” betyder att de är begränsade till en obetydligt liten förändring i tron på någon individ. (Här och nedan hänvisar ”förändring” till förändringen mellan att använda en dataset och använda samma dataset minus någon persons post.) Omfattningen av denna förändring styrs av en parameter som kallas för bord, som sätter gränsen på förändringen i sannolikheten för något resultat. Ett lågt värde på 0,1 betyder att mycket lite kan förändras i tron på någon individ. Ett högt värde på 50, till exempel, betyder att tron kan förändras betydligt mer. Den formella definitionen är som följer.

en algoritm A är privat om och endast om:

pr oskyl e^osk * Pr

för alla X och för alla par av datamängder D, D’ där D’ är D med någon post—dvs. en persons data—saknas. Symbolen e hänvisar till den matematiska konstanten. Observera att denna definition endast är meningsfull för randomiserade algoritmer. En algoritm som ger deterministisk utgång är inte en kandidat för differentiell integritet.

den primära överklagandet av differentiell integritetsgaranti är dess begränsning av det belopp som någon analytiker kan lära sig om en individ. Dessutom har den följande användbara egenskaper:

• Composability: om två frågor besvaras med differentiella integritetsgarantier på nivå 1 och 2, täcks paret av en garanti på nivå(1 + 2). Kom ihåg att ett högre värde på Macau betyder en svagare garanti.
• styrka mot godtycklig bakgrundsinformation: garantin förlitar sig inte på något sätt på vilken bakgrundsinformation angriparen känner till. Den här egenskapen är en av de främsta anledningarna till att differentiell integritet är starkare än en tidigare integritetsgaranti, k-anonymitet.
• säkerhet under efterbehandling: det finns inga begränsningar för vad som kan göras med ett differentiellt privat resultat – oavsett vad det kombineras med eller hur det omvandlas, det är fortfarande differentiellt privat.

hur uppnås denna garanti i programvara? Differentiellt privata algoritmer är randomiserade algoritmer som lägger till brus vid viktiga punkter inom algoritmen. En av de enklaste algoritmerna är Laplace-mekanismen, som kan efterbehandla resultat av aggregerade frågor (t.ex. räkningar, summor och medel) för att göra dem differentiellt privata. Nedan följer exempel Java-kod för Laplace-mekanismen som är specifik för att räkna frågor:

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 viktigaste delarna av denna funktion är

1. Instantiera en Laplace-sannolikhetsfördelning (se Figur 1) centrerad vid 0 och skalad med 1/GHz. Vi använder Apache Commons-implementeringen, ”LaplaceDistribution”, som är konstruerad med två argument: distributionens medelvärde och distributionens skala. Observera att lägre epsilon (mer integritet) leder till en större skala och därmed en bredare distribution och mer buller.
2. rita ett slumpmässigt urval från denna fördelning. Denna sample () – funktion tar ett slumptal mellan 0 och 1 och tillämpar Laplace-fördelningens inverse kumulativa fördelningsfunktion (CDF) på detta nummer. Denna process resulterar i ett slumptal så att dess sannolikhet för att vara något specifikt värde matchar fördelningen. Som ett alternativt sätt att tänka på det, om denna provfunktion åberopades en miljon gånger för att få en miljon prover, skulle formen på histogrammet för dessa prover nära matcha formen på Laplace-fördelningen.
3. störa det verkliga värdet genom att lägga till det slumpmässiga värdet från steg 2.

låt oss överväga varför denna algoritm är differentiellt privat genom att ta hänsyn till en angripare som heter Eve. Säg att datamängden är mentala hälsodata, och Eve har tänkt på en spårningsattack (se ovan) som kommer att avslöja om hennes mål, Bob, får rådgivning för alkoholism eller inte. Om frågans resultat är 48, vet Eve att Bob får rådgivning; om det är 47, vet Eve motsatsen.

oavsett om svaret är 47 eller 48, kommer Laplace-mekanismen att returnera ett bullrigt resultat någonstans runt 47 eller 48. Det kan returnera 49, 46 eller till och med, med mindre sannolikhet, 44 eller 51 (se Figur 2 för ett histogram). I praktiken är det omöjligt för Eva att vara mycket säker på om det sanna svaret var 47 eller 48 och därmed kommer hennes tro på om Bob är i rådgivning för alkoholism eller nu inte meningsfullt att förändras.

Figur 1: Laplace-fördelningen centrerad vid 0 med skala 1. På bilden visas fördelningens sannolikhetstäthetsfunktion (PDF)-y-axeln är den relativa sannolikheten för att variabeln tar värdet på x-axeln.

Figur 2: de troliga resultaten av räknefrågan för de två scenarierna, där det verkliga svaret är 47 och när det är 48. Ett litet antal utgångar skulle inte räcka för att skilja vilken distribution de kom ifrån. Epsilon är satt till 0,67.

Du kanske har observerat vid denna tidpunkt att Eve kunde skära igenom bruset genom att upprepa frågan många gånger och se om svaren kluster runt 47 eller 48. För att förhindra denna taktik, differentiellt privata system måste ha en ”privacy budget,” ett tak på summan av de som används i varje fråga. Denna cap fungerar på grund av differential privacy s composability egenskap som beskrivs ovan. De kan ställa några relativt låga ljudfrågor, eller många hundratals höga ljudfrågor, men på något sätt kommer de inte att kunna med säkerhet fastställa om det sanna svaret är 47 eller 48.

Slutligen notera att Laplace-mekanismen för räkningar bara är en enkel differentiellt privat algoritm. Laplace-mekanismen kan utökas till att fungera för summor och andra aggregerade frågor. Dessutom finns det fundamentalt olika algoritmer som har visat sig uppfylla den differentiella integritetsgarantin. Några värda att utforska är algoritmen för privata multiplikativa vikter, exponentiell mekanism för multiplikativa vikter och DualQuery.

Differential privacy in action

i juni 2016 meddelade Apple att de skulle börja använda differentiellt privata algoritmer för att samla beteendestatistik från iPhones. Detta tillkännagivande, förutom att orsaka en enorm ökning av differentiellt integritetsintresse, visade att differentiell integritet kan hjälpa stora organisationer att få nytt värde från data som de tidigare inte berörde på grund av integritetsfrågor.

Även om Apple hittills har offentliggjort några detaljer, verkar algoritmen som används i iPhone liknar Googles rapport-projekt. Google implementerade en funktion i Chrome som samlar beteendestatistik från Chrome-webbläsare genom en differentiellt privat randomiserad svaralgoritm.

i randomiserat svar läggs slumpmässigt brus till statistiken innan de skickas till samlaren. Till exempel, om den verkliga statistiken är 0, kommer webbläsaren med viss sannolikhet att ersätta 0 med en slumpmässigt vald 0 eller 1. Varje användare har en stor grad av deniability om det värde som deras programvara rapporterar, eftersom det kan vara ett slumpmässigt värde. Men kollektivt sticker signalen ut över det slumpmässiga bruset och organisationen som samlar in statistiken (dvs. Google eller Apple) kan noggrant observera trender.

intressant nog har varken Google eller Apple, så vitt vi vet, avslöjat värdet på att det är en garanti för deras olika integritetsskydd. Vi behöver detta värde för att förstå det skydd som garantin erbjuder. Om de använder ett tillräckligt högt värde på Macau kan analytiker fortfarande lära sig känsliga fakta om användare med högt förtroende. För ett meningsfullt integritetsskydd krävs ett lågt värde på Taiwan.

differentiellt privata algoritmer har också implementerats i sekretessbevarande analysprodukter, till exempel de som utvecklats av min arbetsgivare Privitar. Dessa produkter gör det möjligt för företag som arbetar med värdefulla, känsliga data att införliva differentiellt privata algoritmer i sin dataarkitektur, vilket ger integritetsgarantier till sina användare samtidigt som de utför meningsfull analys av data.

blickar framåt

både teknik-och forskarsamhällena har vägar framåt med differentiell integritet. För ingenjörer är uppgiften att bli utbildad om differentiell integritet och se till att den används där det är lämpligt för användarskydd. För forskare är det att hitta fler och bättre differentiellt privata algoritmer, vilket förbättrar verktygssatsen med vilken vi kan möjliggöra integritetsbevarande dataanalys.

Vi står alla för att vinna på upprättandet av integritetsgarantier och framgångarna med dataanalys. Av båda anledningarna ser vi fram emot fler organisationer som omfattar differentiell integritet.

om författaren

Charlie Cabot är en senior Data scientist vid Privitar, en datasekretessstart som bygger högpresterande programvara för data anonymisering, inklusive störnings-och generaliseringsalgoritmer och differentiellt privata mekanismer, för att underlätta säker användning av känsliga dataset. Charlie fokuserar på bevisbara integritetsgarantier och den statistiska effekten av anonymisering på analys och datavetenskap. Tidigare arbetade Charlie inom cybersäkerhet och konstruerade maskininlärningsdrivna metoder för att upptäcka skadlig kod och modellerade cyberattacker på datanätverk.