WikiDer > Незаметная структура данных

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

В Информатика, не обращая внимания на структуру данных представляет собой структуру данных, которая не дает никакой информации о последовательности или шаблоне операций, которые были применены, за исключением окончательного результата операций.^[1]

В большинстве случаев, даже если данные зашифрованы, шаблон доступа может быть достигнут, и этот шаблон может привести к утечке некоторой важной информации, такой как ключи шифрования. А в аутсорсинге облако данных, эта утечка шаблона доступа по-прежнему очень серьезна. Шаблон доступа - это спецификация режима доступа для каждого атрибута схемы отношения. Например, последовательности чтения или записи пользователем данных в облаке являются шаблонами доступа.

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

Приложения:

• Облачные данные аутсорсинг: При записи или чтении данных из облака сервер, незаметные структуры данных полезны. И современные база данных в значительной степени полагаются на структуру данных, поэтому незаметная структура данных пригодится.
• Защищенный процессор: защищенные процессоры с защитой от взлома используются для защиты от физических атак или для доступа злоумышленников к компьютерным платформам пользователей. Существующие защищенные процессоры, разработанные в научных кругах и промышленности, включают шифрование AEGIS и Intel SGX. Но адреса памяти по-прежнему передаются в открытом виде по шине памяти. Итак, исследование показало, что шины памяти могут выдавать информацию о шифрование ключи. Благодаря тому, что на практике используется структура данных Oblivious, защищенный процессор может скрыть шаблон доступа к памяти доказуемо безопасным способом.
• Безопасные вычисления: Традиционно люди использовали схемную модель для безопасных вычислений, но этой модели недостаточно для обеспечения безопасности, когда объем данных становится большим. В качестве альтернативы традиционной схемной модели было предложено безопасное вычисление по модели RAM, а для предотвращения кражи поведенческого доступа к информации используется не обращающая внимания структура данных.

Забывчивые структуры данных

Забывающая RAM

Гольдрейх и Островский предложили этот термин для защиты программного обеспечения.

Доступ к памяти не обращая внимания на RAM является вероятностным, и вероятностное распределение не зависит от входа. В статье, составленной Гольдрайхом и Островским, есть теорема для забывчивой RAM: пусть БАРАН(м) обозначают RAM с m ячейками памяти и доступом к случайной машине-оракулу. Тогда t шагов произвольной БАРАН(м) программа может быть смоделирована менее чем ${ Displaystyle О (т ( журнал _ {2} т) ^ {3})}$ шаги забывающего ${ displaystyle mathrm {RAM} (m ( log _ {2} m) ^ {2})}$. Каждая не обращающая внимания симуляция БАРАН(м) должен сделать как минимум ${ Displaystyle макс {м, (т-1) журнал _ {2} м }}$ доступа для имитации t шагов.

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

1. Для каждого ${ displaystyle { sqrt {m}}}$доступы, сначала произвольно переставляются ${ displaystyle m + { sqrt {m}}}$ объем памяти.
2. Сначала проверьте слова убежища, если мы хотим получить доступ к слову.
3. Если слово есть, выберите одно из фиктивных слов. А если слова там нет, найдите переставленное место.

Чтобы получить доступ к исходной ОЗУ за t шагов, нам нужно смоделировать ее с помощью ${ displaystyle t + { sqrt {m}}}$ шаги для забывчивой RAM. Стоимость каждого доступа составит O (${ displaystyle { sqrt {m}} cdot log m}$).

Другой способ моделирования - иерархический алгоритм. Основная идея состоит в том, чтобы рассматривать защищенную память как буфер и расширять ее до нескольких уровней буферов. Для уровня я, Существуют ${ displaystyle 4 ^ {i}}$ ведра, и для каждого ведра имеется журнал t элементов. Для каждого уровня есть случайная выбранная хеш-функция.

Операция выглядит следующим образом: Сначала загрузите программу до последнего уровня, который, можно сказать, имеет ${ displaystyle 4 ^ {t}}$ ведра. Для чтения проверьте ведро ${ displaystyle h_ {i} (V)}$ с каждого уровня, если (V, X) уже найден, случайным образом выберите ведро для доступа, а если оно не найдено, проверьте ведро ${ displaystyle h_ {i} (V)}$, есть только одно настоящее совпадение, а остальные - фиктивные записи. Для записи поместите (V, X) на первый уровень, и если первые уровни I заполнены, переместите все уровни I на ${ displaystyle I + 1}$ уровни и очистите первые I. уровни.

Временные затраты для каждого уровня затрат O (log t); стоимость каждого доступа ${ Displaystyle О (( журнал т) ^ {2})}$; Стоимость хеширования составляет ${ Displaystyle О (т ( журнал т) ^ {3})}$.

Забывчивое дерево

Забывающее дерево - это корневое дерево со следующим свойством:

• Все листья находятся на одном уровне.
• Все внутренние узлы имеют степень не выше 3.
• Только узлы на крайнем правом пути в дереве могут иметь степень один.

Невидимое дерево - это структура данных, похожая на 2-3 Дерево, но с дополнительным свойством не обращать внимания. Крайний правый путь может иметь степень один, и это может помочь описать алгоритмы обновления. Дерево забвения требует рандомизации для достижения ${ Displaystyle О ( журнал (п))}$ время выполнения операций обновления. И для двух последовательностей операций M и N, действующих с деревом, выходные данные дерева имеют одинаковые выходные распределения вероятностей. Для дерева есть три операции:

СОЗДАТЬ (L)

построить новое дерево, сохраняя последовательность значений L на его листьях.

ВСТАВИТЬ (b, i, T)

вставить новый листовой узел, сохраняющий значение b как i^th лист дерева Т.

Удалите это)

удалить я^th лист из Т.

Шаг создания: список узлов в i^thlevel получается обходом списка узлов на уровне i + 1 слева направо и повторением следующих действий:

1. Выбираем d {2, 3} равномерно наугад.
2. Если на уровне i + 1 осталось менее d узлов, установите d равным количеству оставшихся узлов.
3. Создайте новый узел n на уровне I со следующими d узлами на уровне i + 1 в качестве дочерних и вычислите размер n как сумму размеров его дочерних узлов.
   

   забывающее дерево

Например, если подбрасывание монеты d {2, 3} имеет результат: 2, 3, 2, 2, 2, 2, 3 сохраняет строку «OBLIVION», как показано в забытом дереве.

Оба ВСТАВИТЬ (b, I, T) и УДАЛИТЕ ЭТО) иметь ожидаемое время работы O (log n). И для ВСТАВЛЯТЬ и УДАЛИТЬу нас есть:

INSERT (b, I, CREATE (L)) = CREATE (L [1] + …… .., L [i], b, L [i + 1] ……… ..) DELETE (I, CREATE (L )) = СОЗДАТЬ (L [1] + ……… L [I - 1], L [i + 1], ……… ..)

Например, если СОЗДАТЬ (ABCDEFG) или же ВСТАВИТЬ (C; 2; СОЗДАТЬ (ABDEFG)) запускается, он дает одинаковые вероятности выхода между этими двумя операциями.

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

• Даниэле Миччансио. Незаметная структура данных: применение в криптографии.
• Одед Гольдрайх. Программная защита и моделирование на забывающем ОЗУ. TR-93-072, ноябрь 1993 г.
• Джон С. Митчелл и Джо Циммерман. Структуры данных, не обращающие внимания на данные. Департамент компьютерных наук, Стэнфордский университет, Стэнфорд, США.
• Крейг Джентри, Кенни А. Голдман, Шай Халеви, Чаранджит С. Ютла, Мариана Райкова и Дэниел Вичс. Оптимизация ORAM и эффективное использование для безопасных вычислений. Эмилиано де Кристофаро и Мэтью Райт, редакторы, технологии повышения конфиденциальности, том 7981 конспектов лекций по информатике, страницы 1–18. Springer, 2013 г.