Объяснение этого понятия, пришедшего из теории графов [619, 622], может занять некоторое время. Граф представляет собой сеть линий соединяющих различные точки. Если два графа идентичны во всем, кроме имен точек, они называются изоморфными.Для очень больших графов доказательство их изоморфности может п о-требовать веков компьютерного времени, это одна из так называемых NP-полныхпроблем, рассматриваемых в разделе 11.1.
Предположим, что Пегги знает об изоморфности двух графов , G, и G2. Следующий протокол докажет Виктору знание Пегги:
(1) Пегги случайным образом тасует G,, получая другой граф, Я, который изоморфен G,. Так как Пегги знает об изоморфизме Я и G,, то ей также известен изоморфизм между Я и G2. Для любого другого поиск изоморфизма между Я и G, или Я и G2 является такой же трудной задачей, как и поиск изоморфизма между G, и G2.
(2) Пегги посылает Я Виктору.
(3) Виктор просит Пегги либо
(a) доказать, что Я и G, изоморфны, либо
(b) доказать, что Я и G2 изоморфны.
(4) Пегги исполняет его просьбу. Она либо:
(a) доказывает, что Я и G, изоморфны, не доказывая, что Я и G2 изоморфны, либо
(b) доказывает, что Я и G2 изоморфны, не доказывая, что Я и G, изоморфны.
(5) Пегги и Виктор повторяют этапы (1) - (4) п раз.
Если Пегги не знает об изоморфизме между G, и G2, она не сможет создать граф Я, изоморфный обоим графам. Она может создать либо граф, который изоморфен G,, либо граф, который изоморфен G2. Как и в предыдущем примере у нее только 50 шансов из 100 угадать, какое доказательство потребует от нее Виктор на этапе (3).
Этот протокол не дает Виктору никакой полезной информации, помогающей ему из ответов Пегги устан о-вить изоморфизм между G, и G2. Так как Пегги для каждого нового раунда протокола генерирует новый граф Я, Виктор не сможет получить информацию независимо от того, из скольких раундов будет состоять их протокол . Он не сможет из ответов Пегги установить изоморфизм между G, и G2.
В каждом раунде Виктор получает новое случайное преобразование Я, вместе с изоморфизмом между Я и G, или G2. Виктор может также создать что-то подобное самостоятельно. Так как Виктор может создать имитацию протокола, это действительно доказательство с нулевым знанием .