Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Challenge = prf ("Осмысленное сообщение, подписанное Алисой" ||
ffResponseyChallenge (mod pj j_ (18.3.2)
Для любого постороннего лица уравнение (18.3.2) означает одно из двух. 1. Уравнение было составлено Алисой с помощью своих закрытых входных данных. В этом случае Алиса раскрывает свою связь с Бобом.
690
Часть VI. Криптографические протоколы
2. Боб успешно взломал псевдослучайную функцию prf с достаточно большим пространством значений Ъя, поскольку ему удалось создать уравнение вида
Challenge = prf (... yChalle"9e).
Как известно, эта задача практически неразрешима, поскольку функция prf
является однонаправленной. Если Боб применяет полиномиально ограниченный алгоритм, посторонний наблюдатель, конечно, решит, что имеет место первый вариант. В стенограмме доказательства (Commit, Challenge, Response) пара (Commit, Challenge), удовлетворяющая условиям (18.3.1) и (18.3.2), представляет собой подпись сообщения "Осмысленное сообщение, подписанное Алисой", созданную по схеме Шнорра (см. алгоритм 10.4, в котором prf = Н). Поскольку эту подпись могла поставить только Алиса (напомним, что в разделе 16.3.2 было доказано, что схема цифровой подписи Шнорра является неуязвимой для подделки с помощью атаки на основе адаптивно подобранных сообщений), посторонний наблюдатель делает правильный вывод!
Алису должно немного утешить, что раскрытая ею информация не является чрезвычайно важной (хотя это зависит от конкретного приложения). Как показано в разделе 7.5.2, если Алиса генерирует числа к е ifLq независимо от предыдущих значений, то величина
Response = к + а - Challenge(mod д)
обеспечивает шифрование секретного числа а с помощью одноразового блокнота, гарантируя стойкость в теоретико-информационном смысле. Это значит, что стенограмма доказательства остается Бобу неизвестной, причем посторонний наблюдатель не имеет никакой информации о секретном числе а, принадлежащем Алисе.
Однако, поскольку интерактивное доказательство сводится к подписи, которая не обязательно создается интерактивным способом, защита, обещанная интерактивным протоколом, оказывается взломанной: теперь любой посторонний наблюдатель может верифицировать результат доказательства. Это значит, что теперь доказательство больше не является секретным. По этой причине модифицированный вариант протокола идентификации Шнорра нельзя считать протоколом доказательства с нулевым разглашением!
Если протокол идентификации Шнорра использует большой оклик из группы Ъч, он называется протоколом с нулевым разглашением при честной верификации (honest-verifier zero-knowledge protocol). В этом случае, если верификатор честно следует инструкциям, протокол гарантирует идеальное нулевое разглашение. Это объясняется тем, что верификатор генерирует абсолютно случайные оклики, позволяющие эффективно вычислять стенограмму доказательства.
Глава 18. Протоколы с нулевым разглашением
691
Если в протоколе с нулевым разглашением при честной верификации (Р, V) поведение участника V фиксируется, и он не может вынуждать участника Р создавать некорректную стенограмму доказательства или стенограмму, не допускающую моделирования, то протокол (Р, V) также остается идеальным. В разделе 18.3.2.3 будет показано, что этого можно добиться, ограничив размер оклика. Существует несколько способов ограничить поведение верификатора V.
• Вынудить участника V продемонстрировать свою честность при выборе случайного оклика. Идеальный протокол с нулевым разглашением, основанный на этой идее, будет описан в разделе 18.6.2.
• Заставить верификатора V сымитировать "доказательство". В этом случае нечестный верификатор разоблачит себя. В разделе 18.7.1 будет описан чрезвычайно эффективный протокол, использующий эту идею.
18.3.2.2 Эвристический метод Шамира-Фиата
Фиат и Шамир предложили общий метод преобразования протокола с нулевым разглашением при честной верификации в схему цифровой подписи [109]. Этот метод использует способ атаки, описанный в разделе 18.3.2.1. Пусть числа Cornmit, Challenge, Response образуют стенограмму в протоколе с нулевым разглашением при честной верификации. Для его преобразования в цифровую подпись сообщения М € {0,1}* используется функция хэширования Н:
Challenge <— Н(М || Commit).
Этот способ называется эвристическим методом Фиата-Шамира (Fiat-Shamir heuristic).
Легко проверить, что тройная схема цифровой подписи Эль-Гамаля (раздел 16.3.1) является частным случаем схем цифровой подписи, созданных с помощью эвристического метода Фиата-Шамира. Формальное доказательство стойкости тройной схемы цифровой подписи Эль-Гамаля (описанное в разделе 16.3.2) распространяется на любую схему цифровой подписи, которую можно получить из протокола с нулевым разглашением при честной верификации с помощью эвристического метода Фиата-Шамира.
Верификатор может проверить утверждение, скрытое с помощью однонаправленной функции (например, утверждение о принадлежности, или утверждение о секретном свидетельстве (witness hiding claim)), используя те же методы, что и при верификации цифровой подписи, поскольку эвристический метод Фиата-Шамира предусматривает открытое, а не секретное доказательство. Довольно часто такое утверждение называют доказательством знания (proof-of-knowledge). Благодаря стойкости к атаке на основе адаптивно подобранных сообщений (см. раздел 16.3.2), доказательство знания является эффективным способом демонстрации утверждений, скрытых с помощью однонаправленной функции.
