Kryptografowie opracowują podejście do całkowitej prywatności wyszukiwania | Magazyn Quanta

Wszyscy wiemy, że należy uważać na szczegóły, które udostępniamy w Internecie, ale informacje, których szukamy, mogą również być odkrywcze. Wyszukaj wskazówki dojazdu, a nasza lokalizacja stanie się znacznie łatwiejsza do odgadnięcia. Jeśli szukasz hasła w zbiorze zainfekowanych danych, ryzykujesz, że sami je wypuścimy.

Sytuacje te rodzą kluczowe pytanie w kryptografii: w jaki sposób można wyciągnąć informacje z publicznej bazy danych, nie ujawniając niczego na temat tego, do czego uzyskano dostęp? To tak, jakby wypożyczyć książkę z biblioteki i bibliotekarz nie wiedział, którą.

Opracowanie strategii rozwiązującej ten problem – zwanej wyszukiwaniem prywatnych informacji – jest „bardzo przydatnym elementem wielu aplikacji chroniących prywatność” – stwierdził David Wu, kryptolog z Uniwersytetu Teksasu w Austin. Od lat 1990. XX wieku badacze rozwiewali tę kwestię, udoskonalając strategie prywatnego dostępu do baz danych. Jednym z głównych celów, wciąż niemożliwym do osiągnięcia w przypadku dużych baz danych, jest odpowiednik prywatnej wyszukiwarki Google, w której można anonimowo przesiewać stertę danych, bez wykonywania ciężkich obliczeń.

Teraz zrobiło to trzech badaczy wykonane długo oczekiwaną wersję wyszukiwania prywatnych informacji i rozszerzyłem ją, aby zbudować bardziej ogólną strategię prywatności. Praca, która otrzymała m.in Nagroda za najlepszy artykuł w czerwcu na corocznym Sympozjum na temat teorii informatyki, obala główną barierę teoretyczną na drodze do prawdziwie prywatnych poszukiwań.

„[To] jest coś w kryptografii, czego chyba wszyscy pragnęliśmy, ale nie do końca wierzyliśmy, że to istnieje” – powiedział Vinod Vaikuntanathan, kryptolog z Massachusetts Institute of Technology, który nie był zaangażowany w pracę nad tą publikacją. „To przełomowy wynik”.

Problem dostępu do prywatnych baz danych ukształtował się w latach 1990. XX wieku. Początkowo badacze zakładali, że jedynym rozwiązaniem jest skanowanie całej bazy danych podczas każdego wyszukiwania, co przypominałoby bibliotekarza przeszukującego każdą półkę przed powrotem z książką. Przecież gdyby w wyszukiwaniu pominięto jakąkolwiek sekcję, bibliotekarz wiedziałby, że Twojej książki nie ma w tej części biblioteki.

Takie podejście sprawdza się wystarczająco dobrze w mniejszych skalach, ale w miarę powiększania się bazy danych czas potrzebny na jej przeskanowanie rośnie co najmniej proporcjonalnie. Kiedy czytasz z większych baz danych – a Internet jest dość duży – proces staje się nadmiernie nieefektywny.

Na początku XXI wieku badacze zaczęli podejrzewać, że mogliby ominąć barierę pełnego skanowania poprzez „wstępne przetwarzanie” bazy danych. Z grubsza oznaczałoby to zakodowanie całej bazy danych jako specjalnej struktury, tak aby serwer mógł odpowiedzieć na zapytanie, czytając tylko niewielką część tej struktury. Wystarczająco ostrożne przetwarzanie wstępne może teoretycznie oznaczać, że pojedynczy serwer hostujący informacje przechodzi ten proces tylko raz, samodzielnie, umożliwiając wszystkim przyszłym użytkownikom prywatne pobieranie informacji bez większego wysiłku.

W razie zamówieenia projektu Daniela Wichsa, kryptolog z Northeastern University i współautor nowego artykułu, wydawało się to zbyt piękne, aby mogło być prawdziwe. Około 2011 roku zaczął udowadniać, że taki schemat jest niemożliwy. „Byłem przekonany, że nie da się tego zrobić” – powiedział.

Ale w 2017 r. dwie grupy badaczy opublikowany wyniki to zmieniło jego zdanie. Stworzyli pierwsze programy, które umożliwiały tego rodzaju wyszukiwanie prywatnych informacji, ale nie byli w stanie wykazać, że programy te są bezpieczne. (Kryptografowie demonstrują bezpieczeństwo systemu, pokazując, że złamanie go jest tak samo trudne, jak rozwiązanie jakiegoś trudnego problemu. Badacze nie byli w stanie porównać tego z kanonicznym trudnym problemem.)

Zatem nawet po odnowieniu nadziei Wichs założył, że do jakiejkolwiek bezpiecznej wersji tych programów wciąż jeszcze daleko. Zamiast tego on i jego współautorzy — Wei-Kai Lin, obecnie na Uniwersytecie Wirginii i Ethana Mooka, także w Northeastern — pracowali nad problemami, które ich zdaniem byłyby łatwiejsze, co dotyczyło przypadków, w których baza danych hostowana jest na wielu serwerach.

W badanych metodach informacje zawarte w bazie danych można przekształcić w wyrażenie matematyczne, które serwery mogą ocenić w celu wyodrębnienia informacji. Autorzy uznali, że możliwe byłoby usprawnienie tego procesu oceny. Zastanawiali się nad pomysłem z 2011 roku, kiedy inni badacze znaleźli sposób na szybką ocenę takiego wyrażenia poprzez wstępne jego przetwarzanie i utworzenie specjalnych, kompaktowych tabel wartości, które pozwalają pominąć normalne etapy oceny.

Metoda ta nie przyniosła żadnych ulepszeń i grupa była bliska poddania się — dopóki nie zaczęła się zastanawiać, czy to narzędzie faktycznie sprawdzi się w pożądanym przypadku z jednym serwerem. Zauważyli, że wybierają wielomian wystarczająco ostrożnie, a pojedynczy serwer może go wstępnie przetworzyć w oparciu o wynik z 2011 roku — uzyskując bezpieczny i wydajny schemat wyszukiwania, nad którym Wichs zastanawiał się od lat. Nagle jednak rozwiązali trudniejszy problem.

Autorzy początkowo w to nie wierzyli. „Zastanówmy się, co w tym złego” – pomyślał Wichs. „Próbowaliśmy ustalić, gdzie się psuje”.

Rozwiązanie jednak okazało się skuteczne: naprawdę odkryli bezpieczny sposób wstępnego przetwarzania bazy danych składającej się z jednego serwera, tak aby każdy mógł w tajemnicy pobierać informacje. „To naprawdę przekracza wszystko, na co liczyliśmy” – powiedział Yuval Ishai, kryptolog w Technion w Izraelu, który nie był zaangażowany w tę pracę. To wynik, „nie mieliśmy nawet dość odwagi, aby o to poprosić” – powiedział.

Po opracowaniu schematu tajnego wyszukiwania autorzy zajęli się rzeczywistym celem, jakim jest prywatne wyszukiwanie w Internecie, co jest bardziej skomplikowane niż wyciąganie fragmentów informacji z bazy danych, powiedział Wichs. Sam schemat wyszukiwania prywatnego pozwala na wersję prywatnego wyszukiwania na wzór Google, ale jest niezwykle pracochłonny: samodzielnie uruchamiasz algorytm Google i w razie potrzeby potajemnie pobierasz dane z Internetu. Wichs powiedział, że prawdziwe wyszukiwanie, podczas którego wysyłasz żądanie i czekasz, aż serwer zbierze wyniki, jest w rzeczywistości celem szerszego podejścia znanego jako szyfrowanie homomorficzne, które ukrywa dane w taki sposób, aby ktoś inny mógł nimi manipulować, nie wiedząc o tym nic .

Typowe strategie szyfrowania homomorficznego natrafiają na ten sam problem, co wyszukiwanie prywatnych informacji, przedzierając się przez całą zawartość Internetu przy każdym wyszukiwaniu. Jednak wykorzystując metodę prywatnego wyszukiwania jako rusztowanie, autorzy skonstruowali nowy schemat, który przeprowadza obliczenia przypominające programy, z których korzystamy na co dzień, i potajemnie pobiera informacje bez przeszukiwania całego Internetu. Zapewniłoby to wzrost wydajności wyszukiwań internetowych i wszelkich programów wymagających szybkiego dostępu do danych.

Chociaż szyfrowanie homomorficzne jest użytecznym rozszerzeniem schematu wyszukiwania prywatnego, Ishai powiedział, że postrzega odzyskiwanie prywatnych informacji jako bardziej podstawowy problem. Rozwiązanie autorów to „magiczny element konstrukcyjny”, a ich strategia szyfrowania homomorficznego jest naturalną kontynuacją.

Na razie żaden ze schematów nie jest praktycznie użyteczny: przetwarzanie wstępne obecnie pomaga w skrajnych przypadkach, gdy rozmiar bazy danych rośnie w nieskończoność. Jednak faktyczne wdrożenie oznacza, że ​​oszczędności te nie mogą się urzeczywistnić, a proces pochłonąłby zbyt dużo czasu i przestrzeni dyskowej.

Na szczęście, powiedział Vaikuntanathan, kryptografowie mają długą historię optymalizacji wyników, które początkowo były niepraktyczne. Uważa, że ​​jeśli przyszłe prace pozwolą usprawnić to podejście, prywatne wyszukiwania w gigantycznych bazach danych mogą być w zasięgu ręki. „Wszyscy myśleliśmy, że w pewnym sensie utknęliśmy w tym miejscu” – powiedział. „Wynik Daniela daje nadzieję”.

Quanta przeprowadza serię ankiet, aby lepiej służyć naszym odbiorcom. Weź nasze ankieta dla czytelników informatyki i zostaniesz wpisany, aby wygrać za darmo Quanta towar.