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

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

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

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

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

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

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

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

  1. Машина MV` запоминает состояние машины V.
  2. Получает от V значения a, b и d.
  3. Выбирает αR{0,1}, RRZq и вычисляет cdagR(modp). Посылает V значение c.
  4. Получает от V значение e.
  5. Проверяет, было ли "угадано" на шаге 2 значение α (это значение было "угадано", если age(modp), bwe(modp) и α=0, либо α re(modp), e(modp) и α=1). Если да, то записывает на входную ленту значение (c, R). В противном случае "отматывает" V на то состояние, которое было запомнено на шаге 1, и переходит на шаг 2.

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

Поскольку значение α выбирается машиной MV` на шаге 3 случайным образом, а c не дает V никакой информации о значении α, на каждой итерации α будет угадано с вероятностью 1/2. Отсюда следует, что машина MV` работает за полиномиальное в среднем время.

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


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

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


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

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