Конец эпохе онлайн-слежки? Криптографы на грани создания полностью анонимного интернет-поиска

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

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

Дэвид У, криптограф из Техасского университета в Остине, отмечает, что решение этой задачи (известной как «поиск приватной информации») является ключевым для многих приложений, обеспечивающих конфиденциальность данных. С 1990-х годов исследователи работают над усовершенствованием стратегий конфиденциального доступа к базам данных. Одна из главных целей — создание чего-то вроде приватного поиска Google, позволяющего анонимно просматривать огромные объемы данных без значительных вычислительных усилий.

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

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

Проблема конфиденциального доступа к базам данных начала формироваться в 1990-х. Сначала считалось, что единственное решение — сканировать всю базу данных при каждом поиске. Это похоже на то, как библиотекарь проверяет каждую полку перед тем, как принести вашу книгу. Ведь если поиск пропускает какой-либо раздел, библиотекарь поймёт, что искомая книга не в этой части библиотеки.

Такой подход приемлем на небольших масштабах, но с ростом базы данных время, необходимое для её сканирования, увеличивается пропорционально. При работе с большими объемами данных процесс становится неэффективным.

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

Даниэль Вичс, криптограф из Северо-Восточного университета и один из авторов революционной публикации, изначально скептически отнесся к идее, считая её слишком утопичной, чтобы быть реальностью. В 2011 году он предпринял попытки доказать её невозможность, уверенный в её нереализуемости.

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

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

Этот метод не принёс улучшений, и группа была близка к отказу от идеи. Но они задались вопросом: а что, если этот инструмент всё-таки может работать в случае с одним сервером? Выбрав подходящий полином, они увидели, что один сервер мог бы предобработать его на основе результата 2011 года — создавая безопасную и эффективную схему поиска, о которой Вичс думал годами. Внезапно они решили более сложную проблему.

Сначала авторы не поверили в это. "Давайте выясним, в чём здесь подвох", — вспоминает Вичс. "Мы продолжали пытаться понять, где это ломается".

Но решение оказалось верным: они действительно нашли безопасный способ предобработки односерверной базы данных, так что любой мог тайно извлекать информацию.

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

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

Сама по себе частная схема поиска действительно позволяет осуществлять поиск, подобный Google, но это чрезвычайно трудоёмко: вы запускаете алгоритм Google самостоятельно и тайно извлекаете данные из интернета по мере необходимости.

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

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

Хотя гомоморфное шифрование является полезным расширением схемы приватного поиска, Ишаи считает, что поиск приватной информации — более фундаментальная проблема. Решение авторов — это "волшебный строительный блок", а их стратегия гомоморфного шифрования — естественное продолжение.

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

К счастью, сказал Вайкунтанатан, криптографы имеют долгую историю оптимизации результатов, которые изначально были непрактичными. Если будущая работа позволит упростить этот подход, он считает, что частный поиск в гигантских базах данных может стать достижимым. «Мы все думали, что застряли там», — сказал он. «Результат Дэниела дает надежду».