Differential Privacy und Anonymisierung in der Praxis: Ein Leitfaden für CSCI 4260/6260

Einführung in die differentielle Privatsphäre

In der heutigen datengetriebenen Welt, in der Unternehmen wie OpenAI oder Google riesige Datenmengen verarbeiten, wird der Schutz der Privatsphäre immer wichtiger. Die differentielle Privatsphäre (Differential Privacy) ist ein mathematisches Framework, das es ermöglicht, statistische Auswertungen durchzuführen, ohne die Privatsphäre einzelner Personen zu gefährden. Dieses Tutorial begleitet dich durch die Konzepte der Anonymisierung und differentiellen Privatsphäre, wie sie in der Assignment-Reihe CSCI 4260/6260 behandelt werden.

Grundlagen der Sensitivität von Abfragen

Die Sensitivität einer Abfragefunktion gibt an, wie stark sich das Ergebnis ändern kann, wenn ein Datensatz minimal verändert wird. Betrachten wir einen Datensatz D = {x1, x2, ..., xn} mit Werten aus U = {1, 2, ..., 100}.

Beispiel 1: Anzahl der Elemente größer als p

Die Funktion q(D) = |{x : x > p, x ∈ D}| zählt die Elemente über einem Schwellwert p. Unter der Subset-Definition (ein Datensatz ist eine Teilmenge des anderen) beträgt die Sensitivität 1, da das Hinzufügen oder Entfernen eines einzigen Elements die Zählung um maximal 1 ändert. Unter der Ersetzungsdefinition (ein Element wird ersetzt) beträgt die Sensitivität ebenfalls 1, da das Ersetzen eines Elements die Zählung um höchstens 1 verändern kann. Ein maximales Beispiel: D = {p+1} und D' = {p} (Subset) oder D = {p+1}, D' = {p} (Ersetzung).

Beispiel 2: Summe aller Elemente

Die Funktion q(D) = Σ xi hat unter der Subset-Definition eine Sensitivität von 100 (maximaler Wert, wenn ein Element hinzugefügt oder entfernt wird). Unter der Ersetzungsdefinition beträgt die Sensitivität 99 (Differenz zwischen 100 und 1).

Beispiel 3: Median

Für den Median bei ungeradem n und Ersetzungsdefinition hängt die Sensitivität von der Position des Medians ab. Im schlimmsten Fall kann der Median um bis zu 99 springen (z.B. D = {1, 1, ..., 1, 100} und D' = {1, 1, ..., 1, 1}).

Der Laplace-Mechanismus und Varianzanalyse

Der Laplace-Mechanismus fügt Rauschen hinzu, um differentielle Privatsphäre zu erreichen. Für eine Abfrage mit Sensitivität Δq wird das Rauschen aus einer Laplace-Verteilung mit Skala λ = Δq/ε gezogen. Die Varianz des Rauschens beträgt 2λ².

Unverzerrtheit und Varianz bei Budgetaufteilung

Der Mechanismus ist unverzerrt, da der Erwartungswert des Rauschens 0 ist. Wenn das gesamte Datenschutzbudget ε auf zwei Anfragen aufgeteilt wird, z.B. [ε/2, ε/2], dann haben die Rauschkomponenten jeweils Varianz 2*(2/ε)² = 8/ε². Die Summe R1+R2 hat dann Varianz 16/ε². Bei einer Aufteilung [ε/3, 2ε/3] haben wir Varianzen 2*(3/ε)² = 18/ε² für R1 und 2*(3/(2ε))² = 9/(2ε²) für R2. Die Summe hat Varianz 18/ε² + 9/(2ε²) = 45/(2ε²). Die Aufteilung [ε/2, ε/2] liefert eine geringere Varianz (16/ε² < 22.5/ε²) und damit bessere Nutzbarkeit.

Erstellung privater synthetischer Daten mittels Histogrammen

Ein gängiger Ansatz zur Generierung synthetischer Daten unter differentieller Privatsphäre ist die Verwendung von Histogrammen. Ein 2D-Histogramm unterteilt den Datenraum in ein Gitter und zählt die Anzahl der Beobachtungen pro Zelle.

Implementierung eines Histogramms

def construct_histogram(X, n_split):
    # X: 2D-Array (n, 2)
    # n_split: Anzahl Intervalle pro Dimension
    # Rückgabe: 1D-Array der Zellenzahlen
    bins = np.linspace(0, 1, n_split+1)
    hist, _, _ = np.histogram2d(X[:,0], X[:,1], bins=[bins, bins])
    return hist.flatten()

k-Anonymität durch Histogramme

Um k-Anonymität zu erreichen, können wir Zellen mit einer Anzahl kleiner als k zusammenfassen oder unterdrücken. Beispiel: Für k=5 fassen wir alle Zellen mit count < 5 zu einer Restkategorie zusammen. Die veröffentlichte Tabelle enthält dann nur Zellen mit count ≥ 5.

Freigabe des Histogramms mit Laplace-Mechanismus

Die Sensitivität eines Histogramms unter der Ersetzungsdefinition beträgt 2 (maximale Änderung einer Zelle um 1, aber insgesamt können zwei Zellen betroffen sein). Unter der Subset-Definition beträgt die Sensitivität 1 (nur eine Zelle ändert sich).

def release_histogram(hist, epsilon, sensitivity=2):
    noise = np.random.laplace(0, sensitivity/epsilon, size=hist.shape)
    return hist + noise

Fazit und Ausblick

Die differentielle Privatsphäre ist ein mächtiges Werkzeug, um datenschutzkonforme Analysen durchzuführen. Mit den vorgestellten Methoden – Sensitivitätsberechnung, Laplace-Mechanismus und Histogramm-basierte Synthese – kannst du selbstständig private Daten auswerten. Diese Techniken werden nicht nur in der Wissenschaft, sondern auch in der Industrie eingesetzt, z.B. bei Apple oder Meta, um Nutzerdaten zu schützen.