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

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

zero-knowledge proof with respect to auxiliary input
Определение 1 протокол доказательства с вычислительно нулевым разглашением в модели с дополнительными входами; см. также [1]
Пусть $(\mathcal P,\mathcal V)$ — протокол интерактивного доказательства для бесконечного языка $L$ с границей полноты $\alpha$ в модели с дополнительными входами. Для произвольного $x\in L$ обозначим через $C(x)$ множество всех $y\in\{0,1\}^*$, удовлетворяющих условию полноты протокола для $x$, т. е. \[ C(x)=\{y\in\{0,1\}^*\,|\,\forall\,z\in\{0,1\}^* \Pr(\langle{\mathcal P(y),\mathcal V(z)}\rangle(x)=1)\geqslant\alpha(\lvert{x}\rvert)\}. \] Протокол $(\mathcal P,\mathcal V)$ называется протоколом доказательства с вычислительно нулевым разглашением в модели с дополнительными входами, если для любого полиномиального параметра $l$ и любого интерактивного полиномиального вероятностного алгоритма $\mathcal V’$ существует полиномиальный вероятностный алгоритм $\mathcal S$ (называемый симулятором для взаимодействия $\mathcal V’$ с $\mathcal P$) такой, что для произвольной функции $x\mapsto f(x)\in C(x)$ ($x\in L$) семейства случайных величин \begin{equation}\label{e:view} \left(\left.\operatorname{view}^{\mathcal P(f(x))}_{\mathcal V’(z)}(x)\,\right|\, x\in L,\, z\in\{0,1\}^{l(\lvert{x}\rvert)}\right) \end{equation} и \begin{equation}\label{e:S} \left(\mathcal S(x,z)\,\left|\, x\in L,\, z\in\{0,1\}^{l(\lvert{x}\rvert)}\right.\right) \end{equation} вычислительно неотличимы.

Преимуществом модели с дополнительными входами по сравнению с обычной моделью интерактивного доказательства с нулевым разглашением является то, что класс протоколов доказательства с вычислительно нулевым разглашением в модели с дополнительными входами замкнут относительно последовательной композиции (см. [2], [3], [1]). В то же время первая из этих моделей, в отличие от второй, содержит неоднородность в определении условия вычислительно нулевого разглашения (см. [1]). В связи с этим естественные аналоги теорем 2 и 3 из статьи Доказательство с вычислительно нулевым разглашением в модели с дополнительными входами доказываются лишь в предположении существования односторонних функций в неоднородной модели вычислений (см. [1]).

Если в определении 1 заменить вычислительную неотличимость семейств случайных величин \eqref{e:view} и \eqref{e:S} на статистическую неотличимость, получится определение протокола доказательства со статистически (или почти абсолютно) нулевым разглашением в модели с дополнительными входами. Если же в определении 1 потребовать, чтобы симулятор $\mathcal S$ был полиномиален в среднем и чтобы семейства случайных величин \eqref{e:view} и \eqref{e:S} определяли одно и то же семейство распределений вероятностей, мы получим определение протокола доказательства с абсолютно нулевым разглашением в модели с дополнительными входами, являющееся аналогом определения 1 из статьи Доказательство с абсолютно нулевым разглашением. Определение 2 протокола доказательства с абсолютно нулевым разглашением переносится в модель с дополнительными входами аналогично.

Литература

  • [1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)
  • [2] Oren, Y. «On the cunning power of cheating verifiers: Some observations about zero-knowledge proofs» 1987
  • [3] Goldreich, O. and Oren, Y. «Definitions and properties of zero-knowledge proof systems» 1994

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