36
правок
Изменения
Нет описания правки
* Виктор выбирает случайный бит <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>. Более того, Виктору сложно будет доказать кому-либо ещё изоморфизм этих графов.
