Data-Mining, Privacy-Preserving

Ein wichtiges Kriterium zur Unterscheidung von verschiedenen Techniken des Privacy-Preserving Data Mining ist die Form der Datenhaltung. Klassischerweise werden alle relevanten Daten vor der Analyse in eine zentrale Datenbank zusammengeführt. Eine zentrale Datenhaltung liegt beispielsweise auch dann vor, wenn im Rahmen einer klinischen Studie alle Daten über Patienten und Behandlungen in einer Datenbank gespeichert werden. In diesem Szenario ist eine der wichtigsten Fragen die, welche Informationen und Analyseergebnisse ohne Bedenken an Dritte weitergegeben werden dürfen.

Das deutsche Bundesdatenschutzgesetz (BDSG) unterscheidet dabei zwischen personenbezogenen Daten, für deren Verwendung starke Hürden vorgesehen sind, und pseudonymen bzw. anonymen Daten, für die wesentlich geringere Datenschutzanforderungen gelten. Für den Gesetzgeber gelten Daten dabei bereits dann als personen-bezogen, wenn der Betroffene dabei potentiell identifizierbar ist (vergl. §3 Abs. 1 BDSG). Es sind also nicht nur identifizierende Attribute wie Name oder Sozialversicherungsnummer personenbezogen - auch wenn diese entfernt werden besteht noch die Gefahr, dass eine Zuordnung der Datensätze auf Individualebene durch Zu-sammenführen mit externen Daten möglich ist. Beispielsweise könnte ein Datensatz, der lediglich die öffentlichen Attribute Postleitzahl und Geburtsdatum enthält, durch Verknüpfung mit öffentlichen Daten wie Wählerlisten, Facebook-Profilen o.a. identifiziert werden. Solch eine identifizierende Kombination von Attributwerten wird als „Quasi-Identifizierer“ bezeichnet.

Um derartige Schlussfolgerungen auf Individualebene zu unterbinden, führen Verfahren wie k-Anonymisierung [Sam01] eine Modifikation der Daten durch. Diese stellt sicher, dass in den modifizierten Daten jeder Quasi-Identifizierer von mindestens k verschiedenen Datensätzen erfüllt wird. Dies erfolgt durch Generalisierung sowie durch Unterdrückung: Generalisierung bedeutet hierbei, dass etwa von einer fünfstelligen Postleitzahl nur die ersten vier Ziffern bestehen bleiben, während Unterdrückung die Entfernung einzelner Datensätze bedeutet.

Nicht nur die Herausgabe von ganzen Datensätzen, sondern auch das Veröffentlichen von Data-Mining Ergebnissen kann potentiell Rückschlüsse auf Individualebene ermöglichen. Betrachten wir den Fall von Assoziationsregeln, einem bekannten Data-Mining Ansatz, bei dem Regeln der Form „Wenn A gilt, dann auch B“ gefunden werden, zu denen auch die Auftretens und die Fehlerwahrscheinlichkeit angegeben ist. Diese Regeln können z.B. verwendet werden, um nach Auswirkungen von Behandlungen auf die Genesung zu suchen.

Auch wenn einzelne Regeln für sich genommen unproblematisch sind, kann es passieren, dass sich aus einer Menge von Regeln Schlussfolgerungen auf Individualebene ziehen lassen. Dies lässt sich an folgendem, aus [Atz08] übernommenen Beispiel zeigen: wir betrachten die beiden Assoziationsregeln: (1) PLZ = 45254 & Religion = Christlich —› Heimatland = USA [n=758, Konfidenz=99,8%] und (2) PLZ = 45254 —› Heimatland = USA [n=1053, Konfidenz=99,9%]. Das Attribut Religion sei hierbei sensitiv und alle anderen Attribute öffentlich. Lassen sich aus einer dieser Regeln alleine sensitive Informationen auf Individualebene erschließen? Nein: Während aus der ersten Regel zwar geschlossen werden kann, dass es genau eine Person im angegebenen PLZ-Gebiet gibt, die christlicher Religion ist und nicht aus den USA stammt (die Zahlenangaben zur Regel besagen, dass von den 758 Personen, auf die die Vorbedingung zutrifft, 99,8% aus den USA stammen), ist zur Identifizierung dieser einen Person bereits die Kenntnis des sensitiven Attributs Religion nötig, so dass sie für einen Angreifer wertlos ist. Die zweite Regel enthält gar keine sensitiven Attribute. Durch die Kombination beider Regeln lässt sich aber nun aus (2) schließen, dass es überhaupt nur eine Person im PLZ-Gebiet gibt, die nicht aus den USA stammt, und dass damit die beiden Individuen aus (1) und (2) identisch sein müssen. Damit ist die Religion dieser Person aus öffentlichen Informationen erschließbar.

Diese Art von Informationsleck lässt sich verhindern, indem vor der Datenanalyse eine k-Anonymisierung durchgeführt wird. Allerdings ist dieser Ansatz häufig nicht optimal: im Allgemeinen gibt es mehrere Möglichkeiten, einen Datensatz zu anonymisieren. Jede führt zu einem Informationsverlust, allerdings ist dieser je nach Fragestellung unterschiedlich schwerwiegend - für medizinische Fragestellungen könnte z.B. die genaue Postleitzahl unerheblich sein, während sie für die Analyse von Verkehrsfragen von zentraler Bedeutung ist. Wird die Anonymisierung ohne Berücksichtigung der Analysefrage durchgeführt, kann dies zu einem unnötig schlechten Ergebnis führen. Als Ausweg wurden Ansätze entwickelt, die auf den Originaldaten arbeiten, jedoch sicherstellen, dass die gefundene Mustermenge unbedenklich ist [Atz08]. Diese Methoden führen gewissermaßen implizit eine für die Analysefrage geeignete Anonymisierung durch.

Die oben diskutierten Verfahren geben Unterstützung bei der Frage, welche Informationen aus einer zentralen Datenbank herausgegeben werden dürfen. Prinzipiell ist aber schon der Aufbau einer solchen zentralen Datenbank problematisch, denn im Falle eines Sicherheitslecks sind die gesamten sensiblen Informationen gefährdet. Insofern ist es wünschenswert – und für personenbezogene Daten vom Gesetzgeber im §3a BDSG wo möglich sogar vorgeschrieben – ganz auf die Zusammenführung der Daten zu verzichten.

Möglichkeiten hierzu bieten sogenannte „Secure Multiparty Computation“-Verfahren. Diese führen die Analyse von verteilten Daten derart durch, dass die Teilnehmer außer dem Ergebnis keinerlei weitergehende Informationen erhalten. Diese Idee wird gut durch das klassische „Millionärsproblem“ verdeutlicht [Yao82]: Zwei Millionäre möchten bestimmen, welcher von beiden reicher ist; dabei soll allerdings keiner der beiden Millionäre das Vermögen des anderen erfahren. Dieses Prinzip lässt sich auf die komplexeren Fragestellungen des Data Mining wie folgt übertragen: Verschiedene Teilnehmer möchten mit Hilfe von Data Mining Informationen aus Ihren (verteilten) Daten extrahieren, jedoch so, dass keiner die Daten eines anderen Teilnehmers erfährt.

Diese auf den ersten Blick paradoxe Aufgabe lässt sich u.a. mit kryptographischen Methoden lösen. Ein wichtiges Unterscheidungskriterium für verschiedene Protokolle sind die Annahmen, die sie über die Teilnehmer machen: Während im semi-honest model davon ausgegangen wird, dass die Teilnehmer zwar versuchen, Rückschlüsse auf die fremden Daten zu ziehen, das verabredete Protokoll ansonsten aber ordnungsgemäß befolgen, berücksichtigt das malicious model auch Teilnehmer, die gezielt falsche Nachrichten verschicken, um Informationen über die Daten anderer Teilnehmer zu gewinnen.

Zur Illustration wollen wir ein einfaches Protokoll besprechen, das die sichere Berechnung der Summe von N verteilt vorliegenden Zahlen ermöglich (unter der Annahme von nicht-kooperierenden Teilnehmern im semi-honest model). Wir gehen also von N Teilnehmern aus, die jeweils eine ganzzahlige Zahl ∨₁ (i=1,…N) kennen und die gemeinsam die Summe

bestimmen wollen. Diese Fragestellung ist eine wichtige Teilaufgabe verschiedener komplexerer Protokolle - z.B. ermöglicht sie, die Gesamtanzahl der verteilt vorliegenden Datensätze zu berechnen. Im Folgenden gehen wir von genau drei Teilnehmern aus und nehmen an, dass eine obere Schranke M für die Summe bekannt ist. Die Summe lässt sich nun wie folgt sicher verteilt berechnen:

•  Teilnehmer 1 generiert eine Zufallszahl rnd uniform im Intervall [0,…M]. Zu dieser Zahl addiert er seine Zahl ∨₁ und schickt die Summe (modulo M) an Teilnehmer 2
• Teilnehmer 2 addiert die Zahl ∨₂ und schickt das Zwischenergebnis (modulo M) an Teilnehmer 3
• Teilnehmer 3 addiert die Zahl ∨₃ und schickt das Zwischenergebnis (modulo M) an Teilnehmer 1
• Teilnehmer 1 subtrahiert rnd vom Ergebnis, erhält somit 

und schickt dieses Ergebnis an alle Teilnehmer.

Das Protokoll wird in Abbildung 1 illustriert. Es ist (unter der Annahme von nicht-kooperierenden Teilnehmern im semi-honest model) sicher, denn keiner der Teilnehmer kann aus den Zwischennachrichten irgendwelche Informationen ableiten: die Zahlen, die die Teilnehmer 2 und 3 erhalten, sind uniform zwischen 0 und M verteilt und lassen daher keine Rückschlüsse auf die einzelnen zu. Allerdings ist dieses einfache Protokoll nicht sicher gegenüber kooperierenden Teilnehmern: z.B. könnten Teilnehmer 1 und 3 durch Austausch Ihrer Information den Wert ermitteln. Auch für den Fall von kooperierenden Teilnehmern existieren sichere Lösungen - diese sind jedoch deutlich komplexer [Pin03].

Auf Basis der oben skizzierten Techniken lassen sich Protokolle entwickeln, die sicheres, verteiltes Data Mining ermöglichen. Es existieren z.B. sichere Protokolle zum Lernen von Entscheidungsbäumen, zum Clustering sowie zur Regelfindung. Im Folgenden wollen wir eine Variante der Regelsuche genauer betrachten, die sogenannte „Subgruppensuche“ [Wro97]. Diese sucht nach Beschreibungen von Teilpopulationen, die sich bezüglich eines Zielattributs vom Rest der Population unterscheiden. Dieses Verfahren wurde z.B. genutzt, um nach charakteristischen Merkmalen von Alzheimer-Patienten zu suchen [Sch09].

Algorithmen zur Subgruppensuche finden die auffälligsten Subgruppen, indem sie (mehr oder weniger systematisch) den Raum der Subgruppenbeschreibungen durchsuchen. Die Auffälligkeit einer Subgruppe wird dabei durch eine sogenannte „Qualitätsfunktion“ gemessen, die auffälligeren Subgruppen einen höheren Wert zuordnet als weniger auffälligen Subgruppen. Soll die Subgruppensuche auf verteilten Daten angewendet werden, so hängt die Qualität aller Subgruppen von allen lokalen Datenbeständen ab, d.h. die Berechnung der Qualität jeder Subgruppe muss verteilt durchgeführt werden. Um zu gewährleisten, dass bei dieser Berechnung keine weitergehenden Informationen über die lokalen Datenbestände verraten werden, müssen diese Berechnungen durch ein sicheres Teilprotokoll abgesichert werden. Tatsächlich lässt sich die Berechnung der Qualität einer Subgruppe auf die verteilte Summenberechnung zurückführen, so dass ein Protokoll ähnlich dem oben besprochenen ver-wendet werden kann [Lem09].

Die Verwendung eines sicheren Protokolls für eine Teilaufgabe reicht jedoch im Allgemeinen nicht aus, um die Sicherheit des Gesamtprotokolls zu gewährleisten. Im Falle der Subgruppensuche muss noch vermieden werden, dass den Teilnehmern die Qualität von Subgruppen offengelegt wird, die nicht Teil des Ergebnisses sind. Ein Ansatz ist, zunächst nur das Maximum aller Subgruppenqualitäten zu berechnen, um dann in einem zweiten Schritt nach Subgruppen mit einer solchen Qualität zu suchen.

Data Mining Verfahren bieten die Chance, interessante Informationen in großen Datenbeständen zu finden. Zugleich wirft der Einsatz dieser Verfahren aber auch Fragen des Datenschutzes auf, falls die zugrundeliegenden Daten sensible Informationen enthalten. In diesem Artikel wurden verschiedene Ansätze des Privacy-Preserving Data Mining vorgestellt, um eine automatische Datenanalyse bei gleichzeitiger Berücksichtigung von Datenschutzaspekten zu ermöglichen.

Privacy-Preserving Data Mining kann sowohl beim Zugriff auf die Daten als auch bei der Berechnung des Ergebnisses ansetzen. Erfahrungen in der praktischen Umsetzung zeigen allerdings auch, dass die Benutzung einer Trusted Third Party - d.h. einer unabhängigen Partei, die die Datenanalyse auf klassischem Wege durchführt und sich vertraglich verpflichtet, keine sensitiven Informationen herauszugeben - in vielen Fällen eine akzeptable, wenn auch weniger sichere Option ist. In einem konkreten Data Mining Szenario sind daher immer die Anforderungen an die Sicherheit gegenüber der Einfachheit und Effizienz der Lösung abzuwägen.

Zugleich soll an dieser Stelle aber betont werden, dass das Thema Datenschutz in seiner vollen rechtlichen und ethischen Dimension nicht rein algorithmisch gelöst werden kann. Dennoch kann Privacy-Preserving Data Mining hierzu einen wichtigen Beitrag leisten, z.B. indem es die Grenzen der aus einem Datensatz extrahierbaren Informationen genauer beleuchtet.

[Atz08] M. Atzori, F. Bonchi, F. Giannotti and D. Pedreschi: Anonymity preserving pattern discovery The VLDB Journal, 2008

[Lem09] Benedikt Lemmen: Subgruppensuche auf verteilten und datenschutzsensiblen Daten Diplomarbeit an der Uni Bonn, 2009

[Lin04] Y. Lindell and B. Pinkas: A proof of Yao's protocol for secure two-party computation Technical report, 2004

[Pin03] B. Pinkas: Cryptographic Techniques for Privacy-Preserving Data Mining SIGKDD Explorations, 2003. 

[Sam01] P. Samarati: Protecting Respondents' Identities in Microdata Release IEEE Transactions on Knowledge and Data Engineering, 2001

[Sch09] J. Schmidt, A. Hapfelmeier, M. Mueller, R. Perneczky, A. Kurz, A. Drzezga und S. Kramer: Interpreting PET scans by structured patient data: a data mining case study in dementia research Knowledge and Information Systems, 2009

[Wro97] S. Wrobel: An algorithm for multi-relational discovery of subgroups Proceedings of the First European Symposion on Principles of Data Mining and Knowledge Discovery, 1997

[Yao82] Andrew C. Yao: Protocols for secure computations. Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

Henrik Grosskreutz, Benedikt Lemmen,  Stefan Rüping
Fraunhofer iais, St.Augustin bei Bonn
E-Mail: vorname.zuname(at)aisi.fraunhofer.de

© 2010 Informatik Spektrum, Springer-Verlag Berlin Heidelberg