Компилятор

Компилятор, обозначаемый через C, является вероятностным отображением, которое по входу целочисленного параметра k и программы П для RAMk возвращает пару (f,Пf) так, чтобы

  • f:{0,1}O(k) > {0,1} случайно выбранная функция;
  • f| =O(|П|);

Для k'=k+O(log k) существует оракульная RAMk'машина такая, что для каждой П, каждой f и каждого x {0,1} инициируется RAMk' на входе (Пf,x) и при доступе к оракулу f обеспечивает П(x).

Оракульная RAMk'машина отличается от RAMkмашины в том, что RAMk' имеет доступ к оракулу, в то время как RAMk нет. Понятно, что RAMk' имеет большую память, а именно RAMk'машина состоит из 2k'=poly(k)2k слов, в то время как память RAMk состоит из 2k слов.

Компиляторы, как определено выше, преобразовывают детерминированные программы в "зашифрованные программы", которые выполняются на вероятностных RAMмашинах. Теперь непосредственно обратимся к определениям компилятора, защищающего программное обеспечение.

Оракул спецификации для программы П это оракул, который на запрос x возвращает тройку (П(x),tП(x),sП(x)).

Отметим, что tП(x) и sП(x) обозначает время выполнения и пространственные размеры программы П на данных x. Далее даются основное определение для задачи защиты программ. В этом определении ADV может рассматриваться как вмешивающийся, так и невмешивающийся противник.

Для данного компилятора C и противника ADV, компилятор C защищает программное обеспечение против противника ADV, если существует вероятностная оракульная (в стандартном смысле) машина М, удовлетворяющая следующим условиям:

  • (М функционирует примерно за то же самое время, как и ADV): Существует полином p(') такой, что для каждой строки α время выполнения М на входе (k', |α|) (и с учетом доступа к случайному оракулу) было ограничено p(k')T, где T обозначает время выполнения ADV при экспериментировании с RAMk' на входе α.
  • (М с доступом к оракулу спецификации обеспечивает выход почти идентичный выходу ADV после экспериментирования с результатами работы компилятора): Для каждой программы П статистическое расстояние между следованием двух распределений вероятностей ограничено 2k'.

Распределение выхода машины ADV при экспериментировании с RAMkf на входе Пf, где (f,Пf)< C(П). Отметим, что RAMkf обозначает интерактивную пару (CPUk',MEMk'), где CPUk' имеет доступ к оракулу f. Распределение берется над пространством вероятностей, состоящим из всех возможных выборов функции f и всех возможных результатов выработки случайного бита ("подбрасываний монеты") машины ADV с равномерным распределением вероятностей.

Распределение выхода оракульной машины М на входе (k',O( П )) и при доступе к оракулу спецификации для П. Распределение берется над пространством вероятностей состоящим из всех возможных результатов подбрасываний монеты машины М с равномерным распределением вероятностей.

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

Далее будет определяться затраты защиты программ. Необходимо напомнить, что для простоты, мы ограничиваем время выполнения программы П следующим условием: tП(x)> |П| + |x| для всех x.

Пусть C компилятор и g:N > N некоторая целочисленная функция. Затраты компилятора C на большинстве аргументов g, если для каждой П, каждого x {0,1}* и каждой случайно выбранной f требуемое время выполнения RAMk' на входе (Пf,x) и при доступе к оракулу f ограничены сверху g(T)T, где T=tП(x).

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

Необходимо начать с определения модели доступа как последовательности ячеек памяти, к которым ЦП обращается в процессе вычислений. Это определение распространяется также на оракульный ЦП.

Модель доступа, обозначаемая как Аk(y) детерминированной RAMkмашины на входе y это последовательность (a1,...,ai,...) такая, что для каждого i, iтое сообщение, посланное CPUk при взаимодействии с MEMk(y) имеет форму (',ai,').

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

Модель доступа, обозначаемая как (y) вероятностной RAMkмашины на входе y это случайная величина, которая принимает значение модели доступа машины RAMk на некотором входе y и при доступе к однородно выбранной функции f.

Теперь можно перейти к определению забывающей RAMмашины. Мы определяем забывающую RAMмашину как вероятностную RAMмашину, для которой распределение вероятностей последовательности адресов памяти, к которым осуществляется доступ в процессе выполнения программы, зависит только от времени выполнения и не зависит от конкретного частичного входа. Для каждого k N определим забывающую RAMkмашину как вероятностную RAMkмашину, удовлетворяющую следующему условию. Для каждых двух строк y1 и y2, если |(y1)|и |(y2)| идентично распределены, тогда также идентично распределены (y1) и (y2).

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

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

Для данных машин, вероятностной RAM'k', и RAMk вероятностная машина RAM'k' моделирует забывающим образом RAMk, если выполняются следующие условия:

  • вероятностная машина RAM'k' моделирует RAMk с вероятностью 1. Другими словами, для каждого входа y и каждого выбора оракульной функции f выход оракула RAM'k' на входе y и при доступе к оракулу f равняется выходу RAMk на входе y.
  • вероятностная машина RAM'k' является забывающей. Необходимо подчеркнуть, что здесь рассматривается модель доступа RAM'k' на фиксированном входе и случайно выбранной оракульной функции.

Случайная величина, представляющая собой время выполнения вероятностной RAM'k' на входе y полностью определена текущим временем RAMk на входе y.

Следовательно, модель доступа при забывающем моделировании (которая описывается случайной величиной, определенной над выбором случайного оракула) имеет распределение, зависящее только от времени выполнения оригинальной машины. А именно, пусть(y) обозначает модель доступа при забывающем моделировании RAMk на входе y. Тогда (y1) и (y2) идентично распределены, если время выполнения RAMk на этих входах (т.е., y1 и y2) идентично.


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

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


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

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