Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
18.3.4 Статистические ZK-протоколы
Голдвассер, Микали и Ракофф [126] ввели понятие статистического протокола с нулевым разглашением (statistical zero-knowledge protocol). IP-протокол называется статистическим протоколом с нулевым разглашением, если существует эффективный имитатор, позволяющий подделать стенограмму доказательства с точностью, которая не поддается статистическому распознаванию. Статистический алгоритм распознавания аналогичен полиномиальному алгоритму распознавания, введенному в определении 4.14, за исключением того, что время его работы не обязательно полиномиально ограничено. Отсюда следует, что статистический ZK-протокол подчиняется более строгим ограничениям, чем вычислительный.
По существу, вычислительный протокол (Алиса, Боб) в примере 18.3.3.1 является статистическим, поскольку выражение (18.3.4) означает, что событие "число Response в поддельной стенограмме меньше числа z" возникает с вероятностью, которая меньше пренебрежимо малой величины 1/N.
Итак, с вероятностью больше (А'" — 1)/N число Response в обеих стенограммах превышает число z и является равномерно распределенным. Эти значения невозможно различить, даже если алгоритм будет работать бесконечно долго!
В принципе, статистические и вычислительные протоколы с нулевым разглашением несущественно отличаются друг от друга. Несмотря на это, поскольку понятие статистического протокола носит более строгий характер, в реальных приложениях оно более предпочтительно.
Глава 18. Протоколы с нулевым разглашением
697
18.4 Доказательство или аргументация?
Ранее было явно указано, что для того, чтобы IP-протокол (Р, V) обладал свойством нулевого разглашения (в любом из четырех'указанных смыслов) вычислительная мощность верификатора V и V должна быть ограничена полиномом, зависящим от размера общих входных данных. Однако до сих пор мы не делали никаких предположений о вычислительной мощи доказывающей стороны Р или Р.
18.4.1 Аргументация с нулевым разглашением
Внимательный читатель мог заметить, что, описывая все протоколы с нулевым разглашением, рассмотренные выше, мы считали, что участник Р (или Р) имеет полиномиально ограниченную вычислительную мощь. Однако доказательство непротиворечивости этих протоколов мы всегда начинали словами "если пользователь Р (или Р) не знает прообраз числа X
Для языков из класса TV = W из этого утверждения следует, что пользователь Р (или Р) применяет полиномиально ограниченный алгоритм. Если предположить, что пользователь, применяющий неограниченный алгоритм, может вычислить прообраз однонаправленной функции /, то все предыдущие рассуждения о непротиворечивости протоколов становятся некорректными. Совершенно ясно, что, используя неограниченный алгоритм, пользователь Р (или Р) может по числу Challenge определить величину Response.
Response <- прообраз ^Commit ¦ xChallen9e) .
В этом случае невозможно получить оценку вероятности противоречивости 6 в выражении (18.2.3). При доказательстве непротиворечивости всех протоколов, рассмотренных ранее, величина 6 была получена при неявном предположении, что пользователь Р (или Р) имеет ограниченные вычислительные ресурсы.
ZK-протокол (P,V) для языка L, в котором требуется, чтобы участник Р (или Р) имел полиномиально ограниченную вычислительную мощь, называется протоколом аргументации с нулевым разглашением (zero-knowledge argument protocol). Как правило, это требование необходимо для обоснования непротиворечивости протокола. Аргументация — это не строгое доказательство. В частности, она становится неубедительной, если пользователь Р (или Р) обладает неограниченными вычислительными ресурсами.
Итак, все протоколы, рассмотренные ранее, — идеальный, с честной верификацией, вычислительный и статистический — являются протоколами аргументации с нулевым разглашением. Протокол идентификации Шнорра также относится к этой категории. По существу, мы до сих пор не рассматривали ни одного протокола доказательства с нулевым разглашением (zero-knowledge proof protocol).
698
Часть VI. Криптографические протоколы
Перед тем как перейти к описанию протоколов доказательства с нулевым разглашением, необходимо четко разъяснить один вопрос. В большинстве реальных приложений, основанных на современных криптографических методах, пользователи секретной системы (включая доказывающую сторону в протоколе с нулевым разглашением), как правило, используют полиномиально ограниченные алгоритмы, а значит, не могут быстро решать NP-сложные задачи. Следовательно, протоколы аргументации с нулевым разглашением остаются весьма полезным понятием.
18.4.2 Доказательство с нулевым разглашением
В протоколе доказательства с нулевым разглашением непротиворечивость устанавливается без требования полиномиальной ограниченности пользователя Р (или Р).
Рассмотрим конкретный пример, в котором осуществляется доказательство того, что некое число является квадратичным вычетом. Этот протокол снова сводится к решению задачи о принадлежности: хЕ QRjv,гле N — нечетное составное целое число.
18.4.2.1 Доказательство принадлежности числа множеству квадратичных вычетов
