Теория и практика защиты программ


         

необходимо сделать следующее пояснение.


В противном случае вычисляет

t=[h-al-b](mod q), выдает (h1,h2,t) на выходную ленту и останавливается.

К пп. 7 и 8 необходимо сделать следующее пояснение. Поскольку logg(p)wºlogr(p)g, из этого следует, что logw(p)gºlogg(p)r. Отсюда

.

Из описания моделирующей машины
 очевидно, что она работает за полиномиальное время. Величины (h1,h2,t) на шаге 5.1 выбираются в точности как в протоколе и поэтому имеют такое же распределение вероятностей. Кроме того, значения (h1,h2), выбираемые на шаге 7, имеют такое же распределение, как и в протоколе. Чтобы показать что и t имеет одинаковое распределение, достаточно заметить, что машина V*

не может по h1 и h2 определить, с кем она имеет дело - с S или
. Поэтому, даже если бы V* могла каким-либо «хитрым» образом строить a и b с учетом (h1,h2), распределение вероятностей величин a

и b в обоих случаях одинаковы. Но значение t определяется однозначно четверкой величин a, b, h1, h2, при условии выполнения проверки на шаге 5 протокола.     n

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

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

Полнота протокола очевидна. Если абоненты S

и V следуют протоколу, тогда абонент V всегда примет доказательства абонента S.

Для доказательства корректности прежде всего заметим, что если logg(p)wºlogr(p)g, то a и b, выбираемые абонентом V

на шаге 1, не несут в себе никакой информации о значении b. Поэтому, если S может “открыть” c, сгенерированное им на шаге 2, лишь единственным образом (то есть выдать на шаге 4 единственное значение R, соответствующее данному a), то проверка на шаге 5 будет выполнена с вероятностью 1/2 в одном цикле и с вероятностью 1/2l во всех l циклах.

Если же S может сгенерировать c таким образом, что с вероятностью, которая не является пренебрежимо малой, он может на шаге 4 “открыть” оба значения a, то есть найти R1 и R2 такие, что
 и
, то алгоритм, который использует S для этой цели, можно использовать для вычисления дискретных логарифмов: loggd=R2-R1.

Содержание  Назад  Вперед