Technisches Resümee: Dependency Triad (DT) zur Quantifizierung von Abhängigkeiten in der Local Differential Privacy

1. Problemstellung

Die Erhebung multidimensionaler Nutzerdaten unter Local Differential Privacy (LDP) steht vor einer kritischen Herausforderung: der Korrelationsbedingten Privacy-Leckage (Correlation-Induced Privacy Leakage, CPL). Während LDP-Mechanismen (z. B. $\epsilon$-LDP) die Leckage für einzelne Attribute begrenzen, können Abhängigkeiten zwischen Attributen unbeabsichtigt korrelierte Informationen offenlegen, was die Sicherheitsrisiken über das beabsichtigte Budget hinaus erhöht.

Bestehende Lösungen zur Quantifizierung von CPL leiden unter zwei primären Einschränkungen, die ihre praktische Anwendbarkeit behindern:

1. Skalierbarkeit und Mechanismus-Beschränkungen: Viele existierende Algorithmen (z. B. ITS, CBP, HCC-1/2, LTM) sind entweder auf spezifische LDP-Mechanismen (z. B. Two-Level-Perturbation) beschränkt oder leiden unter hoher Zeit- und Platzkomplexität (z. B. $O(a^2b^2)$ oder $O(a^2b \log b)$) relativ zu den Alphabetgrößen der Attribute ($a, b$). Dies macht sie für Attribute mit hoher Kardinalität oder iterative Kalibrierung des Privacy-Budgets unpraktikabel.
2. Abhängigkeit von Grundwahrheits-Verteilungen: Aktuelle Methoden setzen den Zugriff auf die exakte Grundwahrheits-Gemeinsame-Wahrscheinlichkeitsverteilung zwischen Attributen voraus. In realen LDP-Szenarien ist diese Verteilung selten bekannt; sie wird oft aus Vorab-Daten, öffentlichen Datensätzen oder Teilmengen der Population geschätzt. Diskrepanzen zwischen der bekannten Prior-Verteilung und der tatsächlichen Verteilung (aufgrund von demografischen Verschiebungen, Stichprobenfehlern oder Veralterung) können zu einer Unterschätzung der Leckage führen, was Sicherheitslücken schafft, oder zu einer Überschätzung, was den Datennutzen reduziert.

Das Paper postuliert, dass ein Metrik benötigt wird, die CPL in konstanter Zeit schätzen kann, kompatibel mit spärlichen (sparse) Verteilungen ist und robust gegenüber Verteilungsunsicherheit bleibt, ohne Kenntnis der Grundwahrheit zu erfordern.

2. Methodik: Die Dependency Triad (DT)

Die Autoren schlagen die Dependency Triad (DT) vor, eine neuartige Metrik, die die paarweisen Abhängigkeitsinformationen relevant für CPL mithilfe von drei Parametern zusammenfasst: $(\alpha, \beta, \delta)$.

A. Kernkonzept

Anstatt die vollständige $a \times b$ gemeinsame Verteilung zu speichern, komprimiert DT die Abhängigkeitsstruktur in drei Skalarparameter. Dies ermöglicht eine konstante Zeit-Schätzung ($O(1)$) von CPL für jedes Privacy-Budget $\epsilon$.

B. Ableitung der Parameter

Die Ableitung umfasst die Approximation der bedingten Wahrscheinlichkeitsvektoren $G$ und $G'$ (die $P(\hat{X}|X_k=x)$ und $P(\hat{X}|X_k=x')$ repräsentieren) durch deren elementweise Verhältnisse.

1. $\alpha$ (Obere Schranke der Verhältnisse): Repräsentiert das maximale Likelihood-Verhältnis und steuert das Leckageverhalten im Low-Privacy-Regime (großes $\epsilon$). Es ist definiert als:
   $$\alpha = \ln \left( \max_{\hat{x}, x, x'} \frac{p(\hat{x}|x) + \Delta_{\hat{x},x}}{p(\hat{x}|x') - \Delta_{\hat{x},x'}} \right)$$
   wobei $\Delta$ die Unsicherheitsmatrix darstellt.

2. $\delta$ (Sparsity-Korrektur): Berücksichtigt Fälle, in denen die Verteilung spärlich ist (d. h. Nenner werden Null). Es erfasst die Massenkonzentration in Grenzfällen, in denen $p(\hat{x}|x') = 0$.

3. $\beta$ (Kalibrierte untere Schranke): Ursprünglich wurde ein Parameter $\gamma$ (minimales Verhältnis) verwendet. Die Autoren stellten jedoch fest, dass $(\alpha, \gamma, \delta)$ zu Fehlern bei der Überschätzung führen können. Um die Genauigkeit zu verbessern und gleichzeitig eine konservative obere Schranke beizubehalten, führen sie einen Kalibrierungsschritt ein. $\beta$ wird durch Kalibrierung der unteren Schranke bei einem spezifischen Privacy-Budget $\epsilon_0$ (typischerweise $\epsilon_0 \to 0$) ermittelt, um die exakte CPL ($CPL^\star$) der bekannten Verteilung zu treffen. Dies stellt sicher, dass der Estimator eine enge obere Schranke für alle $\epsilon \geq \epsilon_0$ ist.

C. Umgang mit Verteilungsunsicherheit

Um das Fehlen von Grundwahrheitsdaten zu adressieren, bezieht DT explizit eine Unsicherheitsmenge $\Delta$ um die bekannte Verteilung $P_K$ ein. Die Parameter $(\hat{\alpha}, \hat{\beta}, \hat{\delta})$ werden durch Optimierung über den durch $P_K \pm \Delta$ definierten zulässigen Bereich berechnet. Dies stellt sicher, dass die resultierende CPL-Schätzung eine konservative obere Schranke ist, selbst wenn die tatsächliche Verteilung $P_A$ innerhalb der Unsicherheitsgrenzen von $P_K$ abweicht.

D. Algorithmen

• Algorithmus 1: Berechnet die $(\alpha, \beta, \delta)$-Parameter aus einer bekannten Verteilung und einer Unsicherheitsmatrix. Dies beinhaltet das Iterieren über Attributpaare und das Lösen eines relaxierten Linearen Programms (LP), um $\phi$ zu finden (verwendet für $\beta$), was zu einer Präkomplexität von $O(a^2b^{3.5})$ führt.
• Algorithmus 2: Schätzt die CPL unter Verwendung der vorberechneten DT-Parameter und des Privacy-Budgets $\epsilon$ in konstanter Zeit $O(1)$.

3. Zentrale Beiträge

1. Neuartige Metrik (DT): Die erste Metrik, die speziell darauf ausgelegt ist, paarweise Abhängigkeiten für die LDP-Leckageanalyse unter Verwendung von nur drei Parametern zusammenzufassen. Sie dient als konservativer Surrogat für die vollständige gemeinsame Verteilung.
2. Theoretische Garantien:
   • Obere Schranke: Die Autoren beweisen, dass der DT-basierte Estimator eine enge obere Schranke auf die wahre CPL ($CPL^\star$) ist, wodurch sichergestellt wird, dass die gemeldete Leckage den tatsächlichen Privacy-Verlust niemals unterschätzt.
   • Robustheit gegenüber Unsicherheit: Es wird bewiesen, dass die Metrik auch dann gültig und konservativ bleibt, wenn die Prior-Verteilung unsicher oder fehlerhaft ist.
   • Komplexität: Sie reduziert die Platzkomplexität von $O(ab)$ auf $O(1)$ und die Evaluierungszeit von polynomiell auf konstant.
3. Kalibrierungsmechanismus: Eine Methode zur Kalibrierung des Parameters $\beta$, um den Schätzfehler zu minimieren und gleichzeitig die Privacy-Garantie zu wahren, was die Genauigkeitslücken einfacher Verhältnis-Approximationen adressiert.
4. Empirische Validierung: Umfangreiche Experimente mit fünf realen Datensätzen (SPM, CelebA, Adult, CVD, DSS) und synthetischen Daten zeigen, dass DT konsistent die CPL mit einem sehr niedrigen Normalized Mean Square Error (NMSE < 0,025) über verschiedene Abhängigkeitsregime und Privacy-Budgets hinweg schätzt.

4. Experimentelle Ergebnisse

• Genauigkeit: DT erreicht im Vergleich zu den Baselines (wie HCC-2 und LTM) sehr geringe Schätzfehler gegenüber der optimalen $CPL^\star$ in realen Datensätzen. In High-Privacy-Regimen ($\epsilon \in (0, 1]$) ist der NMSE außergewöhnlich niedrig (< 0,003).
• Skalierbarkeit: Im Gegensatz zu Baselines, die für jedes Privacy-Budget eine Neuberechnung erfordern, ermöglicht DT eine schnelle Evaluierung. In einem Szenario zur Budget-Kalibrierung schloss DT die Aufgabe in 7 Sekunden ab, verglichen mit 61 Sekunden für die LTM-Baseline.
• Robustheit gegenüber Unsicherheit: Bei Tests mit Verteilungsverschiebungen (simuliert durch Variation der Fehlermargen bis zu 10 %–20 %) behielt DT eine enge obere Schranke auf die tatsächliche Leckage bei, während Methoden, die Unsicherheit ignorieren, das Risiko einer Unterschätzung trugen.
• Strukturelle Regime: DT funktionierte gut über verschiedene Abhängigkeitsstrukturen hinweg (Low-Entropy, Sparse, One-to-Many etc.). Es war extrem eng bei konzentrierten Abhängigkeiten und konservativ genau bei spärlichen oder Tail-sensitiven Verteilungen.
• Privacy-Utility-Trade-off: Bei Attribut-Inferenz-Angriffen und k-Marginal-Schätzaufgaben erreichte die DT-gestützte Budget-Kalibrierung einen vergleichbaren oder besseren Nutzen (niedrigerer Total Variation Distance) als Standard-Splitting (SPL) oder Random Sampling (RS) Methoden, insbesondere für höherwertige Marginals, während sie gleichzeitig eine robuste Resistenz gegen Inferenzangriffe beibielt.

5. Bedeutung und Ansprüche

Das Paper behauptet, dass die Dependency Triad (DT) die Lücke zwischen theoretischer Privacy-Analyse und praktischer Implementierung in multidimensionalen LDP-Settings schließt.

• Praktische Anwendbarkeit: Durch die Entfernung der Anforderung nach Grundwahrheits-Verteilungen und die Ermöglichung der Schätzung in konstanter Zeit macht DT eine rigorose CPL-Analyse für reale Datenerhebungspipelines mit unsicheren Verteilungen und hoher Dimensionalität praktikabel.
• Sicherheit: Die konservative Natur des Estimators stellt sicher, dass die Privacy-Garantien nicht durch Verteilungs-Mismatches gefährdet werden, was eine kritische Anforderung für den Einsatz von LDP in unvertrauenswürdigen Umgebungen ist.
• Effizienz: Die Fähigkeit zur Leckage-Schätzung in konstanter Zeit ermöglicht eine dynamische und iterative Kalibrierung des Privacy-Budgets, wodurch der Privacy-Utility-Trade-off optimiert wird, ohne prohibitive Rechenkosten zu verursachen.

Die Autoren kommen zu dem Schluss, dass DT zwar nicht die gesamte zugrunde liegende gemeinsame Verteilung vollständig charakterisiert, aber einen ausreichenden, handhabbaren und theoretisch fundierten Baustein zur Bewertung der gesamten Privacy-Leckage in multidimensionalen Settings bietet und damit die Skalierbarkeit und die Verfügbarkeitsbeschränkungen bestehender Methoden überwindet.