📊 statistics

A Maximum Entropy Implementation of Differential Privacy Under Linear Invariants

Dieses Paper schlägt eine High-Entropy-Implementierung der Differential Privacy vor, die obligatorische lineare Aggregationsinvarianten (wie etwa Zustandsgesamtsummen) mit nahezu absoluter Sicherheit erfüllt, während sie gleichzeitig neue Privatsphäre-Garantien herleitet und theoretische Fragen bezüglich des Nullraums von Korrelationsmatrizen adressiert.

Ursprüngliche Autoren: Ryan Lafferty, Anindya Roy

Veröffentlicht 2026-07-27

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Ryan Lafferty, Anindya Roy

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

Stellen Sie sich vor, Sie sind ein Bibliothekar, der versucht, eine geheime Liste der Buchleiher mit der Öffentlichkeit zu teilen, aber Sie haben ein strenges Versprechen: Sie dürfen niemals verraten, wer ein bestimmtes Buch ausgeliehen hat. Um dieses Versprechen einzuhalten, beschließen Sie, ein wenig „Rauschen“ oder „Statik“ zur Liste hinzuzufügen, wie zum Beispiel ein paar zufällige Namen, die eigentlich gar nicht da waren, oder einige Namen leicht zu verändern. Dies ist der Kern der Idee der Differential Privacy, eines mathematischen Schutzschildes, den Regierungen und Tech-Giganten verwenden, um aus Daten lernen zu können, ohne Einzelpersonen preiszugeben.

Es gibt jedoch einen Haken: Manchmal verlangen die Regeln des Spiels, dass bestimmte übergeordnete Zahlen exakt gleich bleiben. Beispielsweise muss die Gesamtzahl der Menschen in einem Bundesstaat der Summe der Menschen in all seinen Landkreisen entsprechen. Wenn Sie einfach nur zufälliges Rauschen in jeden einzelnen Landkreis hinzufügen, wird die Gesamtsumme des Bundesstaates wahrscheinlich abweichen, was die Mathematik unbrauchbar für offizielle Aufzeichnungen macht. Dies erzeugt ein Tauziehen: Sie wollen genug Rauschen hinzufügen, um Individuen zu verbergen, aber das Rauschen muss sich so perfekt gegenseitig aufheben, dass die großen Gesamtsummen unberührt bleiben. Dieses Paper befasst sich mit der kniffligen Mathematik, wie man dieses „perfekt ausgleichende“ Rauschen hinzufügt, ohne den Datenschutzschild zu brechen.

Das Rätsel des perfekt ausbalancierten Rauschens

Stellen Sie sich vor, Sie sind ein Koch, der versucht, einen Kuchen für einen sehr wählerischen Richter zu backen. Der Richter hat zwei Regeln:

Die Geschmacksregel: Jeder Bissen des Kuchens muss exakt nach einem bestimmten Aroma schmecken (sagen wir Vanille), um sicherzustellen, dass das Rezept eingehalten wird.
Die Gewichtregel: Das Gesamtgewicht des Kuchens muss exakt 1.000 Gramm betragen. Nicht mehr, nicht weniger.

Nun stellen Sie sich vor, Sie fügen dem Teig „Geheimzutaten“ (Rauschen) hinzu, um den Ursprung des Rezepts zu schützen. Wenn Sie einfach in jede Schüssel zufällig eine Handvoll Vanilleschoten streuen, wird das Gesamtgewicht des Kuchens wahrscheinlich falsch sein. Sie landen vielleicht bei 1.005 Gramm oder 990 Gramm. Wenn Sie versuchen, das Gewicht zu korrigieren, indem Sie einfach die überschüssigen Gramm von oben abziehen, ruinieren Sie die „Geschmacksregel“, weil die obere Schicht nun anders schmeckt als der Rest.

Dies ist genau das Problem, das die Autoren Ryan Lafferty und Anindya Roy lösen. In der Welt der Daten ist der „Kuchen“ eine Datenbank (wie der US-Zensus), die „Bissen“ sind einzelne Datenpunkte (wie die Anzahl der Personen in einer Nachbarschaft) und die „Geheimzutaten“ sind die Zufallszahlen, die hinzugefügt werden, um Identitäten zu schützen. Die „Gewichtregel“ repräsentiert lineare Invarianten – Einschränkungen wie „die Gesamtbevölkerung eines Bundesstaates muss der Summe seiner Landkreise entsprechen“.

Der alte Weg vs. der neue Weg

Zuvor versuchten Datenwissenschaftler, dies zu lösen, indem sie zuerst Rauschen hinzufügten und erst danach die Gesamtsummen „korrigierten“. Sie fügten jedem Landkreis Zufallszahlen hinzu, stellten fest, dass die Gesamtsumme des Bundesstaates nicht stimmte, und passten die Zahlen dann an, um die Summe wieder auf den korrekten Wert zu zwingen.

Die Autoren argumentieren, dass dieser „Fix-es-später“-Ansatz wie der Versuch ist, ein zerknittertes Blatt Papier glattzustreichen, indem man ein schweres Buch darauf presst. Es mag zwar glatt aussehen, aber das Papier ist nun zerdrückt und verzerrt. In mathematischen Begriffen „quetscht“ diese „Projektionsmethode“ das Rauschen in eine Ecke, wodurch es weniger zufällig (geringere Entropie) wird und potenziell die Datenschutzgarantien schwächt. Es ist, als ob das Rauschen vorhersehbar wird, was schlecht für den Datenschutz ist.

Die „Maximum-Entropy“-Lösung

Anstatt das Chaos im Nachhinein zu korrigieren, schlagen die Autoren einen klügeren Weg vor, die Zutaten von vornherein zu mischen. Sie haben eine Methode entwickelt, um Rauschen zu generieren, das korreliert ist.

Denken Sie an ein Team von Tänzern. Wenn jeder Tänzer sich zufällig bewegt, wirkt die Gruppe chaotisch, aber das Zentrum der Gruppe könnte vom Platz abtreiben. Wenn Sie wollen, dass die Gruppe an einem Ort bleibt (die Invariante), können Sie ihnen nicht einfach sagen, sie sollen aufhören, sich zu bewegen. Stattdessen choreografieren Sie sie so, dass, wenn ein Tänzer einen Schritt nach vorne macht, ein anderer mit genau demselben Betrag einen Schritt zurücktritt. Sie bewegen sich gemeinsam, aber ihre Bewegungen sind miteinander verknüpft, sodass die Gruppe an ihrem Platz bleibt.

Das Paper schlägt eine „Maximum-Entropy“-Implementierung vor. Vereinfacht gesagt ist „Entropie“ ein Maß für Zufälligkeit oder Überraschung. Die Autoren wollen, dass das Rauschen so unvorhersehbar und „überraschend“ wie möglich ist (hohe Entropie), während es gleichzeitig der Regel folgt, dass die Summe Null ergibt. Sie verwenden ein mathematisches Werkzeug namens Projected Gradient Descent (eine schicke Art zu sagen: „iteratives Anpassen der Tanzschritte“), um die perfekte Choreografie zu finden.

Sie verwenden auch eine Technik namens POCS (Projection onto Convex Sets), was wie ein Spiel von „Heiß und Kalt“ ist, bei dem man das Rauschen immer wieder anpasst, bis es perfekt in eine durch die Regeln definierte Form passt. Das Ergebnis ist ein Rausch-Vektor, der:

Wie das Standard-Rauschen aussieht, das wir für jeden einzelnen Datenpunkt erwarten (Gauß oder Laplace).
Jedes Mal exakt die Summe Null (oder die erforderliche Invariante) ergibt.
So zufällig wie mathematisch möglich ist, was den stärksten Datenschutz gewährleistet.

Was sie herausgefunden und bewiesen haben

Die Autoren haben nicht nur geraten, dass dies funktionieren könnte; sie haben es bewiesen.

Die Garantie: Sie haben gezeigt, dass dieses komplexe, verknüpfte Rauschen selbst mit diesem komplexen System immer noch die Standardgarantie der Differential Privacy (speziell $(\epsilon, \delta)$ -DP) bietet. Das bedeutet, dass der Datenschutzschild genauso stark ist wie bei den alten, einfacheren Methoden, obwohl das Rauschen nun auf eine koordinierte Weise „tanzt“.

Die mathematische Magie: Ein großer Teil ihrer Arbeit bestand darin, ein schwieriges Rätsel über Korrelationsmatrizen (mathematische Gitter, die beschreiben, wie Variablen miteinander in Beziehung stehen) zu lösen. Sie lieferten eine Teilaufgabe zu einer offenen Frage über den „Nullraum“ dieser Matrizen – sie haben im Wesentlichen herausgefunden, welche Muster von verknüpftem Rauschen überhaupt möglich sind.
Die Simulation: Sie haben ihre Methode mit simulierten Daten getestet, einschließlich eines Szenarios, das den US-Zensus mit Bundesstaaten, Landkreisen und Blöcken nachahmt. Sie zeigten, dass wenn sie Rauschen zu den kleinsten Blöcken hinzufügten, die Kreis- und Bundesstaat-Gesamtsummen perfekt intakt blieben, während die einzelnen Block-Zahlen immer noch ausreichend verschleiert waren, um die Privatsphäre zu schützen.

Warum es wichtig ist

Dies ist kein rein theoretisches Spiel. Das US Census Bureau und andere Behörden stehen jedes Mal vor genau diesem Problem, wenn sie Daten veröffentlichen. Sie haben verfassungsrechtliche Vorgaben, die besagen, dass die Gesamtsummen der Bundesstaaten nicht verändert werden dürfen, aber sie müssen gleichzeitig die Privatsphäre jedes einzelnen Menschen schützen.

Die Methode der Autoren bietet einen „prinzipiengeleiteten“ Weg, dies zu tun. Anstatt die Daten im Nachhinein zu manipulieren, bieten sie einen Weg, die Daten von Anfang an korrekt zu generieren. Sie merkten auch an, dass dieser Ansatz für andere Arten von Daten nützlich sein könnte, wie zum Beispiel Smart-Meter-Ablesungen (wo der Gesamtenergieverbrauch einer Nachbarschaft der Summe der einzelnen Haushalte entsprechen muss) oder Daten von Wearables.

Kurz gesagt zeigt das Paper, dass man sich nicht zwischen genauen Gesamtsummen und starkem Datenschutz entscheiden muss. Indem man ein wenig fortgeschrittene Mathematik nutzt, um das Rauschen zu choreografieren, kann man beides haben: einen Datensatz, der perfekt mit den großen Regeln übereinstimmt und dennoch vollständig sicher für die kleinen Details ist.

Technisches Resümee: Eine Implementierung der maximalen Entropie für differentielle Privatsphäre unter linearen Invarianten

Problemstellung
Differentielle Privatsphäre (DP) ist der Standard für den Datenschutz und wird typischerweise durch das Hinzufügen von unabhängigem Gauß- oder Laplace-Rauschen zu Datenbankabfragen implementiert. In Anwendungen wie dem US-Zensus (Decennial Census) unterliegen bestimmte aggregierte Abfragen (z. B. bevölkerungsbezogene Gesamtzahlen auf Bundesstaatsebene) jedoch „Invarianten“ – linearen Randbedingungen, die gesetzlich oder politisch vorgeschrieben sind und nicht verändert werden dürfen. Standardmäßige DP-Mechanismen, die unabhängiges Rauschen hinzufügen, verletzen diese Invarianten, da die Summe unabhängiger Rauschterme selten Null ergibt.

Obwohl Post-Processing-Techniken existieren, um Aggregate an Invarianten anzupassen, verändern solche Methoden die Rauschverteilung, was die Privatsphäre-Garantien und die Interpretation des DP-Mechanismus potenziell beeinflusst. Darüber hinaus kann die Projektion von unbeschränktem Rauschen auf den Raum der Invarianten oft zu einer Lösung mit geringerer Entropie führen, was den Nutzen der veröffentlichten Daten reduziert. Die zentrale Herausforderung besteht darin, einen Rausch-Additionsmechanismus zu entwerfen, der:

Die spezifizierten Randverteilungen (z. B. Laplace oder Gauß) auf der granularen Ebene beibehält.
Lineare Aggregationsbeschränkungen (Invarianten) mit Wahrscheinlichkeit eins erfüllt.
Die Entropie des Rauschvektors innerhalb des beschränkten Subraums maximiert, um sicherzustellen, dass das Rauschen „so unabhängig wie möglich“ unter den gegebenen Bedingungen ist.

Methodik
Die Autoren schlagen einen Aggregation Invariant Differential Privacy (AI-DP) Mechanismus vor. Der Ansatz behandelt sowohl Gauß- als auch Laplace-Rauschen als Skalenmischungen von Normalverteilungen. Die Methodik gliedert sich in drei Hauptphasen:

Formalisierung des invarianten Datenuiversums:
Die Autoren definieren die Struktur der benachbarten Datenbanken für DP-Garantien neu. Anstatt des Standard-Austauschs eines einzelnen Eintrags müssen benachbarte Datenbanken im invarianten Universum ( $D_{Q,A,c}$ ) so variieren, dass die linearen Beschränkungen $AQ(D) = c$ gewahrt bleiben. Dies erfordert oft den gleichzeitigen Austausch mehrerer Einträge. Die Privatsphäre-Garantien werden dann innerhalb dieses beschränkten Universums bewertet.
Konstruktion der Korrelationsmatrix via POCS:
Um die Beschränkungen $AX = 0$ unter Beibehaltung spezifischer Randverteilungen zu erfüllen, wird der Rauschvektor $X$ als multivariate Normalverteilung $N(0, \Sigma)$ modelliert, wobei $\Sigma = DRD$ gilt. Hierbei ist $D$ eine Diagonalmatrix von Skalen (abgeleitet aus der Mischverteilung) und $R$ eine Korrelationsmatrix, die $RB = 0$ erfüllt (wobei $B = AD$).
Das Finden eines solchen $R$ wird als konvexes Erfüllbarkeitsproblem (Convex Feasibility Problem, CFP) formuliert: Die Suche nach einer Matrix im Schnittpunkt von drei konvexen Mengen:

$C_1$ : Der Kegel der positiv semidefiniten Matrizen.
$C_2$ : Der affine Unterraum von Matrizen mit Einser-Diagonaleinträgen (Korrelationsmatrizen).
$C_3$ : Der Unterraum von Matrizen, für die $RB = 0$ gilt.
Die Autoren verwenden den Cyclic Projection Onto Convex Sets (POCS) Algorithmus, um eine Lösung $R$ in diesem Schnittpunkt zu finden.

Maximierung der Entropie-Optimierung:
Die POCS-Lösung liefert eine gültige Korrelationsmatrix, garantiert jedoch keine maximale Entropie. Um die Anforderung der maximalen Entropie (Anforderung [R3]) zu erfüllen, formulieren die Autoren ein Optimierungsproblem:
$R_{opt} = \min_{R \in C_n} \left[ \text{Tr}(B^T R B) - \tau \log \det(K^T R K) \right]$
wobei der erste Term die Beschränkung erzwingt (idealerweise Null) und der zweite Term (mit dem Tuning-Parameter $\tau$ ) eine niedrige Entropie bestraft. Dies wird mittels eines Projected Gradient Algorithms gelöst.

Wesentliche Beiträge

Theoretische Privatsphäre-Garantien: Das Paper leitet $(\epsilon, \delta)$ -DP-Garantien für den vorgeschlagenen Mechanismus unter dem invarianten Datenuiversum ab. Es beweist, dass der Mechanismus für Datenbanken, die sich durch Einträge unterscheiden, welche die Invarianten bewahren, diese Garantien erfüllt.
Korrelationsmatrix-Theorie: Die Arbeit trägt neue Ergebnisse zur Literatur über Korrelationsmatrizen bei, insbesondere bezüglich des Nullraums von Korrelationsmatrizen.
- Sie liefert eine notwendige und hinreichende Bedingung für die Existenz einer Korrelationsmatrix $R$ , sodass $RB=0$ für eine Rang- $k$ Beschränkungsmatrix $B$ gilt.
- Sie charakterisiert die Menge der Lösungen als Flächen (Faces) der Elliptope (der Menge der Korrelationsmatrizen) und identifiziert die Lösung mit maximalem Rang als liegend im relativen Inneren dieser Menge.
Algorithmischer Rahmen: Das Paper präsentiert einen praktischen Algorithmus (Algorithmus 1 und 2) zur Stichprobenziehung aus Skalenmischungen von Normalverteilungen unter linearen Gleichheitsbeschränkungen, unter Verwendung von POCS und Projected Gradient Descent.
Umgang mit hierarchischen Beschränkungen: Die Methodik zeigt sich anpassungsfähig an verschachtelte hierarchische Strukturen (z. B. Blöcke $\to$ Landkreise $\to$ Bundesstaaten), wodurch Konsistenz über alle Ebenen hinweg gewährleistet und Top-Level-Invarianten gewahrt bleiben.

Ergebnisse

Numerische Illustrationen:
- Einfache Aggregation: Für den Fall, dass der Beschränkungsvektor ein Vektor aus Einsen ist (Summierung zu einem Total), zeigen die Autoren, dass eine spezifische Intraclass-Korrelationsmatrix (Rang $n-1$ ) die eindeutige Max-Rank- und Max-Entropie-Lösung ist, wodurch die Notwendigkeit einer iterativen Optimierung in diesem speziellen Fall entfällt.
- Laplace-Mechanismus: Durch die Darstellung von Laplace-Rauschen als Gaußsche Skalenmischung konnten die Autoren erfolgreich 100 Stichproben von Laplace-verteiltem Rauschen generieren, das eine einzelne lineare Beschränkung erfüllt. Die Q-Q-Plots bestätigten die Randverteilung, und die Verletzungen der Beschränkung waren vernachlässigbar (Größenordnung $10^{-6}$ ).
- Konvergenz: Der Projected Gradient Algorithm zeigte eine Konvergenz bei der Minimierung der Verlustfunktion unter Beibehaltung des Entropie-Strafterms.
Wahrscheinlichkeit der Verletzung: Das Paper analysiert die Wahrscheinlichkeit, dass ein zufälliger Beschränkungsvektor „balanciert“ ist (eine Bedingung, die für die Existenz einer nullenden Korrelationsmatrix erforderlich ist). Es liefert eine Tail-Bound (Schwanzverteilungsschranke), die zeigt, dass die Wahrscheinlichkeit der Unzulänglichkeit für Vektoren mit Heavy-Tailed-Einträgen exponentiell klein ist.

Bedeutung und Behauptungen
Die Autoren behaupten, dass diese Arbeit einen prinzipienbasierten Weg bietet, um Aggregationsbeschränkungen in der DP-Implementierung zu adressieren, ohne die Standardinterpretation der differentiellen Privatsphäre zu opfern. Indem sie sicherstellen, dass der Rauschvektor die maximale Entropie innerhalb der Beschränkungen aufweist, minimieren sie die Verzerrung der statistischen Eigenschaften der Daten über das notwendige Maß zur Erfüllung der Invarianten hinaus.

Das Paper stellt explizit fest, dass es zur Diskussion darüber beiträgt, wie veröffentlichte Daten analysiert und DP-Semantiken in Gegenwart von Invarianten interpretiert werden können – eine Lücke, die in der einschlägigen Literatur zur Census-Implementierung identifiziert wurde (Abowd et al., 2022). Die Methodik wird als allgemein nutzbar über Census-Daten hinaus dargestellt, anwendbar auf jeden Kontext, der das Sampling aus Normalen Mischmodellen unter linearen Gleichheitsbeschränkungen beinhaltet, wie etwa Smart-Meter- oder Wearable-Device-Daten.

Die Autoren bleiben bescheiden hinsichtlich des Umfangs und merken an, dass sich die aktuelle Arbeit auf lineare Gleichheitsbeschränkungen konzentriert und zukünftige Arbeiten notwendig sind, um allgemeinere Systeme von linearen Gleichheits- und Ungleichheitsbeschränkungen (z. B. Nicht-Negativität) zu adressieren. Sie stellen zudem fest, dass der theoretische Beweis bezüglich des Nullraums von Korrelationsmatrizen eine Teillösung zu einer offenen Frage in diesem Feld darstellt.