Забывающая RAM - Oblivious RAM - Wikipedia

An не обращая внимания на RAM (ORAM) симулятор это компилятор что трансформирует алгоритмы таким образом, чтобы полученные алгоритмы сохраняли Вход -выход поведение исходного алгоритма, но распределение из объем памяти Шаблон доступа преобразованного алгоритма не зависит от шаблона доступа к памяти исходного алгоритма. Определение ORAM мотивировано тем фактом, что злоумышленник может получить нетривиальную информацию о выполнении программы и природе данные что он имеет дело, просто наблюдая за шаблоном, в котором во время его выполнения осуществляется доступ к различным областям памяти. Злоумышленник может получить эту информацию, даже если все значения данных зашифрованный. Определение одинаково хорошо подходит для настроек защищенных программ, работающих на незащищенных Общая память а также клиент, запускающий программу в своей системе, получая доступ к ранее сохраненным данным на удаленный сервер. Концепция была сформулирована Одед Гольдрайх в 1987 г.[1]

Определение

А Машина Тьюринга (TM), математическая абстракция реального компьютера (программы), называется не обращая внимания если для любых двух входов одинаковой длины движения головок ленты остаются прежними. Пиппенгер и Фишер[2] доказали, что каждая ТМ с наработкой можно заставить забыть, и что время работы не обращающей внимания ТМ . Более реалистичной моделью вычислений является Модель RAM. В модели вычислений RAM есть ЦПУ который может выполнять основные математические, логические и управляющие инструкции. ЦП также связан с несколькими регистры и физический произвольный доступ объем памяти, где хранятся операнды своих инструкций. ЦП дополнительно имеет инструкции для чтения содержимого ячейки памяти и записи определенного значения в ячейку памяти. Определение ORAM отражает аналогичное понятие доступа к памяти без внимания в этой модели.

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

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

А полиномиальный алгоритм, это компилятор Oblivious RAM (ORAM) с вычислительными затратами и накладные расходы на память , если данный и детерминированная программа RAM с размером памяти выводит программу с размером памяти так что для любого ввода , время работы ограничен куда время работы , и существует незначительная функция такие, что выполняются следующие свойства:

  • Правильность: Для любого и любая строка , с вероятностью не менее , .
  • Забывчивость: Для любых двух программ , любой и любые два входа, если , тогда является -рядом с в статистическое расстояние, куда и .

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

История ORAM

ORAM были представлены Goldreich и Островского[1][4][5] при этом ключевой мотивацией была заявлена ​​защита программного обеспечения от злоумышленника, который может наблюдать схему доступа к памяти (но не ее содержимое).

Главный результат в этой работе[5] заключается в том, что существует компилятор ORAM, который использует пространство на сервере и накладные расходы времени работы при создании программы, использующей клетки памяти не обращают внимания. Эта работа положила начало ряду работ по созданию незаметных RAM, которые продолжаются до сих пор. Есть несколько атрибутов, которые необходимо учитывать при сравнении различных конструкций ORAM. Наиболее важными параметрами конструкции ORAM являются объем клиентского хранилища, объем хранилища сервера и время, необходимое для выполнения одного доступа к памяти. Основываясь на этих атрибутах, конструкция Kushilevitz et al.[6] самая известная конструкция ORAM. Это достигает клиентское хранилище, серверное хранилище и накладные расходы доступа.

Еще одним важным атрибутом конструкции ORAM является то, есть ли накладные расходы на доступ. амортизированный или же худший случай. Некоторые из более ранних конструкций ORAM имеют хорошие гарантии амортизированного доступа, но имеют накладные расходы на доступ в худшем случае. Некоторые конструкции ORAM с полилогарифмический вычислительные накладные расходы в худшем случае составляют.[6][7][8][9][10] Конструкции[1][4][5] были для модели случайного оракула, где клиент предполагает доступ к оракулу, который ведет себя как случайная функция и возвращает согласованные ответы на повторяющиеся запросы. Они также отметили, что этот оракул может быть заменен псевдослучайной функцией, семя которой является секретным ключом, хранящимся клиентом, если предположить существование односторонних функций. Бумаги[11][12] были нацелены на полное исключение этого предположения. Авторы[12] также достичь накладных расходов доступа , что всего лишь на один лог-фактор от наиболее известных накладных расходов на доступ к ORAM.

В то время как большинство более ранних работ сосредоточено на доказательстве безопасности с помощью вычислений, есть более свежие работы.[3][8][11][12] которые используют более сильное статистическое понятие безопасности.

Одна из немногих известных нижних границ накладных расходов на доступ для ORAM принадлежит Goldreich et al.[5] Они показывают нижняя граница накладных расходов на доступ к ORAM, где это размер данных. Существует также условная нижняя граница накладных расходов на доступ для ORAM, обусловленная Бойлом и др.[13] что связывает это количество с размером сортировочных сетей.

Конструкции ORAM

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

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

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

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

Если входная программа Π использует р регистры, программа вывода Π ′ будет нужно регистры, где - параметр конструкции. Π ′ использует память и ее (в худшем случае) накладные расходы на доступ .

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

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

Организация памяти невнимательной программы

Программа Π ′ хранит полное двоичное дерево Т глубины в его памяти. Каждый узел в Т представлен двоичной строкой длиной не более d. Корень - это пустая строка, обозначенная λ. Левый и правый дочерние элементы узла, представленного строкой находятся и соответственно. Программа Π ′ думает о памяти Π как разделенные на блоки, где каждый блок представляет собой непрерывную последовательность ячеек памяти размером α. Таким образом, есть не более всего блоков. Другими словами, ячейка памяти р соответствует блоку .

В любой момент времени существует связь между блоками и листьями в Т.Чтобы отслеживать эту ассоциацию, Π ′ также хранит структуру данных, называемую картой положения, обозначенную , с помощью регистры. Эта структура данных для каждого блока б, хранит лист Т связана с б в .

Каждый узел в Т содержит массив с не более чем K троек. Каждая тройка имеет вид , куда б это идентификатор блока и v - это содержимое блока. Здесь, K является параметром безопасности и .

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

Описание не обращающей внимания программы

Программа Π ′ начинается с инициализации своей памяти, а также регистров для . Описание процедур Писать и Oread достаточно, чтобы завершить описание Π ′. Подпрограмма Писать приведен ниже. Входные данные подпрограммы - это ячейка памяти. и ценность v для хранения на месте л. Он состоит из трех основных фаз, а именно FETCH, PUT_BACK и FLUSH.

    Вход: местоположение л, ценность v
    Процедура FETCH     // Найдите нужный блок.                   // б это блок, содержащий л.                   // я является лкомпонент в блоке б.                  если  тогда .          // Набор  к равномерно случайному листу в Т.         флаг .         за каждый узел N на пути от корня к  делать              если N имеет тройку вида  тогда                   Удалять  из N, хранить Икс в реестр и напишите обновленные N к Т. флаг .              еще                   Написать ответ N к Т.    Процедура PUT_BACK     // Добавьте обратно обновленный блок в корень.         .     // Набор  к равномерно случайному листу в Т.         если флаг тогда              Набор  быть таким же, как Икс кроме v на я-я позиция. еще              Набор  быть блоком с v в я-я позиция и повсюду. если в корне осталось место тогда              Добавьте тройку  к корню Т.         еще              Прервать вывод переполнение.    Процедура FLUSH     // Толкайте блоки, находящиеся в случайном порядке, как можно глубже.         .     // Набор  к равномерно случайному листу в Т.         за каждая тройка  в узлах пройден путь от корня до               Прижмите эту тройку к узлу N что соответствует самому длинному общему префиксу  и .              если в любой момент ведро вот-вот переполнится тогда                   Прервать вывод переполнение.

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

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

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

Подпрограмма Oread похоже на Писать. Для Oread подпрограмма, ввод - это просто место в памяти и это почти то же самое, что Писать. На этапе FETCH, если он не находит тройку, соответствующую местоположению л, он возвращается как значение на месте л. На этапе PUT_BACK он будет записывать обратно тот же блок, который считал, в корень, после связывания его со свежевыбранным равномерно случайным листом.

Правильность простой схемы ORAM

Позволять C обозначает компилятор ORAM, описанный выше. Учитывая программу Π, позволять Π ′ обозначать . Позволять обозначают выполнение программы Π на входе Икс с помощью п ячейки памяти. Кроме того, пусть обозначают шаблон доступа к памяти . Позволять μ обозначим такую ​​функцию, что для любого , для любой программы Π и для любого входа , вероятность того, что выводит переполнение не более . Следующую лемму легко увидеть из описания C.

Лемма об эквивалентности
Позволять и . Учитывая программу Π, с вероятностью не менее , выход идентичен выходу .

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

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

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

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

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

Во время каждого Oread и Писать операции, два случайных пути от корня к листу Т полностью изучены Π ′. Это требует время. Это то же самое, что и вычислительные накладные расходы, и составляет поскольку K является .

Общий объем памяти, использованный Π ′ равен размеру Т. Каждая тройка, хранящаяся в дереве, имеет слов в нем и, таким образом, есть слов на узел дерева. Поскольку общее количество узлов в дереве равно , общий объем памяти слова, что . Следовательно, накладные расходы на память конструкции составляют .


Рекомендации

  1. ^ а б c Гольдрайх, Одед (1987), «К теории защиты программного обеспечения и моделирования с помощью забытых RAM», в Ахо, Альфред В. (ред.), Материалы 19-го ежегодного симпозиума ACM по теории вычислений (STOC '87), Ассоциация вычислительной техники, стр. 182–194, Дои:10.1145/28395.28416
  2. ^ Пиппенгер, Николас; Фишер, Майкл Дж. (1979), «Отношения между мерами сложности», Журнал ACM, 26 (2): 361–381, Дои:10.1145/322123.322138, МИСТЕР  0528038
  3. ^ а б c Чунг, Кай-Мин; Пройдите, Рафаэль (2013), "Простой ORAM", IACR Cryptology ePrint Archive
  4. ^ а б Островский, Рафаил (1990), «Эффективные вычисления на забытых RAM», Материалы 22-го ежегодного симпозиума ACM по теории вычислений (STOC '90), Ассоциация вычислительной техники, стр. 514–523, Дои:10.1145/100216.100289
  5. ^ а б c d Гольдрайх, Одед; Островский, Рафаил (1996), "Программная защита и моделирование на не обращающей внимания RAM", Журнал ACM, 43 (3): 431–473, Дои:10.1145/233551.233553, HDL:1721.1/103684, МИСТЕР  1408562
  6. ^ а б Кушилевиц, Эял; Лу, Стив; Островский, Рафаил (2012), «О (небезопасной) безопасности не обращающей внимания на хэш-память RAM и новой схеме балансировки», Материалы двадцать третьего ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, Ассоциация вычислительной техники, стр. 143–156, Дои:10.1137/1.9781611973099.13, МИСТЕР  3205204
  7. ^ Островский, Рафаил; Шуп, Виктор (1997), "Частное хранилище информации (расширенный аннотация)", в Лейтон, Ф. Томсон; Шор, Питер В. (ред.), Материалы двадцать девятого ежегодного симпозиума ACM по теории вычислений (STOC '97), Ассоциация вычислительной техники, стр. 294–303, Дои:10.1145/258533.258606
  8. ^ а б Ши, Элейн; Чан, Т.-Х. Юбер; Стефанов, Эмиль; Ли, Минфэй (2011), «Забывающая RAM с цена наихудшего случая », в Ли, Дон Хун; Ван, Сяоюнь (ред.), Достижения в криптологии - ASIACRYPT 2011 - 17-я Международная конференция по теории и применению криптологии и информационной безопасности, Сеул, Южная Корея, 4–8 декабря 2011 г., Труды, Конспект лекций по информатике, 7073, Springer, стр. 197–214, Дои:10.1007/978-3-642-25385-0_11
  9. ^ Гудрич, Майкл Т.; Митценмахер, Майкл; Охрименко, Ольга; Тамассия, Роберто (2011), «Забывающая симуляция RAM с эффективными накладными расходами доступа в худшем случае», в Качине, Кристиан; Ристенпарт, Томас (ред.), Материалы 3-го семинара ACM по безопасности облачных вычислений, CCSW 2011, Чикаго, Иллинойс, США, 21 октября 2011 г., Ассоциация вычислительной техники, стр. 95–100, Дои:10.1145/2046660.2046680
  10. ^ Чунг, Кай-Мин; Лю, Чжэньминь; Пасс, Рафаэль (2014), «Статистически безопасный ORAM с накладные расходы », Саркар, Палаш; Ивата, Тецу (ред.), Достижения в криптологии - ASIACRYPT 2014 - 20-я Международная конференция по теории и применению криптологии и информационной безопасности, Каошюн, Тайвань, Р.О.К., 7-11 декабря 2014 г., Материалы, часть II, Конспект лекций по информатике, 8874, Springer, стр. 62–81, Дои:10.1007/978-3-662-45608-8_4
  11. ^ а б Айтай, Миклош (2010), «Незабываемые ОЗУ без криптографических допущений [расширенная аннотация]», Материалы 42-го симпозиума ACM по теории вычислений (STOC 2010), Ассоциация вычислительной техники, стр. 181–190, Дои:10.1145/1806689.1806716, МИСТЕР  2743267
  12. ^ а б c Дамгард, Иван; Мелдгаард, Сигурд; Нильсен, Джеспер Буус (2011 г.), «Совершенно безопасная не обращающая внимания RAM без случайных оракулов», в Ishai, Yuval (ed.), Теория криптографии - 8-я конференция по теории криптографии, TCC 2011, Провиденс, Род-Айленд, США, 28-30 марта 2011 г., Труды, Конспект лекций по информатике, 6597, Springer, стр. 144–163, Дои:10.1007/978-3-642-19571-6_10
  13. ^ Бойл, Элетт; Наор, Мони (2016), «Есть ли незаметная нижняя граница ОЗУ?», Материалы конференции ACM по инновациям в теоретической информатике 2016 г. (ITCS '16), Ассоциация вычислительной техники, стр. 357–368, Дои:10.1145/2840728.2840761, МИСТЕР  3629839

Смотрите также