Data Privacy: Algorithmen für t-Closeness und

Prof. Dr. Rainer Lenz, [email protected]
Data Privacy: Algorithmen für t-Closeness und Differential Privacy
Das Angebot an sensiblen Daten über Personen und Unternehmen ist in den letzten
Jahren sprunghaft gewachsen und wird weiter zunehmen. Daher werden Algorithmen
benötigt, die zu veröffentlichende Daten derart schützen, dass eine Identifikation der
Merkmalsträger nach menschlichem Ermessen ausgeschlossen werden kann.
Andererseits dürfen die Daten nicht zu stark verfremdet bzw. ihr Informationsgehalt
zu sehr reduziert werden, damit eine vernünftige Datenanalyse weiterhin möglich ist.
In der Informatik werden verschiedene Konzepte zur Sicherung des Datenschutzes
vorgeschlagen:
Seien Q1, …, Qn so genannte Quasi-Identifikatoren (das sind Merkmale, die zur
Verknüpfung mit einem anderen Datensatz verwendet werden können wie z.B.
„Geschlecht“, „Alter“, „Nationalität“ bei Personendaten oder „Wirtschaftszweig“,
„Umsatz“, „Unternehmenssitz“ bei Unternehmensdaten); seien weiterhin C1, …, Cm
sensible Merkmale (z. B. Angaben über Krankheiten, das Einkommen von Personen
oder die Investitionen von Unternehmen), die ein potentieller Datenangreifer auf
keinen Fall aufdecken darf.
Eine Datei D heißt
(1) k-anonym, wenn es zu jeder vorkommenden Kombination der QuasiIdentifikatoren mindestens k Einheiten bzw. Datensätze in D gibt.
(2) l-divers für das Merkmal xj, wenn dieses Merkmal für jede Kombination der
Quasi-Identifikatoren mindestens l deutlich unterscheidbare Ausprägungen
aufweist (d.h. bei numerischen Merkmalen wie etwa Einkommen dürfen die
Werte nicht zu nah beieinander liegen).
Eine Anforderung, die über k-Anonymität und l-Diversität hinausgeht, ist die tCloseness. Dazu teilt man die Datei D in Klassen K1, …, Kl auf. D erfüllt diese
Anforderung, wenn die Verteilung eines Merkmales xj sich in jeder Klasse Ki von der
Verteilung des Merkmals für die ganze Datei D anteilig um höchstens t unterscheidet.
Domingo-Ferrer und Soria-Comas schlagen in [1] (Kapitel 6) einen neuen
Algorithmus zur Erreichung von t-Closeness vor, der auf einer so genannten
Bucketisierung des Datensatzes beruht. Eine Beschreibung findet sich in [3].
Hauptziel der Projektarbeit soll die Implementierung dieses Algorithmus und die
Anwendung auf ausgewählte Dateien sein. Es soll für ausgewählte Analysen
verglichen werden, wie stark sich die Ergebnisse mit Original- und veränderten Daten
unterscheiden.
Domingo-Ferrer und Soria-Comas schlagen in [1] (Kapitel 4) ferner eine Erweiterung
der t-Closeness zu einer stochastischen t-Closeness vor.
Eine mögliche Erweiterung der Projektarbeit besteht in der Abänderung des
Algorithmus‘ derart, dass eine stochastische t-Closeness erreicht wird und in einem
Vergleich der Ergebnisse der beiden Ansätze.
Ausgangspunkt für einen anderen Strang der Data Privacy – Forschung stellt das
Konzept der Differential Privacy dar. Dabei soll erreicht werden, dass sich
Analyseergebnisse nur um einen kleinen Faktor ε unterscheiden, wenn man eine
beliebige Einheit aus der Datei entfernt. Eine formale Definition und einen guten
Überblick über die aktuelle Forschung bieten Dwork und Roth [2].
Je nach Rückmeldung der Studierenden bzw. bei größerer Teilnehmerzahl wäre die
zusätzliche Implementierung eines Algorithmus‘ aus diesem Bereich zu
Vergleichszwecken denkbar. Die Anforderungen an die Programmoberfläche können
ebenfalls an die Teilnehmerzahl angepasst werden.
Literatur
[1] Domingo-Ferrer, J. und Soria-Comas, J.: From t-Closeness to Differential Privacy
and Vice Versa in Data Anonymization,
crises2-deim.urv.cat/docs/publications/journals/841.pdf.
[2] Dwork, C. und Roth, A.: The Algorithmic Foundations of Differential Privacy,
www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf.
[3] Soria-Comas, J.: Improving data utility in differential privacy and k-anonymity,
Doctoral Thesis, crises2-deim.urv.cat/docs/publications/theses/jSoria.pdf.

Download Report