Изменения

Назовем проверяющую сторону ПетейВиктор (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 \{0,1\}</tex>* Петя Виктор просит Диму Пегги доказать изоморфизм <tex>G_i</tex> и <tex>H</tex>, то есть предоставить соответствие вершин этих двух графов.* Если <tex>i = 0</tex>, то Дима Пегги отсылает Пете <tex>\phi</tex>, иначе <tex>\phi \cdot \pi</tex>

В каждом раунде Петя Виктор выбирает новый случайный бит, который неизвестен ДимеПегги. Поэтому чтобы ответить на оба вопроса, Диме Пегги нужно чтобы <tex>H</tex> был в самом деле изоморфен <tex>G_i</tex>. Это означает, что после достаточного числа раундов, Петя Виктор может быть уверен в том, что графы <tex>G_0</tex> и <tex>G_1</tex> изоморфны. С другой стороны, Дима Пегги не раскрывает никакой информации о перестановке <tex>\pi</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> для проверок изоморфизма. Таким образом без участия Димы Пегги доказать изоморфизм графов, можно лишь доказав, что во всех раундах протокола выбирались действительно случайные биты.