Доказательство

Доказательство. Информация, доступная невмешивающемуся противнику состоит из сообщений, обмениваемых между ЦП и МП. Напомним, что сообщения от CPUk к MEMk имеют форму (i,a,v), где i{выборка, сохранить, стоп}, a{1,2,...,2k} и v{0,1}O(k), в то время как сообщения от MEMk до CPUk имеют форму v{0,1}O(k). При забывающем моделировании, по определению, "область адресов" (т.е., a) не вскрывает никакой информации относительно входа y=(Пf,x). Просто необходимо устранить возможность, когда "область команд" (т.е., i) обеспечивает любую информацию посредством модификации ЦП так, чтобы всегда имелся доступ к ячейкам памяти при первой выборке. Следовательно, все что осталось должно "зашифровывать" содержимое области значений (т.е., v) так, чтобы ЦП мог восстанавливать оригинальное значение. Идея состоит в том, чтобы выполнить шифрование, используя оракул, доступный ЦП.

Для шифрования CPUk содержит специальный счетчик, обозначаемый счт, инициализированный нулевым значением. Мы модифицируем RAMk добавлением случайного оракула, обозначаемого f. Понятно, что новый случайный оракул может быть объединен со случайным оракулом, используемым при забывающем моделировании. Всякий раз, когда CPUk должен сохранять значение (либо старое значение, которое только читалось, либо новое значение) в памяти MEMk, счетчик счт увеличивается и значение v шифруется посредством пары (vf(счт),счт), где обозначает поразрядную операцию "исключающую или". При восстановлении пары (u,j), зашифрованное значение восстанавливается посредством вычисления uf(j). Подчеркнем, что и шифрование, и дешифрование может быть легко выполнены, когда имеется доступ к оракулу f.

Компилятор C, защищающий программное обеспечение, функционирует следующим образом. На входе параметр k и программы П, состоящей из последовательности команд π1,..,πn, компилятор однороно выбирает функцию f и множества Пf=(π1 f(2k+1),2k+1),...,(πn f(2k+n),2k+n).

Так как общее время выполнения машины RAMk во всех экспериментах, инициированных противником, является не более 2k, мы никогда не используем тот же самый аргумент f для двух различных операций шифрования. Это следует из того, что шифрование (которое использует шифр "одноразовый блокнот") абсолютно безопасно (в информационнотеоретическом смысле), и следовательно, противник не получает никакой информации относительно оригинального содержания области значений.

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

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

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

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

Центральный процессор CPUk, рассмотренный в предыдущей теореме, далее модифицируется следующим образом. Модифицированная машина CPUk имеет доступ к еще одной случайной функции, обозначаемой f. Эта функция может быть объединена с другими. В случае, если CPUk должен сохранить зашифрованное значение v в ячейке памяти он сначала определяет текущий номер версии a. Отметим, что номер версии(a) может быть вычислен CPUk в соответствии с определением моделирования с метками времени. Модифицированная машина CPUk теперь посылает сообщение (сохранить, a, (v,f(a,версия(a),v))) вместо сообщения (сохранить,a,v), посланного первоначально. После получения сообщения (v,t) из МП в ответ на запрос (выборка,a,'), модифицированная машина CPUk определяет текущее значение номера версия(a) и сравнивает t с f(a, версия(a),v). В случае, если эти два значения равны CPUk работает как и прежде. В противном случае, CPUk немедленно останавливается, предотвращая, таким образом, защиту от вмешательства. Таким образом, попытки изменить сообщения от МП к ЦП будут обнаружены с очень высокой вероятностью.


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

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


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

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