Криптографы решили десятилетнюю проблему конфиденциальности

Остерегайтесь не только того, что вы делитесь в Интернете, но и того, что ищете. Поиск информации может раскрыть ваши данные, например, запрос на поиск маршрута выдает ваше местоположение. Эта проблема стоит в центре вопроса в криптографии: как получать информацию из общедоступной базы данных, не выдавая, что именно вы искали?

Исследователи с 90-х годов пытались найти решение этой задачи, известной как "защищенный поиск информации". Цель - создать аналог частного поиска Google, где можно анонимно просматривать данные без значительных вычислений.

Теперь трое исследователей разработали долгожданный метод защищенного поиска информации и расширили его для создания более общей стратегии конфиденциальности. Их работа, удостоенная награды за лучшую статью на ежегодном Симпозиуме по теории вычислений, преодолевает важный теоретический барьер на пути к созданию действительно частного поиска.

"Это результат, о котором мы все мечтали, но не верили, что он возможен", - говорит Винод Вайкунтанатан, криптограф из Массачусетского технологического института, который не участвовал в работе.

Ранее считалось, что единственное решение - сканировать всю базу данных при каждом поиске. Но такой подход становится неэффективным при увеличении объема данных.

Исследователи начали предполагать, что можно обойти полное сканирование за счет предварительной обработки базы данных. Это позволяет серверу отвечать на запрос, читая только небольшую часть специальной структуры. Дэниел Вичс, один из авторов новой работы, первоначально пытался доказать, что такая схема невозможна, но в 2017 году его мнение изменилось.

Теперь ученые нашли способ эффективно обрабатывать информацию на одном сервере, позволяя пользователям анонимно получать данные. "Это действительно больше, чем мы могли надеяться", - говорит Юваль Ишаи, криптограф из Техниона в Израиле.

Впрочем, пока эти методы не готовы к практическому использованию: предварительная обработка эффективна только при очень больших размерах баз данных. Однако Вайкунтанатан уверен, что оптимизация подхода может сделать защищенный поиск по большим базам данных реальностью.