Key Takeaways

• differentiële privacy kan worden bereikt door gerandomiseerde “ruis” toe te voegen aan een geaggregeerd queryresultaat om individuele items te beschermen zonder het resultaat significant te veranderen.
• differentieel private algoritmen garanderen dat de aanvaller vrijwel niets meer over een individu kan leren dan ze zouden leren als het record van die persoon afwezig was in de dataset.
• een van de eenvoudigste algoritmen is het Laplace-mechanisme, dat resultaten van geaggregeerde queries kan verwerken.
• zowel Apple als Google maken gebruik van differentiële privacytechnieken in respectievelijk iOS en Chrome. Differentieel private algoritmen zijn ook geà mplementeerd in privacybeschermende analytics-producten, zoals die ontwikkeld door Privitar.
• differentieel private algoritmen zijn nog steeds een actief onderzoeksgebied.differentiële privacy sprong vorig jaar van research papers naar tech news headlines toen, in de WWDC keynote, Apple VP van Engineering Craig Federighi kondigde Apple ‘ s gebruik van het concept om de privacy van gebruikers in iOS te beschermen.

  Het was het meest recente voorbeeld van een algemene trend: gebruikers en ingenieurs die zich bewust werden van het belang van privacybescherming in software. High-profile privacy schendingen zoals Uber ‘ s “God mode” hebben aangetoond in grimmige termen het gemak waarmee werknemers van een bedrijf kunnen misbruik maken van gevoelige gegevens verzameld van hun klanten.

  de hoeveelheid gevoelige gegevens die digitaal wordt geregistreerd neemt snel toe. Mensen vertrouwen nu meer dan ooit op digitale diensten voor hun betalingen, transport, navigatie, winkelen en gezondheid. Deze nieuwe gegevensverzameling creëert steeds meer manieren om privacy te schenden.

  maar het creëert ook interessante mogelijkheden—om transportnetwerken te verbeteren, criminaliteit te verminderen, ziekten te genezen-als het beschikbaar wordt gesteld aan de juiste datawetenschappers en onderzoekers. Er is een natuurlijke spanning tussen het beschermen van de privacy van individuen in de dataset en het mogelijk maken van analytics die kunnen leiden tot een betere wereld.

  differentieel private algoritmen zijn een veelbelovende technische oplossing die deze spanning zou kunnen verlichten, waardoor analisten goedaardige geaggregeerde analyse kunnen uitvoeren terwijl ze een zinvolle bescherming van de privacy van elk individu garanderen.

  Dit zich ontwikkelende gebied van technologie is het overwegen waard in elk systeem dat gevoelige gegevens probeert te analyseren. Hoewel de differentiële privacygarantie pas tien jaar geleden werd bedacht, is het succesvol geweest in de academische wereld en de industrie. Onderzoekers zijn snel uitvinden en het verbeteren van differentieel private algoritmen, waarvan sommige zijn overgenomen in zowel Apple ’s iOS en Google’ s Chrome.

  Dit artikel bespreekt de historische factoren die leiden tot differentiële privacy in zijn huidige vorm, samen met een definitie van differentiële privacy en voorbeeld differentieel private algoritmen. Het kijkt dan naar een aantal recente high-profile implementaties van differentieel private algoritmen door Google, Apple, en anderen.

  Achtergrond

  differentieel private algoritmen zijn de nieuwste in een decennia oud gebied van technologieën voor privacy-behoud van data-analyse. Twee eerdere concepten hadden rechtstreeks invloed op de differentiële privacy:

  1. Minimum query set size
  2. Dalenius ‘ s statistical disclosure definition.

  We zullen deze eerst uitleggen omdat ze nuttige achtergrond bieden voor differentiële privacy.

  Minimum query set size het eerste concept is een minimum query set size, die-net als differentieel private algoritmes—de veiligheid van geaggregeerde query ‘ s wil waarborgen. Geaggregeerde queries zijn die waarbij de geretourneerde waarde wordt berekend over een subset records in de dataset, zoals tellingen, gemiddelden of sommen. Het kan nuttig zijn om samengevoegde query ’s te zien als SQL query’ s die beginnen met “Select SUM”, “select COUNT” of “SELECT AVG”. Andere soorten geaggregeerde queries omvatten contingency tabellen en histogrammen.

  een minimale query-setgrootte is een beperking die ervoor zorgt dat geaggregeerde query ‘ s geen informatie over individuen kunnen lekken. Gegeven sommige geconfigureerde drempelnummer T, het zorgt ervoor dat elke geaggregeerde query wordt uitgevoerd op een set van ten minste T records. Een minimale query set grootte zou blokkeren geaggregeerde query ‘ s die minder dan t individuen gericht. Bijvoorbeeld, als T=2, Het zou blokkeren het volgende:

  “SELECT AVG (salaris) WHERE name = ‘Troy Brown’;”.

  omdat deze query een gemiddelde zou uitvoeren over één record (we gaan ervan uit dat er maar één Troy Brown is).

  het gebruik van minimale query – setgroottes voorkomt bepaalde aanvallen, maar komt niet met een privacygarantie en kan in de praktijk worden omzeild door ervaren aanvallers. De aanvaller kan bijvoorbeeld de bovenstaande aanval uitvoeren met:

  ” SELECT SUM (salary);”.

  ” selecteer Som (salaris) waar Naam != “Troy Brown”;”.

  of zelfs, als we Troy Brown ’s Leeftijd (45) en positie (WR) kennen, identificeren hem uniek:

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

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

  dergelijke aanvallen worden tracker aanvallen genoemd, en ze kunnen niet worden gestopt door een minimale query set size beperking. Vanwege deze aanvallen werden minimale query-sets beschouwd als een onvoldoende verdediging voor het beschermen van query-systemen (zie het werk van Denning). Iets beters, met een garantie, was nodig om de privacy te waarborgen.in 1977 stelde statisticus Tore Dalenius een strikte definitie van gegevensprivacy voor: dat de aanvaller niets zou moeten leren over een persoon die hij niet kende voordat hij de gevoelige dataset gebruikte. Hoewel deze garantie mislukte (en we zullen zien waarom), is het belangrijk om te begrijpen waarom differentiële privacy is geconstrueerd zoals het is.de definitie van Dalenius mislukte omdat computerwetenschapper Cynthia Dworkin 2006 aantoonde dat deze garantie onmogelijk was—met andere woorden, elke toegang tot gevoelige gegevens zou in strijd zijn met deze definitie van privacy. Het probleem dat ze vond was dat bepaalde soorten achtergrondinformatie altijd kon leiden tot een nieuwe conclusie over een individu. Haar bewijs wordt geïllustreerd in de volgende anekdote: Ik weet dat Alice vijf centimeter groter is dan de gemiddelde Litouwse vrouw. Dan interageer ik met een dataset van Litouwse vrouwen en bereken ik de gemiddelde lengte, die ik voorheen niet kende. Ik weet nu Alice ‘ s lengte precies, ook al stond ze niet in de dataset. Het is onmogelijk om rekening te houden met alle soorten achtergrondinformatie die zou kunnen leiden tot een nieuwe conclusie over een individu uit het gebruik van een dataset.

  Dwwork heeft, na het bovenstaande te hebben aangetoond, een nieuwe definitie voorgesteld: differentiële privacy.

  Wat is differentiële privacy?

  differentiële privacy garandeert het volgende:: dat de aanvaller vrijwel niets meer over een individu kan leren dan ze zouden leren als het record van die persoon afwezig was in de dataset. Hoewel zwakker dan Dalenius ‘ definitie van privacy, is de garantie sterk genoeg omdat het in lijn is met echte prikkels—individuen hebben geen stimulans om niet deel te nemen aan een dataset, omdat de analisten van die dataset dezelfde conclusies zullen trekken over dat individu of het individu zichzelf in de dataset opneemt of niet. Omdat hun gevoelige persoonlijke informatie bijna irrelevant is in de output van het systeem, kunnen gebruikers ervan verzekerd zijn dat de organisatie die hun gegevens verwerkt, hun privacy niet schendt.

  analisten die “vrijwel niets meer over een individu” leren, betekent dat ze beperkt zijn tot een onbeduidend kleine verandering in geloof over een individu. (Hier en hieronder verwijst “verandering” naar de verandering tussen het gebruik van een dataset en het gebruik van dezelfde dataset minus het record van een persoon.) De omvang van deze verandering wordt gecontroleerd door een parameter bekend als ϵ, die de grens aan de verandering in waarschijnlijkheid van een uitkomst stelt. Een lage waarde van ϵ, zoals 0,1, betekent dat er zeer weinig kan veranderen in de overtuigingen over een individu. Een hoge waarde van ϵ, zoals 50, betekent dat overtuigingen aanzienlijk meer kunnen veranderen. De formele definitie luidt als volgt.

  een algoritme A is ϵ-differentieel privé dan en alleen als:

  Pr ≤ e^ϵ * Pr

  voor alle X en voor alle paren datasets D, D ‘waarbij D’ is D met een record—dat wil zeggen gegevens van één persoon-ontbreekt. Het symbool e verwijst naar de wiskundige constante. Merk op dat deze definitie alleen zinvol is voor gerandomiseerde algoritmen. Een algoritme dat deterministische output geeft is geen kandidaat voor differentiële privacy.

  het belangrijkste voordeel van de differentiële privacygarantie is de beperking van het bedrag dat elke analist over een individu kan leren. Daarnaast heeft het de volgende nuttige eigenschappen:

  • Composability: als twee query ’s worden beantwoord met differentiële privacygaranties van niveau11 en ϵ2, wordt het paar query’ s gedekt door een garantie van niveau (ϵ1 +22). Bedenk dat een hogere waarde van ϵ een zwakkere garantie betekent.
  • sterkte tegen willekeurige achtergrondinformatie: de garantie is op geen enkele manier afhankelijk van welke achtergrondinformatie de aanvaller weet. Deze eigenschap is een van de belangrijkste redenen dat differentiële privacy sterker is dan een eerdere privacygarantie, K-anonimiteit.
  • veiligheid na verwerking: er zijn geen beperkingen op wat kan worden gedaan met een differentieel privé resultaat – ongeacht wat het wordt gecombineerd met of hoe het wordt getransformeerd, het is nog steeds differentieel privé.

  Hoe wordt deze garantie in software bereikt? Differentieel private algoritmen zijn gerandomiseerde algoritmen die ruis toevoegen op belangrijke punten binnen het algoritme. Een van de eenvoudigste algoritmen is het Laplace-mechanisme, dat resultaten van geaggregeerde queries (bijvoorbeeld tellingen, sommen en middelen) kan verwerken om ze differentieel privé te maken. Hieronder is voorbeeld Java-code voor het Laplace-mechanisme dat specifiek is voor het tellen van queries:

  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 belangrijkste onderdelen van deze functie zijn

  1. Instantiate een Laplace kansverdeling (zie Figuur 1) gecentreerd op 0 en geschaald met 1/ϵ. We gebruiken de Apache Commons implementatie, “LaplaceDistribution”, die geconstrueerd is met twee argumenten: Het gemiddelde van de distributie, en de schaal van de distributie. Merk op dat lagere Epsilon (meer privacy) leidt tot een grotere schaal en dus een bredere verspreiding en meer ruis.
  2. Trek één aselecte steekproef uit deze verdeling. Deze sample () functie neemt een willekeurig getal tussen 0 en 1 en past de inverse cumulative distribution function (CDF) van de Laplace distributie toe op dit getal. Dit proces resulteert in een willekeurig getal zodanig dat de waarschijnlijkheid van een specifieke waarde overeenkomt met de verdeling. Als een alternatieve manier om erover na te denken, als deze steekproeffunctie een miljoen keer werd gebruikt om een miljoen monsters te krijgen, zou de vorm van het histogram van deze monsters nauw overeenkomen met de vorm van de Laplace-verdeling.
  3. Perturb de reële waarde door de willekeurige waarde toe te voegen uit stap 2.

  laten we eens kijken waarom dit algoritme differentieel privé is door het gezichtspunt van een aanvaller genaamd Eve te nemen. Stel dat de dataset geestelijke gezondheidsgegevens is, en Eve heeft een tracker aanval bedacht (zie hierboven) die zal onthullen of haar doelwit, Bob, therapie voor alcoholisme ontvangt of niet. Als het resultaat van de query is 48, Eve weet dat Bob krijgt begeleiding; als het 47, Eve weet het tegenovergestelde.

  of het antwoord nu 47 of 48 is, het Laplace-mechanisme geeft een luidruchtig resultaat rond 47 of 48. Het kan 49, 46, of zelfs, met een kleinere kans, 44 of 51 (zie Figuur 2 voor een histogram). In de praktijk is het onmogelijk voor Eve om heel zeker te zijn over de vraag of het ware antwoord 47 of 48 was en, dus, haar overtuigingen over de vraag of Bob in therapie is voor alcoholisme of Nu zal niet zinvol veranderen.

  

  figuur 1: de Laplace-verdeling gecentreerd op 0 met schaal van 1. Afgebeeld is de kansdichtheidsfunctie (PDF) van de verdeling—De y-as is de relatieve waarschijnlijkheid dat de variabele de waarde op de x-as zal nemen.

  

  Figuur 2: de waarschijnlijke uitkomsten van de count query voor de twee scenario ‘ s, waarbij het echte antwoord 47 is en wanneer het 48 is. Een klein aantal outputs zou niet voldoende zijn om te onderscheiden van welke distributie ze afkomstig zijn. Epsilon is ingesteld op 0,67.

  U hebt op dit punt gezien dat Eve door de ruis kon snijden door de query vele malen te herhalen, en te zien of de antwoorden rond 47 of 48 clusterden. Om deze tactiek te voorkomen, differentieel private systemen moeten een “privacy budget,” een limiet op de som van de ϵ ‘ s gebruikt in elke query. Deze cap werkt als gevolg van differential privacy composability eigenschap hierboven beschreven. Ze kunnen vragen een paar relatief lage ruis queries, Of vele honderden high-ruis queries, maar hoe dan ook, ze zullen niet in staat zijn om met vertrouwen vast te stellen of het ware antwoord is 47 of 48.

  ten slotte, merk op dat het Laplace mechanisme voor tellingen slechts één eenvoudig differentieel privé algoritme is. Het Laplace-mechanisme kan worden uitgebreid om te werken voor sommen en andere geaggregeerde queries. Bovendien zijn er fundamenteel verschillende algoritmen waarvan is bewezen dat ze voldoen aan de differentiële privacygarantie. Een paar de moeite waard zijn het Private multiplicatieve gewichten algoritme, de multiplicatieve gewichten exponentieel mechanisme, en DualQuery.

  differentiële privacy in actie

  in juni 2016 kondigde Apple aan dat het differentieel private algoritmen zou gaan gebruiken om gedragsstatistieken van iPhones te verzamelen. Deze aankondiging, naast het veroorzaken van een enorme piek in differentiële privacy belang, toonde aan dat differentiële privacy kan helpen grote organisaties krijgen nieuwe waarde van gegevens die ze eerder niet aanraken als gevolg van privacy zorgen.

  hoewel Apple tot nu toe weinig details openbaar heeft gemaakt, lijkt het algoritme dat wordt gebruikt in de iPhone vergelijkbaar met Google ‘ s RAPPOR project. Google implementeerde een functie in Chrome die gedragsstatistieken verzamelt van Chrome-browsers via een differentieel privé gerandomiseerd antwoordalgoritme.

  in gerandomiseerde respons wordt willekeurige ruis toegevoegd aan statistieken voordat deze aan de collector worden voorgelegd. Bijvoorbeeld, als de echte statistiek 0 is, zal de browser met enige waarschijnlijkheid 0 vervangen door een willekeurig geselecteerde 0 of 1. Elke gebruiker heeft een grote mate van ontkenning over de waarde die hun software rapporteert, omdat het een willekeurige waarde zou kunnen zijn. Maar collectief, het signaal onderscheidt zich over de willekeurige ruis en de organisatie het verzamelen van de statistieken (DWZ Google of Apple) kan nauwkeurig trends waar te nemen.

  interessant is dat noch Google noch Apple, voor zover wij weten, de waarde van ϵ dat gaat met hun differentiële privacygarantie heeft onthuld. We hebben deze waarde nodig om inzicht te krijgen in de bescherming die de garantie biedt. Als ze een voldoende hoge waarde van ϵ gebruiken, kunnen analisten nog steeds gevoelige feiten over gebruikers met veel vertrouwen leren. Een lage waarde van ϵ is vereist voor zinvolle privacybescherming.

  differentieel private algoritmen zijn ook geà mplementeerd in analyseproducten die privacy beschermen, zoals die ontwikkeld zijn door mijn werkgever Privitar. Deze producten stellen bedrijven die met waardevolle, gevoelige gegevens werken in staat om differentieel private algoritmen in hun gegevensarchitectuur op te nemen, waardoor hun gebruikers privacygaranties krijgen terwijl ze nog steeds zinvolle analyses van de gegevens uitvoeren.

  vooruitblikkend

  zowel de engineering-als de onderzoeksgemeenschap hebben wegen naar voren met differentiële privacy. Voor ingenieurs, de taak is om te worden opgeleid over differentiële privacy en ervoor te zorgen dat het wordt gebruikt waar nodig voor de bescherming van de privacy van de gebruiker. Voor onderzoekers, het is om meer en betere differentieel private algoritmen te vinden, het verbeteren van de toolset waarmee we privacy-behoud van data-analyse mogelijk te maken.

  we hebben allemaal baat bij de invoering van privacygaranties en de successen van data-analyse. Om beide redenen kijken we uit naar meer organisaties die differentiële privacy omarmen.

  over de auteur

  Charlie Cabot is een senior Data scientist bij Privitar, een data privacy startup die high-performance software bouwt voor data anonimisering, inclusief perturbatie en generalisatie algoritmen en differentieel private mechanismen, om veilig gebruik van gevoelige datasets te vergemakkelijken. Charlie richt zich op aantoonbare privacygaranties en de statistische impact van anonimisering op analytics en Data science. Eerder werkte Charlie in cyber security en ontwikkelde machine learning-gedreven benaderingen van malware detectie en gemodelleerde cyberaanvallen op computernetwerken.