Differential Privacy auf Vertrauensgraphen: Ein neuer Ansatz für Datenschutz

In der heutigen digitalen Welt, in der Daten eine zentrale Rolle spielen, wird der Schutz der Privatsphäre immer wichtiger. Differential Privacy (DP) ist ein mathematisch fundierter Ansatz, der sicherstellt, dass die Ausgabe eines zufälligen Algorithmus statistisch nicht unterscheidbar bleibt, selbst wenn die Daten eines einzelnen Nutzers verändert werden. In diesem Artikel stellen wir ein neues Modell für Differential Privacy vor, das unterschiedliche Vertrauensannahmen zwischen Nutzern integriert und mehrere Algorithmen sowie untere Schranken in diesem Modell entwickelt.

Einführung in Differential Privacy

Differential Privacy hat sich als ein weit verbreitetes und intensiv erforschtes Datenschutzframework etabliert, das in vielen Bereichen, einschließlich Analytik und maschinellem Lernen, Anwendung findet. Es gibt zwei Hauptmodelle von DP: das zentrale Modell und das lokale Modell. Im zentralen Modell hat ein vertrauenswürdiger Kurator Zugang zu Rohdaten und ist verantwortlich für die Erstellung einer datenschutzkonformen Ausgabe. Im lokalen Modell hingegen müssen alle Nachrichten, die von einem Benutzergerät gesendet werden, selbst differential privat sein, wodurch die Notwendigkeit eines vertrauenswürdigen Kurators entfällt.

Das Problem der Vertrauensdynamik

In realen Datenaustausch-Szenarien haben Nutzer oft unterschiedliche Vertrauensniveaus gegenüber anderen, abhängig von ihren Beziehungen. Beispielsweise könnte jemand bereit sein, seine Standortdaten mit Familie oder engen Freunden zu teilen, während er zögert, diese Informationen mit Fremden zu teilen. Diese Asymmetrie spiegelt sich in den philosophischen Ansichten über Privatsphäre wider, die Kontrolle über persönliche Informationen betonen. Daher ist es notwendig, Frameworks zu entwickeln, die über die binären Vertrauensannahmen bestehender Differential Privacy-Modelle hinausgehen und realistischere Vertrauensdynamiken in datenschutzfreundlichen Systemen berücksichtigen.

Das Modell der Vertrauensgraphen

In der Arbeit „Differential Privacy on Trust Graphs“, die auf der Innovationskonferenz für theoretische Informatik (ITCS 2025) veröffentlicht wurde, verwenden wir einen Vertrauensgraphen, um Beziehungen zu modellieren, wobei die Knoten Benutzer darstellen und verbundene Knoten einander vertrauen. Wir untersuchen, wie DP auf diese Vertrauensgraphen angewendet werden kann, um sicherzustellen, dass die Datenschutzgarantie für Nachrichten gilt, die zwischen einem Benutzer (oder seinen vertrauenswürdigen Nachbarn) und allen anderen, denen sie nicht vertrauen, ausgetauscht werden.

Vertrauensgraph-Differential Privacy (TGDP)

Wir nennen dieses Konzept Trust Graph Differential Privacy (TGDP). TGDP interpoliert auf natürliche Weise zwischen dem zentralen und dem lokalen Modell. Das zentrale Modell entspricht TGDP über einem Stern-Graphen, während das lokale Modell TGDP über einem vollständig unverbundenen Graphen entspricht, in dem kein Benutzer einem anderen vertraut. TGDP ermöglicht es uns, die Genauigkeit von Algorithmen unter allgemeineren Vertrauensbeziehungen zu quantifizieren.

Algorithmen zur Aggregation

Wir bieten einen Algorithmus für die Aggregation an, der TGDP erfüllt. Der Algorithmus und die obere Schranke basieren auf einem dominierenden Satz des Vertrauensgraphen. Ein dominierender Satz T ist eine Teilmenge von Graphenknoten, sodass jeder Knoten, der nicht in T ist, mindestens einem Knoten in T benachbart ist. Der Algorithmus funktioniert wie folgt:

1. Finde einen dominierenden Satz T des Vertrauensgraphen.
2. Jeder Benutzer sendet seine Daten an einen Nachbarn im dominierenden Satz T.
3. Jeder Benutzer im dominierenden Satz T sendet die Summe aller empfangenen Zahlen plus Laplace-Rauschen.
4. Die Schätzung ist die Summe aller verrauschten Übertragungen.

Der Fehler dieses Algorithmus ist nicht größer als eine Funktion der Größe des dominierenden Satzes T.

Untere Schranken und das Packungsnummer

Um die besten möglichen Fehler zu charakterisieren, benötigen wir eine untere Schranke, die von der Packungsnummer des Graphen abhängt. Die Packungsnummer ist die maximale Größe einer Menge von Knoten, die keine Nachbarn teilen. Diese Konzepte helfen uns, die Grenzen der TGDP-Algorithmen zu verstehen und zu quantifizieren.

Fazit

In dieser Arbeit haben wir TGDP eingeführt, ein neues Modell für verteilte Differential Privacy, das eine differenziertere Kontrolle über die Vertrauensannahmen jedes Teilnehmers ermöglicht. Unser TGDP-Modell bietet eine wertvolle Perspektive für die Entwicklung datenschutzfreundlicher Systeme, die sich an den unterschiedlichen Vertrauensniveaus der Benutzer orientieren. Die Schließung der Lücke zwischen unseren oberen und unteren Schranken bleibt eine offene theoretische Frage.

Quellen

Quellenliste:

• Quelle: Differential Privacy on Trust Graphs
• Deep Learning with Label Differential Privacy
• Differential Privacy Accounting by Connecting the Dots
• Advances in Private Training for Production on Device Language Models
• Protecting Users with Differentially Private Synthetic Training Data
• Improving Gboard Language Models via Private Federated Analytics
• Bridging the Gap in Differentially Private Model Training
• Generating Synthetic Data with Differentially Private LLM Inference