Список обозначений

Доказательство с абсолютно нулевым разглашением

perfect zero-knowledge proof
Определение 1 протокол доказательства с абсолютно нулевым разглашением; см. также [1], [2]
Протокол интерактивного доказательства $(\mathcal P,\mathcal V)$ для языка $L\subseteq\{0,1\}^*$ называется протоколом доказательства с абсолютно нулевым разглашением, если для любого интерактивного полиномиального вероятностного алгоритма $\mathcal V’$ существует полиномиальный в среднем вероятностный алгоритм $\mathcal S$ (называемый симулятором для взаимодействия $\mathcal V’$ с $\mathcal P$) такой, что при каждом $x\in L$ случайные величины $\operatorname{view}^{\mathcal P}_{\mathcal V’}(x)$ и $\mathcal S(x)$ распределены одинаково.

См. также доказательство с нулевым разглашением в модели с дополнительными входами.

Через $\mathrm{PZK}$ обозначается класс всех языков, для которых существует протокол интерактивного доказательства с абсолютно нулевым разглашением, имеющий границу полноты $2/3$ и границу корректности $1/3$.

Иногда доказательство с абсолютно нулевым разглашением определяется несколько иначе. А именно, симулятор $\mathcal S$ предполагается полиномиальным вероятностным алгоритмом, который может выдавать специальный символ (обозначаемый через $\bot$), означающий, что вычисление закончилось неудачей.

Определение 2 протокол доказательства с абсолютно нулевым разглашением (альтернативный вариант); см. также [1]
Протокол интерактивного доказательства $(\mathcal P,\mathcal V)$ для языка $L\subseteq\{0,1\}^*$ называется протоколом доказательства с абсолютно нулевым разглашением, если для любого интерактивного полиномиального вероятностного алгоритма $\mathcal V’$ существуют полиномиальный вероятностный алгоритм $\mathcal S$ (называемый симулятором для взаимодействия $\mathcal V’$ с $\mathcal P$) и полином $p$ такие, что при каждом $x\in L$ выполняются следующие условия:
  1. $\Pr(\mathcal S(x)\ne\bot)\geqslant1/p(\lvert{x}\rvert)$;
  2. случайная величина $\mathcal S(x)$ при условии, что $\mathcal S(x)\ne\bot$, распределена так же, как и $\operatorname{view}^{\mathcal P}_{\mathcal V’}(x)$.

Разумеется, если в определениях 1 и 2 заменить $\operatorname{view}^{\mathcal P}_{\mathcal V’}(x)$ на $\langle{\mathcal P,\mathcal V’}\rangle(x)$, то получатся определения, эквивалентные исходным (см. также zkproof]{доказательство с нулевым разглашением}).

Легко видеть, что протокол интерактивного доказательства $(\mathcal P,\mathcal V)$ является протоколом доказательства с абсолютно нулевым разглашением в смысле определения 2 тогда и только тогда, когда для любого интерактивного полиномиального вероятностного алгоритма $\mathcal V’$ и любого полинома $q$ существует полиномиальный вероятностный алгоритм $\mathcal S$ такой, что $\Pr(\mathcal S(x)\ne\bot)\geqslant1-2^{-q(\lvert{x}\rvert)}$ и выполнено условие 2 этого определения при каждом $x\in L$ (см. [1]). Очевидно также, что если протокол интерактивного доказательства удовлетворяет определению 2, то он удовлетворяет и определению 1 (см. [1]). Верно ли обратное утверждение, неизвестно (см. [1]).

Следующий пример является классическим (см. [3], [4], [1], [5], [2], [6]).

Пример 3
Под словом «граф» в настоящем примере мы понимаем неориентированный граф без петель и кратных ребер. Пусть язык $\mathrm{GI}$ (GRAPH ISOMORPHISM) состоит из всех пар $(G_0,G_1)$, где $G_0$ и $G_1$ — изоморфные графы с множеством вершин $\{1,\dots,n\}$ при некотором $n\in\mathbb N$, зависящем от $(G_0,G_1)$. Через $S_n$ в этом примере будет обозначаться группа всех перестановок множества $\{1,\dots,n\}$ ($n\in\mathbb N$). Определим протокол доказательства следующим образом. Общий вход: $(G_0,G_1)$, где $G_0$ и $G_1$ — графы с множеством вершин $\{1,\dots,n\}$ ($n\in\mathbb N$). Если эти графы изоморфны, то через $\alpha$ обозначается произвольный изоморфизм $G_0$ на $G_1$.
  1. Доказывающий выбирает $\pi\in_{\mathfrak U} S_n$, вычисляет граф $H=\pi(G_1)$ и посылает $H$ проверяющему.
  2. Проверяющий выбирает $b\in_{\mathfrak U}\{0,1\}$ и посылает $b$ доказывающему (от которого требуется предъявить изоморфизм $G_b$ на $H$).
  3. Если $b=0$, то доказывающий посылает проверяющему композицию $\alpha$ и $\pi$, взятую в этом порядке. В противном случае доказывающий посылает проверяющему $\pi$.
  4. Проверяющий принимает доказательство, если и только если он получил от проверяющего перестановку из $S_n$, являющуюся изоморфизмом $G_b$ на $H$.

Абсолютная полнота протокола очевидна. Кроме того, если изоморфизм $\alpha$ подан доказывающему на дополнительный вход, то доказывающий может выполнить протокол за полиномиальное время.

Пусть $G_0$ и $G_1$ не изоморфны. Тогда какой бы граф $H$ ни послал нечестный доказывающий проверяющему в раунде 1, этот граф не может быть изоморфен обоим графам $G_0$ и $G_1$. Поэтому в данном случае проверяющий примет доказательство с вероятностью не более $1/2$. Таким образом, приведенный выше протокол является абсолютно полной игрой Артура и Мерлина для языка $\mathrm{GI}$ с границей корректности $1/2$.

Докажем теперь свойство абсолютно нулевого разглашения. Пусть $\mathcal V’$ — произвольный интерактивный полиномиальный вероятностный алгоритм. Определим вычисление алгоритма $\mathcal S$ на произвольном входе $(G_0,G_1)$, где $G_0$ и $G_1$ — изоморфные графы с множеством вершин $\{1,\dots,n\}$ ($n\in\mathbb N$), следующим образом.

  1. Выбрать $c\in_{\mathfrak U}\{0,1\}$, $\sigma\in_{\mathfrak U} S_n$ и вычислить граф $H=\sigma(G_c)$.
  2. Запустить алгоритм $\mathcal V’$ на входе $(G_0,G_1)$, используя $H$ в качестве первого сообщения, посланного этому алгоритму (см. раунд 1 протокола). Пусть $b$ — сообщение, посланное алгоритмом $\mathcal V’$ в ответ.
  3. Если $b\notin\{0,1\}$, то положить $b=1$.
  4. Если $b=c$, то продолжить выполнение алгоритма $\mathcal V’$, послав ему сообщение $\sigma$. После окончания работы этого алгоритма возвратить на выходе $(r,H,\sigma)$, где $r$ — строка случайных битов, использованная $\mathcal V’$ при вышеуказанном вычислении. Если же $b\ne c$, то возвратить на выходе $\bot$.
Легко видеть, что $\Pr(\mathcal S(G_0,G_1)\ne\bot)=1/2$, так как $H$ не содержит никакой информации о $c$ (напомним, что $G_0$ и $G_1$ изоморфны). Кроме того, для $\mathcal S$ выполнено условие 2 определения 2. Таким образом, построенный протокол является протоколом доказательства с абсолютно нулевым разглашением в смысле определения 2 (а, следовательно, и определения 1).

Литература

  • [1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)
  • [2] Arora, S. and Barak, B. «Computational complexity: A modern approach» 2007
  • [3] Goldreich, O. and Micali, S. and Wigderson, A. «Proofs that yield nothing but their validity and a methodology of cryptographic protocol design» 1986
  • [4] Goldreich, O. and Micali, S. and Wigderson, A. «Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems» 1991
  • [5] Goldreich, O. «Computational complexity: A conceptual perspective» 2008
  • [6] Luby, M. «Pseudorandomness and cryptographic applications» 1996

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна