Wszyscy wiemy, jak dbać o szczegóły, które udostępniamy online, ale to, czego szukamy, także może coś o nas zdradzić. Wyszukując wskazówki dojazdu, nasza lokalizacja staje się łatwiejsza do odgadnięcia. Sprawdzając hasło w zbiorze skompromitowanych danych, sami narażamy się na wyciek tych informacji.
Te sytuacje rodzą pytanie kluczowe dla kryptografii: Jak możemy pobrać informacje z publicznej bazy danych, nie ujawniając niczego na temat tego, czego dostępujemy? To równoznaczne z wypożyczeniem książki z biblioteki bez wiedzy bibliotekarza, o którą konkretnie prosimy.
Wychodzenie z takiego problemu, znane jako prywatne pobieranie informacji, jest „bardzo przydatnym elementem w wielu aplikacjach ochrony prywatności” – powiedział David Wu, kryptograf z Uniwersytetu Teksańskiego w Austin. Od lat 90. naukowcy starali się rozwiązać ten problem, udoskonalając strategie prywatnego dostępu do baz danych. Jednym z głównych celów, który jest jednak niemożliwy do osiągnięcia z dużymi bazami danych, jest prywatne wyszukiwanie Google, które pozwala przesiewać anonimowo dużą ilość danych bez konieczności dużego obciążenia obliczeniowego.
Teraz, trzej naukowcy opracowali długo poszukiwaną wersję prywatnego pobierania informacji i rozszerzyli ją w celu budowy bardziej ogólnej strategii ochrony prywatności. Praca, która w czerwcu 2023 roku zdobyła nagrodę dla najlepszego artykułu na corocznym sympozjum nad teorią obliczeń, obala jedną z głównych teoretycznych barier na drodze do prawdziwie prywatnej wyszukiwarki.
Problem prywatnego dostępu do bazy danych przybrał na znaczeniu w latach 90. Na początku naukowcy zakładali, że jedynym rozwiązaniem jest przeskanowanie całej bazy danych podczas każdego wyszukiwania, co oznaczałoby, że bibliotekarz musiałby przeszukać każdą półkę zanim wróciłby z twoją książką. Przecież jeśli wyszukiwanie opuściłoby jakąś sekcję, bibliotekarz musiałby wiedzieć, że twoja książka nie znajduje się w tej części biblioteki.
To podejście działało wystarczająco dobrze w mniejszej skali, ale w miarę wzrostu bazy danych, czas potrzebny do przeglądania jej wzrastał proporcjonalnie. W miarę czytania z coraz większych baz danych – a Internet jest dość dużą bazą danych – proces staje się nieefektywny.
Na początku XXI wieku naukowcy zaczęli podejrzewać, że mogą ominąć granicę pełnego skanowania poprzez „preprocessing” bazy danych. W przybliżeniu oznaczałoby to kodowanie całej bazy danych jako strukturę specjalną, dzięki czemu serwer mógłby odpowiedzieć na zapytanie, czytając tylko niewielką część tej struktury. Ostrożne dostateczne przetwarzanie w teorii mogło oznaczać, że pojedynczy serwer przechowujący informacje przeszedłby przez proces tylko raz, samodzielnie, pozwalając wszystkim przyszłym użytkownikom w tajemnicy pobierać informacje bez dodatkowego wysiłku.
Dla Daniela Wichsa, kryptografa z Northeastern University i współautora nowego artykułu, wydawało się, że to jest zbyt piękne, by mogło być prawdziwe. Wokół 2011 roku zaczął próbować udowodnić, że ten rodzaj schematu jest niemożliwy. „Byłem przekonany, że nie ma możliwości, żeby to zrobić” – powiedział.
Ale w 2017 roku dwie grupy badaczy opublikowały wyniki, które zmieniły jego zdanie. Zbudowali pierwsze programy, które mogły robić tego rodzaju prywatne pobieranie informacji, ale nie byli w stanie udowodnić, że programy były bezpieczne. (Kryptografowie udowadniają bezpieczeństwo systemu, pokazując, że jego złamanie jest tak trudne jak rozwiązanie pewnego trudnego problemu. Badacze nie byli w stanie porównać tego do kanonicznego trudnego problemu.)
Więc nawet wraz z odnowionym nadzieją Wichs zakładał, że wciąż długo trzeba będzie czekać na wersję tych programów, która jest bezpieczna. Zamiast tego on i jego współautorzy – Wei-Kai Lin, obecnie na University of Virginia, i Ethan Mook, również na Northeastern – pracowali nad problemami, które uważali za łatwiejsze, dotyczące przypadków, w których kilka serwerów przechowuje bazę danych.
W metodach, które badali, informacje w bazie danych mogą być przekształcone w wyrażenie matematyczne, które serwery mogą ocenić, aby wydobyć informacje. Autorzy przypuszczali, że możliwe byłoby efektywniejsze wykonanie tego procesu oceny. Bawili się z pomysłem z 2011 roku, kiedy inni badacze znaleźli sposób szybkiego wykonania takiego wyrażenia przez jego preprocessing, tworząc specjalne, zwarte tabele wartości, które pozwalają pominąć normalne kroki oceny.
Ta metoda nie przyniosła żadnych poprawek, a grupa zbliżyła się do poddania – aż nagle zastanawili się, czy ten narzędzie naprawdę może działać w pożądanym przypadku jedno-serwerowym. Wybierz wielomian dość dokładnie, zobaczyli, a pojedynczy serwer mógłby go przetworzyć w oparciu o wynik z 2011 roku – dając bezpieczny, wydajny schemat wyszukiwania, o którym Wichs zastanawiał się przez lata. Nagle rozwiązali trudniejszy problem.
Na początku autorzy nie wierzyli w to. „Sprawdźmy, co jest nie tak z tym” – pomysł przewodził myślami Wichsa. „Cały czas próbowaliśmy zrozumieć, gdzie to się załamuje.”
Ale rozwiązanie utrzymało się: naprawdę odkryli bezpieczny sposób przetwarzania bazy danych jedno-serwerowej, dzięki czemu każdy mógł pobierać informacje w tajemnicy. „To jest naprawdę ponad to, na co mieliśmy nadzieję” – powiedział Yuval Ishai, kryptograf z Technionu w Izraelu, który nie był zaangażowany w tę pracę. To „wynik, którego nawet nie odważyliśmy się prosić” – powiedział.
Po zbudowaniu schematu prywatnego wyszukiwania, autorzy zwrócili się do celu realnego świata – prywatnej wyszukiwarki internetowej, która jest bardziej skomplikowana niż pobieranie fragmentów informacji z bazy danych, powiedział Wichs. Sam schemat prywatnego wyszukiwania pozwala na wersję prywatnej wyszukiwarki Google, ale jest to bardzo pracochłonne: uruchamiasz algorytm Google’a sam i w tajemnicy pobierasz dane z Internetu, gdy jest to konieczne. Wichs powiedział, że prawdziwa wyszukiwarka, w której wysyłasz żądanie i oczekujesz wyników ze strony serwera to prawdziwe wyzwanie dla szerokiego podejścia, które nazywane jest szyfrowaniem homomorficznym, co pozwala na zamaskowanie danych, aby ktoś inny mógł nimi manipulować, nie wiedząc o nich niczego.
Typowe strategie szyfrowania homomorficznego napotkałyby ten sam problem, co prywatne pobieranie informacji.
Często zadawane pytania (FAQ):
1. Co to jest prywatne pobieranie informacji?
Prywatne pobieranie informacji to proces pozyskiwania danych z publicznej bazy, nie ujawniając informacji o tym, które konkretne dane są pobierane.
2. Jakie są główne cele prywatnego pobierania informacji?
Głównym celem jest ochrona prywatności użytkowników poprzez umożliwienie dostępu do danych bez ujawniania informacji o konkretnie pobieranych danych.
3. Dlaczego prywatne pobieranie informacji jest ważne?
Prywatne pobieranie informacji jest istotne, ponieważ chroni użytkowników przed wyciekiem ich prywatnych danych podczas korzystania z publicznych baz danych.
4. Jakie były dotychczasowe wyzwania związane z prywatnym pobieraniem informacji?
Dotychczasowe wyzwania obejmowały długotrwałe przeglądanie i skanowanie całej bazy danych podczas każdego wyszukiwania, co było nieefektywne w przypadku dużych baz danych.
5. Czym jest schemat prywatnego wyszukiwania?
Schemat prywatnego wyszukiwania to metoda przetwarzania danych tak, aby użytkownik mógł wyszukiwać informacje w tajemnicy, nie ujawniając konkretnych wyszukiwanych danych.
6. Jakie jest zastosowanie prywatnego pobierania informacji?
Prywatne pobieranie informacji ma zastosowanie w różnych dziedzinach, takich jak ochrona prywatności użytkowników, bezpieczne wyszukiwarki internetowe i ochrona danych przetwarzanych w zbiorach.
Słowniczek:
– Kryptografia: dziedzina nauki zajmująca się zabezpieczaniem informacji poprzez kodowanie i odkodowywanie danych.
– Baza danych: struktura, w której przechowywane są dane, zwykle zorganizowane w tabelach i rekordach.
– Wyciek danych: nieuprawnione ujawnienie poufnych informacji.
– Preprocessing: proces przygotowania danych przed ich przetwarzaniem lub analizą.
– Szyfrowanie homomorficzne: technika szyfrowania danych, która pozwala na przeprowadzanie operacji na zakodowanych danych, nie odsłaniając ich zawartości.
Sugerowane powiązane linki:
– Uniwersytet Teksański w Austin
– Northeastern University
– University of Virginia
– Technion – Israel Institute of Technology
https://youtube.com/watch?v=F6NPQZTVv60
The source of the article is from the blog qhubo.com.ni