Circuit ORAM и практическая производительность

ORAM на логических схемах, предложенный Ваном, Чаном и Ши (2015), разработан для минимизации накладных расходов на пропускную способность и простоты реализации в средах защищённых вычислений (искажённые схемы и разделение секрета). Его ключевое нововведение — уменьшение размера корзины до Z = 2 блоков (по сравнению с Z = 5 в ORAM с путями), что вдвое сокращает объём передаваемых данных при сохранении пренебрежимо малой вероятности сбоя. Процедура вытеснения была переработана так, чтобы её можно было представить в виде небольшой булевой схемы.

В ORAM с путями при Z = 5 вероятность переполнения буфера контролируется наличием нескольких блоков в каждой корзине, чтобы вместить случайно назначенные блокам пути. ORAM на логических схемах доказывает, что Z = 2 достаточно при использовании детерминированной процедуры вытеснения (вытеснения сначала из глубины), а не случайного вытеснения. Это вдвое уменьшает объём серверного хранилища и накладные расходы на обмен данными по сравнению с ORAM с путями при одинаковых параметрах безопасности.

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

Для базы данных из N блоков размером B байт ORAM на логических схемах требует 2 * log N * B байт для каждого обращения (чтение и запись одного пути с Z = 2 блоками в каждой корзине). Для N = 2^20 блоков по 4KB это составляет 160KB на обращение по сравнению с 400KB для ORAM с путями (Z=5). Для типичных параметров накладные расходы на пропускную способность по сравнению с открытым текстом составляют около 40 раз, что меньше показателя 100 раз у ORAM с путями.

Oblix (Мисра, Шлегель, Шервуд, Цудик, 2018) использует ORAM на логических схемах для построения высокоуровневых структур данных со скрытым доступом: связанных списков со скрытым доступом, карт со скрытым доступом (хеш-таблиц) и очередей с приоритетом со скрытым доступом. Эти структуры позволяют выполнять вычисления над динамическими данными без раскрытия шаблонов доступа. Oblix работает внутри анклавов Intel SGX и предназначен для защищённого вычисления пересечения частных множеств и приватных запросов к базам данных.

TaoStore (Sahin, Zhu, Gunter, Borisov, 2016) расширяет Path ORAM для поддержки асинхронного доступа с высокой пропускной способностью: несколько запросов ORAM обрабатываются параллельно, а вытеснения путей объединяются в пакеты. Объединяя обращения к одному и тому же пути, TaoStore обеспечивает значительно более высокую пропускную способность (число запросов в секунду), чем синхронные конструкции ORAM, что делает его подходящим для серверов облачного хранилища с большим числом одновременно работающих клиентов.

Obladi (Crooks, Park, Alvisi, Iyengar, 2018) строит полноценную транзакционную систему хранения данных поверх Path ORAM. Obladi поддерживает транзакции ACID в зашифрованном хранилище со скрытым шаблоном доступа. В системе введено отложенное выполнение: транзакции объединяются в эпохи и выполняются так, чтобы скрыть, к каким именно записям обращались в пределах каждой эпохи. Obladi работает как доверенный посредник между клиентами и недоверенной серверной частью облачного хранилища.

Для ORAM размером 1 ГБ (262 144 блока по 4 КБ), развёрнутого в AWS, когда клиент обращается к блокам через интернет, задержка Path ORAM составляет примерно 50–200 мс на обращение (главным образом из-за времени кругового прохождения при обращении к корзинам на log N = 18 уровнях). При параллельной загрузке корзин задержку можно уменьшить. Для локальных приложений SGX с ORAM в RAM задержка составляет 1–10 мс на обращение, что приемлемо для многих приложений защищённых вычислений.

Накладные расходы ORAM на передачу данных сильно зависят от шаблонов доступа. Для облачного ORAM-хранилища объёмом 1 ТБ с блоками по 1 МБ каждое обращение передаёт около 25 МБ (25-кратные накладные расходы при log N = 25 уровнях). Для небольших блоков (4 КБ) абсолютный объём накладных расходов на обращение ниже, но относительно исходного объёма он выше. Организации, разворачивающие ORAM, должны закладывать увеличение объёма передаваемых данных в 20–50 раз и учитывать это при расчёте пропускной способности сетевых соединений и стоимости исходящего трафика в облаке.

Альтернативой ORAM для обеспечения конфиденциальности доступа служит доверенное оборудование: Intel SGX или AMD SEV предоставляет доверенную среду выполнения, в которой даже OS хоста не может наблюдать вычисления или шаблоны обращений к памяти (при наличии надлежащих средств защиты). SGX без ORAM всё равно допускает утечку шаблонов доступа на уровне страниц аппаратному обеспечению, поэтому для полной защиты требуется ORAM внутри SGX. По сравнению с одним только ORAM доверенное оборудование уменьшает накладные расходы на передачу данных, но требует доверия к производителю оборудования и цепочке поставок.

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

Какой размер корзины использует Circuit ORAM и почему это является улучшением по сравнению с Path ORAM?

Circuit ORAM уменьшает размер корзины до Z=2 (по сравнению с Z=5 в Path ORAM), вдвое сокращая объём передаваемых данных благодаря детерминированному вытеснению от глубоких уровней к корню. Система предназначена для использования внутри защищённых вычислений на искажённых схемах. Для типичных параметров практические накладные расходы составляют 40-кратное увеличение объёма передаваемых данных. В промышленных системах используются Oblix (SGX и структуры данных со скрытием доступа), TaoStore (высокопроизводительный пакетный ORAM) и Obladi (транзакционный ORAM). ORAM внутри SGX необходим, поскольку один только SGX допускает утечку шаблонов доступа на уровне страниц.