Доказательство с нулевым разглашением
Говоря неформально, протокол интерактивного доказательства $(\mathcal P,\mathcal V)$ для языка $L$ называется протоколом доказательства с нулевым разглашением, если для любого интерактивного полиномиального вероятностного алгоритма $\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)$ в некотором смысле неотличимы. Смысл условия нулевого разглашения состоит в том, чтобы нечестный проверяющий (моделью которого является $\mathcal V’$), выполняя протокол с честным доказывающим, не мог получить никакой информации, кроме доступной ему и без взаимодействия с доказывающим.
Это неформальное определение может быть формализовано несколькими способами. Важнейшими видами нулевого разглашения являются вычислительно нулевое разглашение, статистически нулевое разглашение и абсолютно нулевое разглашение. Подробнее см. соответствующие статьи. Здесь мы приведем лишь общие свойства этих трех видов нулевого разглашения.
- Очевидно, что нулевое разглашение для протокола интерактивного доказательства по существу является лишь свойством честного доказывающего.
- Если в определении нулевого разглашения заменить $\operatorname{view}^{\mathcal P}_{\mathcal V’}(x)$ на $\langle{\mathcal P,\mathcal V’}\rangle(x)$, то получится эквивалентное определение (см. также [1]).
Литература
- [1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)