Криптографы разрабатывают подход к обеспечению полной конфиденциальности поиска | Журнал Кванта

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

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

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

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

«[Это] что-то в криптографии, чего, я думаю, мы все хотели, но не совсем верили, что оно существует», – сказал Винод Вайкунтанатан, криптограф из Массачусетского технологического института, не принимавший участия в написании статьи. «Это знаковый результат».

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

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

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

Что касается Дэниел Уичс, криптографа из Северо-Восточного университета и соавтора новой статьи, это казалось слишком хорошим, чтобы быть правдой. Примерно в 2011 году он начал пытаться доказать, что такая схема невозможна. «Я был убежден, что это невозможно сделать», — сказал он.

Но в 2017 году две группы исследователей опубликованный Результаты это изменило его мнение. Они создали первые программы, способные извлекать частную информацию такого рода, но не смогли доказать, что эти программы безопасны. (Криптографы демонстрируют безопасность системы, показывая, что взломать ее так же сложно, как решить какую-то сложную задачу. Исследователи не смогли сравнить ее с канонической сложной задачей.)

Таким образом, даже несмотря на возобновившуюся надежду, Вичс предположил, что до создания безопасной версии этих программ еще далеко. Вместо этого он и его соавторы — Вэй-Кай Линь, сейчас работающий в Университете Вирджинии, и Итан Мук, также в Northeastern, — работали над проблемами, которые, по их мнению, были проще, включая случаи, когда база данных размещается на нескольких серверах.

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

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

Поначалу авторы в это не поверили. «Давайте разберемся, что в этом плохого», — вспоминает мысль Вичса. «Мы продолжали пытаться выяснить, где это сломалось».

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

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

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

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

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

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

Quanta проводит серию опросов, чтобы лучше обслуживать нашу аудиторию. Возьми наш опрос читателей по информатике и вы будете участвовать в бесплатном выигрыше Quanta товар.