Не обращая внимания на ОЗУ

Симулятор Oblivious RAM (ORAM) — это компилятор , который преобразует алгоритм таким образом, что полученный алгоритм сохраняет поведение ввода - вывода исходного алгоритма, но распределение шаблонов доступа к памяти преобразованного алгоритма не зависит от доступа к памяти. образец исходного алгоритма.

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

Это определение подходит для таких настроек, как защищенные программы, работающие в незащищенной общей памяти , или клиенты, запускающие программы в своих системах путем доступа к ранее сохраненным данным на удаленном сервере . Концепция была сформулирована Одедом Гольдрейхом и Рафаилом Островским в 1996 году.

Определение

Говорят, что машина Тьюринга (TM), математическая абстракция реального компьютера (программы), не обращает внимания , если для любых двух входных данных одинаковой длины движения головок ленты остаются одинаковыми. Пиппенгер и Фишер доказал, что каждая ТМ со временем работы $T(n)$ можно заставить забыть, и что время работы забывчивого ТМ $O(T(n)\log T(n))$. Более реалистичной моделью вычислений является модель RAM . В модели вычислений RAM имеется ЦП , который может выполнять основные математические, логические и управляющие инструкции. Процессор также связан с несколькими регистрами и физической оперативной памятью , где он хранит операнды своих инструкций. ЦП также имеет инструкции для чтения содержимого ячейки памяти и записи определенного значения в ячейку памяти. Определение ORAM отражает аналогичное понятие игнорирования доступа к памяти в модели RAM.

Неформально, ORAM — это алгоритм на интерфейсе защищенного ЦП и физического ОЗУ, который действует как ОЗУ для ЦП, запрашивая физическую ОЗУ для ЦП, при этом скрывая информацию о фактическом шаблоне доступа к памяти ЦП от физическая оперативная память. Другими словами, распределение обращений к памяти двух программ, совершающих одинаковое количество обращений к оперативной памяти, неотличимо друг от друга. Это описание по-прежнему будет иметь смысл, если ЦП будет заменен клиентом с небольшим хранилищем, а физическое ОЗУ заменено удаленным сервером с большой емкостью хранилища, на котором находятся данные клиента.

Ниже приводится формальное определение ORAM. Позволять $\Pi$ обозначают программу, требующую памяти размером $n$ при выполнении на входе $x$. Предположим, что $\Pi$ имеет инструкции по основным математическим и управляющим операциям, а также две специальные инструкции. ${\mathsf {read}}(l)$ и ${\mathsf {write}}(l,v)$, где ${\mathsf {read}}(l)$ считывает значение в местоположении $l$ и ${\mathsf {write}}(l,v)$ записывает значение $v$ к $l$. Последовательность ячеек памяти, к которым обращается программа $\Pi$ во время его выполнения называется шаблоном доступа к памяти и обозначается ${\tilde {\Pi }}(n,x)$.

Алгоритм с полиномиальным временем $C$ представляет собой компилятор Oblivious RAM (ORAM) с вычислительными издержками. $c(\cdot )$ и накладные расходы на память $m(\cdot )$, если $C$ данный $n\in N$ и детерминированная программа RAM $\Pi$ с объемом памяти $n$ выводит программу $\Pi _{0}$ с объемом памяти $m(n)\cdot n$ такой, что для любого входа $x$, время работы $\Pi _{0}(n,x)$ ограничен $c(n)\cdot T$ где $T$ это время работы $\Pi (n,x)$, и существует пренебрежимо малая функция $\mu$ такие, что выполняются следующие свойства:

• Корректность: Для любого $n\in \mathbb {N}$ и любая строка $x\in \{0,1\}^{*}$, с вероятностью по крайней мере $1-\mu (n)$, $\Pi (n,x)=\Pi _{0}(n,x)$.
• Забывчивость: Для любых двух программ $\Pi _{1},\Pi _{2}$, любой $n\in \mathbb {N}$ и любые два входа, $x_{1},x_{2}\in \{0,1\}^{*}$ если $|{\tilde {\Pi }}_{1}(n,x_{1})|=|{\tilde {\Pi }}_{2}(n,x_{2})|$, затем ${{\tilde {\Pi }}_{1}}'(n,x_{1})$ является $\mu$-близко к ${{\tilde {\Pi }}_{2}}'(n,x_{2})$ на статистическом расстоянии , где ${\Pi _{1}}'=C(n,\Pi _{1})$ и ${\Pi _{2}}'=C(n,\Pi _{2})$.

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

История ORAM

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

Основной результат в этой работе заключается в том, что существует компилятор ORAM, который использует $O(n)$ серверного пространства и требует дополнительных затрат времени в размере ${O(\log ^{3}n)}$ при создании программы, которая использует $n$ клетки памяти не обращают внимания. Существует несколько атрибутов, которые необходимо учитывать при сравнении различных конструкций ORAM. Наиболее важными параметрами производительности конструкции ORAM являются накладные расходы на пространство на стороне клиента, накладные расходы на пространство на стороне сервера и затраты времени, необходимые для осуществления одного доступа к памяти. На основании этих признаков построена Ашаров и др., под названием «OptORAMa» это первая оптимальная конструкция ORAM. Это достигает $O(1)$ клиентское хранилище, $O(n)$ серверное хранилище и $O(\log n)$ издержки доступа, соответствующие известным нижним границам.

Еще одним важным атрибутом конструкции ORAM является то, амортизируются ли издержки доступа или учитываются наихудшие условия . Некоторые более ранние конструкции ORAM имели хорошие гарантии амортизированных накладных расходов на доступ, но $\Omega (N)$ накладные расходы на доступ в худшем случае. Некоторые конструкции ORAM с полилогарифмическими вычислительными затратами в наихудшем случае являются таковыми. Конструкции были в модели случайного оракула, где клиент предполагает доступ к оракулу, который ведет себя как случайная функция и возвращает согласованные ответы на повторяющиеся запросы. Доступ к оракулу можно было бы заменить псевдослучайной функцией , начальным числом которой является секретный ключ, хранимый клиентом, если предположить существование односторонних функций . Документы были направлены на полное устранение этого предположения. Авторы также добиться накладных расходов на доступ в размере $O(\log ^{3}n)$

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

Одна из единственных известных нижних границ затрат на доступ к ORAM принадлежит Goldreich et al. Они показывают $\Omega (\log {n})$ нижняя граница накладных расходов на доступ к ORAM, где $n$ это размер данных. Другая нижняя оценка принадлежит Ларсену и Нильсену. Существует также условная нижняя граница накладных расходов на доступ к ORAM, предложенная Бойлом и др. что связывает эту величину с размером сортировочных сетей .

Конструкции ОРАМ

Тривиальная конструкция

Тривиальная конструкция симулятора ORAM для каждой операции чтения или записи считывает и записывает каждый отдельный элемент массива, выполняя значимое действие только для адреса, указанного в этой единственной операции. Таким образом, тривиальное решение сканирует всю память для каждой операции. Эта схема требует временных затрат в размере $\Omega (n)$ для каждой операции с памятью, где n — размер памяти.

Простая схема ORAM

Простая версия статистически безопасного компилятора ORAM, созданная Чунгом и Пассом. описывается ниже вместе с обзором доказательства его правильности. Компилятор на входе n и программе Π с требуемой памятью n выводит эквивалентную забывчивую программу Π′ .

Если входная программа Π использует r регистров, выходной программе Π' потребуется $r+n/{\alpha }+{\text{poly}}\log {n}$ регистры, где $\alpha >1$ является параметром конструкции. Π' использует $O(n{\text{ poly}}\log n)$ память и ее (в худшем случае) накладные расходы на доступ $O({\text{poly}}\log n)$.

Компилятор ORAM описать очень просто. Предположим, что исходная программа Π помимо двух специальных инструкций содержит инструкции для основных математических и управляющих операций. ${\mathsf {read}}(l)$ и ${\mathsf {write}}(l,v)$, где ${\mathsf {read}}(l)$ считывает значение в позиции l и ${\mathsf {write}}(l,v)$ записывает значение v в l . Компилятор ORAM при построении Π' просто заменяет каждую инструкцию чтения и записи подпрограммами Oread и Owrite , оставляя остальную часть программы прежней. Можно отметить, что эту конструкцию можно заставить работать даже с запросами к памяти, поступающими в режиме онлайн .

Компилятор ORAM заменяет инструкции чтения и записи в исходной программе подпрограммами Oread и Owrite.

Организация памяти забывчивой программы

Программа Π' хранит полное двоичное дерево T глубины $d=\log(n/\alpha )$ в его памяти. Каждый узел в T представлен двоичной строкой длиной не более d . Корень — это пустая строка, обозначаемая λ . Левый и правый дочерние элементы узла, представленного строкой $\gamma$ являются $\gamma _{0}$ и $\gamma _{1}$ соответственно. Программа Π' рассматривает память Π как разделенную на блоки, где каждый блок представляет собой непрерывную последовательность ячеек памяти размера α . Таким образом, существует не более $\lceil n/\alpha \rceil$ блоков всего. Другими словами, ячейка памяти r соответствует блоку $b=\lfloor r/\alpha \rfloor$.

Иллюстрация памяти забывчивой программы, показывающая двоичное дерево и карту позиций.

В любой момент времени между блоками и листьями в T существует связь . Чтобы отслеживать эту связь, Π' также хранит структуру данных, называемую картой положения, обозначаемую $Pos$, с использованием $O(n/\alpha )$ регистры. Эта структура данных для каждого блока b хранит лист T , связанный с b в $Pos(b)$.

Каждый узел в T содержит массив, содержащий не более K троек. Каждая тройка имеет вид $(b,Pos(b),v)$, где b — идентификатор блока, а v — содержимое блока. Здесь K является параметром безопасности и $O({\text{poly}}\log n)$.

Описание программы «Забывчивость»

Программа Π′ начинается с инициализации своей памяти, а также регистрируется в ⊥ . Описания процедур Owrite и Oread достаточно, чтобы завершить описание Π' . Подпрограмма Owrite приведена ниже. Входные данные подпрограммы представляют собой ячейку памяти. $l\in [n]$ и значение v, которое должно быть сохранено в местоположении l . Он состоит из трех основных фаз: FETCH, PUT_BACK и FLUSH.

 input: a location l, a value v

 Procedure FETCH  // Search for the required block.
   $b\leftarrow \lfloor l/\alpha \rfloor$    // b is the block containing l.
   $i\leftarrow l\mod \alpha$    // i is l's component in block b.
   $pos\leftarrow Pos(b)$
   if $pos=\perp$ then $pos\leftarrow _{R}[n/\alpha ]$.    // Set pos to a uniformly random leaf in T.
   flag $\leftarrow 0$.
   for each node N on the path from the root to pos do
     if N has a triple of the form $(b,pos,x)$ then
       Remove $(b,pos,x)$ from N, store x in a register, and write back the updated N to T.
       flag $\leftarrow 1$.
     else
       Write back N to T.

 Procedure PUT_BACK  // Add back the updated block at the root.
   $pos'\leftarrow _{R}[n/\alpha ]$.  // Set pos' to a uniformly random leaf in T.
   if flag$=1$ then
     Set x' to be the same as x except for v at the i-th position.
   else
     Set x' to be a block with v at i-th position and ⊥'s everywhere else.
   if there is space left in the root then
     Add the triple $(b,pos',x')$ to the root of T.
   else
     Abort outputting overflow.

 Procedure FLUSH  // Push the blocks present in a random path as far down as possible.
   $pos^{*}\leftarrow _{R}[n/\alpha ]$.  // Set $pos^{*}$ to a uniformly random leaf in T.
   for each triple $(b'',pos'',v'')$ in the nodes traversed the path from the root to $pos^{*}$
     Push down this triple to the node N that corresponds to the longest common prefix of $pos''$ and $pos^{*}$.
     if at any point some bucket is about to overflow then
       Abort outputting overflow.

— найти местоположение l в дереве T. Задача этапа FETCH Предположим, что pos — это лист, связанный с блоком, содержащим местоположение l . Для каждого узла N в T на пути от корня до pos эта процедура перебирает все тройки в N и ищет тройку, соответствующую блоку, содержащему l . Если он находит эту тройку в N , он удаляет тройку из N обновленное состояние N. и записывает обратно он просто записывает обратно весь узел N. В противном случае

На следующем этапе он обновляет блок, содержащий l, значением v , связывает этот блок со свежевыбранным равномерно случайным листом дерева и записывает обновленную тройку обратно в корень T. новым

Последняя фаза, которая называется FLUSH, представляет собой дополнительную операцию по освобождению ячеек памяти в корне и других более высоких внутренних узлах. В частности, алгоритм выбирает равномерно случайный лист. $pos^{*}$ а затем пытается максимально опустить каждый узел на пути от корня до $pos^{*}$. Он прерывает вывод переполнения, если в какой-то момент какая-то корзина вот-вот переполнит свою емкость.

Подпрограмма Oread аналогична Owrite . Для подпрограммы Oread входные данные — это просто ячейка памяти. $l\in [n]$ и это почти то же самое, что и Owrite . Если на этапе FETCH не найдена тройка, соответствующая местоположению l , оно возвращает ⊥ как значение в местоположении l . На этапе PUT_BACK он запишет обратно тот же блок, который он прочитал, в корень после связывания его со свежевыбранным равномерно случайным листом.

Корректность простой схемы ORAM

Пусть C обозначает компилятор ORAM, описанный выше. Для данной программы Π пусть Π′ обозначает $C(\Pi )$. Позволять $\Pi (n,x)$ обозначаем выполнение программы Π на входе x с использованием n ячеек памяти. Кроме того, пусть ${\tilde {\Pi }}(n,x)$ обозначают шаблон доступа к памяти $\Pi (n,x)$. Обозначим через µ функцию такую, что для любого $n\in \mathbb {N}$, для любой программы Π и для любого входа $x\in \{0,1\}^{*}$, вероятность того, что $\Pi '(n,x)$ выводит переполнение не более $\mu (n)$. Следующую лемму легко увидеть из описания C .

Лемма об эквивалентности

Позволять $n\in \mathbb {N}$ и $x\in \{0,1\}^{*}$. Дана программа Π с вероятностью не менее $1-\mu (n)$, выход $\Pi '(n,x)$ идентичен выходу $\Pi (n,x)$.

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

Лемма о забывчивости

Учитывая две программы ⁠ $\Pi _{1}$⁠ и ⁠ $\Pi _{2}$⁠ и два входа $x_{1},x_{2}\in \{0,1\}^{*}$ такой, что $|{\tilde {\Pi _{1}}}(x_{1},n)|=|{\tilde {\Pi _{2}}}(x_{2},n)|$, с вероятностью по крайней мере $1-2\mu (n)$, шаблоны доступа ${\tilde {\Pi _{1}'}}(x_{1},n)$ и ${\tilde {\Pi _{2}'}}(x_{2},n)$ идентичны.

Следующая лемма завершает доказательство корректности схемы ORAM.

Лемма о переполнении

Существует пренебрежимо малая функция µ такая, что для каждой программы Π , каждого n и входа x программа $\Pi '(n,x)$ выходы переполняются с вероятностью не более $\mu (n)$.

Накладные расходы на вычисления и память

Во время каждой операции Oread и Owrite два случайных пути от корня к листу T полностью исследуются Π' . Это занимает $O(K\cdot \log(n/\alpha ))$ время. Это то же самое, что и вычислительные затраты, и $O({\text{poly}}\log n)$ поскольку К ​ $O({\text{poly}}\log n)$.

Общий объем памяти, используемый Π′, равен размеру T . Каждая тройка, хранящаяся в дереве, имеет $\alpha +2$ слова в нем и, таким образом, есть $K(\alpha +2)$ слов на узел дерева. Поскольку общее количество узлов в дереве равно $O(n/\alpha )$, общий объем памяти $O(nK)$ слова, что $O(n{\text{ poly}}\log n)$. Следовательно, затраты памяти на конструкцию равны $O({\text{poly}}\log n)$.

См. также

• Забывчивая структура данных
• Алгоритм, не обращающий внимания на кэш