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

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

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

6. Боб выбирает случайное число x, меньшее n и взаимно простое с n. Он посылает Алисе:

a = x² mod n

7. Алиса, зная p и q, вычисляет четыре квадратных корня a: x, n-x, y и n-y. Она случайным образом выбирает любой из этих корней и посылает его Бобу.

8. Если Боб получает y или n-y, он может вычислит наибольший общий делитель x+y и n, которым будет либо p, либо q. Затем, конечно же, n/p = q. Если Боб получает x или n-x, он не может ничего вычислить.

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

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

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

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

7. Алиса выбирает большое случайное число x и шифрует его открытым ключом Боба.

c = E_B(x)

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

9. Боб вычисляет следующие 100 чисел:

y_u = D_B(c-i+u), для 1u100

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

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

z_u = (y_u mod p), для 1u100

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

|z_u - z_м|  2

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

0 < z_u < p-1

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

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

z_l, z₂, . . . z_j, z_j+1+1, z_j+2+1, . . . z₁₀₀+1, p

11. Алиса проверяет, конгруэнтен ли i-ый член последовательности x mod p. Если это так, она делает вывод, что ij. В противном случае она решает, что i> j.

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

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

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

Пример протокола

Пусть они используют RSA. Открытым ключом Боба является 7, а закрытым - 23. n = 55. Секретное число Алисы, i, равно 4, секретное число Боба, j - 2. (Предположим, что числа i и j могут принимать только значения 1, 2, 3 и 4.)

7. Алиса выбирает x = 39 и c = E_B(39) = 19.

8. Алиса вычисляет c-i=19-4=15. Она посылает 15 Бобу.

9. Боб вычисляет следующие четыре числа:

y₁ = D_B{15+l) =26

y₂ = D_B{15+2) = 18

y₃ = D_B{15+3) =2

y₄ = D_B{15+4) = 39

Он выбирает p = 31 и вычисляет:

z₁ = (26 mod 31) = 26

z₂ = (18 mod 31) =18

z₃ = (2 mod 31) = 2

z₄ = (39 mod 31) = 8

Он выполняет все проверки и убеждается, что последовательность правильна.

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

26, 18, 2+1, 8+1, 31, т.е., 26, 18, 3, 9, 31

11. Алиса проверяет, конгруэнтно ли четвертое число X mod p. Так как 9  39 (mod 31 ), то i > j.

12. Алиса сообщает об этом Бобу.

Этот протокол можно использовать для создания намного более сложных протоколов. Группа людей может проводить секретный аукцион по сети. Они логически упорядочивают себя по кругу и, с помощью попарных сравнений, определяют, кто предложил большую цену. Чтобы помешать людям уже изменять сделанные предложения в середине аукциона должен использоваться какой-то протокол вручения битов. Если аукцион проводится по голландской системе, то предложивший наивысшую цену получает предмет за предложенную цену. Если аукцион проводится по английской системе, то он получает предмет за вторую высшую цену. (Это может быть выяснено во время второго круга попарных сравнений.) Аналогичные идеи применимы при заключении сделок, переговорах и арбитраже.