Доказательство с нулевым знанием для дискретного логарифма

Пегги хочет доказать Виктору, что ей известно x, являющееся решением

A^xº B(mod p)

где p- простое число, а x- произвольное число, взаимно простое с p-1. Числа A, B и pобщедоступны, а xхранится в секрете. Вот как Пегги, не раскрывая значения x, может доказать, что оно ей известно (см. раздел 5.1) [338, 337].

(1) Пегги генерирует tслучайных чисел, r_l, r₂,... r_t, причем все r_iменьше p-1.

(2) Пегги вычисляет h_i= mod p для всех значений i и посылает их Виктору.

(3) Пегги и Виктор, воспользовавшись протоколом бросания монеты генерируют tбитов: b₁, b₂,... b_t.

(4) Для всех tбитов Пегги выполняет одну из следующих операций:

a) Если b_i = 0, она посылает Виктору r_i

b) Если b_i= 1, она посылает Виктору s_i= (r_i-r_j)mod (p-1), где j- наименьшее значение индекса, при котором b_j= 1

(5) Для всех tбитов Виктор проверяет одно из следующих условий:

a) При b_i= 0 что º h_i(mod p)

b) При b_i = 1 что º h_ih_j^-1 (mod p)

(6) Пегги посылает Виктору Z, где

Z= (x- r_j)mod (p-1)

(7) Виктор проверяет, что A^Zº Bh_j^-1(mod p)

Вероятность удачного мошенничества Пегги равна 1/2^t.