Differential Privacy

Differential Privacy (englisch für ‚differentielle Privatsphäre‘) hat das Ziel, die Genauigkeit von Antworten zu Anfragen an Datenbanken zu maximieren, unter Minimierung der Wahrscheinlichkeit, die zur Beantwortung verwendeten Datensätze identifizieren zu können. Der Begriff fällt in den Bereich des sicheren, Privatsphären erhaltenden Veröffentlichens von sensiblen Informationen. Mechanismen, die Differential Privacy erfüllen, verhindern, dass Angreifer unterscheiden können, ob eine bestimmte Person in einer Datenbank enthalten ist oder nicht.

2017 erhielten Cynthia Dwork, Frank McSherry, Kobbi Nissim und Adam Davison Smith den Gödel-Preis und 2021 Avrim Blum, Irit Dinur, Cynthia Dwork, Frank McSherry, Adam Davison Smith und Kobbi Nissim den Paris-Kanellakis-Preis für die Entwicklung von Differential Privacy.

Situation

Man verwendet Differential Privacy im Kontext des Veröffentlichens von empfindlichen Informationen. Dabei möchte man zum einen allgemeine, statistische Informationen zugänglich machen, aber gleichzeitig die Privatsphäre einzelner Teilnehmer wahren.

Ein vorstellbares Szenario ist das Veröffentlichen von Patientendaten eines Krankenhauses, um Forschern zu ermöglichen, statistische Zusammenhänge aufzudecken. Dabei ist es notwendig, die Daten so zu bearbeiten, dass die einzelnen Patienten nicht identifizierbar sind. Für die Forschungszwecke ist es ausreichend, dass die statistischen Verteilungen in den veröffentlichten Daten denen der echten Daten entsprechen. Es spielt keine Rolle, ob einzelne Eigenschaften, wie etwa die Namen der Patienten, verändert wurden.

Motivation

Mit dem Aufkommen von Online Outsourcing und Cloud-Computing nimmt auch die Sensibilität für den Datenschutz in diesem Kontext zu. Die Kostenreduzierung und die Leistungssteigerung, die man sich vom Nutzen der neuen Technologien verspricht, gehen einher mit dem Verlust der Kontrolle über die Daten.

Während mit der Verschlüsselung ein Instrument etabliert ist, mit dem man Datenschutz effektiv gewährleisten kann, so wird dadurch auch die Verarbeitbarkeit der Daten eingeschränkt. Um auf verschlüsselten Daten Operationen auszuführen, werden wesentlich komplexere Algorithmen benötigt, die mit entsprechendem Zeitaufwand verbunden sind. Außerdem verhindert der Einsatz von Verschlüsselung eine uneingeschränkte Veröffentlichung.

Daher sucht man nach Verfahren, mit denen man Informationen unter Wahrung der Privatsphäre veröffentlichen kann, ohne die Daten zu verschlüsseln.

Differential Privacy verfolgt hierbei den Ansatz, Daten mit Rauschen zu versehen, um eindeutige Aussagen über bestimmte Eigenschaften der Daten unmöglich zu machen.

ε-Differential Privacy

Der ursprüngliche Begriff für Differential Privacy nutzt einen zentralen Parameter ε, um ein Maß für die Wahrung der Privatsphäre zu ermöglichen.

Definition

Eine randomisierte Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \kappa} liefert $\varepsilon$-Differential Privacy, falls für alle Datensätze $D_{1}$ und $D_{2}$, die sich in höchstens einem Eintrag unterscheiden, und alle Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle S\subseteq Range(\kappa )} gilt: $\Pr[\kappa (D_{1})\in S]\leq e^{\varepsilon }\times \Pr[\kappa (D_{2})\in S]$.

Mechanismen

Es gibt unterschiedliche Ansätze, die Forderungen von Differential Privacy in Mechanismen umzusetzen. Durch das Hinzufügen von Rauschen zu einem gegebenen Datensatz ist es möglich, die gewünschten Eigenschaften zu erhalten. Rauschen kann hierbei durch die Generierung neuer Einträge erreicht werden. Diese neuen Einträge, auch Dummys genannt, müssen gegenüber den ursprünglichen Daten ununterscheidbar sein, um den Anforderungen von Differential Privacy gerecht zu werden.

Schwächen

ε-Differential Privacy stellt hohe Anforderungen an Mechanismen, wodurch die Ergebnisse zum Teil stark an Nutzen verlieren. Wird zu viel Rauschen generiert und ist dieses zu unterschiedlich von den Ursprungsdaten, so wird der Informationsgehalt sehr eingeschränkt.

(ε,δ)-Differential Privacy

Da ε-Differential Privacy gewisse Einschränkungen bezüglich der Anwendbarkeit vorweist, entstand die Erweiterung (ε,δ)-Differential Privacy. Dieser Begriff erlaubt, dass Voraussetzungen bis zu einem gewissen Grad unerfüllt bleiben.

Definition

Für einen gegebenen randomisierten Mechanismus $M:D\rightarrow {\mathcal {R}}$ sagt man, dass M Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle (\varepsilon ,\delta )} -Differential Privacy erfüllt, falls für alle Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle D_{1},D_{2}\in D} mit Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle |D_{1}\triangle D_{2}|=1} und $R\subseteq {\mathcal {R}}$ die folgende Gleichung gilt: $\Pr[M(D_{1})\in R]\leq e^{\varepsilon }*\Pr[M(D_{2})\in R]+\delta$.

Probabilistische Definition

Für einen gegebenen randomisierten Mechanismus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M : D \rightarrow \mathcal{R}} und Konstanten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varepsilon > 0} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0 < \delta < 1} sagt man, dass M Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (\varepsilon, \delta)} -Probabilistic Differential Privacy erfüllt, falls man für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_1 \in D} den Wertebereich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{R}} in zwei Mengen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R, R' \subseteq \mathcal{R}} unterteilen kann, sodass Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \Pr[M(D_{1})\in R']\leq \delta } , und für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D_2 \in D} , so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |D_1 \triangle D_2| = 1} , und für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R \subseteq \mathcal{R}} die folgende Gleichung gilt: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Pr[M(D_1) \in R] \leq e^\varepsilon * \Pr[M(D_2) \in R]} .

Unterschiede zu ε-Differential Privacy

ε-Differential Privacy wurde um den Parameter δ erweitert. Damit ist es dem Mechanismus erlaubt, die Anforderungen bis zu einem gewissen Grad zu verletzen, der durch δ bestimmt ist.

Zusammensetzbarkeit

Differential Privacy besitzt die Eigenschaft der Zusammensetzbarkeit. Werden an einen Differential-Privacy-Mechanismus mit gegebenem ε eine Reihe von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t} Anfragen gestellt, und verwendet der Mechanismus für jede Verarbeitung eine unabhängige Zufallsquelle, so ergibt sich schließlich ein Ergebnis, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varepsilon * t} Differential Privacy vorweist.

Computational Differential Privacy

Differential Privacy ist ein statischer Begriff, welcher keine formellen Einschränkungen verlangt für die Mächtigkeit von Angreifern. Für die Anwendung in der Praxis jedoch ist es sinnvoll, gewisse Einschränkungen vorzunehmen. Etwa setzt die Verwendung von Verschlüsselung voraus, dass ein Angreifer nicht durch simples Anwenden von Versuch und Irrtum den privaten Schlüssel herausfinden kann.

Grundsätzlich gibt es zwei Arten, Computational Differential Privacy (CDP) zu erreichen. Zum einen ist es ausreichend, einfach die bestehende Definition von Differential Privacy um eine Beschränkung von Angreifern zu erweitern. Dieser Ansatz wird IND-CDP genannt. Daneben existiert auch der Begriff SIM-CDP, der eine Simulation der Sicht des Angreifers zugrunde legt.

Siehe auch

• K-Anonymität

Literatur

• Cynthia Dwork: Differential Privacy. In: 33rd International Colloquium on Automata, Languages and Programming, part II (ICALP 2006). Springer, Juli 2006, S. 1–12, doi:10.1007/11787006_1. 
• Cynthia Dwork, Frank McSherry, Kobbi Nissim, Adam Smith: Calibrating Noise to Sensitivity in Private Data Analysis. In: Shai Halevi, Tal Rabin (Hrsg.): Theory of Cryptography. Springer, 2006, ISBN 978-3-540-32731-8, S. 265–284, doi:10.1007/11681878_14. 
• Ilya Mironov, Omkant Pandey, Omer Reingold, Salil Vadhan: Computational Differential Privacy. In: Advances in Cryptology - CRYPTO 2009. Springer, August 2009, doi:10.1007/978-3-642-03356-8_8.