Дополнения к базовой модели и вероятностные RAMмашины

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

Для каждого k N определим оракульный CPUk как CPUk с двумя дополнительными лентами, названными оракульными лентами. Одна из этих лент является "толькодлячтения", а другая "толькодлязаписи". Всякий раз, когда машина входит в специальное состояние вызова оракула, содержимое оракульной ленты "толькодлячтения" изменяется мгновенно (т.е., за единственный шаг) и машина переходит к другому специальному состоянию. Строка, записанная на оракульной ленте "толькодлячтения" между двумя вызовами оракула называется запросом, соответствующим последнему вызову. Будем считать, что CPUk имеет доступ к функции f, если делается запрос q и оракул отвечает и изменяет содержимое оракульной ленты "толькодлячтения" на f(q). Вероятностная машина CPUk это оракульная машина CPUk с доступом к однородно выбранной функции

f:{0,1}O(k) > {0,1}.

Для каждого k N определим оракульную RAMkмашину как RAMkмашину, в которой машина CPUk заменена на оракульную CPUk. Скажем, что эта RAMkмашина имеет доступ к функции f, если CPUk имеет доступ к функции f и будем обозначать как RAMkf. Вероятностная RAMkмашина это RAMkмашина, в которой CPUk заменен вероятностным CPUk. (Другими словами, вероятностная RAMkмашина это оракульная RAMkмашина с доступом к однородно выбранной функции).

Повторные выполнения RAMмашины. Для решения проблемы защиты программ необходимо использовать повторные выполнения "одной и той же" RAMпрограммы на нескольких входах. Задача состоит в том, что RАМмашина начинает следующее выполнение с рабочими лентами ЦП и МП, имеющих содержимое, идентичное их содержимому при окончании предыдущего выполнения программы.

Для каждого k N, повторные выполнения RAMkмашины на входной последовательности y1,y2,... рассматриваются как последовательность вычислений RAMkмашины, при котором первое вычисление началось с входа y1, когда рабочие ленты и СРUk, и MEMk пусты и iтое вычисление начинается с входа уi, когда рабочая лента каждой машины (т.е., и СРUk, и MEMk) содержит ту же самую строку, которую она содержала по окончании i1 вычисления.

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

Для простоты, основное внимание будет уделяться противникам с экспоненциально ограниченным временем выполнения. Кроме того, время выполнения противника ограничено сверху 2n, где n размер рабочей ленты ЦП. На практике противник будет ограничен по времени некоторым полиномом от длины рабочей ленты ЦП.

Невмешивающийся противник, обозначаемый как ADV является вероятностной машиной, которая на входе k и "шифрованной программе" α, которая имеет следующий доступ к оракульной RAMkмашине. Машина ADV инициирует повторные выполнения RAMkмашины на входах по своему выбору до тех пор, пока общее время выполнения не стане равным 2k. В процессе каждого из этих выполнений, машина ADV имеет доступ "толькодлячтения" к коммуникационным лентам между CPUk и MEMk.

Вмешивающийся противник определяется аналогично невмешивающемуся противнику за исключением того, что в процессе повторных выполнений противник имеет доступ для чтения и записи к коммуникационным лентам между CPUk и МЕМk.

Преобразования, защищающие программное обеспечение

Определим компиляторы, которые по данной программе П, производят пару (ff), где f случайно выбранная функция и Пf "зашифрованная программа", которая соответствует П и f. Здесь имеется в виду оракульная RAMмашина, которая на входе (Пf) и при доступе к оракулу f моделирует выполнение П на данных х так, чтобы это моделирование "защищало бы" оригинальную программу П.

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


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

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


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

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