Пегги хочет доказать Виктору, что ей известно х, являющееся решением Ax = B (jaod p)
тпер - простое число, а х - произвольное число, взаимно простое с р-. Числа А, В ир общедоступны, а х хранится в секрете. Вот как Пегги, не раскрывая значения х, может доказать, что оно ей известно (см. раздел 5.1) [338, 337].
(1) Пегги генерирует t случайных чисел, г, г2, . . . г,, причем все г, меньше р-1.
(2) Пегги вычисляет А,- = Ar- mod p для всех значений i и посылает их Виктору.
(3) Пегги и Виктор, воспользовавшись протоколом бросания монеты генерируют t битов: Ьи Ь2, . . . Ь,.
(4) Для всех t битов Пегги выполняет одну из следующих операций:
a) Если Ь, = 0, она посылает Виктору г,
b) Если *,■ = 1, она посылает Виктору s, = (г, - rj) mod (р-1), где; - наименьшее значение индекса, при котором bj = 1
(5) Для всех t битов Виктор проверяет одно из следующих условий:
a) При Ь, = 0 что Аг-■ = A,- (mod p)
b) При Ъ, = 1 что А* = h,hjl {mod p)
(6) Пегги посылает Виктору Z, где Z = (х- rj) mod (р-1)
(7) Виктор проверяет, что Az = Bhj1 (mod p)
Вероятность удачного мошенничества Пегги равна 1/2(.