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

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

zero-knowledge proof

Говоря неформально, протокол интерактивного доказательства $(\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)

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