Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Prob[(P, V){x) = Принять \xeL]^e (18.2.2) I
и
Prob[(P, V)(x) = Принять \х<?Ь]^6, (18.2.3)
где числа е и 6 являются константами, удовлетворяющими условиям
ЦИ'Чо'0- (18-2-4)
Вероятностное пространство состоит из всех входных значений протокола (Р, V) и всех случайных входных данных пользователей Р uV.
Оценка (18.2.2) характеризует полноту (completeness) протокола (Р, V). Величина е называется вероятностью полноты (completeness probability) протокола (Р, V). Это значит, что если х G L, то проверяющая сторона V принимает предложение х с вероятностью, которая не меньше величины е.
Оценка (18.2.3) характеризует непротиворечивость (soundness) протокола (Р, V). Величина 6 называется вероятностью противоречивости протокола (Р, V). Это значит, что если х ? L, то проверяющая сторона V принимает предложение х с вероятностью, не превышающей величины 6.
Сравнивая определение 18.1 с определением 4.5 (из раздела 4.4), в котором | описан класс алгоритмов W, получаем следующий результат.
Теорема 18.1. IV = W, где XV — класс всех языков, допускающих распознавание своих предложений с помощью IP-протоколов.
Более того, из раздела 4.4.1 следует, что оценку вероятности полноты (соответственно противоречивости) можно увеличить (соответственно уменьшить).
Глава 18. Протоколы с нулевым разглашением
679
приблизив ее сколь угодно близко к единице (соответственно к нулю), последовательно и независимо повторяя протокол (Р, V) полиномиально ограниченное количество раз (зависящее от размера входного предложения). В этом случае проверяющая сторона V принимает решение путем голосования. Рассмотрим введенные понятия на примере протокола 18.1.
Протокол 18.1. Протокол интерактивного доказательства принадлежности подгруппе (* см. примечание 18.1 *)
ОБЩИЕ ВХОДНЫЕ ДАННЫЕ:
1. /: однонаправленная функция, определенная в группе Zn и удовлетворяющая гомоморфному условию:
Vx, yeZn:f(x + y) = /(я) • f(y).
2. X = f{z) для некоторого z е Ъп. ЗАКРЫТЫЕ ВХОДНЫЕ ДАННЫЕ АЛИСЫ:
z < п. ЗАКЛЮЧЕНИЕ БОБА:
X е (/(1)), т.е. элемент X порождается элементом /(1).
Следующие шаги выполняются т раз.
1. Алиса генерирует число к е и%п, находит число Commit <— f(k) и посылает его Бобу.
2. Боб генерирует число Challenge е rj{0,1} и посылает его Алисе.
если Challenge = О,
[к
3. Алиса вычисляет число Response
+ z(modn), если Challenge = 1,
и посылает его Бобу.
,._ . ? (Commit, если Challenge = О,
4. Боб проверяет значение /(Response) = <
I CommitX, если Challenge = 1.
Если проверка завершается неудачно, Боб посылает отказ и прекращает работу протокола. Боб принимает доказательство.
Пример 18.1. В протоколе 18.1 Алиса является доказывающей, а Боб — проверяющей стороной. Общими входными данными Алисы и Боба является число X = f(z), где функция / является однонаправленной и гомоморфной функцией, заданной над группой Ъп. Утверждение о принадлежности формулируется Алисой и выглядит следующим образом: X е {/(я) | я е Zn}. Оно означает, что элемент X принадлежит подгруппе (/(1)), поскольку X = /(I)2 (см. замеча-
680
Часть VI. Криптографические протоколы
ние 18.1, в котором показано, почему Бобу трудно решить эту задачу). Закрытыми входными данными Алисы является элемент z G Zn — прообраз элемента X при однонаправленном и гомоморфном отображении /.
В протоколе 18.1 обе стороны вступают в контакт т раз и создают следующую стенограмму доказательства.
Commiti, Challenge^ Responsel5..., Commit™, Challengem, Responsem.
Протокол выводит результат Принять, если каждая проверка, выполняемая Бобом, завершается успешно. В противном случае результатом является слово Отклонить.
Описанный протокол является полным. Иначе говоря, если Алиса знает прообраз z и следует инструкциям, то Боб всегда будет отвечать: Принять.
Действительно, оценка вероятности полноты протокола (18.2.2) выполняется^ причем е = 1, поскольку ответы Алисы всегда успешно проходят проверку у Боба, т.е.
при любом выборе случайного числа Challenge &и{®, 1}-Протокол является непротиворечивым.
Непротиворечивость
Оценим вероятность противоречивости 6.
Результат проверки, выполняемой Бобом на этапе 4, зависит от случайного] выбора числа Challenge после получения числа Commit от Алисы. Проверка за! вершается успешно в двух случаях.
Вариант Challenge = 0: Боб видит, что Алисе известен прообраз числа Commit, i Вариант Challenge = 1: Боб видит число
Поскольку Алиса не может предугадать случайный выбор Боба после получения передачи, если передаваемое число не равно единице, она должна знать npoo6pa3(Commit), а значит, и прообраз(Х).
Если Алиса не знает число прообраз(Х), она может сжульничать, попытав-)! шись угадать случайный бит оклика перед отправкой своей передачи. В "нечестном" доказательстве Алиса вычисляет передаваемое значение следующим образом.
• Выбирает случайное число Response е Zn.
• Угадывает число Challenge.
Полнота
если Challenge = 0, если Challenge = 1,
прообраз(-АТ) = Response — npoo6pa3(Commit)(mod п).
• Вычисляет число Commit <—
если Challenge = 0, если Challenge = 1.
