# '''Полнота''': если утверждение действительно верно, то доказывающий убедит в этом проверяющего.
# '''Корректность''': если утверждение неверно, то даже нечестный доказывающий не сможет убедить проверяющего за исключением пренебрежимо малой вероятности.
# '''Нулевое разглашение''': если утверждение верно, то любой даже нечестный проверяющий не узнает ничего кроме самого факта, что утверждение верно.
== Формальное определение ==
Пусть <tex>L</tex> ∈ '''[[NP]]''', и <tex>M</tex> — машина Тьюринга для проверки сертификата, то есть <tex>x \in L \Leftrightarrow \exists y \in \{0,1\}^{p(|x|)} : M(x, y) = 1</tex>. Пара <tex>\langle P, V \rangle</tex> интерактивных вероятностных алгоритмов называется доказательством с нулевым разглашением для <tex>L</tex>, если выполнены следующие три условия:
# '''Полнота''': Для любого <tex>x \in L</tex> и сертификата <tex>y</tex> выполнено <tex>P \left( \text{out}_V \left\langle P(x,y), V(x) \right\rangle = 1 \right) \ge 2/3</tex>
# '''Корректность''': Если <tex>x \not \in L</tex>, то для любых <tex>P^*, y</tex> выполнено <tex> P \left( \text{out}_V \left\langle P^*(x,y), V(x) \right\rangle = 1 \right) \le 1/3</tex>
# '''Нулевое разглашение''': Для любой вероятностной полиномиальной интерактивной стратегии <tex>V^*</tex> существует вероятностный полиномиальный алгоритм <tex>S^*</tex>, такой что для любого <tex>x \not \in L</tex> и соответствующего сертификата ''y'' выполнено <tex>\text{out}_{V^*} \left \langle P(x,y), V^*(x) \right \rangle\equiv S^*(x)</tex>. Такой алгоритм <tex>S^*</tex> называется симулятором для <tex>V^*</tex>, он симулирует результат взаимодействия <tex>V^*</tex> c proover'ом без доступа к последнему.
== Пример: изоморфизм графов ==
== Пример: изоморфизм Назовем проверяющую сторону Виктор (Victor), а доказывающую сторону Пегги (Peggy). Им обоим известна пара графов<tex>\langle G_0, G_1 \rangle</tex>. Допустим, эти графы изоморфны и Пегги известна биекция между вершинами этих графов, то есть некоторая перестановка <tex>\pi</tex>, такая что <tex>G_0 ==\pi G_1</tex>. Пегги хочет доказать Виктору, что графы изоморфны, не выдавая при этом ни самой перестановки, ни какой-либо информации о ней.
Назовем проверяющую сторону ПетейДля этого Виктор и Пегги совместно выполняют несколько раундов протокола:* Вначале Пегги создает случайную перестановку <tex>\phi</tex>. Применив ее к <tex>G_0</tex>, а доказывающую сторону Димойона получает некий граф <tex>H = \phi G_0</tex>. Им обоим известна пара графов * Пегги передает граф <tex>H</tex> Виктору.* Виктор выбирает случайный бит <tex>i \leftarrow \langle G_0{0, G_1 1\rangle}</tex>* Виктор просит Пегги доказать изоморфизм <tex>G_i</tex> и <tex>H</tex>. Допустим, Диме известена биекция между вершинами то есть предоставить соответствие вершин этих двух графов.* Если <tex>i = 0</tex>, то есть некоторая перестановка Пегги отсылает Виктору <tex>\piphi</tex>, такая что иначе <tex>G_0 = \phi \cdot \pi G_1</tex>. Дима хочет доказать Пете, что графы изоморфны, не выдавая при этом ни самой перестановки, ни какой-либо информации о ней.
Для этого Петя и Дима совместно выполняют несколько раундов протокола:* Вначале Дима создает случайную перестановку <tex>\phi</tex>В каждом раунде Виктор выбирает новый случайный бит, который неизвестен Пегги. Применив ее к <tex>G_0</tex>Поэтому чтобы ответить на оба вопроса, он получает некий граф Пегги нужно чтобы <tex>H = \phi G_0</tex>.* Дима передает граф был в самом деле изоморфен <tex>HG_i</tex> Пете.* Петя выбирает случайный бит <tex>i \leftarrow \{0Это означает, что после достаточного числа раундов, Виктор может быть уверен в том,1\}что графы </tex>* Петя просит Диму доказать изоморфизм <tex>G_iG_0</tex> и <tex>HG_1</tex>, то есть предоставить соответствие вершин этих двух графовизоморфны.* Если <tex>i = 0</tex>С другой стороны, то Дима отсылает Пете Пегги не раскрывает никакой информации о перестановке <tex>\phipi</tex>. Более того, иначе <tex>\phi \cdot \pi</tex>Виктору сложно будет доказать кому-либо ещё изоморфизм этих графов.
В каждом раунде Петя выбирает новый случайный битПредположим, который неизвестен Димечто у Пегги нет перестановки <tex>\pi</tex> и она хочет обмануть Виктора. Поэтому чтобы ответить на оба вопроса, Диме нужно чтобы Тогда граф <tex>H</tex> был в самом деле , который она отсылает Виктору, будет не изоморфен хотя бы одному из пары графов <tex>G_i\langle G_0, G_1 \rangle</tex>. Это означаетПоэтому вероятность того, что после достаточного числа раундов, Петя может быть уверен она сможет обмануть Виктора в том, что графы одном раунде не более <tex>G_0\frac{1}{2}</tex> и . Вероятность того, что Пегги сможет обманывать Виктора на протяжении <tex>G_1n</tex> изоморфны. С другой стороны, Дима раундов не раскрывает никакой информации о перестановке превосходит <tex>\pi2^{-n}</tex>. Более того, Пете сложно будет доказать кому-либо ещё изоморфизм этих графов.
Предположим, что у Димы нет перестановки <tex>\pi</tex> и он хочет обмануть Петю. Тогда граф <tex>H</tex>, который он отсылает Пете, будет не изоморфен хотя бы одному из пары графов <tex>\langle G_0, G_1 \rangle</tex>. Поэтому вероятность того, что он сможет обмануть Петю в одном раунде не более <tex>\frac{1}{2}</tex>. Вероятность того, что Дима сможет обманывать Петю на протяжении <tex>n</tex> раундов не превосходит <tex>2^{-n}</tex>. Предположим, что Петя Виктор не узнал перестановку <tex>\pi</tex>, но хочет доказать ВасеФренку, что Дима Пегги ее знает. Если ПетяВиктор, например, заснял на видео все раунды протокола, Вася Френк едва ли ему поверит. Вася Френк может предположить, что Петя Пегги и Дима Виктор в сговоре и в каждом раунде Петя Виктор заранее сообщал Диме Пегги свой выбор случайного бита, чтобы Дима мог Пегги могла передавать ему <tex>H</tex> для проверок изоморфизма. Таким образом без участия Димы Пегги доказать изоморфизм графов, можно лишь доказав, что во всех раундах протокола выбирались действительно случайные биты.
