Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Иначе говоря, аргументы функции / всегда принадлежат пространству ^Wjv(a)> размер которого меньше размера пространства Zjv-
Легко видеть, что функция f(x) является гомоморфной и однонаправленной. Ее гомоморфизм тривиально следует из равенства
f(x + у) = ах+у = ах ¦ ^(mod/V).
Однонаправленность этой функции основана на невозможности вычислить дискретный логарифм по модулю р (напомним, что большое простое число р | N нам неизвестно): найти число х из уравнения f(x) = f(l)x(modN) намного сложнее, чем определить число a;(modp — 1) из уравнения /(l)a;(modp), поскольку по предположению 8.2 функция /(l)a;(modp) является однонаправленной.
18.3.3.2 Вычислительный протокол с нулевым разглашением
Используя функцию f(x), построенную в разделе 18.3.3.1, можно сконструировать вычислительный протокол с нулевым разглашением.
Пример 18.3. Пусть (Алиса, Боб) — вариант протокола 18.1, в котором используется гомоморфная однонаправленная функция f(x), сконструированная в разделе 18.3.3.1, т.е. функция, определенная по формуле (18.3.3).
Теперь Алиса больше не знает число п = огДу(а) и не может извлекать случайные числа из пространства %OTdN(a)> имеющие равномерное распределение. Для того чтобы Алиса могла провести доказательство (т.е. чтобы сохранялось свойство полноты), инструкции протокола для Алисы необходимо немного исправить (будем считать, что z < N).
1. Алиса генерирует число к ? [/Zjv2_2, вычисляет значение Commit <— /(fc) и посылает его Бобу.
2. Боб ... (* Без изменений. *)
_ I к, если Challenge = О,
3. Алиса вычисляет значение Response «— <
I к + z, если Challenge = 1,
и посылает его Бобу.
4. Боб ... (* Без изменений. *)
В этой модификации инструкции Боба остались неизменными. Однако в инструкции Алисы внесены два изменения. На первом шаге случайное число к
Глава 18. Протоколы с нулевым разглашением
695
извлекается из группы "Epp-z- Выбор такого пространства будет обоснован позднее. На шаге 3 (если Challenge = 1) Алиса вычисляет значение Response <— к + z, используя сложение в целочисленном пространстве Ъ, т.е. без приведения по модулю. Алиса не может выполнить приведение по модулю, поскольку модуль п = ord/v(a) ей неизвестен.
Полнота и непротиворечивость этой модификации доказывается, как и прежде.
Однако теперь мы не можем больше утверждать, что этот вариант протокола является идеальным протоколом с нулевым разглашением, поскольку не можем сконструировать эффективный алгоритм создания уравнения, позволяющий создать стенограмму "доказательства", имеющую то же распределение, что и протокол (Алиса, Боб)(Х).
Действительно, обычные методы моделирования создают стенограмму с другим распределением. Как правило, алгоритм моделирования § сводится к следующим этапам.
1. Алгоритм моделирования S генерирует число Response € u%n2-
2. Алгоритм моделирования S генерирует число Challenge G гу{0,1}.
3. Алгоритм моделирования S вычисляет значение Commit <— /(Response)/
XChallenge(modAO.
Когда Challenge = 1, величина Response в стенограмме доказательства имеет равномерное распределение в интервале [z, N2), а в поддельной стенограмме величина Response равномерно распределена в интервале [О, N2). Это разные распределения. Если бы не число z, алгоритм S просто не смог бы моделировать поведение Алисы!
Несмотря на это, вариант (Алиса, Боб) является вычислительным протоколом с нулевым разглашением. Это объясняется тем, что распределения величин х € €u[z, N2) и у€[/[0, N2) при z < N неразличимы с вычислительной точки зрения. Из оценки
Prob[y < z < N | у е u[0,N2)] <^ = ^ (18.3.4)
следует, что
|Prob [Response G u[z, N2)] - Prob [Response € v[0, N2)] \ <
По определению 4.15 (из раздела 4.7) значения Response в истиной и поддельной стенограмме доказательства невозможно отличить. Таким образом, мы построили полиномиальный имитатор §, т.е. протокол (Алиса, Боб) является вычислительным протоколом с нулевым разглашением. о
Теперь мы в состоянии объяснить, почему Алиса извлекает числа к из необычного пространства ZN2_Z.
696
Часть VI. Криптографические протоколы
Во-первых, поскольку алгоритм не предусматривает операции приведения по модулю, из числа N2 необходимо вычесть z, чтобы число Response не стало больше N2. Если это случится, протокол потеряет смысл!
Во-вторых, само число N2 необходимо для того, чтобы оценка вероятности (18.3.4) и сам протокол гарантировали вычислительную эффективность. На самом деле число N2 не обязательно должно быть очень большим. Вычислительный протокол с нулевым разглашением можно сконструировать при Nl+Ct, где а > 0 — произвольная константа. Читатели могут сами доказать это утверждение (подсказка: в правой части выражения (18.3.4) число можно заменить на -j^r).
В реальных приложениях протоколов с нулевым разглашением (например, в протоколе идентификации Шнорра) большинство однонаправленных функций реализуются с помощью доступных криптографических средств (например, так, как показано в разделе 18.3.3.1). Следовательно, вычислительные протоколы с нулевым разглашением являются наиболее важным прикладным понятием в теории ZK-протоколов.
