Доказательство со статистически нулевым разглашением
См. также доказательство с нулевым разглашением в модели с дополнительными входами.
Мы предполагаем бесконечность языка $L$ в этом определении, чтобы избежать проблем с определением вычислительной неотличимости семейств случайных величин, индексированных элементами $L$. Кроме того, конечные языки для рассматриваемой теории не представляют интереса.
Через $\mathrm{SZK}$ обозначается класс всех языков, для которых существует протокол интерактивного доказательства со статистически нулевым разглашением, имеющий границу полноты $2/3$ и границу корректности $1/3$. Иногда этот класс обозначается через $\mathrm{APZK}$ (см., например, [2]).
Из этой теоремы ввиду следствия 3 из статьи Игра Артура и Мерлина и теоремы 5 из статьи Протокол интерактивного доказательства вытекает, что если $\mathrm{PH}\ne\Sigma_2^{\mathrm P}\cap\Pi_2^{\mathrm P}$, то уже в $\mathrm{NP}$ есть языки, не принадлежащие $\mathrm{SZK}$.
Хороший обзор по доказательствам со статистически нулевым разглашением можно найти в [5], [6].Литература
- [1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)
- [2] Fortnow, L. «The complexity of perfect zero-knowledge» 1987
- [3] Aiello, W. and H\aastad, J. «Perfect zero-knowledge languages can be recognized in two rounds» 1987
- [4] Fortnow, L. «The complexity of perfect zero-knowledge» 1989
- [5] Vadhan, S. P. «A study of statistical zero-knowledge proofs» 1999
- [6] Vadhan, S. P. «A study of statistical zero-knowledge proofs» 2011