Jakie proste, skuteczne techniki zaciemniania punktów są dostępne?

14

Tworzymy stronę internetową, która będzie zbierać informacje o lokalizacji (punkty) od użytkowników. Badamy techniki, aby zachować prywatność lokalizacji użytkowników (np. Często użytkownicy udostępniają swój adres domowy, który jest poufny). Jedną z opcji, która przyszła mi do głowy, jest zaciemnianie lub „mieszanie” punktów przed przechowywaniem ich w bazie danych, co eliminuje potrzebę przechowywania tych wrażliwych danych w ogóle.

Uważam, że nasze podstawowe wymagania to:

  1. Biorąc pod uwagę pojedynczy zaciemniony punkt, nie jest możliwe wyprowadzenie pierwotnego punktu w odległości (powiedzmy) kilometra, nawet biorąc pod uwagę wszystkie metadane związane z tym punktem (tj. Zakładając, że cała baza danych jest zagrożona).

  2. Biorąc pod uwagę dowolnie duży zestaw zaciemnionych punktów odpowiadających temu samemu punktowi pierwotnemu, nadal nie można uzyskać punktu początkowego. (Na przykład łatwą techniką byłoby dodanie losowego wektora do pierwotnego punktu, ale jeśli zrobisz to wystarczająco dużo razy, zaciemnione punkty skupią się wokół oryginalnego punktu).

Byłoby miło, gdyby zachowano różne właściwości statystyczne, choć nie wiem, które właściwości są ważne na tym etapie. Na przykład wolałbym, aby zaciemnione punkty rozpraszały się w „naturalny” sposób, zamiast gromadzić się w siatkę. Jednak prywatność jest ważniejsza niż to.

security Reid
źródło
Twoje wymagania nie wspominają o tym, jaką dokładność chcesz zachować, koncentrujesz się tylko na wymogu zaciemnienia. Poniższy algorytm w sposób trywialny spełnia wymienione wymagania, ale jest raczej bezwartościowy: zamapuj każdy punkt na 0 ° N, 0 ° wschód. Przypuszczalnie chcesz również spełnić pewne kryterium, np. Zaciemniony punkt znajduje się w odległości x km od rzeczywistego punktu.
Llaves,
Drugie pytanie: wspominasz o metadanych i jesteś w stanie zrekonstruować prawdziwy punkt, jeśli cała baza danych zostanie naruszona. Jeśli metadane nie pozwalają zidentyfikować zaciemnionych punktów związanych z tym samym „punktem prawdziwym”, to jak ktoś może zrekonstruować „punkt prawdziwy” z powtarzanych losowych próbek, jeśli nie można ich ze sobą powiązać? Z drugiej strony, jeśli metadane pozwalają na powiązanie punktów, wtedy gdy zostaniesz poproszony o ponowne zgłoszenie lokalizacji jakiegoś już zaciemnionego punktu, po prostu zwróć tę samą zaciemnioną wartość, która została zwrócona wszystkie poprzednie czasy.
Llaves,
Czy musisz być w stanie odtworzyć rzeczywistą lokalizację z zaszyfrowanych danych, czy może posłuży tylko do potwierdzenia, że ​​dana osoba jest tam, gdzie się podaje? Jeśli to drugie, wystarczy skrót jednokierunkowy, mieszanie soli + WKT geometrii. Jeśli jest to pierwsze, musisz mieć jakąś funkcję, aby wykonać odwrotną transformację swojej funkcji skrótu - dwukierunkowy skrót.
MerseyViking
Czy punkty będą porównywane z danymi innych użytkowników / innymi zestawami danych w ramach usługi?
Matthew Snape
@Llaves, tak naprawdę: „w odległości około kilometra”. Mam jednak nadzieję, że poziom zaciemnienia jest parametrem algorytmu. Jeśli chodzi o twój drugi komentarz, tak, metadane pozwalają na powiązanie punktów (np. Jeden użytkownik może wprowadzić ten sam punkt wiele razy). Algorytm, który daje ten sam zaciemniony punkt, biorąc pod uwagę ten sam oryginalny punkt, jest w porządku; ale jeśli algorytm tego nie robi, nie mogę odzyskać pierwotnego punktu (to jest cały powód pytania), aby sprawdzić, czy należy użyć tego samego zaciemnionego punktu.
Reid

Odpowiedzi:

6

Spójrz na:

MP Armstrong, Rushton G, Zimmerman DL. Geograficzne maskowanie danych zdrowotnych w celu zachowania poufności . Stat Med. 1999; 18: 497–525.

( cytat , pełny tekst )

Dyskutują o różnych „geomaskach” danych punktowych, w tym o przemieszczeniu, rotacji, przypadkowym zaburzeniu i agregacji. Chociaż nie omawiają konkretnych rozwiązań technicznych, jak to wdrożyć, istnieją przydatne wskazówki dotyczące informacji o tym, co zyskujesz / tracisz przy każdym podejściu.

Aby uzyskać więcej teoretycznych rozważań, zobacz moją odpowiedź na pytanie na podobny temat.

radek
źródło
2
Ładne odniesienie, jest to pole aktywne, więc dostępnych jest wiele. Poleciłem artykuł poglądowy ( Mathews i Harel, 2011 ) w innym pytaniu . Wierzę również, że International Journal of Health Geographics od czasu do czasu publikuje dokumenty (zobacz moją bibliotekę z cytatami z tagiem geomask ). Nie natknąłem się jednak na żadne narzędzia do wykonania tej pracy, prawdopodobnie przydatne przedsięwzięcie.
Andy W
1
@AndyW Dzięki za wskazówki Andy. Rzeczywiście - wraz z rosnącą liczbą geodanych o wysokiej rozdzielczości wykorzystywanych w epidemiologii zdrowia publicznego / epidemiologii przestrzennej problem staje się coraz bardziej istotny. Miałem to samo wrażenie, że praktyczne rozwiązania wciąż pozostają daleko w tyle za rozwiązaniami teoretycznymi - zdecydowanie miejsce, w którym można dokonać ciekawych zmian!
radek
1

Możesz spróbować użyć szumu Perlina, aby przesunąć punkty o dowolną liczbę, ale z tą zaletą, że punkty blisko siebie pozostaną blisko siebie, ale podobieństwo to maleje wraz z odległością. Jeśli funkcja szumu jest wyśrodkowana wokół 0, analiza statystyczna powinna nadal zwracać podobne dane jak w źródle, ponieważ szum Perlina (zwłaszcza wersja z 2002 r.) Jest z grubsza rozkładem Gaussa.

MerseyViking
źródło
Jeśli przesunę wiele kopii tego samego punktu, czy oryginalny punkt można następnie odzyskać, analizując przesunięte punkty?
Reid
Tak, jak to sobie wyobrażałem, użyłbyś współrzędnych punktu jako funkcji szumu. Tak więc dwa identyczne punkty pozostałyby zbieżne. Możesz użyć trzeciej wartości, powiedzmy datę utworzenia punktu jako wyszukiwanie funkcji szumu Perlina 3D. Następnie (i nie jestem statystykiem) rekonstrukcja danych źródłowych byłaby niepraktyczna, chyba że losowe ziarno i skala wybranego szumu byłyby znane. Nawet wtedy nie jestem pewien, czy byłoby to praktycznie wykonalne.
MerseyViking
Ach, więc zmieniasz ją w funkcję skrótu. Jednak założenie, że losowe nasiona i skala pozostają tajne, może być niebezpieczne; Zakładam, że serwer został całkowicie przejęty.
Reid
Uff! OK, więc lubię wyzwania :) Teraz naprawdę mówisz o bezpieczeństwie fizycznym. Masz oddzielną maszynę zewnętrzną do generowania skrótów, wysyłania ich za pośrednictwem bezpiecznego połączenia za pomocą czegoś takiego jak SSL. Możesz ustawić watchdoga na jednym lub obu serwerach tak, że jeśli jeden z nich ulegnie awarii lub naciśniesz duży czerwony przycisk, drugi automatycznie się wyłączy. Jeśli użyto instancji chmura, wtedy nie byłoby praktycznym sposobem na uzyskanie czegoś od drugiej instancji, krótkie złamania w serwerowniach Amazon ...
MerseyViking
W konsekwencji powinieneś wydać tyle na bezpieczeństwo danych, ile są one warte. Istnieje wiele warstw, które możesz dodać do swojego modelu bezpieczeństwa, ale w pewnym momencie musisz powiedzieć wystarczająco dużo. Być może warto byłoby zadać to pytanie jednej z innych stron SE.
MerseyViking
0

Jest to być może bardziej skomplikowane i zaangażowane niż to konieczne, jednak może to być droga:

Utwórz prosty skrypt Pythona, który pobiera oryginalne punkty wejściowe, buforuje je o pewną akceptowalną odległość zaciemniającą, tworzy n liczby losowych punktów, używając buforów jako ograniczenia funkcji (na przykład 100), a następnie wybiera jeden z punktów za pomocą generator liczb pseudolosowych do użycia jako nowy zaciemniony punkt. Konieczne byłoby również utworzenie nowej pseudolosowej liczby dla każdego zaciemnienia.

W zależności od scenariusza może to być spakowane w Przyborniku i dostępne jako usługa GPS z punktem końcowym REST, więc zaciemnianie występuje w lokalizacjach pamięci i tylko zaciemniony punkt jest wysyłany do fizycznej bazy danych.

Wysokość
źródło
1
Zakłada się implementację ArcGIS, ale żadnej nie wspomniano w PO. Nadal ciekawe rozwiązanie!
blah238,
3
To naturalne rozwiązanie ma pewne potencjalne wady podczas badania: (1) kilka różnych punktów może zostać przypisanych do tego samego punktu. (2) Jak pokazuje PO, łatwo jest zdemaskować punkty. (3) Często punkty muszą znajdować się w pewnym związku geograficznym z powiązanymi cechami: np. Lokalizacje domów powinny znajdować się w pobliżu ulic, a nie w jeziorach lub na stacjach kolejowych. Takie problemy sprawiają, że problem jest naprawdę trudny, interesujący i warty analizy GIS (w przeciwnym razie można po prostu losowo wstrząsnąć oryginalne współrzędne, gdy są one po raz pierwszy wprowadzane do bazy danych i wykonywane).
whuber
0

OK, więc algorytm, który rozważamy, jest następujący:

  1. Zaokrąglić punkt do 200-metrowej siatki (aby zrekompensować kaprysy w geokodowaniu).
  2. Mieszaj tekst współrzędnych punktu za pomocą jakiegoś algorytmu kryptograficznego mieszania (np. SHA2).
  3. Zastąp bity niższego rzędu współrzędnych punktu (do żądanego poziomu zaciemnienia 1 km) wynikami funkcji haszowania.
Reid
źródło