Изменения

Перейти к: навигация, поиск

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

2 байта убрано, 11:58, 22 июня 2010
Пример: изоморфизм графов.
== Пример: изоморфизм графов. ==
Назовем проверяющую сторону Виктор (Victor), а доказывающую сторону Пегги (Peggy). Им обоим известна пара графов <tex>\langle G_0, G_1 \rangle</tex>. Допустим, эти графы изоморфны и Пегги известена известна биекция между вершинами этих графов, то есть некоторая перестановка <tex>\pi</tex>, такая что <tex>G_0 = \pi G_1</tex>. Пегги хочет доказать Виктору, что графы изоморфны, не выдавая при этом ни самой перестановки, ни какой-либо информации о ней.
Для этого Виктор и Пегги совместно выполняют несколько раундов протокола:
Анонимный участник

Навигация