Path ORAM: сокрытие доступа к памяти

ORAM с путями, предложенный Стефановым, ван Дейком, Ши, Флетчером, Реном, Ю и Девадасом (2013), — наиболее значимая на практике конструкция ORAM. Она организует серверное хранилище в виде двоичного дерева корзин, где каждому листу соответствует позиция блока данных. В базовой форме ORAM с путями обеспечивает накладные расходы на обмен данными O(log^2 N) для каждого обращения и достаточно прост для реализации в нескольких сотнях строк программного кода.

Карта позиций — это структура данных на стороне клиента, сопоставляющая адрес каждого логического блока с листовым узлом двоичного дерева. Для базы данных из N блоков и дерева высоты L = log N карта позиций представляет собой массив из N индексов листьев. Перед обращением к блоку b клиент находит его текущий назначенный лист в карте позиций и назначает ему новый случайный лист. Путь к старому листу будет прочитан с сервера и записан обратно на сервер.

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

Серверное хранилище представляет собой полное двоичное дерево с L+1 уровнями (L = log N). Каждый узел (корзина) содержит Z блоков (обычно Z = 5). Листья соответствуют позициям блоков данных. Всего имеется N листовых узлов, поэтому общее количество узлов равно 2N-1, а общий объём серверного хранилища — O(NZ). Каждый путь от листа к корню содержит log N узлов и может вместить Z*log N блоков, обеспечивая ёмкость для стратегии вытеснения блоков с пути.

Чтобы прочитать блок b: (1) найти в карте позиций текущий лист l для b; (2) назначить b новый случайный лист l' и обновить карту позиций; (3) прочитать все корзины на пути от листа l к корню (log N корзин); (4) найти блок b на прочитанном пути или в буфере; (5) записать обратно все блоки, которые можно назначить новому пути l', а оставшиеся места в корзинах заполнить фиктивными блоками. Сервер каждый раз видит чтение случайного пути.

ORAM с путями сохраняет свойство сокрытия доступа, поскольку при каждом обращении читает и записывает ровно один путь от корня к листу независимо от того, к какому блоку обращаются. Путь определяется равномерно случайным назначением листа, а не содержимым или адресом блока. Фиктивные блоки заполняют пустые места в корзинах, чтобы каждый путь содержал одинаковое количество занятых мест. Противник, наблюдающий за сервером, видит только обращения к случайным путям.

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

Наивная карта позиций требует хранить на клиенте N записей, то есть O(N) клиентского хранилища — столько же, сколько занимает вся база данных. Рекурсивная карта позиций уменьшает объём клиентского хранилища до O(log^2 N), поскольку сама карта позиций рекурсивно хранится в меньшем ORAM. Рекурсия завершается, когда ORAM становится достаточно малым, чтобы поместиться в буфере. Это стандартный способ сделать ORAM с путями практичным для больших наборов данных.

Размер буфера в ORAM с путями увеличивается, если блоки нельзя вытеснить на назначенные им пути из-за конфликтов путей. Стефанов и др. доказали, что буфер переполняется (превышает R блоков) с вероятностью, экспоненциально малой по R, — в стандартном анализе она составляет не более 14 * (0.6002)^R. При R = 40 вероятность сбоя равна примерно 2^{-38}, причём это верно для любых последовательностей обращений, включая выбранные противником.

До появления ORAM с путями лучшие практические конструкции ORAM имели накладные расходы O(log^3 N) (Ши и др., 2011, «ORAM со скрытым доступом и затратами в худшем случае O((log N)^3)»). ORAM с путями уменьшил их до O(log^2 N) благодаря гораздо более простой структуре. Последующие работы (ORAM на логических схемах, OptORAMa) дополнительно улучшили константы и асимптотические оценки, но ORAM с путями остаётся наиболее широко реализованной конструкцией благодаря своей простоте.

ORAM с путями реализован в десятках исследовательских и промышленных систем. ZeroTrace (Intel SGX + ORAM с путями), Obladi (ORAM с путями в облачном хранилище) и Opaque (ORAM с путями поверх Apache Spark) — заметные примеры таких реализаций. Стэнфордская группа по защищённым вычислениям поддерживает реализацию ORAM с путями на C++ с открытым исходным кодом. AWS предлагает ORAM с путями в составе исследовательских прототипов Nitro Enclaves для анализа данных с сохранением конфиденциальности.

Какова роль карты позиций в ORAM с путями?

ORAM с путями организует серверное хранилище в виде двоичного дерева, где при каждом обращении читается или записывается один путь от корня к листу. Карта позиций отслеживает текущий назначенный лист каждого блока, а буфер временно хранит недавно использованные блоки. Каждое обращение рандомизируется назначением новых случайных позиций листьев, благодаря чему все видимые серверу обращения имеют одинаковое распределение. Накладные расходы на обмен данными составляют O(Z * log N) для каждого обращения. Рекурсивные карты позиций уменьшают объём клиентского хранилища до O(log^2 N). ORAM с путями — наиболее широко реализованная конструкция ORAM.