# 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. 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.

## 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.
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.
| Identifikator | Quasi-Identifikatoren | Quasi-Identifikatoren | Quasi-Identifikatoren | Sensibles Attribut |
| Name | Alter | Geschlecht | PLZ | Krankheit |
| 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:
| Identifikator | Quasi-Identifikatoren | Quasi-Identifikatoren | Quasi-Identifikatoren | Sensibles Attribut |
| Name | Alter | Geschlecht | PLZ | Krankheit |
| * | 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:
| | Identifikator | Quasi-Identifikatoren | Quasi-Identifikatoren | Quasi-Identifikatoren | Sensibles Attribut |
| Äquivalenzklasse | Name | Alter | Geschlecht | PLZ | Krankheit |
| A | * | 20 < Alter < 25 | Weiblich | 76* | Grippe |
| A | * | 20 < Alter < 25 | Weiblich | 76* | Grippe |
| | Identifikator | Quasi-Identifikatoren | Quasi-Identifikatoren | Quasi-Identifikatoren | Sensibles Attribut |
| Äquivalenzklasse | Name | Alter | Geschlecht | PLZ | Krankheit |
| B | * | 30 < Alter < 40 | Männlich | 77* | Krebs |
| B | * | 30 < Alter < 40 | Männlich | 77* | Vergiftung |
| B | * | 30 < Alter < 40 | Männlich | 77* | Demenz |
| | Identifikator | Quasi-Identifikatoren | Quasi-Identifikatoren | Quasi-Identifikatoren | Sensibles Attribut |
| Äquivalenzklasse | Name | Alter | Geschlecht | PLZ | Krankheit |
| C | * | 20 < Alter < 40 | Männlich | 63* | Haarausfall |
| C | * | 20 < Alter < 40 | Männlich | 63* | Muskelzerrung |
| | Identifikator | Quasi-Identifikatoren | Quasi-Identifikatoren | Quasi-Identifikatoren | Sensibles Attribut |
| Äquivalenzklasse | Name | Alter | Geschlecht | PLZ | Krankheit |
| 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.

### 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.
| | Identifikator | Quasi-Identifikatoren | Quasi-Identifikatoren | Quasi-Identifikatoren | Sensibles Attribut |
| Äquivalenzklasse | Name | Alter | Geschlecht | PLZ | Krankheit |
| B | * | 25 < Alter < 30 | Weiblich | 13* | ... |
| B | * | 25 < Alter < 30 | Weiblich | 13* | Herzerkrankung |
| C | * | 40 < Alter < 50 | Männlich | 13* | Krebs |
| C | * | 40 < Alter < 50 | Männlich | 13* | Krebs |
| C | * | 40 < Alter < 50 | Männlich | 13* | Krebs |
| C | * | 40 < Alter < 50 | Männlich | 13* | 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.
| | Identifikator | Quasi-Identifikatoren | Quasi-Identifikatoren | Quasi-Identifikatoren | Sensibles Attribut |
| Äquivalenzklasse | Name | Alter | Geschlecht | PLZ | Krankheit |
| A | * | 30 < Alter < 35 | Männlich | 14* | ... |
| A | * | 30 < Alter < 35 | Männlich | 14* | Grippe |
| B | * | 20 < Alter < 30 | Weiblich | 12* | Herzerkrankung |
| B | * | 20 < Alter < 30 | Weiblich | 12* | Viruserkrankung |
| B | * | 20 < Alter < 30 | Weiblich | 12* | Viruserkrankung |
| B | * | 20 < Alter < 30 | Weiblich | 12* | 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.