Трое исследователей нашли долгожданный способ тайно извлекать информацию из больших баз данных, приближая нас к абсолютному приватному поиску в Интернете.
Все мы знаем, что нужно быть осторожными в деталях, которыми мы делимся в Интернете, но информация, которую мы ищем, также может раскрыть информацию о вас. Вот вы вводите в поисковике - “как добратся на автомобиле...”, и ваше местонахождение, и возможное прибытие, “для кого нибудь” станет яснее... . Проверьте наличие пароля в массиве “скомпрометированных” данных, и вот, вы уже рискуете разгласить свой.
Подобные ситуации порождают ключевой вопрос в криптографии - а как можно извлекать информацию из общедоступных базы данных, при этом, ничего не раскрывая о том, к какой информации вы получили доступ? Это равносильно тому, как взять книгу у библиотекаря из рук, которой этого не видит.
Разработка стратегии, которая может решить эту проблему, является “очень полезным строительным блоком в ряде приложений, обеспечивающих сохранение конфиденциальности”, — сказал Дэвид Ву, криптограф из Техасского университета.
С 1990-х годов исследователи изучали этот вопрос, совершенствуя стратегии приватного доступа к базам данных. Одна из целей, которая все еще неосуществима с большими базами данных - это приватный поиск в Google или Яндекс, где вы можете анонимно просматривать кучу данных, не выполняя никаких огромных вычислительных работ.
Три исследователя разработали версию поиска частной информации и расширили ее для создания более "общей стратегии конфиденциальности." Работа, получившая премию за лучшую статью в июне, на ежегодном симпозиуме по теории вычислений, устраняет главный теоретический барьер на пути к реальному - приватному поиску.
Проблема частного доступа к базам данных сформировалась ещё в 1990-х годах. Сперва исследователи предполагали, что единственным решением была возможность сканировать всю базу данных, во время каждого поиска, что было бы похоже на то, как библиотекарь, вместо того что бы пойти сразу в указанное место, где находится книга, обыскивает каждую полку. И в итоге, вместо того что бы сразу выдать вам информацию о том, есть ли эта книга или нет, вам приходится очень долго ожидать результат поиска.
Этот подход достаточно хорошо работает в небольших масштабах, но по мере роста базы данных, время необходимое для ее сканирования, растет пропорционально. По мере того, как вы читаете любую информацию из больших баз данных — а Интернет “довольно большой" — процесс сканирования становится запредельно неэффективным.
В начале 2000-х годов исследователи начали подозревать, что они могут обойти барьер полного сканирования, “предварительно обработав” базу данных. Грубо говоря, это означало бы кодирование всей базы данных в виде специальной структуры, для того, что бы сервер мог ответить на ваш запрос, прочитав лишь небольшую часть этой структуры. Предварительная обработка, в теории, будет происходить на том сервере, на котором размещается информация, а процесс сканирования будет проводится только один раз, “самостоятельно”, позволяя всем будущим пользователям получать информацию конфиденциально без каких-либо дополнительных усилий.
Для Дэниела Уичса, криптографа из Северо-Восточного университета и соавтора новой статьи, это казалось “слишком хорошим” вариантом для того, что бы является правдой. В 2011 году он начал пытаться доказать, что подобная схема невозможна.
“Я был уверен, что это невозможно сделать”, - сказал он.
В 2017 году две группы исследователей опубликовали результаты, изменившие его мнение. Они создали первые программы, способные осуществлять конфиденциальный поиск информации, но не смогли продемонстрировать, то что программы, при помощи которых обрабатывалась информация, были безопасными. Викс хотел возродить подобие версий таких программ, которые предоставляли бы безопасность в дальнейшей перспективе. Вместо этого он и его соавторы - Уэй-Кай Лин и Итан Мук - работали над проблемами, которые, по их мнению, были проще, и которые включали случаи, когда несколько серверов хранят единую базу данных.
В методах, которые они изучали, информацию в базе данных можно было преобразовать в математическое выражение, в которых сервера, могли бы оценивать информацию для извлечения. Авторы предположили, что процесс оценки возможно сделать более эффективным. Они “поиграли” с идеей из 2011 года, когда другие исследователи нашли способ быстро оценивать информацию, путем предварительной обработки, создавая специальные компактные таблицы значений, которые позволяют пропускать обычные этапы оценки.
Этот метод не принес улучшений, и группа почти отказалась от идеи, когда начала рассматривать вариант для работы с одним сервером. Если выбрать правильный полином (Полиномы являются одним из основных понятий в математике и широко используются в различных областях науки и инженерии), то результаты показывали, что один сервер может обработать всю информацию находящуюся на нём, на основе результатов 2011 года, получив безопасную и эффективную схему поиска, над которой Викс размышлял много лет. Внезапно, таким образом, они смогли решить текущую проблему.
Сначала авторы не поверили в это.
"Надо узнать, в чем тут ошибка", - вспоминал Викс. "Мы продолжали пытаться найти то, где возможно произошла ошибка."
Но алгоритм работал верно. Викс и его команда действительно обнаружила безопасный способ предварительной обработки базы данных с одним сервером, чтобы любой человек смог безопасно извлекать информацию.
"Это превзошло все наши надежды", - сказал Юваль Исхай, криптограф в Технионе. “Это результат, на который мы даже не посмели бы надеяться", - сказал он.
После того как исследователи построили свою схему конфиденциального поиска, они перешли к мировой приватности интернет-поиска, который был более сложен, чем извлечение фрагментов информации из базы данных, сказал Викс. Схема приватного поиска может работать совместно с приватной версией Google, но это крайне трудоёмки процесс - вы сами запускаете алгоритм Google и “тайно” извлекаете данные из интернета по мере необходимости. Викс заявил, что традиционный способ поиска информации, при котором человек задает запрос и ждет от сервера ответов, по сути, является целью для обширной стратегии, известной как гомоморфное шифрование (Форма шифрования, позволяющая производить определённые математические действия с зашифрованным текстом и получать зашифрованный результат, который соответствует результату операций, выполненных с открытым текстом), которое скрывает данные так, что другой человек может работать с ними, ничего не зная о том, что происходит за "кулисам".
Традиционные методы гомоморфного шифрования сталкиваются с аналогичной проблемой, что конфиденциальный поиск информации, очень долго просматривает все содержимое интернета для каждого запроса. Однако, используя свой метод частного поиска в качестве фундамента, авторы разработали новую схему, которая выполняет вычисления, близкие к программам, которые мы используем каждый день при этом конфиденциально извлекая информацию, без необходимости просматривать весь интернет. Это может повысить эффективность поиска в интернете и других программ, требующих быстрого доступа к данным.
Несмотря на то, что гомоморфное шифрование является полезным расширением схемы приватного поиска, Ишая считает, что конфиденциальный поиск информации представляет более фундаментальную проблему. Решение авторов - становится "волшебным строительным блоком", и их стратегия гомоморфного шифрования - естественное дополнение.
На данный момент ни одна из схем практически не пригодна. Предварительная обработка помогает в крайних случаях, когда размер базы данных стремится к бесконечности. Но ее фактическое внедрение означает, что эти “экономии” не могут реализоваться, и процесс потребует слишком много времени и места для хранения.
К счастью, сказал Вайкунтанатан, у криптографов долгая история оптимизации результатов, которые изначально казались непрактичными. Если будущие исследования смогут улучшить этот подход, то приватные поиски в гигантских базах данных могут стать реальностью.
"Мы все думали, что мы как бы застряли", - сказал он.
"То, что дает результат Даниэля, - это надежда."
В заключение, криптографы всё таки смогли найти решение для долговременной проблемы конфиденциальности. Теперь, используя новые знания и навыки, специалисты смогут создать инновационные методы шифрования, которые позволяя защитить информацию от несанкционированного доступа. Это значительно повысит уровень безопасности как в личной жизни людей, так и в бизнесе. Возможно, уже в ближайшем будущем, благодаря усилиям криптографов, мы сможем смело использовать новые технологии с полной уверенностью в безопасности наших данных.