Welche einfachen und wirksamen Techniken zur Verschleierung von Punkten gibt es?

14

Wir erstellen eine Website, auf der Standortinformationen (Punkte) von Benutzern gesammelt werden. Wir erforschen Techniken, um die Privatsphäre der Benutzer zu schützen (z. B. teilen Benutzer häufig ihre Privatadresse, die vertraulich ist). Eine Option, die mir in den Sinn kam, besteht darin, die Punkte zu verschleiern oder zu "hacken", bevor sie in der Datenbank gespeichert werden. Auf diese Weise müssen diese sensiblen Daten überhaupt nicht mehr gespeichert werden.

Unsere Grundvoraussetzungen sind meines Erachtens:

  1. Bei einem einzelnen verschleierten Punkt ist es nicht möglich, den ursprünglichen Punkt innerhalb von (etwa) einem Kilometer abzuleiten, selbst wenn alle mit dem Punkt verbundenen Metadaten vorhanden sind (dh wenn die gesamte Datenbank gefährdet ist).

  2. Bei einer willkürlich großen Menge von verschleierten Punkten, die demselben ursprünglichen Punkt entsprechen, ist es immer noch nicht möglich, den ursprünglichen Punkt abzuleiten. (Eine einfache Methode wäre beispielsweise, dem ursprünglichen Punkt einen zufälligen Vektor hinzuzufügen. Wenn Sie dies jedoch genügend oft tun, werden die verschleierten Punkte um den ursprünglichen Punkt gruppiert.)

Es wäre schön, wenn verschiedene statistische Eigenschaften erhalten blieben, obwohl ich nicht weiß, welche Eigenschaften in dieser Phase wichtig sind. Zum Beispiel wäre es mir lieber, wenn verschleierte Punkte auf "natürliche" Weise verstreut würden, anstatt sich in einem Gitter anzusammeln. Datenschutz ist jedoch wichtiger als dies.

Reid
quelle
In Ihren Anforderungen wird nicht erwähnt, welche Genauigkeit Sie beibehalten möchten. Sie konzentrieren sich nur auf die Verschleierungsanforderungen. Der folgende Algorithmus erfüllt die von Ihnen angegebenen Anforderungen trivial, ist jedoch ziemlich wertlos: Ordnen Sie jeden Punkt 0 ° N, 0 ° Ost zu. Vermutlich möchten Sie auch ein Kriterium erfüllen, zum Beispiel, dass der verschleierte Punkt innerhalb von x km vom tatsächlichen Punkt liegt.
Llaves
Eine zweite Frage: Sie erwähnen Metadaten und können den wahren Punkt rekonstruieren, wenn die gesamte Datenbank kompromittiert ist. Wenn Sie mit den Metadaten keine verschleierten Punkte identifizieren können, die demselben "wahren Punkt" zugeordnet sind, wie kann dann jemand den "wahren Punkt" aus wiederholten Zufallsstichproben rekonstruieren, wenn Sie sie nicht miteinander verknüpfen können? Wenn Sie jedoch anhand der Metadaten die Punkte zuordnen können, geben Sie einfach denselben verschleierten Wert zurück, der alle vorherigen Male zurückgegeben wurde, wenn Sie aufgefordert werden, die Position eines bereits verschleierten Punkts erneut zu melden.
Llaves
Müssen Sie in der Lage sein, den tatsächlichen Standort aus den gehashten Daten neu zu erstellen, oder werden Sie nur dazu verwendet, um zu bestätigen, dass sich eine Person dort befindet, wo sie sich befindet? Wenn es das letztere ist, ein One-Way-Hash, Hashing ein Salz + die WKT der Geometrie würde ausreichen. Wenn es das erstere ist, müssen Sie irgendwo eine Funktion haben, um die inverse Transformation Ihrer Hash-Funktion durchzuführen - einen Zwei-Wege-Hash.
MerseyViking
Werden die Punkte im Rahmen des Service mit den Daten anderer Nutzer / anderer Datensätze verglichen?
Matthew Snape
@Llaves, ich mache eigentlich: "Innerhalb eines Kilometers oder so". Aber ich würde hoffen, dass der Verschleierungsgrad ein Parameter für den Algorithmus ist. Ja, in Bezug auf Ihren zweiten Kommentar ermöglichen die Metadaten die Zuordnung von Punkten (z. B. kann ein Benutzer denselben Punkt mehrmals eingeben). Und ein Algorithmus, der bei gleichem Ursprungspunkt denselben verschleierten Punkt ergibt, ist in Ordnung. aber wenn der Algorithmus das nicht macht, kann ich den ursprünglichen Punkt nicht wiederherstellen (das ist der ganze Grund für die Frage), um zu testen, ob derselbe verschleierte Punkt verwendet werden sollte.
Reid

Antworten:

6

Schauen Sie sich an:

Abgeordneter Armstrong, Rushton G, Zimmerman DL. Geografische Maskierung von Gesundheitsdaten zur Wahrung der Vertraulichkeit . Stat Med.1999; 18: 497–525.

( Zitat , Volltext )

Sie diskutieren verschiedene 'Geomasken' für Punktdaten, einschließlich Verschiebung, Rotation, zufällige Störung und Aggregation. Obwohl sie keine spezifischen technischen Lösungen für die Implementierung diskutieren, gibt es nützliche Hinweise darauf, was Sie bei jedem Ansatz gewinnen / verlieren.

Weitere theoretische Überlegungen finden Sie in meiner Antwort auf die Frage zu einem ähnlichen Thema.

radek
quelle
2
Nizza Hinweis, es ist ein aktives Feld, also sind viele vorhanden. Ich habe einen Übersichtsartikel ( Mathews & Harel, 2011 ) in einer anderen Frage empfohlen . Ich glaube auch, dass das International Journal of Health Geographics von Zeit zu Zeit Artikel enthält (siehe meine citeulike-Bibliothek mit dem Geomaskentag ). Ich bin jedoch nicht auf Werkzeuge gestoßen, um die Arbeit zu erledigen, wahrscheinlich ein nützliches Unterfangen.
Andy W
1
@ AndyW Danke für die Hinweise Andy. In der Tat wird das Problem mit der wachsenden Menge an hochauflösenden Geodaten, die in der öffentlichen Gesundheit / räumlichen Epidemiologie verwendet werden, immer relevanter. Ich hatte das gleiche Gefühl, dass praktische Lösungen immer noch weit hinter theoretischen zurückbleiben - definitiv ein Ort, an dem einige nette Entwicklungen gemacht werden können!
Radek
1

Sie können versuchen, Ihre Punkte mit Perlin-Rauschen zufällig zu verschieben, aber mit dem Vorteil, dass Punkte, die nahe beieinander liegen, nahe beieinander bleiben, aber diese Ähnlichkeit mit der Entfernung abnimmt. Wenn die Rauschfunktion auf 0 zentriert ist, sollte die statistische Analyse immer noch ähnliche Daten wie die Quelle zurückgeben, da Perlin-Rauschen (insbesondere die Version 2002) eine grobe Gauß-Verteilung ist.

MerseyViking
quelle
Wenn ich viele Kopien desselben Punktes verschiebe, kann der ursprüngliche Punkt dann durch Analysieren der verschobenen Punkte wiederhergestellt werden?
Reid
So wie ich es mir vorgestellt habe, würden Sie die Koordinaten des Punktes als Nachschlagewerk für die Rauschfunktion verwenden. Zwei identische Punkte würden also zusammenfallen. Sie können einen dritten Wert verwenden, z. B. das Datum, an dem der Punkt erstellt wurde, als Referenz für eine 3D-Perlin-Rauschfunktion. Dann (und ich bin kein Statistiker) wäre es unpraktisch, die Quelldaten zu rekonstruieren, es sei denn, der Zufallskeim und das Ausmaß des von Ihnen gewählten Rauschens waren bekannt. Selbst dann bin ich mir nicht sicher, ob es praktisch machbar wäre.
MerseyViking
Ah, also machst du daraus eine Hash-Funktion. Es kann jedoch unsicher sein anzunehmen, dass der zufällige Samen und die zufällige Schuppe geheim bleiben; Ich gehe davon aus, dass der Server vollständig kompromittiert wurde.
Reid
Puh! OK, dann mag ich eine Herausforderung :) Jetzt redest du wirklich über physische Sicherheit. Sie haben einen separaten externen Computer, um die Hashes zu generieren und über eine sichere Verbindung mit so etwas wie SSL zu senden. Sie können einen Watchdog auf einem oder beiden Servern so einrichten, dass der andere automatisch herunterfährt, wenn einer ausfällt oder Sie einen großen roten Knopf drücken. Wenn Sie Cloud-Instanzen verwenden würden, gäbe es keine praktische Möglichkeit, etwas von der anderen Instanz zu erhalten,
außer
Folglich sollten Sie nur so viel für die Datensicherheit ausgeben, wie die Daten wert sind. Es gibt viele Ebenen, die Sie Ihrem Sicherheitsmodell hinzufügen könnten, aber irgendwann müssen Sie genug sagen. Es lohnt sich vielleicht, diese Frage an eine der anderen SE-Sites zu richten.
MerseyViking
0

Dies ist vielleicht komplizierter und komplizierter als nötig, es kann jedoch ein Weg sein, den man nehmen muss:

Erstellen Sie ein einfaches Python-Skript, das Ihre ursprünglichen Eingabepunkte aufnimmt, sie um einen bestimmten zulässigen Verschleierungsabstand puffert, n zufällige Punkte mit den Puffern als Feature-Einschränkung erstellt (z. B. 100) und dann einen der Punkte mit a auswählt Pseudozufallszahlengenerator zur Verwendung als neuer verschleierter Punkt. Es wäre auch notwendig, für jede Verschleierung eine neue Pseudozufallszahl zu erstellen.

Abhängig von Ihrem Szenario kann dies in eine Toolbox gepackt und als GPS-Dienst mit einem REST-Endpunkt aufgerufen werden, sodass die Verschleierung an Speicherorten erfolgt und nur der verschleierte Punkt in Ihrer physischen Datenbank gespeichert wird.

Ein hoch
quelle
1
Dies setzt eine ArcGIS-Implementierung voraus, im OP wurde jedoch keine erwähnt. Trotzdem eine interessante Lösung!
blah238
3
Diese natürliche Lösung weist bei der Untersuchung einige potenzielle Mängel auf: (1) Es können mehrere unterschiedliche Punkte auf denselben Punkt abgebildet werden. (2) Es ist einfach, Punkte zu demaskieren, wie das OP zeigt. (3) Oft müssen Punkte in einem bestimmten geografischen Verhältnis zu verwandten Merkmalen stehen: z. B. sollten sich die Standorte von Häusern in der Nähe von Straßen und nicht in Seen oder Bahnhöfen befinden. Probleme wie diese machen das Problem wirklich schwierig, interessant und der GIS-Analyse würdig (andernfalls könnten die ursprünglichen Koordinaten beim erstmaligen Einfügen in die Datenbank nur zufällig verwackelt werden).
whuber
0

OK, also der Algorithmus, den wir betrachten, ist wie folgt:

  1. Runden Sie den Punkt auf ein 200-Meter-Raster ab (um Abweichungen bei der Geokodierung auszugleichen).
  2. Hash den Text der Punktkoordinaten mit einem kryptografischen Hashing-Algorithmus (z. B. SHA2).
  3. Ersetzen Sie die niederwertigen Bits der Punktkoordinaten (bis zum gewünschten Verschleierungsgrad von 1 km) durch die Ergebnisse der Hash-Funktion.
Reid
quelle