różnica prywatności skoczyła z artykułów naukowych do nagłówków wiadomości technicznych w zeszłym roku, kiedy w keynote WWDC wiceprezes ds. inżynierii Apple Craig Federighi ogłosił wykorzystanie przez Apple tej koncepcji do ochrony prywatności użytkowników w systemie iOS.

był to najnowszy przykład ogólnego trendu: użytkownicy i inżynierowie uświadamiali sobie znaczenie ochrony prywatności w oprogramowaniu. Głośne naruszenia prywatności, takie jak „God mode” Ubera, wykazały w surowy sposób łatwość, z jaką pracownicy firmy mogą nadużywać wrażliwych danych zebranych od swoich klientów.

ilość wrażliwych danych, które są rejestrowane cyfrowo, szybko rośnie. Teraz ludzie polegają na usługach cyfrowych w zakresie płatności, transportu, nawigacji, zakupów i zdrowia bardziej niż kiedykolwiek. Ten nowy zbiór danych tworzy coraz większe sposoby naruszania prywatności.

ale stwarza również ekscytujące możliwości—poprawy sieci transportowych, zmniejszenia przestępczości, leczenia chorób—jeśli są one udostępniane właściwym naukowcom i badaczom danych. Istnieje naturalne napięcie między ochroną prywatności osób w zbiorze danych a włączaniem analiz, które mogą prowadzić do lepszego świata.

algorytmy Differentially private są obiecującym rozwiązaniem technicznym, które może złagodzić to napięcie, umożliwiając analitykom przeprowadzenie łagodnej analizy zbiorczej, gwarantując jednocześnie znaczącą ochronę prywatności każdej osoby.

ta rozwijająca się dziedzina technologii jest warta rozważenia w każdym systemie, który ma na celu analizę wrażliwych danych. Chociaż różnicowa gwarancja prywatności powstała zaledwie dziesięć lat temu, odniosła sukces w środowisku akademickim i przemysłowym. Naukowcy szybko wymyślają i ulepszają różne prywatne algorytmy, z których niektóre zostały przyjęte zarówno w Apple iOS, jak i Google Chrome.

w artykule omówiono historyczne czynniki prowadzące do różnicowej prywatności w jej obecnej formie, wraz z definicją różnicowej Prywatności i przykładowymi algorytmami różnicowo prywatnymi. Następnie przegląda kilka ostatnich głośnych implementacji różnych algorytmów prywatnych przez Google, Apple i inne.

kontekst

różne algorytmy prywatne są najnowszą dziedziną technologii do analizy danych chroniących prywatność. Dwa wcześniejsze pojęcia bezpośrednio wpływały na prywatność różniczkową:

1. minimalna wielkość zbioru zapytań
2. definicja ujawnienia statystycznego Daleniusa.

wyjaśnimy je najpierw, ponieważ zapewniają one pomocne tło dla różnicowej prywatności.

minimalny rozmiar zestawu zapytań pierwszą koncepcją jest minimalny rozmiar zestawu zapytań, który-podobnie jak różne algorytmy prywatne-ma na celu zapewnienie bezpieczeństwa zapytań zbiorczych. Zapytania zbiorcze to te, w których zwracana wartość jest obliczana w podzbiorze rekordów w zbiorze danych, takich jak liczby, średnie lub sumy. Pomocne może być myślenie o zapytaniach zbiorczych jako zapytaniach SQL zaczynających się od „SELECT SUM”, „SELECT COUNT” lub „SELECT AVG”. Inne rodzaje zapytań zbiorczych obejmują tabele awaryjne i histogramy.

minimalny rozmiar zestawu zapytań jest ograniczeniem, które ma na celu zapewnienie, że zapytania zbiorcze nie mogą wyciekać informacji o osobach. Biorąc pod uwagę pewną skonfigurowaną liczbę progową t, zapewnia ona, że każde zagregowane zapytanie jest przeprowadzane na zestawie co najmniej rekordów T. Minimalny rozmiar zestawu zapytań blokowałby zapytania zbiorcze skierowane do mniejszej liczby osób niż T. Na przykład, Jeśli T = 2, blokuje to:

„SELECT AVG(payment) WHERE name = 'Troy Brown’;”.

ponieważ to zapytanie prowadziłoby średnią nad jednym rekordem (Zakładamy, że jest tylko jeden rekord).

używanie minimalnych rozmiarów zestawów zapytań zapobiega niektórym atakom, ale nie zapewnia gwarancji Prywatności i w praktyce może być omijane przez wykwalifikowanych atakujących. Na przykład atakujący może wykonać powyższy atak za pomocą:

„SELECT SUM(payment);”.

„wybierz sumę (wynagrodzenie) gdzie nazwa != „Troy Brown”,

lub nawet, jeśli znamy wiek (45 lat) i pozycję (WR), jednoznacznie go identyfikujemy:

” SELECT SUM (payment) WHERE position = 'WR’;”.

„SELECT SUM (payment) WHERE position =’ WR ’ AND age != 45;

takie ataki nazywane są atakami trackera i nie mogą być zatrzymane przez ograniczenie minimalnego rozmiaru zestawu zapytań. Z powodu tych ataków minimalne rozmiary zestawów zapytań zostały uznane za niewystarczającą obronę dla ochrony systemów zapytań (patrz praca Denninga). Coś lepszego, z gwarancją, było potrzebne, aby zapewnić prywatność.

definicja ujawnienia danych statystycznych Daleniusa

w 1977 roku statystyk Tore Dalenius zaproponował ścisłą definicję prywatności danych: atakujący powinien dowiedzieć się nic o osobie, której nie znał przed użyciem wrażliwego zestawu danych. Chociaż ta gwarancja nie powiodła się (i zobaczymy, dlaczego), ważne jest zrozumienie, dlaczego różnica prywatności jest skonstruowana tak, jak jest.

definicja Daleniusa nie powiodła się, ponieważ w 2006 roku informatyk Cynthia Dwork udowodniła, że tej gwarancji nie da się udzielić—innymi słowy, jakikolwiek dostęp do danych wrażliwych naruszałby tę definicję prywatności. Problem, który odkryła, polegał na tym, że pewne rodzaje informacji ogólnych zawsze mogą prowadzić do nowego wniosku o jednostce. Jej dowód ilustruje poniższa anegdota: Wiem, że Alice jest dwa cale wyższa od przeciętnej Litwinki. Następnie wchodzę w interakcję z zestawem danych litewskich kobiet i obliczam średni wzrost, którego wcześniej nie znałem. Teraz wiem dokładnie wysokość Alice, mimo że nie było jej w zbiorze danych. Niemożliwe jest uwzględnienie wszystkich rodzajów informacji podstawowych, które mogą prowadzić do nowego wniosku o osobie z korzystania z zestawu danych.

Dwork, po udowodnieniu powyższego, zaproponował nową definicję: prywatność różniczkowa.

czym jest prywatność różniczkowa?

różnicowa prywatność gwarantuje następujące: że atakujący może dowiedzieć się praktycznie nic więcej o osobie, niż dowiedzieliby się, gdyby rekord tej osoby był nieobecny w zbiorze danych. Chociaż definicja prywatności Daleniusa jest słabsza niż definicja prywatności Daleniusa, gwarancja jest wystarczająco silna, ponieważ odpowiada rzeczywistym zachętom – osoby fizyczne nie mają motywacji, aby nie uczestniczyć w zbiorze danych, ponieważ analitycy tego zbioru danych wyciągną te same wnioski na temat tej osoby, niezależnie od tego, czy dana osoba zawiera się w zbiorze danych, czy nie. Ponieważ ich wrażliwe dane osobowe są prawie nieistotne w wyjściach systemu, użytkownicy mogą być pewni, że organizacja przetwarzająca ich dane nie narusza ich prywatności.

analitycy uczący się „praktycznie nic więcej o jednostce” oznacza, że ograniczają się do nieznacznej zmiany przekonań o dowolnej jednostce. (Tutaj i poniżej „zmiana” odnosi się do zmiany między użyciem zestawu danych a użyciem tego samego zestawu danych minus rekord jednej osoby.) Zakres tej zmiany jest kontrolowany przez parametr znany jako ϵ, który wyznacza granicę na zmianie prawdopodobieństwa dowolnego wyniku. Niska wartość ϵ, taka jak 0,1, oznacza, że bardzo niewiele może zmienić przekonania dotyczące każdej osoby. Wysoka wartość ϵ, np. 50, oznacza, że przekonania mogą się znacznie zmienić. Formalna definicja jest następująca.

algorytm a jest ϵ-różnie prywatny wtedy i tylko wtedy, gdy:

Pr ≤ e^ϵ * Pr

dla wszystkich x i dla wszystkich par zbiorów danych D, D’ gdzie D’ to D z dowolnym rekordem—tzn. brak danych jednej osoby. Symbol e odnosi się do stałej matematycznej. Zauważ, że ta definicja ma sens tylko dla algorytmów randomizowanych. Algorytm dający wynik deterministyczny nie jest kandydatem do prywatności różniczkowej.

główną zaletą różnicowej gwarancji prywatności jest jej ograniczenie do kwoty, którą każdy analityk może dowiedzieć się o danej osobie. Dodatkowo ma następujące użyteczne właściwości:

• Komponowalność: jeśli na dwa zapytania udzielane są różne gwarancje prywatności poziomu ϵ1 i ϵ2, para zapytań jest objęta gwarancją poziomu (ϵ1 + ϵ2). Przypomnijmy, że wyższa wartość ϵ oznacza słabszą gwarancję.
• Siła wobec dowolnych informacji tła: gwarancja nie polega w żaden sposób na tym, jakie informacje tła zna atakujący. Ta właściwość jest jednym z głównych powodów, że różnica prywatności jest silniejsza niż wcześniejsza gwarancja prywatności, K-anonimowość.
• bezpieczeństwo w ramach post-processingu: nie ma ograniczeń co do tego, co można zrobić z różnie prywatnym rezultatem – bez względu na to, z czym jest połączony lub jak jest przekształcany, nadal jest różnie prywatny.

jak ta gwarancja jest osiągana w oprogramowaniu? Algorytmy differentially private są algorytmami randomizowanymi, które dodają szum w kluczowych punktach algorytmu. Jednym z najprostszych algorytmów jest mechanizm Laplace ’ a, który może przetwarzać wyniki zapytań zbiorczych (np. liczby, sumy i środki) w celu uczynienia ich różnicowo prywatnymi. Poniżej znajduje się przykładowy kod Javy dla mechanizmu Laplace ’ a specyficznego dla zliczania zapytań:

import org.apache.commons.math3.distribution.LaplaceDistribution;double laplaceMechanismCount(long realCountResult, double epsilon) { LaplaceDistribution ld = new LaplaceDistribution(0, 1 / epsilon); double noise = ld.sample(); return realCountResult + noise;}

kluczowe części tej funkcji to

1. utworzenie rozkładu prawdopodobieństwa Laplace ’ a (patrz rysunek 1) wyśrodkowanego na 0 i skalowanego przez 1 / ϵ. Używamy implementacji Apache Commons, „LaplaceDistribution”, która jest zbudowana z dwóch argumentów: średniej dystrybucji i skali dystrybucji. Należy zauważyć, że niższy epsilon (więcej prywatności) prowadzi do większej skali, a tym samym szerszej dystrybucji i więcej hałasu.
2. Narysuj jedną losową próbkę z tego rozkładu. Funkcja sample () pobiera losową liczbę z zakresu od 0 do 1 i stosuje do tej liczby funkcję odwrotnego rozkładu kumulacyjnego rozkładu Laplace ’ a (CDF). Proces ten powoduje losową liczbę tak, że jej prawdopodobieństwo bycia dowolną określoną wartością pasuje do rozkładu. Jako alternatywny sposób myślenia o tym, gdyby ta funkcja próbki została wywołana milion razy, aby uzyskać milion próbek, kształt histogramu tych próbek byłby ściśle zgodny z kształtem rozkładu Laplace ’ a.
3. Zaburz rzeczywistą wartość, dodając losową wartość z kroku 2.

zastanówmy się, dlaczego algorytm ten jest różnie prywatny, biorąc pod uwagę punkt widzenia atakującego o imieniu Eve. Powiedzmy, że zestaw danych to dane o zdrowiu psychicznym, a Ewa wymyśliła atak tropiciela (patrz wyżej), który ujawni, czy jej cel, Bob, otrzymuje terapię alkoholizmu, czy nie. Jeśli wynik zapytania wynosi 48, Eve wie, że Bob otrzymuje poradę; jeśli jest to 47, Eve wie coś przeciwnego.

niezależnie od tego, czy odpowiedź to 47 czy 48, Mechanizm Laplace ’ a zwróci głośny wynik gdzieś w okolicach 47 czy 48. Może zwrócić 49, 46 lub nawet, z mniejszym prawdopodobieństwem, 44 lub 51 (patrz rysunek 2 dla histogramu). W praktyce nie jest możliwe, aby Ewa była bardzo pewna, czy prawdziwa odpowiedź to 47 czy 48 lat, a zatem jej przekonania o tym, czy Bob jest w poradni alkoholizmu, czy teraz nie zmienią się znacząco.

Rysunek 1: rozkład Laplace ’ a wyśrodkowany na 0 ze skalą 1. Na zdjęciu Funkcja gęstości prawdopodobieństwa (PDF) rozkładu-oś y jest względnym prawdopodobieństwem, że zmienna przyjmie wartość na osi X.

Rysunek 2: prawdopodobne wyniki kwerendy count dla dwóch scenariuszy, gdzie rzeczywista odpowiedź to 47, a kiedy to 48. Niewielka liczba wyników nie wystarczyłaby do rozróżnienia, z której dystrybucji pochodzą. Epsilon jest ustawiony na 0.67.

być może zauważyłeś w tym punkcie, że Ewa może przeciąć hałas powtarzając zapytanie wiele razy i sprawdzając, czy odpowiedzi skupiają się wokół 47 czy 48. Aby zapobiec tej taktyce, różne systemy prywatne muszą mieć” budżet prywatności”, limit sumy ϵ używanych w każdym zapytaniu. Ta czapka działa ze względu na opisaną powyżej właściwość składalności differential privacy. Mogą zadać kilka stosunkowo cichych zapytań lub wiele setek zapytań o wysokim poziomie hałasu, ale tak czy inaczej, nie będą w stanie pewnie ustalić, czy prawdziwa odpowiedź to 47 czy 48.

na koniec zauważ, że mechanizm Laplace ’ a dla liczników jest tylko jednym prostym algorytmem różnicowym. Mechanizm Laplace ’ a można rozszerzyć do pracy dla sum i innych zapytań zbiorczych. Ponadto istnieją zasadniczo różne algorytmy, które okazały się spełniać zróżnicowaną gwarancję prywatności. Kilka wartych zbadania to prywatny algorytm Mas mnożących, Mechanizm wykładniczy Mas mnożących i DualQuery.

Differential privacy in action

w czerwcu 2016 roku Apple ogłosiło, że zacznie używać różnych algorytmów prywatnych do zbierania statystyk behawioralnych z iphone ’ ów. To ogłoszenie, oprócz tego, że powoduje ogromny wzrost różnicowego zainteresowania prywatnością, pokazało, że różnica prywatności może pomóc głównym organizacjom uzyskać nową wartość z danych, których wcześniej nie dotykały z powodu obaw o prywatność.

chociaż Apple do tej pory upubliczniło niewiele szczegółów, algorytm zastosowany w iPhonie wydaje się podobny do projektu RAPPORA Google. Google wdrożyło funkcję w Chrome, która zbiera statystyki behawioralne z przeglądarek Chrome za pomocą różnicowo prywatnego algorytmu randomizowanej odpowiedzi.

w odpowiedzi randomizowanej losowy szum jest dodawany do statystyk przed ich przesłaniem do kolektora. Na przykład, jeśli rzeczywista statystyka wynosi 0, przeglądarka z pewnym prawdopodobieństwem zastąpi 0 losowo wybranym 0 LUB 1. Każdy użytkownik ma duży stopień zaprzeczenia co do wartości, którą zgłasza jego oprogramowanie, ponieważ może to być wartość losowa. Ale łącznie sygnał wyróżnia się nad przypadkowym szumem, a organizacja zbierająca statystyki (np. Google lub Apple) może dokładnie obserwować trendy.

Co ciekawe, ani Google, ani Apple, zgodnie z naszą wiedzą, nie ujawniły wartości, która idzie w parze z ich gwarancją prywatności. Potrzebujemy tej wartości, aby zrozumieć ochronę oferowaną przez gwarancję. Jeśli używają wystarczająco wysokiej wartości ϵ, analitycy mogą nadal uczyć się wrażliwych faktów o Użytkownikach z dużym zaufaniem. Niska wartość ϵ jest wymagana do znaczącej ochrony prywatności.

różne algorytmy prywatne zostały również zaimplementowane w produktach analitycznych chroniących prywatność, takich jak te opracowane przez mojego pracodawcę Privitar. Produkty te umożliwiają firmom, które pracują z cennymi, wrażliwymi danymi, włączenie różnych algorytmów prywatnych do ich architektury danych, zapewniając gwarancję prywatności swoim użytkownikom, a jednocześnie przeprowadzając znaczącą analizę danych.

patrząc w przyszłość

zarówno środowiska inżynieryjne, jak i badawcze mają ścieżki do przodu z różną prywatnością. Dla inżynierów zadaniem jest zdobycie wiedzy na temat różnicowej Prywatności i zapewnienie, że jest ona wykorzystywana w stosownych przypadkach do ochrony prywatności użytkowników. Dla badaczy jest znalezienie coraz lepszych algorytmów różniących się prywatnością, ulepszając zestaw narzędzi, dzięki którym możemy umożliwić analizę danych zachowujących prywatność.

wszyscy możemy zyskać na ustanowieniu gwarancji Prywatności i sukcesach analityki danych. Z obu powodów oczekujemy, że więcej organizacji wykorzysta zróżnicowaną prywatność.

o autorze

Charlie Cabot jest starszym analitykiem danych w Privitar, startupie zajmującym się prywatnością danych, który buduje wysokowydajne oprogramowanie do anonimizacji danych, w tym algorytmy perturbacji i generalizacji oraz różne mechanizmy prywatne, aby ułatwić bezpieczne korzystanie z wrażliwych zbiorów danych. Charlie koncentruje się na gwarantowanych gwarancjach Prywatności i statystycznym wpływie anonimizacji na analitykę i naukę o danych. Wcześniej, pracując w cyberbezpieczeństwie, Charlie zaprojektował oparte na uczeniu maszynowym podejścia do wykrywania złośliwego oprogramowania i modelował cyberataki w sieciach komputerowych.