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

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

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

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

Мы предполагаем бесконечность языка $L$ в определении 1, чтобы избежать проблем с определением вычислительной неотличимости семейств случайных величин, индексированных элементами $L$. Кроме того, конечные языки для рассматриваемой теории не представляют интереса.

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

Теорема 2 см. также [1], [2], [3]
Предположим, что существуют односторонние функции. Пусть $L\in\mathrm{IP}$, а $q$ — произвольный полином. Тогда существует абсолютно полный протокол интерактивного доказательства с вычислительно нулевым разглашением для языка $L$, имеющий границу корректности $2^{-q}$. В частности, $\mathrm{CZK}=\mathrm{IP}$.

В связи с этой теоремой отметим, что $\mathrm{IP}=\mathrm{PSPACE}$ (см. теорему 3 из статьи Протокол интерактивного доказательства).

Теорема 3 см. также  [4], [1], [2]
Предположим, что существуют односторонние функции. Пусть $R$ — $\mathrm{NP}$-отношение, $L_R=\{x\,|\,\exists\,y (x,y)\in R\}$ — соответствующий ему язык, а $q$ — произвольный полином. Тогда существует абсолютно полный протокол интерактивного доказательства $(\mathcal P,\mathcal V)$ с вычислительно нулевым разглашением для языка $L_R$, имеющий границу корректности $2^{-q}$, в котором $\mathcal P$ выполняется за полиномиальное время, если ему на дополнительный вход подается некоторое $\mathrm{NP}$-доказательство для общего входа из $L_R$ относительно $R$.

Литература

  • [1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)
  • [2] Goldreich, O. «Computational complexity: A conceptual perspective» 2008
  • [3] Ben-Or, M. and Goldreich, O. and Goldwasser, S. and H\aastad, J. and Kilian, J. and Micali, S. and Rogaway, P. «Everything provable is provable in zero-knowledge» 1990
  • [4] Luby, M. «Pseudorandomness and cryptographic applications» 1996

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