Определение затрат забывающего моделирования

Теперь мы обратимся к определению затрат забывающего моделирования. Для данных вероятностных машин RAM'k' и RAMk предположим, что вероятностная RAM'k' моделирует забывающим образом вычисления RAMk и путь g:N > N есть некоторая целочисленная функция. Тогда затраты на моделирование являются не больше g, если для каждого y требуемое время выполнения RAM'k' на входе y ограничено сверху g(T)T, где T обозначает время выполнения RAMk на входе y.

Моделирование с метками времени. В заключение этого подраздела приводится свойство некоторого RAMмоделирования. Это свойство требует, чтобы при восстановлении значения из ячеек памяти, ЦП "знает" сколько раз содержимое этих ячеек модифицировалось. То есть, для данного адреса МП a и общего числа команд (обозначенных j), выполнение всех команд ЦП "запомнить в ячейку a" может быть эффективно вычислено алгоритмом Q(j,a). Далее рассматривается только моделирование детерминированных RAMмашин.

Для данной оракульной машины RAM'k', машины RAMk предположим, что оракульная RAM'k' с доступом к оракулу f' моделирует вычисления RAM'k'. Тогда моделирование является моделированием с метками времени, если существует O(k')временной алгоритм Q(',') такой, что выполняется следующее условие. Пусть (i,a,v) jтое сообщение, посланное CPU'k' (в процессе повторных выполнений RAM'k'). Тогда, число предыдущих сообщений формы ("запомнить",a,"), посланных CPU'k', равняется точно (j,a). Далее, необходимо обратить запустить алгоритм на Q(j,a) для получения номер версии(a) в раунде j. Таким образом, чтобы "знать" номер версии любого адреса в некоторый момент времени, достаточно для ЦП сохранить счет числа шагов, которые выполняются. Подчеркнем, что ЦП не мог бы позволить себе хранить номер версии всех адресов памяти, так что проставление меток времени важно для получения доказуемой защиты программ от вмешательства.

Сведение защиты программ к забывающему моделированию на RAMмашине

Наконец сейчас будет показано, как свести задачу защиты программ к задаче моделирования RAMмашины на забывающей RAMмашине. Эта задача заключается в сокрытии модели доступа, полностью игнорируя тот факт, что содержимое памяти и коммуникаций между ЦП и МП доступно для противника. Мы начинаем со сведения задачи достижения слабой защиты программ (т.е., защита от невмешивающихся противников) к построению забывающего RAMмоделирования. Далее мы сводим задачу защиты программ (доказуемой защиты от вмешательства) к построению забывающего моделирования с метками времени.

Защита программ от невмешивающихся противников. Напомним, что противник называется невмешивающимся, если все выбранные им входы инициируют выполнение программы на них и он читает содержимое памяти и коммуникаций между ЦП и МП при таком выполнении. Без потери общности, достаточно рассматривать противников, которые только читают коммуникационные ленты (так как содержимое ячеек памяти определено входом и коммуникациями между ЦП и МП). При использовании забывающего моделирования универсальной RAMмашины остается только скрыть содержимое "области значений" в сообщениях, обмениваемых между ЦП и МП. Это делается посредством шифрования, которое использует случайный оракул.

Теорема 2.1. Пусть {RAMk}k N вероятностная RAMмашина, которая выполняет забывающее моделирование универсальной RAMмашины. Кроме того, предположим, что t шагов оригинальной RAMмашины моделируются за менее чем g(t)t шагов забывающей RAMмашины. Тогда существует компилятор, который защищает программы от невмешивающихся противников с затратами не боле O(g(t)).


Ведете ли вы блог?

Да
Нет
Планирую


Результаты опроса

Новостной блок