Так как при случайном выборе

Так как при случайном выборе значения d логарифм loggd может быть вычислен с вероятностью, которая не является пренебрежимо малой, это противоречит гипотезе о трудности вычисления дискретных логарифмов.

Далее доказывается, что отвергающий протокол является доказательством с абсолютно нулевым разглашением. Для этого необходимо для всякого возможного проверяющего V*

построить моделирующую машину

, которая создает на выходе (без участия S) такое же распределение случайных величин (в данном случае, c и R), какое возникает у V* в результате выполнения протокола.

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

Следующие шаги выполняются в цикле l раз.

Машина

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

Получает от V*

значения a, b и d.

Выбирает aÎR{0,1}, RÎRZq и вычисляет

. Посылает V* значение c.

Получает от V*

значение e.

Проверяет, было ли «угадано» на шаге 2 значение a (это значение было «угадано», если

и a=0, либо

и a=1). Если да, то записывает на входную ленту значение (c,R). В противном случае «отматывает» V* на то состояние, которое было запомнено на шаге 1, и переходит на шаг 2.

Легко видеть, что распределения случайных величин (c,R), возникающее в процессе выполнения протокола и создаваемые моделирующей машиной

, одинаковы, поскольку R в обоих случаях - чисто случайная величина, а величина c

записывается на выходную ленту машины

только тогда, когда a совпало с b.

Поскольку значение a выбирается машиной

на шаге 3 случайным образом, а c не дает V*

никакой информации о значении a, на каждой итерации a

будет угадано с вероятностью 1/2. Отсюда следует, что машина

работает за полиномиальное в среднем время. n

В работе [Ка14] показано, как строить схемы конвертируемой и селективно конвертируемой подписи с верификацией по запросу на основе отечественного стандарта ГОСТ Р 34.10-94. В таких схемах открытие определенного секретного параметра некоторой схемы подписи с верификацией по запросу позволяет трансформировать последнюю в обычную схему цифровой подписи.При этом открытие секретного параметра в конвертируемой схеме подписи с верификацией по запросу дает возможность верифицировать все имеющиеся и сгенерированные в дальнейшем подписи, в то время как в селективно конвертируемых схемах подписи с верификацией по запросу можно верифицировать лишь какую-либо одну подпись.

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