Path ORAM: Приховування шаблонів доступу до пам’яті

Деревоподібна структура та карта розташування

Path ORAM зберігає N логічних блоків всередині бінарного дерева з приблизно N листовими вузлами, де кожен вузол дерева є контейнером (бакетом), здатним утримувати невелику постійну кількість блоків, зазвичай чотири, плюс заповнення дрібними блок-заповнювачами, коли бакет не повний. Клієнт підтримує карту розташування, вихідний стовпчик, який асоціює кожен ідентифікатор логічного блоку з випадково обраним листовим вузлом, тобто клієнт завжди знає, до якого листового вузла належить блок, навіть якщо точне розташування блоку вздовж шляху від кореня до цього листового вузла може змінюватися. Оскільки сама карта розташування може бути великою для великих наборів даних, практичні реалізації рекурсивно зберігають її в меншому ORAM, зменшуючи розмір метаданих клієнта до того, що комфортно поміщається в локальну пам'ять. Ця деревоподібна структура робить Path ORAM ефективною порівняно з ранішими конструкціями ORAM на основі квадратного кореня та ієрархічних ORAM: замість переміщення всього набору даних при кожному доступі потрібно лише торкатися одного шляху, довжина якого є лише логарифмічною відносно загальної кількості блоків.

Доступний протокол: читати, виганяти, перемальовувати

Кожна операція, будь то логічне читання або логічне записування, дотримується одного й того ж трьох кроків, і ця однорідність саме по собі приховує, чи була операція читанням, чи записом. По-перше, клієнт шукає поточний лист для цільового блоку у своєму карті позицій та завантажує всі барабани вздовж шляху від кореня до цього листа, дешифруючи їх локально, щоб знайти цільовий блок серед реальних і фіктивних записів. По-друге, клієнт оновлює блок, якщо це було записом, або просто зберігає його значення без змін, якщо це було читанням. По-третє, перш ніж щось повертати на сервер, клієнт призначає доступному блоку новий випадковий лист і потім повторно шифрує весь шлях, жадібно просуваючи всі барабани, які він зараз утримує, включаючи ті, що були отримані з попередніх доступу та все ще чекають на виганяння, наскільки це дозволено його власним призначеним шляхом, перш ніж записувати весь шлях назад на сервер. Оскільки кожен доступ завантажує та перезавантажує повний шлях барабанів з свіжим шифруванням незалежно від того, який логічний блок було запрошено, спостерігач, що стежить за адресами барабанів, бачить лише випадковий лист на кожній операції, без кореляції до блоку, до якого зверталися, або до того, чи було це читанням чи записом.

Чому перемальовування до випадкового листка запобігає витоку шаблонів

Найважливіший трюк у Path ORAM полягає в тому, що обраний блок завжди призначається свіжому, незалежно випадковому листку негайно після звернення до нього, перш ніж він повертається на сервер. Це означає, що навіть якщо клієнт запитує один і той же логічний блок двічі поспіль, обидва доступі торкаються двох незалежних випадкових шляхів через дерево, оскільки карта позицій тепер вказує кудись зовсім нове після першого доступу. Без цього кроку перемальовування повторні звернення до популярного блоку будуть простежувати один і той же шлях знову і знову, дозволяючи пасивному спостерігачеві негайно помітити, який блок є гарячим, навіть не розшифровуючи нічого. Доказ безпеки Path ORAM формалізує це, показуючи, що послідовність завантажених та завантажених шляхів обчислювально відмінна від послідовності випадково вибраних шляхів, рівномірно розподілених незалежно від фактичного шаблону доступу клієнта, що є точним криптографічним визначенням непомітності, яке прагне досягти схема.

Зберігання: захисна сітка для переповнених блоків

Оскільки ємність кошика фіксована та невелика, немає гарантії, що кожен блок, який зараз знаходиться у клієнтській пам’яті, зможе бути відправлений вниз по призначеному шляху під час виселення, особливо враховуючи, що багато блоків на перехресних шляхах конкурують за обмежену кількість слотів кошика. Path ORAM вирішує це завдяки клієнтному сховищу – невеликому локальному буферу, який тимчасово зберігає блоки, які не могли бути повернуті до дерева під час поточного виселення. Під час наступного доступу ці схоплені блоки знову стають доступними для відправки вниз по будь-якому новому шляху, який зараз читається, а завдяки ретельному аналізу видно, що середній розмір сховища залишається дуже малим і ймовірність його перевищення дорівнює нулю, за умови, що розмір кошика підібрано правильно, зазвичай чотири фізичні слоти на кошик. Це сховище – ціна, яку платиться за підтримку логарифмічної пропускної здатності: замість того, щоб змушувати кожен виселення досягти успіху, протокол дозволяє тимчасову затримку, яка природним чином вирішується при подальшому доступі до перехресних шляхів.

Вартість, випадки використання та місцезнаходження Path ORAM

Path ORAM's overhead is dominated by path length: each logical access transfers O(log N) buckets, each holding a small constant number of blocks, giving an overall bandwidth blowup of O(log N) times the block size rather than the O(N) blowup of naive shuffle-everything approaches or the higher polylogarithmic factors of earlier hierarchical ORAM schemes. This efficiency has made it the workhorse behind secure processor designs like Intel SGX-oriented oblivious memory controllers, encrypted cloud storage systems that want to hide query patterns from the storage provider, and secure multiparty computation protocols that need oblivious memory as a building block.

The tradeoffs are real: there is genuine bandwidth and latency overhead compared to plaintext access, the client must maintain nontrivial local state such as the position map and stash, and naive recursion for the position map needs care to avoid becoming a bottleneck itself. Still, for scenarios where leaking access patterns is unacceptable, such as private database queries, encrypted search, or oblivious code execution, Path ORAM remains one of the most practical and widely implemented solutions available.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Path ORAM: Hiding Memory Access Patterns і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.