🤖 machine learning

How Well Can Differential Privacy Be Audited in One Run?

Diese Arbeit charakterisiert die maximale Wirksamkeit des Differential-Privacy-Audits in einem einzigen Durchlauf, identifiziert Interferenzen zwischen den beobachtbaren Effekten verschiedener Datenelemente als Hauptbarriere und schlägt neue konzeptionelle Ansätze vor, um diese zu minimieren und die Audit-Genauigkeit zu verbessern.

Ursprüngliche Autoren: Amit Keinan, Moshe Shenfeld, Katrina Ligett

Veröffentlicht 2026-02-23

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Amit Keinan, Moshe Shenfeld, Katrina Ligett

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Titel: Der Ein-Runde-Privatsphären-Test: Warum man nicht alles auf einmal erraten kann

Stellen Sie sich vor, Sie sind ein Sicherheitsprüfer für eine Maschine, die sensible Daten verarbeitet. Diese Maschine soll nach dem Prinzip des „Differential Privacy" (Differenziellen Privatsphären) arbeiten. Das bedeutet: Wenn Sie einen einzigen Datensatz (z. B. einen Namen) in die Maschine ändern, darf das Ergebnis der Maschine kaum anders aussehen. So soll verhindert werden, dass jemand aus dem Ergebnis auf den einzelnen Datensatz schließen kann.

Die Frage der Autoren dieses Papers ist: Wie gut können wir diese Maschine testen, ohne sie tausendfach zu starten?

Das Problem: Der „Ein-Runde-Test" (One-Run Auditing)

Normalerweise testen Sie eine solche Maschine, indem Sie sie tausendmal laufen lassen: einmal mit Person A, einmal mit Person B, und schauen, wie sehr sich die Ergebnisse unterscheiden. Das ist wie ein Marathon – sehr genau, aber extrem zeitaufwendig und teuer.

Die Forscher haben eine schnellere Methode entwickelt: den Ein-Runde-Test.

Die Idee: Sie nehmen eine große Gruppe von Testpersonen (z. B. 1000). Für jede Person legen Sie zwei Optionen auf den Tisch (z. B. „Roter Ball" oder „Blauer Ball").
Der Trick: Ein Zufallsgenerator entscheidet für jede Person, welcher Ball tatsächlich in die Maschine kommt. Die Maschine läuft ein einziges Mal mit dieser gemischten Gruppe.
Das Ziel: Der Prüfer schaut sich das Ergebnis an und versucht zu erraten: „Bei Person 1 war es der Rote Ball, bei Person 2 der Blaue..."

Wenn der Prüfer oft richtig liegt, ist die Maschine nicht privat genug. Wenn er nur zufällig rät (50/50), ist sie sicher.

Das große Hindernis: Das „Interferenz-Problem" (Die Störung)

Hier kommt das Hauptproblem ins Spiel, das die Autoren untersuchen. Stellen Sie sich vor, die Maschine ist ein riesiges Mischglas. Sie werfen 1000 Bälle hinein und rührt kräftig um. Am Ende kommt nur ein einziges, gemischtes Ergebnis heraus.

Wenn Sie versuchen zu erraten, welcher Ball von Person 1 war, stören sich die Bälle von Person 2 bis 1000 gegenseitig.

Die Analogie: Stellen Sie sich vor, Sie versuchen, in einem vollen, lauten Konzertsaal (der Maschine) die Stimme eines einzelnen Sängers (eines Datums) zu hören. Wenn alle anderen 999 Sänger auch singen, ist es unmöglich, die eine Stimme klar zu isolieren. Die Stimmen interferieren miteinander.

Das Paper zeigt: Je mehr Datenpunkte Sie gleichzeitig testen, desto mehr „Rauschen" entsteht. Der Prüfer kann nicht mehr genau sagen, welcher Ball von wem kam, weil die anderen Bälle das Ergebnis verfälschen.

Drei Arten von „Lücken" im Test

Die Autoren identifizieren drei Gründe, warum dieser schnelle Test manchmal versagt, selbst wenn die Maschine eigentlich unsicher ist:

Die „Schwächlinge"-Lücke: Die Maschine ist für die meisten Daten super sicher, aber für eine winzige Gruppe von Daten extrem unsicher. Da der Test aber alle Daten gleichzeitig prüft, wird dieser eine unsichere Fall von den vielen sicheren „überdeckt" und bleibt unentdeckt.
- Vergleich: Ein Schloss ist für 999 Türen unknackbar, aber für eine Tür ist es aus Pappe. Wenn Sie alle Türen gleichzeitig prüfen, merken Sie vielleicht nicht, dass eine davon aus Pappe ist.
Die „Glücksfall"-Lücke: Die Maschine ist nur selten unsicher. Meistens gibt sie ein harmloses Ergebnis, aber manchmal (sehr selten) gibt sie alle Daten preis. Da der Test nur einmal läuft, ist es sehr wahrscheinlich, dass er genau in den Moment fällt, in dem die Maschine harmlos ist.
- Vergleich: Ein Dieb stiehlt fast nie. Wenn Sie ihn nur einmal beobachten, werden Sie ihn wahrscheinlich nicht beim Diebstahl erwischen, auch wenn er ein Dieb ist.
Die „Interferenz"-Lücke (Die wichtigste): Wie oben beschrieben. Wenn die Maschine die Daten vermischt, kann der Prüfer die einzelnen Beiträge nicht trennen.
- Vergleich: Sie versuchen, das Rezept eines Kuchens zu erraten, indem Sie ihn probieren. Aber wenn 100 verschiedene Köche gleichzeitig Zutaten hineingeworfen haben, können Sie nicht mehr sagen, wer genau was hinzugefügt hat.

Die Lösung: Adaptive Tests und mehr Mut

Die Autoren schlagen neue Methoden vor, um diese Lücken zu schließen:

Adaptive Tests (AORA): Statt alle 1000 Personen gleichzeitig zu raten, darf der Prüfer schrittweise vorgehen.
- Die Idee: Der Prüfer schaut sich das Ergebnis an, errät die Person, bei der er sich am sichersten ist, und nutzt diese Information, um die nächste Person besser zu erraten.
- Vergleich: Es ist wie ein Detektiv, der nicht alle Verdächtigen auf einmal verhört, sondern den ersten verhört, dessen Aussage ihm hilft, den zweiten zu überführen, und so weiter. Durch dieses „Wissen über die anderen" wird das Rauschen reduziert.
Mehr Daten pro „Kanal": Sie können auch versuchen, mehrere Testpersonen auf denselben „Kanal" der Maschine zu legen. Das Paper zeigt, dass man durch geschickte Kombination von Datenpunkten die Interferenz überlisten kann, solange man nicht zu viele auf einmal packt.

Fazit für den Alltag

Dieses Paper sagt uns im Grunde: Schnelle Tests sind toll, aber sie haben Grenzen.

Wenn Sie eine KI auf Privatsphäre testen wollen, indem Sie sie nur einmal laufen lassen, müssen Sie vorsichtig sein. Wenn die KI Daten stark vermischt (Interferenz), wird der Test oft schwache Ergebnisse liefern, selbst wenn die KI eigentlich unsicher ist.

Die Autoren zeigen uns jedoch, wie wir diesen Test cleverer machen können: Indem wir den Prüfer nicht blind raten lassen, sondern ihm erlauben, seine bisherigen Erfolge zu nutzen, um die nächsten Raten zu verbessern. So können wir auch mit wenigen Versuchen herausfinden, ob eine Maschine wirklich sicher ist oder ob sie doch ein paar Risse hat.

Kurz gesagt: Man kann nicht alles auf einmal perfekt sehen, aber mit dem richtigen Werkzeug (Adaptivität) kann man die Schwachstellen trotzdem finden, ohne den ganzen Laden abzureißen.

1. Problemstellung

Differential Privacy (DP) ist der Standard zum Schutz von Trainingsdaten in maschinellen Lernverfahren. Obwohl theoretische Obergrenzen für die Privatsphäre-Parameter ( $\varepsilon$ ) bereitgestellt werden, können diese in der Praxis zu locker sein oder durch Implementierungsfehler ungültig werden. Daher gewinnt das Privacy Auditing (Überprüfung) an Bedeutung, um empirische Untergrenzen für die tatsächliche Privatsphäre zu ermitteln.

Traditionelle Auditing-Methoden („Classic Auditing") vergleichen die Ausgabealgorithmen auf benachbarten Datensätzen (die sich in einem Eintrag unterscheiden) über viele Wiederholungen. Dies ist jedoch rechnerisch extrem aufwendig.
One-Run Auditing (ORA), eingeführt von Steinke et al. [1], versucht dies zu optimieren, indem es einmalig mehrere Einträge im Trainingsdatensatz gleichzeitig manipuliert und eine einzige Trainingsdurchführung nutzt, um die Privatsphäre zu schätzen.

Das Kernproblem: Während ORA als valide (d.h. die geschätzten Grenzen sind sicher) erwiesen wurde, ist unklar, wie präzise diese Methode ist. Kann ORA die wahren Privatsphäre-Parameter eines Algorithmus asymptotisch genau erfassen, oder gibt es fundamentale Lücken, die die Genauigkeit begrenzen, selbst bei optimaler Wahl der Audit-Strategie?

2. Methodik und theoretischer Rahmen

Die Autoren analysieren ORA im Rahmen eines Rätsel-Spiels (Guessing Game):

Ein Auditor wählt für jeden der $n$ Datensatzeinträge ein Paar von Optionen $(x_i, y_i)$ .
Ein zufälliger Bitvektor $S$ bestimmt, welche Option tatsächlich im Datensatz verwendet wird.
Der Algorithmus $M$ wird einmal auf diesem Datensatz ausgeführt.
Ein „Guesser" versucht basierend auf der Ausgabe von $M$ zu erraten, welche Bits in $S$ gesetzt waren.
Die Effektivität wird durch das Verhältnis von korrekten zu getätigten Vermutungen gemessen.

Die Autoren führen den Begriff der Effizienz (Efficacy) ein, definiert als die erwartete Genauigkeit des Guessers. Sie zeigen, dass die asymptotische Schärfe (Tightness) von ORA direkt mit dieser Effizienz verknüpft ist.

Um die Grenzen von ORA zu verstehen, definieren die Autoren drei fundamentale Lücken (Gaps), die zwischen der ORA-Effizienz und dem wahren DP-Parameter $\varepsilon(M)$ bestehen:

Non-worst-case Privacy for Elements: DP schützt den schlimmsten Eintrag. ORA muss jedoch oft Vermutungen über Einträge treffen, die nicht den Worst-Case-Verlust erfahren. Wenn nur ein kleiner Teil der Daten schlecht geschützt ist, sinkt die durchschnittliche Trefferquote des Auditors.
Non-worst-case Outputs: DP betrachtet den Worst-Case über alle möglichen Ausgaben. ORA führt den Algorithmus jedoch nur einmal aus. Wenn die spezifische Ausgabe, die generiert wird, nicht den Worst-Case darstellt (z.B. bei seltenen „schlechten" Ereignissen), kann der Auditor die volle Privatsphäre nicht erkennen.
Interference (Interferenz): Dies ist die zentrale Innovation der Arbeit. Bei ORA werden viele Einträge gleichzeitig auditiert. Wenn die Ausgabe des Algorithmus eine Aggregation mehrerer Eingaben ist (z.B. Summe oder XOR), ist die Unsicherheit über die anderen Einträge für den Auditor hoch. Der Auditor kennt den Kontext nicht vollständig, was die Unterscheidbarkeit einzelner Einträge verschlechtert.

Die Autoren formalisieren diese Lücken durch neue privacy-ähnliche Konzepte:

Distributional Differential Privacy (DDP): Berücksichtigt die Verteilung der Daten.
Average-Case DDP (AC-DDP): Mittelt über die Ausgaben.
Average-Element AC-DDP (AE-AC-DDP): Mittelt über die Elemente.
Sie beweisen, dass die optimale Effizienz von ORA genau durch diese relaxierten Konzepte begrenzt ist.

3. Wichtige Beiträge

Charakterisierung der fundamentalen Grenzen: Die Autoren beweisen, dass ORA für bestimmte Algorithmen nicht asymptotisch scharf ist, selbst mit dem besten möglichen Auditor. Sie identifizieren die drei oben genannten Lücken als die exakten Ursachen für diese Unschärfe.
Theoretische Charakterisierung der Schärfe:
- Sie geben eine notwendige und hinreichende Bedingung für die asymptotische Schärfe von ORA: Ein Algorithmus kann in einem Durchlauf genau auditiert werden, wenn eine unbegrenzte Anzahl von Elementen einen Verteilungs-Privatsphäre-Verlust nahe am Worst-Case $\varepsilon(M)$ aufweist, der isoliert betrachtet werden kann.
- Für lokale Algorithmen (die jeden Eintrag separat verarbeiten) ist ORA asymptotisch scharf.
Analyse von DP-SGD als Fallstudie:
- DP-SGD (Differentially Private Stochastic Gradient Descent) aggregiert Gradienten, was zu massiver Interferenz führt.
- Die Autoren zeigen, dass der klassische Ansatz von Steinke et al., bei dem pro Koordinatenachse nur ein Audit-Element verwendet wird, suboptimal ist.
- Sie demonstrieren, dass das Zuweisen mehrerer Audit-Elemente pro Koordinatenachse die Effizienz steigern kann, da mehr Vermutungen möglich sind, obwohl dies die Interferenz erhöht. Es gibt einen optimalen Trade-off.
Einführung von Adaptive ORA (AORA):
- Um das Problem der Interferenz zu lösen, schlagen sie Adaptive ORA vor.
- Beim AORA darf der Auditor die wahren Werte der bereits geratenen Elemente nutzen, um die Vermutungen für die verbleibenden Elemente zu verbessern.
- Dies reduziert die Unsicherheit über den Kontext erheblich. Die Autoren beweisen, dass AORA weiterhin valide ist (die statistischen Garantien bleiben erhalten) und die Effizienz signifikant steigert.
- Bei Algorithmen wie „XOR-in-Pairs" ist ORA völlig wirkungslos (Effizienz = 0,5), während AORA perfekte Effizienz erreicht.

4. Ergebnisse

Theoretische Ergebnisse:
- Für den XOR-Algorithmus (der alle Eingaben XORt) ist die optimale Effizienz von ORA $1/2$ (reines Raten), obwohl der Algorithmus keine DP erfüllt. AORA hingegen kann XOR perfekt auditierten.
- Für Count-In-Sets (eine vereinfachte Version von DP-SGD) zeigen sie, dass ORA asymptotisch scharf ist, solange die Gruppengröße $s(n)$ langsamer als $\log(n)$ wächst.
- Für DP-SGD zeigen Experimente, dass die Verwendung mehrerer Elemente pro Koordinatenachse die geschätzten $\varepsilon$ -Grenzen verbessert, aber nur bis zu einem Punkt, an dem die Interferenz überwiegt.
Experimentelle Ergebnisse:
- In Experimenten mit DP-SGD ( $d=1000$ , $T=100$ ) zeigte sich, dass AORA deutlich engere (bessere) Untergrenzen für $\varepsilon$ liefert als ORA.
- Während die ORA-Grenzen bei mehr als 5 Elementen pro Koordinate abnehmen (wegen Interferenz), profitieren AORA-Grenzen weiter von zusätzlichen Elementen, da der adaptive Guessing-Prozess die Interferenz kompensiert.
- Die Studie bestätigt, dass die Wahl der Audit-Datensätze und die Anzahl der getätigten Vermutungen (Abstentions-Strategie) kritisch für die Genauigkeit sind.

5. Bedeutung und Fazit

Diese Arbeit liefert das erste vollständige theoretische Verständnis dafür, wie gut Differential Privacy in einem einzigen Trainingslauf auditiert werden kann.

Kritische Einsicht: One-Run Auditing ist nicht universell scharf. Es gibt fundamentale Lücken, die durch die Interferenz zwischen gleichzeitig auditierten Datenpunkten entstehen. Dies bedeutet, dass ein „schlechter" ORA-Ergebnis nicht unbedingt auf einen fehlerhaften Algorithmus hindeutet, sondern auf die inhärenten Grenzen der Methode.
Praktische Implikationen: Die Autoren warnen davor, ORA-Ergebnisse unkritisch als „Beweis" für gute Privatsphäre zu verwenden, wenn die Algorithmen stark aggregieren.
Lösungsansatz: Die vorgeschlagene Adaptive ORA (AORA) ist ein wichtiger methodischer Fortschritt. Sie ermöglicht es, die Interferenz-Lücke zu überwinden, indem sie den Auditor mit mehr Kontextinformationen versorgt, ohne die mathematische Validität der Audit-Ergebnisse zu gefährden.

Zusammenfassend zeigt das Paper, dass effizientes Auditing möglich ist, aber nur durch sorgfältige Anpassung der Strategie (z.B. adaptive Guessing, optimierte Verteilung der Audit-Elemente) die theoretischen Grenzen der Privatsphäre-Parameter tatsächlich angenähert werden können.