Differential Privacy sprang letztes Jahr von Forschungsarbeiten zu Schlagzeilen in den Tech-Nachrichten, als Apple VP of Engineering Craig Federighi in der WWDC-Keynote die Verwendung des Konzepts von Apple zum Schutz der Privatsphäre der Benutzer in iOS ankündigte.

Es war das jüngste Beispiel eines allgemeinen Trends: Benutzer und Ingenieure erwachten zur Bedeutung des Datenschutzes in Software. Hochkarätige Datenschutzverletzungen wie Ubers „God Mode“ haben in krassen Worten gezeigt, mit welcher Leichtigkeit Mitarbeiter eines Unternehmens sensible Daten ihrer Kunden missbrauchen können.

Die Menge an sensiblen Daten, die digital erfasst werden, nimmt rasant zu. Die Menschen verlassen sich heute mehr denn je auf digitale Dienste für Zahlungen, Transport, Navigation, Einkaufen und Gesundheit. Diese neue Datenerfassung schafft immer mehr Möglichkeiten, die Privatsphäre zu verletzen.

Aber es schafft auch aufregende Möglichkeiten — Transportnetze zu verbessern, Kriminalität zu reduzieren, Krankheiten zu heilen — wenn es den richtigen Datenwissenschaftlern und Forschern zur Verfügung gestellt wird. Es besteht eine natürliche Spannung zwischen dem Schutz der Privatsphäre von Personen im Datensatz und der Ermöglichung von Analysen, die zu einer besseren Welt führen könnten.Differentiell private Algorithmen sind eine vielversprechende technische Lösung, die diese Spannung lindern könnte und es Analysten ermöglicht, gutartige Aggregatanalysen durchzuführen und gleichzeitig einen sinnvollen Schutz der Privatsphäre jedes Einzelnen zu gewährleisten.

Dieses sich entwickelnde Technologiefeld ist in jedem System, das sensible Daten analysieren möchte, eine Überlegung wert. Obwohl die Differential Privacy Guarantee erst vor zehn Jahren konzipiert wurde, hat sie sich in Wissenschaft und Industrie bewährt. Forscher erfinden und verbessern schnell unterschiedlich private Algorithmen, von denen einige sowohl in Apples iOS als auch in Googles Chrome übernommen wurden.

Dieser Artikel beschreibt die historischen Faktoren, die zu Differential Privacy in seiner aktuellen Form führen, zusammen mit einer Definition von Differential Privacy und beispielhaft differentiell privaten Algorithmen. Anschließend werden einige aktuelle hochkarätige Implementierungen von differentiell privaten Algorithmen von Google, Apple und anderen untersucht.

Hintergrund

Differentiell private Algorithmen sind die neuesten in einem jahrzehntelangen Feld von Technologien zur datenschutzschonenden Datenanalyse. Zwei frühere Konzepte beeinflussten die differentielle Privatsphäre direkt:

1. Minimale Abfragesatzgröße
2. Dalenius’statistische Offenlegungsdefinition.

Wir werden diese zuerst erklären, da sie einen hilfreichen Hintergrund für die differenzielle Privatsphäre bieten.

Minimale Abfragesatzgröße Das erste Konzept ist eine minimale Abfragesatzgröße, die — wie differentiell private Algorithmen — darauf abzielt, die Sicherheit aggregierter Abfragen zu gewährleisten. Aggregierte Abfragen sind Abfragen, bei denen der zurückgegebene Wert für eine Teilmenge von Datensätzen in der Datenmenge berechnet wird, z. B. Zählungen, Durchschnittswerte oder Summen. Es kann hilfreich sein, aggregierte Abfragen als SQL-Abfragen zu betrachten, die mit „SELECT SUM“, „SELECT COUNT“ oder „SELECT AVG“ beginnen. Andere Arten von Aggregatabfragen umfassen Kontingenztabellen und Histogramme.

Eine minimale Abfragesatzgröße ist eine Einschränkung, die sicherstellen soll, dass aggregierte Abfragen keine Informationen über Personen preisgeben können. Bei einer konfigurierten Schwellennummer T wird sichergestellt, dass jede Aggregatabfrage für einen Satz von mindestens T Datensätzen durchgeführt wird. Eine minimale Abfragesatzgröße würde aggregierte Abfragen blockieren, die auf weniger als T Personen abzielen. Zum Beispiel, wenn T=2 , würde es Folgendes blockieren:

„SELECT AVG(salary) WHERE name = ‚Troy Brown‘;“.

weil diese Abfrage einen Durchschnitt über einen Datensatz durchführen würde (wir gehen davon aus, dass es nur einen Troy Brown gibt).

Die Verwendung von minimalen Abfragesatzgrößen verhindert bestimmte Angriffe, bietet jedoch keine Datenschutzgarantie und kann in der Praxis von erfahrenen Angreifern umgangen werden. Zum Beispiel könnte der Angreifer den obigen Angriff ausführen mit:

„SELECT SUM(salary);“.

„SELECT SUM(Gehalt) WHERE name != ‚Troy Brown‘;“.

Oder sogar, wenn wir Troy Browns Alter (45) und Position (WR) kennen, identifizieren Sie ihn eindeutig:

„SELECT SUM(salary) WHERE position = ‚WR‘;“.

„SUMME(Gehalt) AUSWÄHLEN, WOBEI Position = ‚WR‘ UND Alter!= 45;

Solche Angriffe werden Tracker-Angriffe genannt, und sie können nicht durch eine minimale Beschränkung der Abfragesatzgröße gestoppt werden. Aufgrund dieser Angriffe wurden minimale Abfragesatzgrößen als unzureichende Verteidigung zum Schutz von Abfragesystemen angesehen (siehe Dennings Arbeit). Etwas Besseres mit einer Garantie war erforderlich, um die Privatsphäre zu gewährleisten.

Dalenius’statistical Disclosure Definition

1977 schlug der Statistiker Tore Dalenius eine strenge Definition des Datenschutzes vor: dass der Angreifer nichts über eine Person erfahren sollte, die er vor der Verwendung des sensiblen Datensatzes nicht wusste. Obwohl diese Garantie fehlgeschlagen ist (und wir werden sehen, warum), ist es wichtig zu verstehen, warum Differential Privacy so konstruiert ist, wie es ist.Dalenius ‚Definition scheiterte, weil die Informatikerin Cynthia Dwork 2006 bewies, dass diese Garantie nicht gegeben werden konnte — mit anderen Worten, jeder Zugriff auf sensible Daten würde diese Definition von Privatsphäre verletzen. Das Problem, das sie fand, war, dass bestimmte Arten von Hintergrundinformationen immer zu einer neuen Schlussfolgerung über eine Person führen konnten. Ihr Beweis wird in der folgenden Anekdote veranschaulicht: Ich weiß, dass Alice zwei Zoll größer ist als die durchschnittliche Litauerin. Dann interagiere ich mit einem Datensatz litauischer Frauen und berechne die durchschnittliche Größe, was ich vorher nicht wusste. Ich kenne jetzt Alices Größe genau, obwohl sie nicht im Datensatz war. Es ist unmöglich, alle Arten von Hintergrundinformationen zu berücksichtigen, die aus der Verwendung eines Datensatzes zu einer neuen Schlussfolgerung über eine Person führen könnten.

Dwork schlug nach dem Nachweis des oben Genannten eine neue Definition vor: differenzielle Privatsphäre.

Was ist Differential Privacy?

Differential Privacy garantiert Folgendes: dass der Angreifer praktisch nichts mehr über eine Person lernen kann, als wenn der Datensatz dieser Person im Datensatz fehlen würde. Die Garantie ist zwar schwächer als Dalenius ‚Definition der Privatsphäre, aber stark genug, weil sie mit realen Anreizen übereinstimmt — Einzelpersonen haben keinen Anreiz, nicht an einem Datensatz teilzunehmen, da die Analysten dieses Datensatzes die gleichen Schlussfolgerungen über diese Person ziehen, ob die Person sich selbst in den Datensatz einbezieht oder nicht. Da ihre sensiblen persönlichen Daten in den Ausgaben des Systems fast irrelevant sind, können Benutzer sicher sein, dass die Organisation, die mit ihren Daten umgeht, ihre Privatsphäre nicht verletzt.Analysten, die „praktisch nichts mehr über ein Individuum“ lernen, bedeutet, dass sie auf eine unbedeutend kleine Änderung des Glaubens an ein Individuum beschränkt sind. (Hier und unten bezieht sich „Ändern“ auf den Wechsel zwischen der Verwendung eines Datensatzes und der Verwendung desselben Datensatzes abzüglich des Datensatzes einer Person.) Das Ausmaß dieser Änderung wird durch einen Parameter namens ϵ gesteuert, der die Grenze für die Änderung der Wahrscheinlichkeit eines Ergebnisses festlegt. Ein niedriger Wert von ϵ, wie 0,1, bedeutet, dass sich sehr wenig an den Überzeugungen eines Individuums ändern kann. Ein hoher Wert von ϵ, wie 50, bedeutet, dass sich Überzeugungen wesentlich stärker ändern können. Die formale Definition lautet wie folgt.

Ein Algorithmus A ist genau danndiffer-differentiell privat, wenn:

Pr ≤ e^ϵ * Pr

für alle x und für alle Paare von Datensätzen D, D‘ wobei D‘ D ist, wobei ein Datensatz — dh die Daten einer Person — fehlt. Das Symbol e bezieht sich auf die mathematische Konstante. Beachten Sie, dass diese Definition nur für randomisierte Algorithmen sinnvoll ist. Ein Algorithmus, der eine deterministische Ausgabe liefert, ist kein Kandidat für die differentielle Privatsphäre.Der primäre Reiz der Differential Privacy Guarantee ist die Begrenzung des Betrags, den jeder Analyst über eine Person erfahren kann. Darüber hinaus hat es die folgenden nützlichen Eigenschaften:

• Zusammensetzbarkeit: Wenn zwei Abfragen mit differentiellen Datenschutzgarantien der Ebenen ϵ1 und ϵ2 beantwortet werden, ist das Abfragepaar durch eine Garantie der Ebene (ϵ1 + ϵ2) abgedeckt. Denken Sie daran, dass ein höherer Wert von ϵ eine schwächere Garantie bedeutet.
• Stärke gegen beliebige Hintergrundinformationen: Die Garantie beruht in keiner Weise darauf, welche Hintergrundinformationen der Angreifer kennt. Diese Eigenschaft ist einer der Hauptgründe dafür, dass die differenzielle Privatsphäre stärker ist als eine frühere Datenschutzgarantie, k-Anonymität.
• Sicherheit bei der Nachbearbeitung: Es gibt keine Einschränkungen, was mit einem differentiell privaten Ergebnis gemacht werden kann – egal, womit es kombiniert oder wie es transformiert wird, es ist immer noch differentiell privat.

Wie wird diese Garantie in der Software erreicht? Differentiell private Algorithmen sind randomisierte Algorithmen, die Rauschen an Schlüsselpunkten innerhalb des Algorithmus hinzufügen. Einer der einfachsten Algorithmen ist der Laplace-Mechanismus, der Ergebnisse aggregierter Abfragen (z. B. Zählungen, Summen und Mittelwerte) nachverarbeiten kann, um sie differentiell privat zu machen. Unten finden Sie einen Beispiel-Java-Code für den Laplace-Mechanismus, der für Count-Abfragen spezifisch ist:

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

Die wichtigsten Teile dieser Funktion sind

1. Instanziieren Sie eine Laplace-Wahrscheinlichkeitsverteilung (siehe Abbildung 1), die bei 0 zentriert und um 1/ scaled skaliert ist. Wir verwenden die Apache Commons-Implementierung „LaplaceDistribution“, die mit zwei Argumenten erstellt wird: dem Mittelwert der Verteilung und dem Maßstab der Verteilung. Beachten Sie, dass ein niedrigeres Epsilon (mehr Privatsphäre) zu einem größeren Maßstab und damit zu einer breiteren Verteilung und mehr Rauschen führt.
2. Ziehen Sie eine Stichprobe aus dieser Verteilung. Diese sample() -Funktion verwendet eine Zufallszahl zwischen 0 und 1 und wendet die inverse kumulative Verteilungsfunktion (CDF) der Laplace-Verteilung auf diese Zahl an. Dieser Prozess führt zu einer Zufallszahl, so dass ihre Wahrscheinlichkeit, ein bestimmter Wert zu sein, mit der Verteilung übereinstimmt. Wenn diese Stichprobenfunktion eine Million Mal aufgerufen würde, um eine Million Stichproben zu erhalten, würde die Form des Histogramms dieser Stichproben der Form der Laplace-Verteilung sehr nahe kommen.
3. Stören Sie den realen Wert, indem Sie den Zufallswert aus Schritt 2 hinzufügen.

Betrachten wir, warum dieser Algorithmus differentiell privat ist, indem wir den Standpunkt eines Angreifers namens Eve einnehmen. Angenommen, es handelt sich bei dem Datensatz um Daten zur psychischen Gesundheit, und Eve hat sich einen Tracker-Angriff ausgedacht (siehe oben), der aufzeigt, ob ihr Ziel Bob wegen Alkoholismus beraten wird oder nicht. Wenn das Ergebnis der Abfrage 48 ist, weiß Eve, dass Bob Beratung erhält; Wenn es 47 ist, weiß Eve das Gegenteil.

Unabhängig davon, ob die Antwort 47 oder 48 lautet, gibt der Laplace-Mechanismus ein verrauschtes Ergebnis um 47 oder 48 zurück. Es kann 49, 46 oder sogar mit geringerer Wahrscheinlichkeit 44 oder 51 zurückgeben (siehe Abbildung 2 für ein Histogramm). In der Praxis ist es für Eva unmöglich, sehr sicher zu sein, ob die wahre Antwort 47 oder 48 war, und daher wird sich ihre Überzeugung, ob Bob in der Beratung für Alkoholismus ist oder nicht, nicht sinnvoll ändern.

Abbildung 1: Die Laplace-Verteilung zentriert bei 0 mit einer Skala von 1. Abgebildet ist die Wahrscheinlichkeitsdichtefunktion (PDF) der Verteilung — die y-Achse ist die relative Wahrscheinlichkeit, dass die Variable den Wert auf der x-Achse annimmt.

Abbildung 2: Die wahrscheinlichen Ergebnisse der Zählungsabfrage für die beiden Szenarien, in denen die tatsächliche Antwort 47 ist und wenn es 48 ist. Eine kleine Anzahl von Ausgaben würde nicht ausreichen, um zu unterscheiden, aus welcher Verteilung sie stammen. Epsilon ist auf 0,67 eingestellt.

Vielleicht haben Sie zu diesem Zeitpunkt bemerkt, dass Eve das Rauschen durchschneiden könnte, indem Sie die Abfrage viele Male wiederholen und sehen, ob sich die Antworten um 47 oder 48 gruppieren. Um diese Taktik zu verhindern, müssen differentiell private Systeme über ein „Datenschutzbudget“ verfügen, eine Obergrenze für die Summe der in jeder Abfrage verwendeten ϵ . Diese Obergrenze funktioniert aufgrund der oben beschriebenen Composability-Eigenschaft von Differential Privacy. Sie können ein paar relativ rauscharme Abfragen oder viele hundert rauschstarke Abfragen stellen, aber so oder so werden sie nicht in der Lage sein, sicher festzustellen, ob die wahre Antwort 47 oder 48 ist.Beachten Sie schließlich, dass der Laplace-Mechanismus für Zählungen lediglich ein einfacher differentiell privater Algorithmus ist. Der Laplace-Mechanismus kann erweitert werden, um für Summen und andere Aggregatabfragen zu arbeiten. Darüber hinaus gibt es grundsätzlich unterschiedliche Algorithmen, die nachweislich die Differential Privacy Garantie erfüllen. Einige, die es wert sind, erkundet zu werden, sind der private multiplikative Gewichtungsalgorithmus, der multiplikative Gewichtungsexponentialmechanismus und DualQuery.

Differential Privacy in Action

Im Juni 2016 gab Apple bekannt, dass es beginnen würde, differentiell private Algorithmen zu verwenden, um Verhaltensstatistiken von iPhones zu sammeln. Diese Ankündigung hat nicht nur zu einem enormen Anstieg des Interesses an differenzieller Privatsphäre geführt, sondern auch gezeigt, dass differenzielle Privatsphäre großen Unternehmen dabei helfen kann, neuen Wert aus Daten zu ziehen, die sie zuvor aufgrund von Datenschutzbedenken nicht berührt haben.Obwohl Apple bisher nur wenige Details veröffentlicht hat, scheint der im iPhone verwendete Algorithmus dem RAPPOR-Projekt von Google zu ähneln. Google hat eine Funktion in Chrome implementiert, die Verhaltensstatistiken von Chrome-Browsern über einen differentiell privaten randomisierten Antwortalgorithmus sammelt.

Bei der randomisierten Antwort wird den Statistiken zufälliges Rauschen hinzugefügt, bevor sie an den Collector gesendet werden. Wenn die reale Statistik beispielsweise 0 ist, ersetzt der Browser mit einiger Wahrscheinlichkeit 0 durch eine zufällig ausgewählte 0 oder 1. Jeder Benutzer kann den Wert, den seine Software meldet, in hohem Maße leugnen, da es sich um einen zufälligen Wert handeln kann. Insgesamt hebt sich das Signal jedoch vom Zufallsrauschen ab, und die Organisation, die die Statistiken sammelt (d. H. Google oder Apple), kann Trends genau beobachten.Interessanterweise haben unseres Wissens weder Google noch Apple den Wert von ϵ offenbart, der mit ihrer differenziellen Datenschutzgarantie einhergeht. Wir brauchen diesen Wert, um den Schutz zu verstehen, den die Garantie bietet. Wenn sie einen ausreichend hohen Wert von ϵ verwenden, können Analysten dennoch vertrauliche Fakten über Benutzer mit hoher Sicherheit erfahren. Ein niedriger Wert von ϵ ist für einen sinnvollen Datenschutz erforderlich.

Differentiell private Algorithmen wurden auch in datenschutzschonenden Analyseprodukten implementiert, wie sie beispielsweise von meinem Arbeitgeber Privitar entwickelt wurden. Mit diesen Produkten können Unternehmen, die mit wertvollen, sensiblen Daten arbeiten, differentiell private Algorithmen in ihre Datenarchitektur integrieren, ihren Benutzern Datenschutzgarantien bieten und gleichzeitig aussagekräftige Analysen der Daten durchführen.

Blick in die Zukunft

Sowohl die Ingenieur- als auch die Forschungsgemeinschaft haben Wege mit differenzieller Privatsphäre eingeschlagen. Für Ingenieure besteht die Aufgabe darin, sich über differenzielle Privatsphäre zu informieren und sicherzustellen, dass sie gegebenenfalls zum Schutz der Privatsphäre der Benutzer verwendet wird. Für Forscher geht es darum, mehr und bessere differentiell private Algorithmen zu finden und das Toolset zu verbessern, mit dem wir datenschutzschonende Datenanalysen ermöglichen können.

Wir alle profitieren von der Einführung von Datenschutzgarantien und den Erfolgen der Datenanalyse. Aus beiden Gründen freuen wir uns auf mehr Organisationen, die Differential Privacy nutzen.

Über den Autor

Charlie Cabot ist Senior Data Scientist bei Privitar, einem Datenschutz-Startup, das Hochleistungssoftware für die Datenanonymisierung entwickelt, einschließlich Störungs- und Generalisierungsalgorithmen und differentiell privaten Mechanismen, um die sichere Verwendung sensibler Datensätze zu erleichtern. Charlie konzentriert sich auf nachweisbare Datenschutzgarantien und die statistischen Auswirkungen der Anonymisierung auf Analytics und Data Science. Zuvor arbeitete Charlie in der Cybersicherheit und entwickelte maschinell lernende Ansätze zur Erkennung von Malware und modellierte Cyberangriffe auf Computernetzwerke.