k-Anonymität

Die k-Anonymität ist ein formelles Datenschutzmodell, mit dem Aussagen über anonymisierte Datensätze getroffen werden können.

Eine Veröffentlichung von Daten bietet k-Anonymität, falls die identifizierenden Informationen jedes einzelnen Individuums von mindestens k-1 anderen Individuen ununterscheidbar sind und somit eine korrekte Verknüpfung mit den zugehörigen sensiblen Attributen erschwert wird.^[1] Der Buchstabe k stellt somit einen Parameter dar, der im konkreten Fall durch eine natürliche Zahl ersetzt wird. Ein größeres k repräsentiert in diesem Kontext eine größere Anonymität.

Das Konzept wurde 2002 von Latanya Sweeney, Professorin der Universität Harvard, veröffentlicht mit dem Ziel, wissenschaftliche Daten zu veröffentlichen und dabei garantieren zu können, dass die Individuen, von denen die Daten handeln, nicht reidentifiziert werden können, während die Daten weiterhin nützlich sind für die vorgesehenen Anwendungen. Dabei handelt es sich um einen Kompromiss zwischen einem höheren Maß an Datenschutz auf der einen Seite und einem Verlust an Datengenauigkeit auf der anderen Seite. k-Anonymität und dessen Umsetzung durch Generalisierung und Suppression wurde dabei erstmalig von Pierangela Samarati 2001 definiert.^[2]

Erklärung

Im Kontext der k-Anonymität versteht man unter einer Datenbank eine Tabelle mit n Zeilen sowie m Spalten. Jede Zeile stellt einen (nicht notwendigerweise einzigartigen) Datensatz dar, der zu einem spezifischen Individuum gehört. Die Werte in den verschiedenen Spalten sind die Werte der Attribute, die den Individuen entsprechen.

Bei den einzelnen Attributen kann man unterscheiden zwischen Identifikatoren, Quasi-Identifikatoren sowie sensiblen Attributen. Anhand von Identifikatoren, etwa Ausweisnummern oder Matrikelnummern können Individuen eindeutig identifiziert werden. Quasi-Identifikatoren sind Attribute, die für sich genommen keine Identifikation erlauben, allerdings in Kombination mit allgemein zugänglichen Daten eine eindeutige Zuordnung ermöglichen. Sensible Attribute enthalten persönliche, schützenswerte Informationen, wie etwa Krankheiten oder Gehaltsangaben. Daher soll der genaue Wert des sensiblen Attribut eines Individuums nicht preisgegeben werden.^[3]

Eine Anonymisierung kann, unabhängig vom Konzept der k-Anonymität, mit verschiedenen Mitteln erreicht werden, etwa indem Rauschen hinzugefügt, Informationen unterdrückt oder Daten generalisiert werden.

Veranschaulichung

Die folgende Tabelle ist eine nicht-anonymisierte Datenbank, bestehend aus Patientendaten aus einem fiktiven Krankenhaus.

Name	Alter	Geschlecht	PLZ	Krankheit
Identifikator	Quasi-Identifikatoren			Sensibles Attribut
Anna	21	Weiblich	76189	Grippe
Louis	35	Männlich	77021	Krebs
Holger	39	Männlich	63092	Haarausfall
Frederic	23	Männlich	63331	Muskelzerrung
Anika	24	Weiblich	76121	Grippe
Peter	31	Männlich	77462	Vergiftung
Tobias	38	Männlich	77109	Demenz
Charlotte	19	Weiblich	83133	Karies
Sarah	27	Weiblich	89777	Akne

Die nächste Tabelle ergibt sich aus einer Anonymisierung mittels Generalisierung:

Name	Alter	Geschlecht	PLZ	Krankheit
Identifikator	Quasi-Identifikatoren			Sensibles Attribut
*	20 < Alter < 25	Weiblich	76*	Grippe
*	30 < Alter < 40	Männlich	77*	Krebs
*	20 < Alter < 40	Männlich	63*	Haarausfall
*	20 < Alter < 40	Männlich	63*	Muskelzerrung
*	20 < Alter < 25	Weiblich	76*	Grippe
*	30 < Alter < 40	Männlich	77*	Vergiftung
*	30 < Alter < 40	Männlich	77*	Demenz
*	18 < Alter < 28	Weiblich	8*	Karies
*	18 < Alter < 28	Weiblich	8*	Akne

Es ergeben sich 4 Äquivalenzklassen:

Äquivalenzklasse	Name	Alter	Geschlecht	PLZ	Krankheit
	Identifikator	Quasi-Identifikatoren			Sensibles Attribut
A	*	20 < Alter < 25	Weiblich	76*	Grippe
A	*	20 < Alter < 25	Weiblich	76*	Grippe

Äquivalenzklasse	Name	Alter	Geschlecht	PLZ	Krankheit
	Identifikator	Quasi-Identifikatoren			Sensibles Attribut
B	*	30 < Alter < 40	Männlich	77*	Krebs
	*	30 < Alter < 40	Männlich	77*	Vergiftung
	*	30 < Alter < 40	Männlich	77*	Demenz

Äquivalenzklasse	Name	Alter	Geschlecht	PLZ	Krankheit
	Identifikator	Quasi-Identifikatoren			Sensibles Attribut
C	*	20 < Alter < 40	Männlich	63*	Haarausfall
C	*	20 < Alter < 40	Männlich	63*	Muskelzerrung

Äquivalenzklasse	Name	Alter	Geschlecht	PLZ	Krankheit
	Identifikator	Quasi-Identifikatoren			Sensibles Attribut
D	*	18 < Alter < 28	Weiblich	8*	Karies
D	*	18 < Alter < 28	Weiblich	8*	Akne

Jede einzelne Äquivalenzklasse enthält mindestens 2 Elemente, somit ist eine 2-Anonymität gewährleistet. Man beachte, dass in der Äquivalenzklasse A auch die sensiblen Attributwerte übereinstimmen, während dies in den übrigen Äquivalenzklassen nicht der Fall ist. Die k-Anonymität macht über die Verteilung der Werte der sensiblen Attribute keine Aussage (siehe dazu Abschnitt Homogenitätsattacke).

Mängel

Das Konzept der k-Anonymität hat bekannte Mängel, die eine Deanonymisierung ermöglichen können. Das bedeutet, dass einzelne Teilnehmer einer k-anonymen Tabelle unter Umständen eindeutig identifizierbar sein können. Im Folgenden werden zwei Mängel näher erläutert.^[4]

Homogenitätsattacke

Bei der Homogenitätsattacke wird ausgenutzt, dass unter Umständen alle k Datensätze einer Äquivalenzklasse identische sensible Attribute vorweisen. Weiß der Angreifer um die Existenz einer Person in einer Datenbank und kann er diese Person der korrekten Äquivalenzklasse zuweisen, erfährt er deren sensible Attribute.

Veranschaulichung

Alice ist eine sehr neugierige Nachbarin von Bob. Als Bob eines Tages mit dem Krankenwagen abgeholt wird, möchte Alice herausfinden, woran Bob erkrankt ist. Sie entdeckt die 4-anonyme Tabelle mit aktuellen Patientendaten, die vom Krankenhaus veröffentlicht wird. Sie weiß, dass Bob in der Tabelle enthalten sein muss und kennt sein Alter, Geschlecht sowie Postleitzahl. Dadurch schließt sie darauf, dass sein Datensatz in der Äquivalenzklasse C enthalten sein muss. Da alle Patienten dieser Äquivalenzklasse an derselben Krankheit leiden, erfährt Alice auch Bobs Krankheit.^[4]

Äquivalenzklasse	Name	Alter	Geschlecht	PLZ	Krankheit
	Identifikator	Quasi-Identifikatoren			Sensibles Attribut
B	*	25 < Alter < 30	Weiblich	13*	...
B	*	25 < Alter < 30	Weiblich	13*	Herzerkrankung
C	*	40 < Alter < 50	Männlich	13*	Krebs
					Krebs
					Krebs
					Krebs
D	*	20 < Alter < 35	Weiblich	12*	Grippe
D	*	20 < Alter < 35	Weiblich	12*	...

Background Knowledge Attack

Durch den Einsatz von Zusatzwissen kann es möglich sein, Personen trotz k-Anonymität eindeutig zuzuordnen. Weiß der Angreifer um die Existenz einer Person in einer Datenbank und kann er diese Person der korrekten Äquivalenzklasse zuweisen, so kann er gegebenenfalls durch das Zusatzwissen manche sensible Attribute für die Person ausschließen.

Veranschaulichung

Alice hat eine Brieffreundin namens Yui, die in ein Krankenhaus eingeliefert wurde und deren Patientendaten in einer 4-anonymen Tabelle enthalten sind, die vom Krankenhaus regelmäßig veröffentlicht wird. Alice weiß, dass Yui eine 21 Jahre alte Japanerin ist, die momentan unter der PLZ 12345 gemeldet ist. Ausgehend von diesen Informationen kann Alice darauf schließen, dass Yuis Datensatz in der Äquivalenzklasse B enthalten sein muss. Ohne zusätzliche Informationen kann sich Alice nicht sicher sein, ob Yui an einer Viruserkrankung oder an einer Herzerkrankung leidet. Jedoch ist hinlänglich bekannt, dass Japaner sehr selten an Herzerkrankungen leiden. Dadurch kann Alice darauf schließen, dass bei Yui wohl eine Viruserkrankung vorliegt.^[4]

Äquivalenzklasse	Name	Alter	Geschlecht	PLZ	Krankheit
	Identifikator	Quasi-Identifikatoren			Sensibles Attribut
A	*	30 < Alter < 35	Männlich	14*	...
A	*	30 < Alter < 35	Männlich	14*	Grippe
B	*	20 < Alter < 30	Weiblich	12*	Herzerkrankung
					Viruserkrankung
					Viruserkrankung
					Herzerkrankung
C	*	30 < Alter < 35	Weiblich	12*	Krebs
C	*	30 < Alter < 35	Weiblich	12*	...

Erweiterungen

Um die genannten Mängel von k-Anonymität zu beheben, wurden mit l-diversity sowie darauf aufbauend t-closeness Erweiterungen entworfen. l-diversity verbessert insbesondere die Schwäche gegenüber Homogenitätsattacken, indem ein gewisses Maß an Verschiedenheit der sensiblen Attribute in den einzelnen Äquivalenzklassen gewährleistet wird. t-closeness erweitert das Konzept dahingehend, dass die Verteilung der Werte der sensiblen Attribute in den einzelnen Äquivalenzklassen möglichst der Verteilung in der gesamten Tabelle entspricht.^[5]

Siehe auch

Differential Privacy

Einzelnachweise

↑ Latanya Sweeney: k-anonymity: A model for protecting privacy In: International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, Vol. 10, Issue 5, World Scientific, 2002, S. 557–570 (englisch).
↑ P. Samarati, "Protecting Respondents' Identities in Microdata Release," in IEEE Transactions on Knowledge and Data Engineering, vol. 13, n. 6, November/December 2001, pp. 1010-1027. online, pdf
↑ Zhen Li, Xiaojun Ye: Privacy protection on multiple sensitive attributes In: Information and Communications Security, Vol. 1, Springer Berlin Heidelberg, 2007, S. 141–152 (englisch).
↑ ^a ^b ^c Ashwin Machanavajjhala, Daniel Kifer, Johannes Gehrke, Muthuramakrishnan Venkitasubramaniam: l-diversity: Privacy beyond k-anonymity In: ACM Transactions on Knowledge Discovery from Data (TKDD), Vol. 1, ACM, 2007 (englisch).
↑ Ninghui Li, Tiancheng Li, Suresh Venkatasubramanian: t-Closeness: Privacy Beyond k-Anonymity and l-Diversity In: ICDE, Vol. 7, 2007, S. 106–115 (englisch).

[k-anonymity:_A_model_for_protecting_privacy-1] Latanya Sweeney: k-anonymity: A model for protecting privacy In: International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, Vol. 10, Issue 5, World Scientific, 2002, S. 557–570 (englisch).

[2] P. Samarati, "Protecting Respondents' Identities in Microdata Release," in IEEE Transactions on Knowledge and Data Engineering, vol. 13, n. 6, November/December 2001, pp. 1010-1027. online, pdf

[attributes-3] Zhen Li, Xiaojun Ye: Privacy protection on multiple sensitive attributes In: Information and Communications Security, Vol. 1, Springer Berlin Heidelberg, 2007, S. 141–152 (englisch).

[l-diversity-4] Ashwin Machanavajjhala, Daniel Kifer, Johannes Gehrke, Muthuramakrishnan Venkitasubramaniam: l-diversity: Privacy beyond k-anonymity In: ACM Transactions on Knowledge Discovery from Data (TKDD), Vol. 1, ACM, 2007 (englisch).

[t-closeness-5] Ninghui Li, Tiancheng Li, Suresh Venkatasubramanian: t-Closeness: Privacy Beyond k-Anonymity and l-Diversity In: ICDE, Vol. 7, 2007, S. 106–115 (englisch).

[1]

[2]

[3]

[4]

[5]