Geekly articles weekly

Mathematik zum Schutz der Privatsphäre: Ein neuer Ansatz zur Datensicherheit

Als medizinische Forscher aus Massachusetts 1997 damit begannen, Zugang zu den Krankenakten der Beamten zu gewähren, entfernte die Regierung die Namen der Patienten, ihre Adressen und Sozialversicherungsnummern aus den Listen. Der damalige Gouverneur William Weld versicherte der Öffentlichkeit, dass es unmöglich sei, die Identität durch Ernennung wiederherzustellen.

Einige Tage später traf ein Brief von einem Studenten des Massachusetts Institute of Technology in Welds Büro ein. Auszüge aus der Gesundheitskarte des Gouverneurs waren dem Umschlag beigefügt.

Obwohl die offensichtlichen Kennungen entfernt wurden, beschlossen die Beamten, das Geburtsdatum, das Geschlecht und die Postleitzahl (Postleitzahl) zu hinterlassen. Nach dem Vergleich dieser Daten mit Sprachaufzeichnungen konnte Latanya Sweeney die Krankenakte von Weld berechnen.

Sweeneys Arbeit und andere Durchbrüche im Bereich Datenschutz in den letzten 15 Jahren werfen Sicherheitsbedenken für angeblich anonyme Daten auf.

"Wir haben festgestellt, dass die Intuition der Menschen, welche Daten als privat zu betrachten sind, nicht gut funktioniert", sagt Frank McSherry von Microsoft Research Silicon Valley. "Computer verbessern ständig ihre Fähigkeit, einzelne Daten aus einer Reihe von Informationen zu extrahieren, die der Laie als sicher erachten würde."

Das Studium Ihrer Krankengeschichte kann Ihnen helfen, die Gene zu finden, die für das Alzheimer-Risiko verantwortlich sind, die Anzahl der Fehler in Krankenhäusern zu verringern oder das beste Medikament für eine Krankheit zu finden. Die Frage ist nur, wie man all diese Daten erhält, ohne persönliche Informationen preiszugeben. Eine zehnjährige Studie zu diesem Thema nähert sich bereits einer universellen Lösung.

Dieser Ansatz wird als "differenzierter Datenschutz" bezeichnet und ermöglicht es Ihnen, Daten zu veröffentlichen und gleichzeitig persönliche Informationen zu schützen. Der Datendifferenzierungsalgorithmus ermöglicht es Forschern, jede Abfrage an eine Datenbank mit vertraulichen Informationen zu formulieren und eine „unscharfe“ Antwort so zu erhalten, dass keine persönlichen Daten angezeigt werden - selbst wenn Daten einer bestimmten Person in dieser Datenbank vorhanden sind.

"Die Idee ist, dass Sie Ihre Daten ohne Risiko verwenden können", sagt Cynthia Dvork von Microsoft Research Silicon Valley. Dvork führte 2005 mit Hilfe von McSherry, Cobby Nissim und Adam Smith das Konzept des Differential Privacy (RP) ein.

Die Methode behält sich das Recht auf „plausible Ablehnung“ vor, sagt Avrim Blum von der Carnegie Mellon University. „Wenn ich so tun möchte, als ob meine persönlichen Daten anders sind als die, die ich tatsächlich habe, kann ich das tun. Die Ausgabe des RP-Mechanismus wird sich in der Praxis nicht wesentlich unterscheiden, egal ob er das echte oder das falsche Ich enthält - also kann ich alles ablehnen, was ich will.

Ein so hohes Maß an Privatsphäre scheint unerreichbar. Tatsächlich gibt es keinen nützlichen RP-Algorithmus, der ein völlig identisches Ergebnis liefert, wenn Sie Ihre realen oder fiktiven Daten bereitstellen. Sie können jedoch zulassen, dass die Algorithmen nahezu identische Daten erzeugen. Der Grad der Differenz ist kalibriert und stellt eine Quantifizierung der Privatsphäre dar. Personen oder Gemeinschaften können entscheiden, welcher Wert dieses Parameters einem akzeptablen Grad an Datenschutzverlust entspricht, und dann die geeigneten Algorithmen auswählen.

Datenschutzfachleute haben eine breite Palette von RP-Algorithmen entwickelt, um unterschiedliche Daten zu verarbeiten und unterschiedliche Fragen zu beantworten. Der größte Teil der Arbeit ist für Menschen, die keine Experten auf diesem Gebiet sind, schwer wahrzunehmen. Daher entwickeln Wissenschaftler standardisierte Computersprachen, mit denen nicht nur Experten sensible Daten auf RP-Weise veröffentlichen können, indem sie einfach ein einfaches Programm schreiben. "RP ist eine vielversprechende und sehr interessante Technologie", sagt Aaron Roth, Informatikspezialist an der University of Pennsylvania.


Das OnTheMap Census Committee verwendet unterschiedliche Datenschutzbestimmungen, indem es Daten veröffentlicht, jedoch keine persönlichen Informationen preisgibt

Nadel im Heuhaufen


Es scheint, dass Sie zur Lösung von Datenschutzproblemen nur allgemeine Daten veröffentlichen müssen, die sich auf große Personengruppen beziehen. Aber auch dieser Ansatz ist mit einer Verletzung der Integrität personenbezogener Daten behaftet.

Angenommen, Sie müssen herausfinden, ob der Autor an Diabetes leidet, und Sie wissen, dass sich meine Daten in der Datenbank befinden. Man könnte die Ergebnisse von zwei Abfragen subtrahieren: "Wie viele Personen haben Diabetes in der Datenbank" und "Wie viele Personen in der Datenbank mit einem anderen Namen als Eric Clarreich haben Diabetes."

Die Kombination von zwei dieser Abfragen verletzt meine Privatsphäre. Es ist jedoch nicht immer klar, welche bestimmten Kombinationen von Fragen die Privatsphäre verletzen können. Das Finden solcher Kombinationen ist eine NP-vollständige Aufgabe, dh es gibt keinen effektiven Computeralgorithmus zum Verfolgen solcher „Angriffe“.

Im Jahr 2008 zeigten die Forscher die Gefahr, die aggregierten Informationen aus der allgemeinen Genforschung zu veröffentlichen - eines der wichtigsten Instrumente, um die Abhängigkeit von Diabetes von Genen zu ermitteln. Diese Studien umfassen die Dekodierung der Gene der Testgruppe von 100 bis 1000 Patienten mit derselben Krankheit, gefolgt von der Berechnung der durchschnittlichen Häufigkeit, mit der eine der 100.000 Mutationen auftritt. Wenn eine der Mutationen in der Gruppe viel häufiger auftritt, wird festgestellt, dass sie möglicherweise mit der Krankheit assoziiert ist.

Ein Forscherteam unter der Leitung von Niels Homer, der zu diesem Zeitpunkt ein Doktorand an der University of California war, zeigte, dass man in vielen Fällen, wenn man das Genom des Patienten kennt, herausfinden kann, ob er Teil der Genomtestgruppe war. Danach widerrief der Verband der medizinischen Institute das Dekret, dass die in genetischen Studien gewonnenen Daten veröffentlicht werden sollten.

Die Forscher kamen 2011 zu einer noch überraschenderen Schlussfolgerung: Es ist möglich, persönliche Informationen über Einkäufe zu extrahieren, die von einem Empfehlungssystem mit Amazon geleitet werden und Ergebnisse wie „Wer hat B und C gekauft und auch gekauft“ liefern. In mehreren Fällen konnten Forscher feststellen, dass ein bestimmter Käufer einen bestimmten Artikel an einem bestimmten Tag gekauft hat, bevor er eine Bewertung zu diesem Artikel abgegeben hat, indem er Änderungen in den Empfehlungen beobachtet und diese mit den Bewertungen der gekauften Artikel verglichen hat.

In allen Fällen scheinen Datenschutzmaßnahmen angemessen zu sein, solange sie nicht ausreichen. Zu diesem Zeitpunkt wurde jedoch bereits ein neuer Ansatz zum Schutz der Privatsphäre ausgearbeitet, bei dem nach der Antwort auf die Hauptfrage gesucht wurde: Was bedeutet es, die Privatsphäre zu schützen?

Die Privatsphäre zweier Welten


Wenn Forscher die Patientendatenbank untersuchen und einen Zusammenhang zwischen Rauchen und irgendeiner Form von Krebs feststellen, schützt die unterschiedliche Privatsphäre eine Person, die an einem öffentlichen Ort raucht, nicht vor dem Etikett einer Person mit einem erhöhten Krankheitsrisiko. Aber wenn Rauchen das Geheimnis einer Person ist, das in der Basis versteckt ist, wird RP sie beschützen.

"Unterschied" bedeutet, den Unterschied zweier Welten zu berücksichtigen: In einer von ihnen können Sie Ihre persönlichen Daten in die Datenbank aufnehmen, in der anderen nicht. Die beiden Welten werden nicht absolut identisch sein, aber sie können so ähnlich wie möglich gemacht werden, und es wird fast unmöglich sein, zwischen ihnen zu unterscheiden. Dies ist der Zweck des RP.

RP konzentriert sich auf Algorithmen, die Daten ausgeben, Anfragen an die Datenbank empfangen und Antworten ausgeben - nicht genau, aber zufällig geändert. Wenn Sie dieselbe Frage auf zwei Grundlagen stellen, die sich nur in den Daten für eine Person unterscheiden, erhalten Sie im Wesentlichen die gleichen Antworten.


RP-Darstellung des Standorts von Benutzern, die in einer Suchmaschine nach dem Wort „Cricket“ suchen

Genauer gesagt sollte für jede mögliche Antwort die Wahrscheinlichkeit des Eingangs für beide Datenbanken gleich sein. Das Verhältnis dieser beiden Wahrscheinlichkeiten sollte auf eine Zahl R nahe der Einheit begrenzt werden. Je näher R an 1 liegt, desto schwieriger ist es für einen Angreifer herauszufinden, ob er Informationen von Basis A oder von Basis B erhält, und desto geschützter ist die Person X. Da der Angreifer nicht wissen kann, ob die von ihm empfangenen Informationen Informationen zu X enthalten, kann er dies nicht Verstehen Sie, welche Daten sich auf X beziehen.

RP-Forscher sprechen normalerweise über den Logarithmus von R und bezeichnen ihn mit Ɛ. Der Parameter quantifiziert den Verlust personenbezogener Daten. Je näher Ɛ an Null liegt, desto besser schützt der Algorithmus die Privatsphäre.

Um zu verstehen, wie der RP-Algorithmus konstruiert werden kann, betrachten wir das einfachste Beispiel eines solchen Algorithmus. Er verwendet ein Szenario, in dem der Fragesteller nur quantitative Abfragen durchführen kann. Zum Beispiel: "Wie viele Personen in der Datenbank haben die Eigenschaft C?"

Angenommen, die eigentliche Antwort auf eine der Fragen lautet 157. Der RP-Algorithmus addiert „Rauschen“ - addieren oder subtrahieren Sie eine Zufallszahl, bevor Sie eine Antwort ausgeben. Als Ergebnis erhalten wir 153, 159 oder 292. Der Fragesteller kennt die vom Algorithmus verwendete Wahrscheinlichkeitsverteilung, sodass er weiß, wie verzerrt das tatsächliche Ergebnis ist (andernfalls wäre die Rückgabe völlig nutzlos). Aber welche Art von Zufallszahl der Antwort hinzugefügt wurde, weiß er nicht.

Die Verteilungsformel muss sorgfältig ausgewählt werden. Um zu verstehen, welche Distribution den Datenschutz garantiert, stellen wir uns vor, dass ein hartnäckiger Fragesteller versucht herauszufinden, ob ich in der Datenbank bin. Er fragt: "Wie viele Personen namens Eric Clarreich sind in der Datenbank?" Angenommen, er erhält eine Antwort von 100. Da dieser Name selten ist, erkennt er, dass die Antwort tatsächlich 0 oder 1 war. Er hat zwei Möglichkeiten:

A) Die Antwort ist 0, und der Algorithmus addiert 100 als Rauschen;
B) Die Antwort ist 1, und der Algorithmus fügte hinzu 99 Die

Wahrscheinlichkeit, 100 und 99 zu wählen, sollte gleich sein. Dann kann der Fragesteller nicht zwischen diesen beiden Fällen unterscheiden. Genauer gesagt sollte das Verhältnis dieser beiden Wahrscheinlichkeiten ein vorbestimmtes R nicht überschreiten. Eine solche Bedingung sollte nicht nur für die Paare 100 und 99, sondern auch für zwei beliebige aufeinanderfolgende Zahlen beibehalten werden.

Diese Eigenschaft hat die Laplace-Verteilung. Sein scharfer Peak fällt auf Null, und dann nimmt der Graph in beide Richtungen allmählich ab. Dafür ist die Bedingung für das Vorhandensein der Zahl R (Verteilungsbreite) erfüllt, so dass für zwei aufeinanderfolgende Zahlen das Verhältnis ihrer Wahrscheinlichkeiten R ist.

Für jede Breite gibt es eine mögliche Laplace-Verteilung. Daher können Sie mit der Breite spielen, um eine Verteilung zu erhalten, die genau den Grad an Privatsphäre bietet, den wir benötigen. Für eine starke Privatsphäre ist die Verteilung relativ breit und flach. Zahlen, die weit von 0 entfernt sind, fallen mit fast der gleichen Wahrscheinlichkeit aus wie Zahlen nahe Null. Die Daten werden ziemlich unscharf.

Natürlich gibt es eine Konfrontation zwischen Privatsphäre und Nutzen. Je mehr Privatsphäre Sie benötigen, desto mehr Lärm müssen Sie hinzufügen und desto weniger nützlich ist die Antwort. Bei Verwendung der Laplace-Verteilung ist die Menge des hinzugefügten Rauschens wieder Ɛ. Wenn der Datenschutzparameter 0,01 ist, verwischt der Algorithmus die quantitativen Indikatoren um etwa 100.

Je größer der Datensatz, desto weniger wirkt sich die angegebene Unschärfe auf das Dienstprogramm aus. In einer Datenbank mit Hunderten von Datensätzen stört eine Unschärfe von 100 mehr als in einer Datenbank mit Millionen von Datensätzen. Laut Dvork bietet der Algorithmus für Daten im Internet, dh Hunderte von Millionen, bereits ausreichend Datenschutz für den praktischen Gebrauch.

Und das „Rauschen“ von Laplace ist nur die erste Stufe der Implementierung des RP. Die Forscher haben bereits eine Vielzahl komplexerer Algorithmen entwickelt, bei denen das Verhältnis von Nutzen und Datenschutz in bestimmten Situationen das von Laplace übersteigt.

„Die Menschen finden immer Möglichkeiten, sich zu verbessern, und es gibt noch Raum für Verbesserungen“, sagt Dvork. In Bezug auf bescheidenere Datensätze als das Internet sagte sie: „Es gibt Algorithmen für viele Aufgaben.“

Mit dem RP-Algorithmus müssen Probleme nicht sorgfältig auf Datenschutzverletzungen analysiert werden. Dieser Schutz ist bereits in den Algorithmus integriert. Da Fragen, die sich auf ihre eigenen Angelegenheiten auswirken, in der Regel auf eine geringe Anzahl bestimmter Personen zurückzuführen sind und Fragen anderer Art das Verhalten großer Gruppen untersuchen, hat die Menge an zusätzlichem Lärm, der einzelne Merkmale negiert, nur geringe Auswirkungen auf die Antworten auf berechtigte Fragen.

Mit RP verschwinden die Probleme von Datenforschern wie Kreuzvergleiche mit externen Quellen. Der mathematische Ansatz erwartet nicht, dass der Angreifer nur über begrenzte externe Informationsquellen verfügt.

"Der RP-Ansatz impliziert, dass der Angreifer allmächtig ist", sagt McSherry. - Selbst wenn der Angreifer nach 100 Jahren zurückkehrt und ständig Ideen und Computertechnologien sammelt, kann er nicht herausfinden, ob Sie sich in der Datenbank befinden. RP ist vor der Zukunft geschützt. “

Grundlegendes Grundelement


Bisher haben wir eine Situation in Betracht gezogen, in der jemand Anfragen an die Datenbank mit einer Nummer als Antwort stellt. Die Realität ist jedoch komplizierter. Forscher möchten der Datenbank viele Fragen stellen. Und im Laufe der Zeit gelangen Teile Ihrer persönlichen Daten in verschiedene Datenbanken, von denen jede Daten liefert, ohne den Rest zu fragen.

RP bietet eine genaue und einfache Möglichkeit, die allgemeine Bedrohung der Privatsphäre zu bewerten, wenn Forscher allen Datenbanken, in denen Ihre Daten vorhanden sind, mehrere Fragen stellen. Angenommen, Ihre Daten befinden sich in zwei Datenbanken und diese Daten werden gemäß Algorithmen angegeben, die die Datenschutzparameter Ɛ1 und Ɛ2 bereitstellen. Die Gesamtmenge der durchgesickerten persönlichen Informationen beträgt nicht mehr als Ɛ1 + Ɛ2. Die gleiche Formel gilt für eine einzelne Datenbank mit mehreren Abfragen. Bei m Abfragen wird das Leck über m * Ɛ begrenzt.

Theoretisch kann ein Datenbankkurator Forschern ermöglichen, so viele Fragen zu stellen, wie sie möchten, und jeder Antwort die erforderliche Menge an Laplace-Rauschen hinzufügen, damit die Gesamtmenge der durchgesickerten persönlichen Daten einen bestimmten Grenzwert nicht überschreitet.

Es stellt sich heraus, dass die Grenze für numerische Antworten nicht so kritisch ist. Viele andere Abfragen können so geändert werden, dass sie quantitativ werden. Wenn Sie beispielsweise eine Liste mit Hunderten der beliebtesten Namen für 2012 geborene Babys erstellen müssen, können Sie beispielsweise eine Reihe von Fragen stellen wie „Wie vielen Kindern wurden Namen gegeben, die mit A beginnen?“ Und die Ergebnisse verarbeiten.

„Eines der ersten Ergebnisse des Lernens von maschinellem Lernen besagt, dass alles, was im Prinzip gelernt werden kann, mithilfe numerischer Abfragen gelernt werden kann“, sagt Aaron Roth. „Solche Anforderungen sind kein Spielzeug für sich, sondern ein grundlegendes Grundelement“, dh Bausteine, auf deren Grundlage komplexere Algorithmen erstellt werden können.

Aber es gibt einen Haken. Je mehr Fragen wir stellen können, desto mehr Rauschen wird zu jeder Antwort hinzugefügt. Schauen wir uns ein Beispiel mit Namen an. Wenn wir uns entscheiden, den maximalen Datenschutzaufwand 0.01 auf 0,01 zu begrenzen und die Namen 10.000 betragen, beträgt das Datenschutzlimit für jede Ausgabe Ɛ / 10.000 oder 0,000001. Der Geräuschpegel beträgt 10.000 / Ɛ oder 1.000.000 - und dieser Pegel eliminiert einfach die tatsächlichen Ergebnisse.

Mit anderen Worten, der "frontale" Ansatz mit dem Hinzufügen von Laplace-Rauschen zu jeder Antwort ist durch die Anzahl möglicher Fragen begrenzt. Um Abhilfe zu schaffen, mussten Programmierer geeignetere Grundelemente entwickeln - algorithmische "Bausteine", mit deren Hilfe sie angesichts der Struktur einer bestimmten Basis und Aufgabe mehr Fragen genauer beantworten können.

Beispielsweise stellte Smith 2005 fest, dass die Aufgabe mit Namen eine spezielle Struktur aufweist: Durch das Entfernen von Informationen zu einer Person aus der Datenbank wird die Antwort für nur einen von 10.000 Namen geändert. Daher können wir jeder Antwort nicht mehr als 1 / Ɛ Rauschen anstelle von 10.000 / Ɛ hinzufügen, und die Vertraulichkeit der Antwort bleibt innerhalb unserer Grenze. Ein solches Grundelement kann auf jede "Histogramm" -Abfrage angewendet werden, dh auf eine Abfrage, wie viele Personen in eine von mehreren sich gegenseitig ausschließenden Kategorien fallen, z. B. Namen.

Als Smith dem Dwork davon erzählte, "freute sich etwas in mir", sagt das Dwork. "Ich habe festgestellt, dass wir die Struktur der Anfrage oder Berechnung verwenden und eine viel genauere Antwort erhalten können."

Seitdem haben Informatiker eine große Bibliothek solcher Grundelemente entwickelt. Und da die additive Regel erklärt, was beim Kombinieren von Algorithmen mit dem Datenschutz geschieht, können Programmierer diese „Bausteine“ zu komplexen Strukturen zusammenfügen und gleichzeitig die Einschränkung des Datenschutzverlusts überwachen.

Um den Zugriff auf das RP-System für Personen zu vereinfachen, die keine Experten sind, arbeiten mehrere Gruppen an der Erstellung einer Programmiersprache, mit der wir von den mathematischen Grundlagen von Algorithmen abstrahieren können.


PINQ - eines der Beispiele für PL für RP

Programmiersprachen für die Arbeit mit unterschiedlichen Datenschutzbestimmungen wie PINQ bieten eine Schnittstelle für vertrauliche Daten und ermöglichen es Ihnen, Fragen zu diesen zu stellen und Antworten zum Schutz der Privatsphäre zu optimieren. "Wenn Sie für einen Datensatz verantwortlich sind, müssen Sie sich keine Gedanken darüber machen, was die Leute damit machen, während ihre Anfragen mit diesem PL gestellt werden", sagt McSherry, der die PINQ-Sprache erstellt hat. "Das Programm garantiert die Sicherheit von Abfragen."

Nicht erneuerbare Ressource


Da die einfache additive Regel für Ɛ die genaue Obergrenze für den Verlust der Privatsphäre festlegt, wenn verschiedene Datenbanken, die Ihre Daten enthalten, Antworten auf Fragen liefern, verwandelt diese Regel laut McSherry die Privatsphäre in eine Währung.

Wenn Sie beispielsweise entscheiden, welche Einschränkung des Verlusts der Privatsphäre für Sie persönlich für Ihr ganzes Leben akzeptabel ist, können Sie diese Privatsphäre "ausgeben" - gegen Geld eintauschen oder ein gutes Forschungsprojekt unterstützen. Jedes Mal, wenn Sie die Verwendung Ihrer Daten in einer neuen Version von Informationen zulassen, wissen Sie, wie hoch Ihr "Budget" für den Datenschutz ist.

Der Kurator des Datensatzes kann entscheiden, wie er die Menge an Datenschutz ausgeben möchte, die er freigeben möchte. Berücksichtigen Sie beispielsweise Vorschläge aus Forschungsprojekten, in denen nicht nur die verfügbaren Anforderungen, sondern auch die in den Projekten verwendete Menge an Datenschutz beschrieben werden. Anschließend kann der Kurator auswählen, welche Projekte das vorhandene „Budget“ dieser Informationen am besten nutzen. Nachdem das Budget ausgegeben wurde, wird der Datensatz geschlossen.

"Datenschutz ist eine nicht erneuerbare Ressource", sagt McSherry. "Sobald Sie es ausgeben, verschwindet es."

Auf die Frage, welcher Wert Ɛ eine akzeptable Einschränkung für den Verlust der Privatsphäre darstellt, sollte die Gesellschaft antworten, nicht die Programmierer. Und jeder kann seine eigene Antwort haben. Und während die Aussicht, einer immateriellen Sache wie der Privatsphäre ein Preisschild zuzuweisen, entmutigend erscheint, gibt es bereits Analoga dazu.

"Es gibt eine andere Ressource mit den gleichen Eigenschaften - die Uhr Ihres Lebens", sagt McSherry. "Ihre Anzahl ist begrenzt, und nachdem Sie sie ausgegeben haben, verschwinden sie." Aber da wir eine Währung und einen Arbeitsmarkt haben, hat sich unsere Gesellschaft ausgedacht, wie man der menschlichen Zeit ein Preisschild zuweist. Man kann sich vorstellen, wie das Gleiche mit der Privatsphäre passieren wird. “

Source: https://habr.com/ru/post/de398011/

More articles:


All Articles