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

statistical 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$ в этом определении, чтобы избежать проблем с определением вычислительной неотличимости семейств случайных величин, индексированных элементами $L$. Кроме того, конечные языки для рассматриваемой теории не представляют интереса.

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

Теорема 2 см. [3], [2], [4], [1]

$\mathrm{SZK}\subseteq\mathrm{AM}\cap\mathrm{coAM}$.

Из этой теоремы ввиду следствия 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

Математическая криптография

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

Литература