Доказательство с нулевым знанием того, что п является числом Блюма

(3) Алиса снимает маскировку с t, вычисляя

s = t^d/k mod n (4) Результатом является s = m^d mod n Это можно легко показать

/ _{s {}m_h?y _s „л (mod _й)_{; поэтому} <*/_ifc = „/_{м s} „/ (mod _и).

Чаум придумал целое семейство более сложных алгоритмов слепой подписи [320, 324], называемых неожи­данными слепыми подписями. Схемы этих подписей сложнее, но они дают больше возможностей.

23.13 Передача с забыванием

В этом протоколе, предложенном Майклом Рабином (Michael Rabin) [1286], Алиса с вероятностью 50 про­центов удается передать Бобу два простых числа,/; и q. Алиса не знает, успешно ли прошла передача (См. раз­дел 5.5.) (Этот протокол можно использовать для передачи Бобу любого сообщения с 50-процентной вероятно­стью успешной передачи, если/; и q раскрывают закрытый ключ RSA.)

(1) Алиса посылает Бобу произведение двух простых чисел: n = pq.

(2) Боб выбирает случайное число х, меньшее п и взаимно простое с п. Он посылает Алисе: a = x² mod n

(3) Алиса, зная/; и q, вычисляет четыре квадратных корня а: х, п-х, у и п-у. Она случайным образом выбирает любой из этих корней и посылает его Бобу.

(4) Если Боб получает у или п-у, он может вычислит наибольший общий делитель х+у и п, которым будет ли­бо/;, либо q. Затем, конечно же, nip = q. Если Боб получает х или п-х, он не может ничего вычислить.

У этого протокола может быть слабое место: возможна ситуация, когда Боб может вычислить такое число а, что при известном квадратном корне а он сможет все время раскладывать я на множители.

23.14 Безопасные вычисления с несколькими участниками

Этот протокол взят из [1373]. Алиса знает целое число i, а Боб - целое число/ Алиса и Боб вместе хотят уз­нать, что правильно - i<j или i>j, но ни Алиса, ни Боб не хочет раскрыть свое число партнеру. Этот особый слу­чай безопасных вычислений с несколькими участниками (см. раздел 6.2) иногда называют проблемой мил­лионера Яо [162, 7].

В приводимом примере предполагается, что i nj выбираются из диапазона от 1 до 100. У Боба есть откры­тый и закрытый ключи.

(1) Алиса выбирает большое случайное число х и шифрует его открытым ключом Боба. с = Е_в{х)

(2) Алиса вычисляет c-j и посылает результат Бобу.

(3) Боб вычисляет следующие 100 чисел: у_и = D_B(c-i+u), для 1<и<100

D_B обозначает дешифрирование закрытым ключом Боба.

Он выбирает большое случайное число р. (Размер р должен быть немного меньше х. Боб не знает х, но Алиса может легко сообщить ему размер х.) он вычисляет следующие 100 чисел:

z_u = (у_и mod/;), для 1<и<100

Далее он проверяет, что для всех u*v

\z_u - z_M\>2

и что для всех и

0 < z_u < p-l

Если это не так, то Боб выбирает другое простое число и пробует снова.

(4) Боб посылает Алисе эту последовательность чисел, соблюдая их точный порядок:

Z_h Z₂,... Zj, Z_j+l + \, Zy+2+1,... Z_W0+l, p

(5) Алиса проверяет, конгруэнтен ли г'-ый член последовательности х mod/;. Если это так, она делает вывод, что i<j. В противном случае она решает, что i> j.

(6) Алиса сообщает Бобу свои выводы.

Проверка, которую Боб выполняет на этапе (3), должна гарантировать, что ни одно число не появится дваж­ды в последовательности, генерированной на этапе (4). В противном случае, если z_a = z_b, Алиса узнает, что a <j <Ъ.

Недостатком этого протокола является то, что Алиса узнает результаты вычислений раньше Боба. Ничто не помешает ей завершить протокол на этапе (5), отказавшись сообщать Бобу результаты. Она даже может солгать Бобу на этапе (6).