Differenzielle Privatsphäre

Differential Privacy ( DP ) ist ein mathematisch präziser Rahmen für die Veröffentlichung statistischer Informationen über Datensätze unter Wahrung der Privatsphäre einzelner Datensubjekte. Er ermöglicht es Dateninhabern, aggregierte Muster der Gruppe zu teilen und gleichzeitig die Offenlegung von Informationen über einzelne Personen einzuschränken. ^{[ 1 ] [ 2 ]} Dies geschieht durch das Einfügen sorgfältig kalibrierten Rauschens in statistische Berechnungen, sodass die Aussagekraft der Statistik erhalten bleibt, während die Rückschlüsse auf einzelne Personen im Datensatz nachweislich eingeschränkt werden.

Eine andere Möglichkeit, differentielle Privatsphäre zu beschreiben, ist als Einschränkung der Algorithmen, die zur Veröffentlichung aggregierter Informationen aus einer statistischen Datenbank verwendet werden. Diese Einschränkung begrenzt die Offenlegung privater Informationen einzelner Datensätze in der Datenbank. Beispielsweise nutzen einige Regierungsbehörden Algorithmen mit differentieller Privatsphäre, um demografische Daten oder andere statistische Aggregate zu veröffentlichen und gleichzeitig die Vertraulichkeit von Umfrageantworten zu gewährleisten. Unternehmen verwenden diese Algorithmen, um Informationen über das Nutzerverhalten zu sammeln und gleichzeitig zu kontrollieren, was selbst für interne Analysten sichtbar ist.

Grob gesagt ist ein Algorithmus differenziell privat, wenn ein Beobachter seiner Ausgabe nicht erkennen kann, ob die Informationen einer bestimmten Person in die Berechnung einbezogen wurden. Differenzielle Privatsphäre wird häufig im Zusammenhang mit der Identifizierung von Personen diskutiert, deren Informationen sich in einer Datenbank befinden könnten. Obwohl der Begriff nicht direkt auf Identifizierungs- und Reidentifizierungsangriffe Bezug nimmt, sind differenziell private Algorithmen nachweislich resistent gegen solche Angriffe. ^{[ 3 ]}

Der Artikel von Cynthia Dwork , Frank McSherry , Kobbi Nissim und Adam D. Smith aus dem Jahr 2006 ^{[ 3 ]} führte das Konzept der ε-Differential Privacy ein, eine mathematische Definition für den Datenschutzverlust, der mit der Veröffentlichung von Daten aus einer statistischen Datenbank verbunden ist . ^{[ 4 ]} (Hierbei bezeichnet der Begriff statistische Datenbank einen Datensatz, der unter Zusicherung der Vertraulichkeit zum Zweck der Erstellung von Statistiken erhoben wird, die durch ihre Erstellung die Privatsphäre derjenigen Personen, die die Daten bereitgestellt haben, nicht beeinträchtigen.)

Die Definition von ε-Differential Privacy erfordert, dass die Änderung eines einzelnen Datenbankeintrags die Wahrscheinlichkeitsverteilung der Messwerte aus Sicht eines Angreifers nur geringfügig verändert. ^{[ 3 ]} Die Definition von ε-Differential Privacy beruht auf der Annahme, dass die Privatsphäre einer Person durch die Veröffentlichung statistischer Daten nicht beeinträchtigt werden kann, solange sich ihre Daten nicht in der Datenbank befinden. ^{[ 5 ]} Bei Differential Privacy genießt jede Person annähernd denselben Datenschutz, als wären ihre Daten gelöscht worden. ^{[ 5 ]} Das heißt, die auf der Datenbank ausgeführten statistischen Funktionen sollten durch das Entfernen, Hinzufügen oder Ändern von Daten einer Person nicht wesentlich beeinträchtigt werden. ^{[ 5 ]}

Wie stark der Beitrag einer einzelnen Person zum Ergebnis einer Datenbankabfrage ist, hängt unter anderem davon ab, wie viele Personendaten in die Abfrage einbezogen sind. Enthält die Datenbank Daten einer einzelnen Person, trägt deren Daten zu 100 % bei. Enthält die Datenbank hingegen Daten von hundert Personen, trägt jede einzelne Person nur 1 % bei. Die zentrale Erkenntnis der differentiellen Privatsphäre besteht darin, dass dem Abfrageergebnis immer mehr Rauschen hinzugefügt werden muss, um denselben Grad an Privatsphäre zu gewährleisten, je weniger Personen die Abfrage umfasst. Daher auch der Titel der 2006 veröffentlichten Arbeit: „Calibrating Noise to Sensitivity in Private Data Analysis “ ^{[ 3 ] .}

Sei ε eine positive reelle Zahl und ein randomisierter Algorithmus , der einen Datensatz als Eingabe erhält (der die Aktionen der vertrauenswürdigen Partei repräsentiert, die die Daten besitzt). Sei das Bild von . ${\displaystyle {\mathcal {A}}}$${\displaystyle {\textrm {im}}\ {\mathcal {A}}}$${\displaystyle {\mathcal {A}}}$

Der Algorithmus bietet (ε, δ)-differenzielle Privatsphäre, wenn für alle Datensätze und , die sich in einem einzigen Element unterscheiden (d. h. den Daten einer Person), und für alle Teilmengen von : ${\displaystyle {\mathcal {A}}}$${\displaystyle D_{1}}$${\displaystyle D_{2}}$${\displaystyle S}$${\displaystyle {\textrm {im}}\ {\mathcal {A}}}$

$${\displaystyle \Pr[{\mathcal {A}}(D_{1})\in S]\leq e^{\varepsilon }\Pr[{\mathcal {A}}(D_{2})\in S]+\delta .}$$

Dabei wird die Wahrscheinlichkeit über die vom Algorithmus verwendete Zufälligkeit berechnet . ^{[ 6 ]} Diese Definition wird mitunter als „approximative differentielle Privatsphäre“ bezeichnet, wobei „reine differentielle Privatsphäre“ ein Spezialfall ist, wenn . Im letzteren Fall spricht man üblicherweise davon, dass der Algorithmus ε-differentielle Privatsphäre erfüllt (d. h. weglässt ). ${\displaystyle \delta =0}$${\displaystyle \delta =0}$

Differential Privacy bietet starke und robuste Garantien, die die modulare Entwicklung und Analyse von Differential Privacy-Mechanismen aufgrund ihrer Kompositionsfähigkeit , Robustheit gegenüber der Nachbearbeitung und sanften Verschlechterung bei Vorhandensein korrelierter Daten erleichtern .

Gemäß dieser Definition ist differentielle Privatsphäre eine Bedingung für den Veröffentlichungsmechanismus (d. h. die vertrauenswürdige Partei, die Informationen über den Datensatz freigibt) und nicht für den Datensatz selbst. Intuitiv bedeutet dies, dass sich ein gegebener Algorithmus mit differentieller Privatsphäre bei zwei ähnlichen Datensätzen annähernd gleich verhält. Die Definition gewährleistet weitgehend, dass die Anwesenheit oder Abwesenheit einer Person das Endergebnis des Algorithmus nicht wesentlich beeinflusst.

Nehmen wir beispielsweise an, wir haben eine Datenbank mit medizinischen Datensätzen, wobei jeder Datensatz ein Paar ( Name , X ) ist, wobei X ein boolescher Wert ist , der angibt, ob eine Person Diabetes hat oder nicht. Zum Beispiel: ${\displaystyle D_{1}}$${\displaystyle X}$

Angenommen, ein Angreifer möchte herausfinden, ob Chandler Diabetes hat oder nicht. Er weiß auch, in welcher Zeile der Datenbank sich Chandlers Eintrag befindet. Weiterhin darf der Angreifer nur eine bestimmte Abfrageform verwenden, die die Teilsumme der ersten Zeilen einer bestimmten Spalte in der Datenbank zurückgibt. Um Chandlers Diabetesstatus zu ermitteln, führt der Angreifer die Abfragen `chandler.diabetes.status` und `chandler.diabetes.status` aus und berechnet anschließend deren Differenz. In diesem Beispiel ist `chandler.diabetes.status` gleich 1, die Differenz beträgt also 1. Dies bedeutet, dass das Feld „Hat Diabetes“ in Chandlers Zeile den Wert 1 haben muss. Dieses Beispiel verdeutlicht, wie persönliche Daten kompromittiert werden können, selbst ohne explizit nach den Informationen einer bestimmten Person zu fragen. ${\displaystyle Q_{i}}$${\displaystyle i}$${\displaystyle X}$${\displaystyle Q_{5}(D_{1})}$${\displaystyle Q_{4}(D_{1})}$${\displaystyle Q_{5}(D_{1})=3}$${\displaystyle Q_{4}(D_{1})=2}$

Um dieses Beispiel fortzuführen: Wenn wir (Chandler, 1) durch (Chandler, 0) ersetzen, kann ein Angreifer die beiden Datensätze unterscheiden, indem er für jeden Datensatz berechnet . Müsste der Angreifer die Werte jedoch über einen -differenziell privaten Algorithmus erhalten, wäre er bei ausreichend kleinem nicht in der Lage, die beiden Datensätze zu unterscheiden.${\displaystyle D_{2}}$${\displaystyle D_{2}}$${\displaystyle D_{1}}$${\displaystyle Q_{5}-Q_{4}}$${\displaystyle Q_{i}}$${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$

Kompositionsfähigkeit bedeutet, dass die gemeinsame Verteilung der Ausgaben von (möglicherweise adaptiv gewählten) differentiell privaten Mechanismen die differentielle Privatsphäre erfüllt. ^{[ 3 ]}

• Sequenzielle Komposition. Wenn wir einen ε-Differential-Privacy-Mechanismus n-mal abfragen und die Randomisierung des Mechanismus für jede Abfrage unabhängig ist, dann ist das Ergebnis ε-differentiell privat. Im allgemeineren Fall, wenn unabhängige Mechanismen existieren, deren Datenschutzgarantien jeweils Differential Privacy sind, dann ist jede Funktion dieser Mechanismen ε-differentiell privat. ^{[ 7 ]}${\displaystyle t}$${\displaystyle \varepsilon t}$${\displaystyle n}$${\displaystyle {\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{n}}$${\displaystyle \varepsilon _{1},\dots ,\varepsilon _{n}}$${\displaystyle g}$${\displaystyle g({\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{n})}$${\displaystyle \left(\sum \limits _{i=1}^{n}\varepsilon _{i}\right)}$

• Parallele Komposition. Werden die vorherigen Mechanismen auf disjunkten Teilmengen der privaten Datenbank berechnet, so wäre die Funktion stattdessen -differentiell privat. ^{[ 7 ]}${\displaystyle g}$${\displaystyle (\max _{i}\varepsilon _{i})}$

Eine weitere wichtige Eigenschaft für die modulare Anwendung von Differential Privacy ist die Robustheit gegenüber der Nachbearbeitung. Dies bedeutet, dass für jede deterministische oder randomisierte Funktion, die über dem Bild des Mechanismus definiert ist , gilt: Wenn ε-Differential Privacy erfüllt, dann auch . ^{[ 3 ]}${\displaystyle F}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle F({\mathcal {A}})}$

Die Kompositionseigenschaft ermöglicht den modularen Aufbau und die Analyse differenziell privater Mechanismen ^{[ 3 ]} und motiviert das Konzept des Datenschutzverlustbudgets . Wenn alle Elemente, die auf sensible Daten eines komplexen Mechanismus zugreifen , einzeln differenziell privat sind, gilt dies auch für deren Kombination, gefolgt von beliebiger Nachbearbeitung. ^{[ 3 ]}

Im Allgemeinen dient ε-Differential Privacy dem Schutz der Privatsphäre benachbarter Datenbanken, die sich nur in einer Zeile unterscheiden. Das bedeutet, dass kein Angreifer mit beliebigen Zusatzinformationen wissen kann, ob ein bestimmter Teilnehmer seine Daten übermittelt hat. Dieses Prinzip ist jedoch erweiterbar. ^{[ 3 ]} Es kann wünschenswert sein, Datenbanken zu schützen , die sich in Zeilen unterscheiden. Dies würde bedeuten, dass ein Angreifer mit beliebigen Zusatzinformationen wüsste, ob bestimmte Teilnehmer ihre Daten übermittelt haben. Dies lässt sich erreichen, da die Wahrscheinlichkeitsdilatation bei Änderungen der Elemente durch anstatt durch begrenzt ist . [ ^{8 ] Das} heißt, für D₁ _und D₂ _, die sich in Elementen unterscheiden: Setzt man ε stattdessen auf , so erreicht man das gewünschte Ergebnis (Schutz der Elemente). ^{[ 3 ]} Anders ausgedrückt: Anstatt jedes Elements ε-differentiell privat zu schützen, ist nun jede Gruppe von Elementen ε-differentiell privat geschützt (und jedes Element ε- differentiell privat). ^{[ 3 ]}${\displaystyle c}$${\displaystyle c}$${\displaystyle c}$${\displaystyle \exp(\varepsilon c)}$${\displaystyle \exp(\varepsilon )}$${\displaystyle c}$$${\displaystyle \Pr[{\mathcal {A}}(D_{1})\in S]\leq \exp(\varepsilon c)\cdot \Pr[{\mathcal {A}}(D_{2})\in S]\,\!}$$${\displaystyle \varepsilon /c}$${\displaystyle c}$${\displaystyle c}$${\displaystyle (\varepsilon /c)}$

Man kann sich differentielle Privatsphäre als eine Begrenzung der Fehlerraten in einem Hypothesentest vorstellen. Betrachten wir zwei Hypothesen:

• ${\displaystyle H_{0}}$Die Daten der betreffenden Person sind nicht im Datensatz enthalten.

• ${\displaystyle H_{1}}$Die Daten der Person befinden sich im Datensatz.

Dann gibt es zwei Fehlerraten:

• Falsch-Positiv-Rate (FPR): ${\displaystyle P_{\text{FP}}=\Pr[{\text{Adversary guesses }}H_{1}\mid H_{0}{\text{ is true}}].}$

• Falsch-Negativ-Rate (FNR): ${\displaystyle P_{\text{FN}}=\Pr[{\text{Adversary guesses }}H_{0}\mid H_{1}{\text{ is true}}].}$

Idealer Schutz würde bedeuten, dass beide Fehlerraten gleich sind, aber für eine feste (ε, δ)-Einstellung kann ein Angreifer die folgenden Raten erreichen: ^{[ 9 ]}

• ${\displaystyle \{(P_{\text{FP}},P_{\text{FN}})\mid P_{\text{FP}}+e^{\varepsilon }P_{\text{FN}}\geq 1-\delta ,\ e^{\varepsilon }P_{\text{FP}}+P_{\text{FN}}\geq 1-\delta \}}$

Da differentielle Privatsphäre ein probabilistisches Konzept ist, ist jeder Mechanismus zur Gewährleistung differentieller Privatsphäre notwendigerweise randomisiert. Einige dieser Mechanismen, wie der unten beschriebene Laplace-Mechanismus, basieren auf dem Hinzufügen von kontrolliertem Rauschen zur zu berechnenden Funktion. Andere, wie der Exponentialmechanismus ^{[ 10 ]} und das Posterior-Sampling ^{[ 11 ],} ziehen stattdessen Stichproben aus einer problemabhängigen Familie von Verteilungen.

Eine wichtige Definition im Zusammenhang mit ε-differenziell privaten Mechanismen ist die Sensitivität. ^{[ 3 ]} Sei eine positive ganze Zahl, eine Menge von Datensätzen und eine Funktion. Die Sensitivität einer Funktion, bezeichnet mit , lässt sich wie folgt definieren: ^{[ 3 ]} Dabei wird das Maximum über alle Paare von Datensätzen und in gebildet, die sich in höchstens einem Element unterscheiden, und bezeichnet die L1-Norm . ^{[ 3 ]} Im unten stehenden Beispiel der medizinischen Datenbank ist die Sensitivität der Funktion gleich eins, wenn wir sie als Funktion betrachten , da die Änderung eines beliebigen Eintrags in der Datenbank den Funktionsausgang um null oder eins verändert. Dies lässt sich auf andere metrische Räume (Abstandsmaße) verallgemeinern und ist notwendig, damit bestimmte differenziell private Algorithmen funktionieren, beispielsweise das Hinzufügen von Rauschen aus der Gauß-Verteilung (was die L2-Norm erfordert ) anstelle der Laplace-Verteilung . ^{[ 3 ]}${\displaystyle d}$${\displaystyle {\mathcal {D}}}$${\displaystyle f\colon {\mathcal {D}}\rightarrow \mathbb {R} ^{d}}$${\displaystyle \Delta f}$$${\displaystyle \Delta f=\max \lVert f(D_{1})-f(D_{2})\rVert _{1},}$$${\displaystyle D_{1}}$${\displaystyle D_{2}}$${\displaystyle {\mathcal {D}}}$${\displaystyle \lVert \cdot \rVert _{1}}$${\displaystyle f}$${\displaystyle Q_{i}}$

Es gibt Techniken (die im Folgenden beschrieben werden), mit denen wir einen differenziell privaten Algorithmus für Funktionen erstellen können, dessen Parameter je nach ihrer Sensitivität variieren. ^{[ 3 ]}

Der Laplace-Mechanismus fügt Laplace-Rauschen hinzu (d. h. Rauschen aus der Laplace-Verteilung , das durch die Wahrscheinlichkeitsdichtefunktion mit Mittelwert Null und Standardabweichung ausgedrückt werden kann ). In unserem Fall definieren wir die Ausgabefunktion von als reellwertige Funktion (die sogenannte Transkriptausgabe von ), wobei und die ursprüngliche reellwertige Abfrage/Funktion ist, die wir auf der Datenbank ausführen wollten. Nun kann offensichtlich als stetige Zufallsvariable betrachtet werden, wobei ${\displaystyle {\text{noise}}(y)\propto \exp(-|y|/\lambda )\,\!}$${\displaystyle {\sqrt {2}}\lambda \,\!}$${\displaystyle {\mathcal {A}}\,\!}$${\displaystyle {\mathcal {A}}\,\!}$${\displaystyle {\mathcal {T}}_{\mathcal {A}}(x)=f(x)+Y\,\!}$${\displaystyle Y\sim {\text{Lap}}(\lambda )\,\!\,\!}$${\displaystyle f\,\!}$${\displaystyle {\mathcal {T}}_{\mathcal {A}}(x)\,\!}$

$${\displaystyle {\frac {\mathrm {pdf} ({\mathcal {T}}_{{\mathcal {A}},D_{1}}(x)=t)}{\mathrm {pdf} ({\mathcal {T}}_{{\mathcal {A}},D_{2}}(x)=t)}}={\frac {{\text{noise}}(t-f(D_{1}))}{{\text{noise}}(t-f(D_{2}))}}\,\!}$$

was höchstens ist . Wir können als Datenschutzfaktor betrachten . Daraus ergibt sich ein differenziell privater Mechanismus (wie aus der obigen Definition ersichtlich). Wenden wir dieses Konzept auf unser Diabetesbeispiel an, so folgt aus der oben hergeleiteten Tatsache, dass für einen -differenziell privaten Algorithmus gelten muss . Obwohl wir hier Laplace-Rauschen verwendet haben, können auch andere Rauschformen, wie z. B. Gaußsches Rauschen, eingesetzt werden. Diese erfordern jedoch möglicherweise eine leichte Lockerung der Definition von differentieller Privatsphäre. ^{[ 8 ]}${\displaystyle e^{\frac {|f(D_{1})-f(D_{2})|}{\lambda }}\leq e^{\frac {\Delta (f)}{\lambda }}\,\!}$${\displaystyle {\frac {\Delta (f)}{\lambda }}\,\!}$${\displaystyle \varepsilon \,\!}$${\displaystyle {\mathcal {T}}\,\!}$${\displaystyle {\mathcal {A}}\,\!}$${\displaystyle \varepsilon \,\!}$${\displaystyle \lambda =1/\varepsilon \,\!}$

Ein einfaches Beispiel, das insbesondere in den Sozialwissenschaften entwickelt wurde ^{[ 12 ]} , besteht darin, einer Person die Frage „Besitzen Sie das Attribut A ?“ zu stellen, und zwar nach folgendem Verfahren:

1. Wirf eine Münze .
2. Bei Kopf wirf die Münze erneut (das Ergebnis ignorierend) und beantworte die Frage ehrlich.
3. Bei Zahl werfen Sie die Münze erneut und antworten Sie mit „Ja“ bei Kopf und mit „Nein“ bei Zahl.

(Der scheinbar überflüssige zusätzliche Wurf im ersten Fall ist in Situationen erforderlich, in denen allein der Akt des Münzwurfs von anderen beobachtet werden kann, selbst wenn das tatsächliche Ergebnis geheim bleibt.) Die Vertraulichkeit ergibt sich dann aus der Widerlegbarkeit der einzelnen Antworten.

Insgesamt sind diese Daten mit vielen Antworten jedoch signifikant, da ein Viertel der positiven Antworten von Personen stammt, die das Merkmal A nicht besitzen , und drei Viertel von Personen, die es tatsächlich besitzen. Wenn p der wahre Anteil der Personen mit A ist , erwarten wir also (1/4)(1- p ) + (3/4) p = (1/4) + p /2 positive Antworten. Daher lässt sich p schätzen .

Insbesondere wenn das Attribut A gleichbedeutend mit illegalem Verhalten ist, dann ist die Antwort „Ja“ nicht strafbar, sofern die Person eine Wahrscheinlichkeit für eine Antwort „Ja“ hat, wie auch immer diese Wahrscheinlichkeit aussehen mag.

Obwohl dieses Beispiel, inspiriert von randomisierten Antworten , auf Mikrodaten anwendbar sein könnte (d. h. die Veröffentlichung von Datensätzen mit jeder einzelnen Antwort), schließt die differentielle Privatsphäre definitionsgemäß die Veröffentlichung von Mikrodaten aus und ist nur auf Abfragen anwendbar (d. h. die Aggregation einzelner Antworten zu einem Ergebnis), da dies die Anforderungen, insbesondere die plausible Abstreitbarkeit der Teilnahme einer Person, verletzen würde. ^{[ 13 ] [ 14 ]}

Eine Transformation heißt -stabil, wenn der Hamming-Abstand zwischen zwei beliebigen Datenbanken höchstens das -fache des Hamming-Abstands zwischen zwei beliebigen Datenbanken beträgt . Wenn ein Mechanismus -differenziell privat ist , dann ist auch der zusammengesetzte Mechanismus -differenziell privat. ^{[ 7 ]}${\displaystyle T}$${\displaystyle c}$${\displaystyle T(A)}$${\displaystyle T(B)}$${\displaystyle c}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A,B}$${\displaystyle M}$${\displaystyle \varepsilon }$${\displaystyle M\circ T}$${\displaystyle (\varepsilon \times c)}$

Dies ließe sich auf die Gruppenprivatsphäre verallgemeinern, da die Gruppengröße als Hamming-Distanz zwischen zwei Variablen betrachtet werden könnte (wobei die Variable die Gruppe enthält und die Variable nicht). In diesem Fall ist die Gruppe differentiell privat. ${\displaystyle h}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle M\circ T}$${\displaystyle (\varepsilon \times c\times h)}$

1977 formalisierte Tore Dalenius die Mathematik der Zellunterdrückung . ^{[ 15 ]} Der schwedische Statistiker Tore Dalenius leistete mit seiner 1977 veröffentlichten Arbeit einen wichtigen Beitrag zum Datenschutz in statistischen Datenbanken. Darin legte er dar, dass Datenbanken keine Informationen über Einzelpersonen preisgeben sollten, die nicht anderweitig zugänglich sind. ^{[ 16 ]} Er definierte außerdem eine Typologie für statistische Offenlegungen. ^{[ 4 ]}

1979 formalisierten Dorothy Denning , Peter J. Denning und Mayer D. Schwartz das Konzept des Trackers, eines Angreifers, der die vertraulichen Inhalte einer statistischen Datenbank durch gezielte Abfragen und das Speichern der Ergebnisse ermitteln kann. ^{[ 17 ]} Diese und nachfolgende Forschungen zeigten, dass die Datenschutzeigenschaften einer Datenbank nur dann gewahrt werden können, wenn jede neue Abfrage im Lichte (möglicherweise aller) vorherigen Abfragen betrachtet wird. Dieser Forschungszweig wird mitunter als Abfrage-Datenschutz bezeichnet. Das Endergebnis war, dass die Nachverfolgung der Auswirkungen einer Abfrage auf die Privatsphäre von Personen in der Datenbank NP-schwer ist .

Im Jahr 2003 zeigten Kobbi Nissim und Irit Dinur , dass es unmöglich ist, beliebige Abfragen an eine private statistische Datenbank zu veröffentlichen, ohne dabei private Informationen preiszugeben. Sie demonstrierten, dass der gesamte Informationsgehalt der Datenbank durch die Veröffentlichung der Ergebnisse einer überraschend geringen Anzahl zufälliger Abfragen – weit weniger als in früheren Arbeiten angenommen – offengelegt werden kann. ^{[ 18 ]} Dieses allgemeine Phänomen ist als das Fundamentale Gesetz der Informationswiederherstellung bekannt . Die zentrale Erkenntnis, dass im allgemeinsten Fall die Privatsphäre nicht ohne das Einbringen eines gewissen Maßes an Rauschen geschützt werden kann, führte zur Entwicklung der differentiellen Privatsphäre.

Im Jahr 2006 veröffentlichten Cynthia Dwork , Frank McSherry , Kobbi Nissim und Adam D. Smith einen Artikel ^{[ 3 ]} , in dem sie die Menge des hinzuzufügenden Rauschens formalisierten und einen allgemeinen Mechanismus dafür vorschlugen. Diese Arbeit lieferte auch die erste formale Definition von differentieller Privatsphäre. ^{[ 4 ] Ihre Arbeit wurde 2016 mit dem TCC Test-of-Time Award [ 19 ]} und 2017 mit dem Gödel-Preis ausgezeichnet . ^{[ 20 ]}

Seitdem haben nachfolgende Forschungen gezeigt, dass es viele Möglichkeiten gibt, aus der Datenbank sehr genaue Statistiken zu erstellen und gleichzeitig ein hohes Maß an Datenschutz zu gewährleisten . ^{[ 1 ]}

Bis heute gibt es über 12 reale Anwendungen von Differential Privacy , die bemerkenswertesten davon sind:

• 2008: US Census Bureau , zur Darstellung von Pendelmustern. ^{[ 21 ]}
• 2014: Googles RAPPOR, für Telemetriedaten wie Lernstatistiken über unerwünschte Software, die die Einstellungen von Nutzern manipuliert. ^{[ 22 ] [ 23 ]}
• 2015: Google, für die Bereitstellung historischer Verkehrsstatistiken. ^{[ 24 ]}
• 2016: Apple iOS 10 , zur Verwendung in intelligenten persönlichen Assistententechnologien. ^{[ 25 ]}
• 2017: Microsoft, für Telemetrie in Windows. ^{[ 26 ]}
• 2020: Social Science One und Facebook , ein Datensatz mit 55 Billionen Zellen, der Forschern Einblicke in Wahlen und Demokratie ermöglicht. ^{[ 27 ] [ 28 ]}
• 2021: Das US Census Bureau nutzt Differential Privacy, um Daten zur Wahlkreisneueinteilung aus der Volkszählung 2020 zu veröffentlichen. ^{[ 29 ]}

Im Hinblick auf die differentielle Privatsphäre sind mehrere Aspekte des öffentlichen Interesses zu berücksichtigen, insbesondere für politische Entscheidungsträger und politikorientierte Zielgruppen, die sich für die sozialen Chancen und Risiken der Technologie interessieren: ^{[ 30 ]}

• Datennutzen und -genauigkeit. Die Hauptsorge bei differenzieller Privatsphäre ist der Zielkonflikt zwischen Datennutzen und individueller Privatsphäre. Wird der Parameter für den Datenschutzverlust so eingestellt, dass der Nutzen im Vordergrund steht, sinkt der Nutzen für die Privatsphäre (weniger „Rauschen“ wird in das System eingespeist); wird er hingegen so eingestellt, dass ein hoher Datenschutz im Vordergrund steht, sinken Genauigkeit und Nutzen des Datensatzes (mehr „Rauschen“ wird in das System eingespeist). Entscheidungsträger sollten die mit differenzieller Privatsphäre verbundenen Zielkonflikte berücksichtigen, um geeignete Best Practices und Standards für die Anwendung dieser datenschutzfreundlichen Methode zu entwickeln, insbesondere angesichts der Vielfalt organisatorischer Anwendungsfälle. Es ist jedoch anzumerken, dass eine geringere Genauigkeit und ein geringerer Nutzen ein häufiges Problem aller statistischen Methoden zur Einschränkung der Datenweitergabe darstellen und nicht spezifisch für differenzielle Privatsphäre sind. Einzigartig ist hingegen, wie Entscheidungsträger, Forscher und Anwender die Risiken dieses Zielkonflikts minimieren können.
• Datenschutz und Datensicherheit. Differenzielle Privatsphäre bietet ein quantifiziertes Maß für den Datenschutzverlust und eine Obergrenze und ermöglicht es Datenverantwortlichen, den Kompromiss zwischen Datenschutz und Genauigkeit explizit festzulegen. Sie ist robust gegenüber noch unbekannten Datenschutzangriffen. Allerdings fördert sie einen verstärkten Datenaustausch , der bei unsachgemäßer Umsetzung das Datenschutzrisiko erhöht. Differenzielle Privatsphäre suggeriert zwar Datenschutz, dieser hängt jedoch stark vom gewählten Datenschutzverlustparameter ab und kann stattdessen ein trügerisches Sicherheitsgefühl erzeugen. Schließlich ist sie zwar robust gegenüber unvorhergesehenen zukünftigen Datenschutzangriffen, doch können Gegenmaßnahmen entwickelt werden, die wir nicht vorhersehen können.

Da Differential Privacy-Verfahren auf realen Computern implementiert werden, sind sie anfällig für verschiedene Angriffe, die sich nicht allein durch die mathematischen Grundlagen der Verfahren selbst kompensieren lassen. Zusätzlich zu den üblichen Softwarefehlern, die sich durch Tests oder Fuzzing identifizieren lassen , können Implementierungen von Differential Privacy-Mechanismen die folgenden Schwachstellen aufweisen:

• Subtile algorithmische oder analytische Fehler. ^{[ 31 ] [ 32 ]}
• Timing-Seitenkanalangriffe. ^{[ 33 ]} Im Gegensatz zu Timing-Angriffen gegen Implementierungen kryptografischer Algorithmen, die typischerweise eine geringe Leckrate aufweisen und mit einer nicht-trivialen Kryptoanalyse beantwortet werden müssen , kann ein Timing-Kanal zu einer katastrophalen Kompromittierung eines differenziell privaten Systems führen, da ein gezielter Angriff dazu genutzt werden kann, genau das Bit zu exfiltrieren, das das System zu verbergen versucht.
• Datenlecks durch Gleitkommaarithmetik . ^{[ 34 ]} Differential-private Algorithmen werden typischerweise in der Sprache der Wahrscheinlichkeitsverteilungen dargestellt, was naheliegend zu Implementierungen mit Gleitkommaarithmetik führt. Die Abstraktion der Gleitkommaarithmetik ist jedoch lückenhaft , und ohne sorgfältige Beachtung der Details kann eine naive Implementierung die differentielle Privatsphäre nicht gewährleisten. (Dies gilt insbesondere für ε-differentielle Privatsphäre, die selbst im ungünstigsten Fall keine Ausfallwahrscheinlichkeit zulässt.) Beispielsweise umfasst der Träger eines Standard-Samplers der Laplace-Verteilung (der beispielsweise für den Laplace-Mechanismus benötigt wird ) weniger als 80 % aller Gleitkommazahlen doppelter Genauigkeit ; darüber hinaus ist der Träger für Verteilungen mit unterschiedlichen Mittelwerten nicht identisch. Eine einzelne Stichprobe aus einer naiven Implementierung des Laplace-Mechanismus ermöglicht es, zwei benachbarte Datensätze mit einer Wahrscheinlichkeit von über 35 % zu unterscheiden.
• Zeitliche Schwankungen bei Gleitkommaarithmetik. ^{[ 35 ]} Im Gegensatz zu Operationen mit ganzen Zahlen, die auf modernen CPUs typischerweise in konstanter Zeit ausgeführt werden, weist die Gleitkommaarithmetik eine signifikante, eingabeabhängige Zeitvariabilität auf. ^{[ 36 ]} Die Verarbeitung von Subnormalzahlen kann besonders langsam sein, bis zu ×100 im Vergleich zum Normalfall. ^{[ 37 ]}

• Implementierungen von differenziell privaten Analysen – Einsatz von differenzieller Privatsphäre
• Quasi-Identifikator
• Exponentialmechanismus (differentielle Privatsphäre) – eine Technik zur Entwicklung differenziell privater Algorithmen
• k-Anonymität
• Differenziell private Analyse von Graphen
• Geschützte Gesundheitsdaten
• Lokale differentielle Privatsphäre
• Datenschutz
• Kompositionssätze für differentielle Privatsphäre

• Kalibrierung von Rauschen zur Sensitivität in der privaten Datenanalyse , Cynthia Dwork , Frank McSherry , Kobbi Nissim und Adam Smith. 2006. In: Proceedings of the Third conference on Theory of Cryptography (TCC’06). Springer-Verlag, Berlin, Heidelberg, S. 265–284. Kalibrierung von Rauschen zur Sensitivität in der privaten Datenanalyse (Dies ist die Originalveröffentlichung von Differential Privacy und nicht der gleichnamige Artikel von Dwork, der im selben Jahr veröffentlicht wurde.)
• Differential Privacy: Eine Übersicht der Ergebnisse von Cynthia Dwork, Microsoft Research, April 2008 (Präsentiert die Erkenntnisse aus den ersten zwei Jahren der Forschung zur Differential Privacy.)
• Differential Privacy: Eine Einführung für ein nicht-technisches Publikum , Alexandra Wood, Micah Altman , Aaron Bembenek, Mark Bun, Marco Gaboardi u. a., Vanderbilt Journal of Entertainment & Technology Law, Band 21, Ausgabe 1, Herbst 2018. (Ein gutes Einführungsdokument, aber definitiv *nicht* für ein nicht-technisches Publikum!)
• Technology Factsheet: Differential Privacy von Raina Gandhi und Amritha Jayanti, Belfer Center for Science and International Affairs, Herbst 2020
• Differential Privacy und die US-Volkszählung 2020 , MIT Case Studies in Social and Ethical Responsibilities of Computing, Nr. Winter 2022 (Januar). Differential Privacy und die US-Volkszählung 2020 .
• Garfinkel, Simson (2025). Differenzielle Privatsphäre . MIT Press Essential Knowledge. MIT Press. doi : 10.7551/mitpress/15354.001.0001 . ISBN 9780262551656Die
• Bowen, Claire McKay und Simson Garfinkel, Die Philosophie der differentiellen Privatsphäre , AMS Notices, November 2021.

• Eine praktische Einführung in die differentielle Privatsphäre von Christine Task, Purdue University, April 2012