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



         

Схема подписи с верификацией по запросу - часть 4


Для доказательства нулевого разглашения необходимо для любого возможного проверяющего V* построить моделирующую машину
, которая является вероятностной машиной Тьюринга, работает за полиномиальное в среднем время и создает на выходе (без участия S) такое же распределение случайных величин, которое возникает у V* в результате выполнения протокола. В нашем случае, случайные величины, которые «видит» V*, - это h1, h2, и t. Необходимо доказать, что протокол верификации является доказательством с абсолютно нулевым разглашением, то есть моделирующая машина создает распределение случайных величин (h1,h2,t), которое в точности совпадает с их распределением, возникающим при выполнении протокола. Моделирующая машина
 использует в своей работе V* в качестве «черного ящика».

Моделирующая машина

    Запоминает состояние машины V*, то есть содержимое всех ее лент, внутреннее состояние и позиции головок на лентах. Затем получает от V*

значение d

и после этого снова запоминает состояние машины V*.

    Выбирает hÎRZq и вычисляет

 и
.

    Получает от V* значения a и b. Если

, то
 останавливается.

    Машина

 «отматывает» V*

на состояние, которое было запомнено в конце шага 1. Выбирает tÎRZq

и вычисляет

 и
.

    Машина

 передает V*

h1, h2 и получает ответ (a¢,b¢). Возможны два варианта:

    5.1.    a=a¢, b=b¢. В этом случае моделирование закончено и

 записывает на выходную ленту тройку (h1,h2,t) и останавливается.

    5.2.    a¹a¢ или b¹b¢. Отсюда следует, что

. Предположим, что b¹b¢. Из этого следует, что a¹a¢. Следовательно,
 может вычислить
. Отсюда (b¢-b)/(a-a¢)=l - дискретный логарифм r по основанию g.

6. Машина

 «отматывает» V*

на состояние, которое было заполнено в начале шага 1. Получает от V* значение d.

7. Выбирает hÎRZq вычисляет

 и
 и передает их V*.

8. Получает от V* значения a и b. Если

, то
 останавливается.


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