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

TL;DR: мы построили новую схему получения скрытой информации (Private Information Retrieval, PIR), которую мы назвали FrodoPIR, которая, как мы надеемся, облегчит и удешевит внедрение PIR для многих кейсов, таких как сейфбраузинг, проверка паролей из утёкших баз данных, проверка отзыва сертификатов, стриминг и т.д. Имплементация этой схемы с открытым исходным кодом доступна здесь, а также вы можете ознакомиться со статьёй, более глубоко раскрывающей суть схемы (статья будет опубликована в PoPETS 2023). Мы назвали нашу сеть FrodoPIR, так как клиент может выполнять скрытые запросы к серверу, как Фродо, который спрятался от Саурона.

Конфиденциальный доступ к базам данных

Почему возможность конфиденциального доступа к базам данных важна? Предположим, что вы очень любите смотреть видео с щенками и хотите использовать для этого вашу любимую стриминговую платформу. Однако же, вам немного стыдно выдавать платформе, как много видео с щенками вы смотрите (вам не должно быть за это стыдно, но таков мир, в котором мы живём). Более того, вы хотели бы, чтобы эти данные не попали никому в руки, чтобы не стать, к примеру, целью множества навязчивых кампаний таргетированной рекламы. То есть было бы замечательно, если бы было можно получить желаемый контент при том, чтобы (ненадёжный) провайдер не знал, что именно за контент вы получаете.

Схемы получения скрытой информации (Private Information Retrieval, PIR) — это множество криптографических протоколов, которые призваны решить именно эту проблему. Первые прототипы этих схем появились ещё в девяностые, однако же, реалистичные варианты их реализации появились только в последние 6-7 лет, да и теперь не без сложностей: многие схемы решают слишком специфичные задачи или слишком сложны в имплементации.

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

Что такое PIR

Обобщая, большинство односерверных схем PIR работают с использованием инструмента шифрования, известного как аддитивное гомоморфное шифрование (AHE). Такая схема позволяет кому-либо с двумя шифротекстами, кодирующими А и Б, просчитать шифротекст, кодирующий А+Б без знания секретного ключа. Подобные схемы существуют со времён RSA, а один из наиболее часто встречающихся примеров — криптосистема Пэйе.

Но как построить на основе этого протокол PIR? Ответ весьма прост:

1. Сервер организует свою базу данных как множество из М рядов, каждый из которых содержит один элемент. Другими словами, база данных теперь вектор.

2. Любой клиент, желающий узнать i-тый элемент, шифрует М шифротекстов, где i-тый шифротекст шифрует 1, а остальные шифруют 0.

3. Клиент отправляет свои шифротексты на сервер, который не может знать, что именно зашифровано, благодаря самой природе шифровки.

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

5. После того, как клиент расшифрует каждый шифротекст, он легко узнает db_entry_i, так как: 0db_entry_1,…,1db_entry_i,…,0*db_entry_M = db_entry_i.

За последние годы было убедительно показано, что схемы PIR могут быть успешно и эффективно реализованы с использованием этого простого метода (и некоторых оптимизаций). Это достигается использованием схем AHE, основанных на криптографии на решётках, в частности на основе полностью гомоморфного шифрования (FHE), где безопасность выводится из предположения кольцевого обучения с ошибками (RLWE).

Отметим следующее:

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

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

• Мы предполагаем, что база данных сервера публична. Если речь идёт о чувствительной базе данных (клиенты не должны получать никакой информации, помимо прямо связанной с их запросом), то в данном случае PIR не является оптимальным инструментом (хотя существуют некоторые конструкции симметричного PIR, которые обладают потенциалом в данной области).

Ограничения существующих подходов

Мы в Brave давно хотели использовать PIR для того, чтобы клиенты получали определённые данные от наших серверов конфиденциально для самих серверов. Мы экспериментировали с различными уже существующими системами, но упирались либо в очень большую стоимость, либо в сложности в развёртывании подобных систем. Поняв это, мы решили вместо этого создать собственную систему, FrodoPIR. Каковы ограничения существующих систем?

Схемы PIR часто оказываются затратными либо с точки зрения пропускной способности, либо с точки зрения времени, необходимого на обработку каждого клиентского запроса. Чтобы уменьшить эти затраты, схемы PIR на основе FHE могут переносить значительную часть онлайн-вычислений и коммуникации (чем является, к примеру, отправка запроса) в офлайн-фазу («подготовительную»‎ фазу, которая может быть потом повторно использована для создания онлайн-запроса). Подобные схемы называются офлайн-онлайн или фиксирующими состояние (offline-online или stateful), в отличие от только онлайн, не фиксирующих состояние (online-only или stateless).

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

Встречайте FrodoPIR!

FrodoPIR — это фиксирующая состояние схема PIR, которая напрямую построена на модели обучения с ошибками. Как и нужно было сделать Фродо, мы избавились от колец (на решётках) для создания гибкой, практичной и мультифункциональной схемы PIR. Её ключевым элементом является офлайн-фаза, которой не требуются клиентозависимые исчисления и которая нуждается в относительно небольшом объёме передаваемой информации по сравнению с размером базы данных (в 170 раз меньше). Это делает нашу схему применимой для больших задач в реальном мире, где требуется уменьшение финансовых затрат на серверные операции. FrodoPIR значительно проще, чем схемы, которые предлагались ранее, он не пользуется инструментарием FHE и требует лишь модульной арифметики. (Вы можете ознакомиться с нашей статьёй здесь).

FrodoPIR базируется на задаче разрешимости обучения с ошибками (decisional LWE problem): каждый клиентский запрос — это шумный вектор, который выглядит единообразно случайным для сервера. У нашей схемы есть офлайн и онлайн фазы:

1. В офлайн-фазе сервер интерпретирует базу данных как матрицу, применяет к ней функцию сжатия и делает результаты сжатия публично доступными параметрами (mu и M). Это уменьшает размер базы данных. 

2. В офлайн-фазе клиент получает публичные параметры (mu и M) и исчисляет множества предварительно обработанных параметров запроса ‘c’.

3. В онлайн-фазе клиент использует единое множество предварительно обработанных параметров запроса для получения «зашифрованного»‎ вектора запроса, который отправляется на сервер.  

4. Сервер отвечает на запрос умножением вектора на свою матрицу базы данных.

5. Клиент возвращает результат, «дешифруя»‎ ответ сервера, используя свои предварительно обработанные параметры запроса. 

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

FrodoPIR — это мощный примитив, так как он позволяет применять схемы PIR в задачах реального мира, где необходимо учитывать не только вычислительные и коммуникационные, но и финансовые издержки. Схемы PIR вообще чрезвычайно полезны: их можно применять для безопасного браузинга, проверки потенциальных утечек паролей (и любых других учётных данных), проверки прозрачности и отзыва сертификатов, а также для стриминга. Дешёвые и эффективные схемы улучшат конфиденциальность интернета не только для больших игроков, но и для любого участника, предоставляющего подобные сервисы. 

Существуют и другие схемы PIR, но FrodoPIR выгоднее их, как вы можете убедиться из рис. 3, показывающего результаты сравнения вычислительных, коммуникационных и финансовых издержек в пересчёте на один клиент. Мы сравнили FrodoPIR, Stateful OnionPIR (SOnionPIR) и PSIR, с условием, что каждый клиент производит c = 500 запросов.

Что дальше для этой схемы, и как она будет задействована в Brave? Внедрение защищающих конфиденциальность схем является одним из наших приоритетов, так как это обеспечивает безопасность и конфиденциальность интернета. Одно из наших следующих направлений разработки — это чекер учётных данных, с помощью которого можно было бы проверить, нет ли любых учётных данных, введённых через браузер Brave (например, паролей) в уже известных утёкших базах данных. В свою очередь, это станет безопасным механизмом, который будет сигнализировать пользователям о том, что им, к примеру, необходимо сменить пароль. Такие проверки (запросы к скомпрометированным базам данных) чувствительны к информационной безопасности, и FrodoPIR является прекрасным механизмом обеспечения недорогой, быстрой и эффективной конфиденциальности для подобных кейсов.