Einführung

Dies ist eine interaktive Ergänzung zur Vorlesung "Datenschutz mit Ɛ-Differential Privacy". Aktuell ist dies kein eigenständiges Manuskript und nur in Kombination mit der Präsentation wirklich vollständig, die Inhalte werden jedoch kontinuierlich ausgebaut und verbessert.

Unsere Daten

Im folgenden nutzen wir Beispieldaten, die das Einkommen verschiedener Personen beschreiben. Wir untersuchen, wie das Hinzufügen eines einzelnen Datenpunktes dsa Ergebnis statistischer Analysen auf dem Datensatz verändert, und wie dies die Privatsphäre der Person gefährdet, der die zugefügten Daten gehören.

Im Folgenden repräsentieren wir einzelne Datensätze als einzelne Blöcke.

Datensatz $ D $

Der Datensatz $ D $ enthält alle Punkte aus Datensatz $ D ' $, bis auf einen einzigen der diesem hinzugefügt wird.

Datensatz $ D' $

Der Datensatz $ D' $ ist bis auf einen einzelnen hinzugefügten Datenpunkt identisch zum Datensatz $ D $. Diesen hinzugefügten Datenpunkt nennen wir im Folgenden Differenzpunkt.

Eine erste Statistik

Eine der einfachsten Erkenntnisse, die wir aus unseren Daten gewinnen können ist die Verteilung der Einkommen der Personen im Datensatz. Hierzu bilden wir zunächst Einkommensgruppen. Beispielsweise kann eine Gruppe alle Datensätze enthalten die ein Einkommen zwischen 50-60 T€ aufweisen. Anschließend zählen wir die Anzahl der Datensätze in jeder Gruppe, was der statistischen Häufigkeit dieser Gruppe entspricht.

wobei $ x _ i = 1 $ falls das Einkommen des Datenpunktes $ i $ im Bereich der Einkommen aus Gruppe $ g $ liegt $ [E^g _ \mathrm{min}, E^g _ \mathrm{max}] $, und $ x _ i = 0 $ andernfalls:

Umsetzung in Code

// Wir berechnen die Häufigkeiten in den Datensätzen D und D'
    const frequency = (d) => 
      d.filter(row => row.income >= incomeGroup.min
                   && row.income < incomeGroup.max).length

Ergebnis

Angriff auf die anonymisierten Daten

Ein Angreifer, der bis auf einen einzigen Wert $x _ j $ alle Datenwerte $x _ i$ kennt, kann aus dem Ergebnis $ X _ t $ leicht den fehlenden Wert $ x _ j $ berechnen:

Da die Beziehung zwischen dem Ausgabewert und den Eingabewerten deterministisch ist, kann der Angreifer mit 100 % Sicherheit vorhersagen, ob der hinzugefügte Datenpunkt im betrachteten Einkommensbereich liegt:

Hinzufügen von Rauschen

Um solche Angriffe zu erschweren, könnten wir dem wahren Ergebniswert $X _ t$ einen Zufallswert $n$ hinzufügen: $ X = X _ t + n $. Dies erschwert dem Angreifer die Schätzung des Ursprungswertes $ x _ j $, denn er/sie kennt den hinzugefügten Zufallswert $ n $ nicht:

Allerdings gibt es immer noch Randfälle, bei denen solche verrauschten Daten Ursprungswerte preisgeben können. Hierzu ein Beispiel: Wir fügen dem Ergebnis von oben einen zufälligen Wert im Bereich $[-3, 3]$ hinzu. Wir wiederholen dies und tragen die Häufigkeit der beobachteten Werte auf. Wie vorher markieren grüne Balken das Ergebnis für den Datensatz $D$, und rote Balken das Ergebnis für den Datensatz $D'$.

Fällt Ihnen hier ein Problem auf? Nein? Dann schauen Sie mal auf die Ränder der Häufigkeitsverteilung: Durch Hinzufügen des Differenz-Datensatzes verschiebt sich die Wahrscheinlichkeitsverteilung maximal um den Betrag 1 nach rechts (falls der Datenpunkt Teil der betrachteten Gruppe ist). D.h. beobachtet ein Angreifer den Wert ganz rechts, weiß er/sie sofort, dass der gesuchte Datenpunkt in der Gruppe sein muss, und hat damit das Einkommen der Person aufgedeckt. Warum? Schauen wir uns dazu die Häufigkeiten an:

Entscheidend für den Angreifer ist das Verhältnis der Wahrscheinlichkeiten der beobachteten Werte: Ist ein gegebener Wert in $ D $ und $ D' $ gleich wahrscheinlich, kann der Angreifer im Besten Fall nur raten, wie der Datenpunkt $ x _ j $ zu dem Ergebnis beigetragen hat. Je stärker jedoch das Verhältnis von einer von 1 abweicht, umso mehr Informationen liefert das beobachtete Ergebnis dem Angreifer. In dem obigen Fall beträgt die Wahrscheinlichkeit, dass ein Angreifer unsere Daten aufdeckt bei immerhin 25%!

Das heißt entscheidend für die Sicherheit unserer rauschbasierten Anonymisierung ist das minimale (oder maximale) Verhältnis der Wahrscheinlichkeiten für einen gegebenen Ergebniswert für die beiden Differenzdatensätze $ D $ und $ D' $:

Um den schlimmstmöglichen Fall zu finden, müssen wir dieses Wahrscheinlichkeitsverhältnis über alle möglichen Ergebnismengen betrachten:

Je höher der Wert $\alpha$, umso mehr Informationen kann ein Angreifer im schlimmsten Fall aus einem beobachteten Ergebniswert ableiten. In der Praxis schreiben wir zusätzlich $\alpha = \exp{\epsilon}$, da es uns dies ermöglicht, den Privatsphäre-Verlust auch für komplexere Fälle abzuschätzen. Oft wollen wir nämlich nicht nur eine Statistik veröffentlichen, sondern gleiche mehrere. Z.B. könnten wir zu unseren Einkommensdaten einen Mittelwert, die oben betrachteten Häufigkeiten sowie Quantilwerte veröffentlichen. Jeder einzelne Datenpunkt würde dann zu allen dieser Werte beitragen. Dementsprechend müssen wir nicht nur das Wahrscheinlichkeitsverhältnis für einzelne Werte, sondern für alle Werte zusammen betrachten um eine Abschätzung des Privatsphäre-Verlustes zu erhalten. Geht unser Datenpunkt z.B. in zwei unterschiedliche Werte $X$ und $Y$ ein, könnte ein Angreifer wiederum die Wahrscheinlichkeiten für Wertekombinationen $(X, Y)$ betrachten. Falls die Werte $X$ und $Y$ unabhängig sind, gilt für ihre Wahrscheinlichkeiten

, unter der Annahme, dass die beiden Wahrscheinlichkeitswerte jeweils DP mit Wert $\epsilon$ erfüllen. Für den Fall, dass die Werte $X$ und $Y$ nicht unabhängig sind, bleibt der Wert unter der Grenze (der Beweis hiervon ist allerdings etwas kompliziert). Der oben definierte Privatshpäre-Verlust ist somit additiv, was eine sehr nützliche Eigenschaft ist: Wissen wir, dass wir insgesamt $n$ Ergebnisse veröffentlichen wollen die auf einem Datenwert $x$ basieren, können wir den maximalen Privatsphäre-Verlust einfach als $n\cdot\epsilon$ abschätzen. Wir können somit ein Privatsphäre-Budget definieren, anhand dessen wir unsere Veröffentlichung planen können.

Beispiel: Geometrischer Mechanismus

Der geometrische Mechanismus fügt zu einem diskreten Ergebniswert einen Zufallswert hinzu, dessen Verteilung der geometrischen Verteilung folgt:

Diese Verteilung gilt für den Wertebereich $\mathbb{N}^0 = {1,2,3,\ldots}$. Die geometrische Verteilung kann auch zweiseitig sein, d.h. alle ganzzahligen Werte $\mathbb{N}$ definiert werden:

Der folgende Code-Schnipsel implementiert die beidseitige Funktion:

const geometricNoise = (epsilon, symmetric) => {
  let p = Math.exp(-epsilon)
  let pv = Math.random()
  if (symmetric){
    if (pv < (1-p)/(1+p)) {
      return 0
    }
  } else if (pv > p) {
    return 0
  }
  if (p < 1e-6) {
    return 0
  }
  pv = Math.random()
  let pe = 1.0 - p + p*pv
  let k = Math.floor(Math.log(1-pe)/Math.log(p))
  if (symmetric && Math.random() < 0.5) {
    return -k
  }
  return k
}

Epsilon

Ändern Sie den Wert von $ \epsilon $, um ein Gefühl dafür zu bekommen, wie der Parameter die Genauigkeit der Ergebniswerte und die Erfolgswahrscheinlichkeit eines Angreifers beeinflusst. Generell gilt: Je kleiner $ \epsilon $, um so geringer ist der potentielle Privatsphäre-Verlust für Betroffene, aber umso höher ist die Standardabweichung der resultierenden Daten.

Sensitivität

In unserem Beispiel oben hat das Hinzufügen eines Datenpunktes zu unserem Datensatz das Ergebnis maximal um einen Betrag von 1 verändert (da wir Häufigkeiten berechnet haben). Was aber, wenn wir eine Funktion berechnen möchten, bei der ein einzelner Datenpunkt einen größeren Effekt auf das Ergebnis hat? Beispielsweise könnten wir am Mittelwert interessiert sein, der sich berechnet als

wobei $e _ i$ das jeweilige Einkommen einer Person ist. Wie stark ein einzelner Datenpunkt für diese Funktion das Ergebnis beeinflussen kann, hängt zum einen von dem möglichen Wertebereich (hier also der möglichen Gehaltsspanne) ab, als auch von der Anzahl der Datenpunkte $N$. Ist $e _ \mathrm{max}$ das maximal zu betrachtende Gehalt beträgt die Sensitivität des Mittelwertes $\bar{E}$ daher annäherungsweise

\begin{equation} \delta f(\bar{E}) \approx \frac{e_\mathrm{max}}{N} - \ldots \end{equation}

Unser Datensatz hat Einträge. Legen wir ein maximales Einkommen von 100.000 € zu Grunde, beträgt die Sensitivität damit angenähert $\delta f(\bar{E}) = $ . Um den Mittelwert mithilfe von Differential Privacy zu schützen bräuchten wir eigentlich einen anderen Mechanismus, da der Wert reel ist und der geometrische Mechanismus nur auf diskrete Daten angewandt werden kann. Wir können jedoch den Mittelwert diskretisieren, um ihn mit dem Mechanismus verarbeiten zu können. Wählen wir das Diskretisierungsintervall identisch zur Sensitivität $\delta f$, brauchen wir unseren Mechanismus oben nicht zu modifizieren. Wollen wir eine größere Genauigkeit, müssen wir den Mechanismus entsprechend anpassen.

// Wir berechnen den Mittelwert der Einkommen
const mean = (d, min, max) => {
  if (d.length === 0)
    throw 'empty list received'
  let m = 0
  d.forEach(row => {
    if (row.income < min || row.income > max)
      throw 'out of bounds value detected'
    m += row.income
  })
  return m/d.length
}

Testen von DP-Mechanismen