Вариант этого примера был впервые представлен Мануэлем Блюмом (Manuel Blum) [196]. Пегги знает кружной, продолжительный путь вдоль линий графа, который проходит через каждую точку только один раз . Этот путь называется гамильтоновым циклом.Поиск гамильтонова цикла является другой тяжелой задачей . У Пегги есть эта информация - она, возможно, получила ее создав граф с конкретным гамильтоновым циклом -и она хочет доказать Виктору, что эта информация ей известна.
Пегги знает гамильтонов цикл графа, G. Виктору известен G, но не его гамильтонов цикл. Пегги хочет доказать Виктору, что она знает гамильтонов цикл, не раскрывая самого цикла . Вот как она должна действовать:
(1) Пегги случайным образом преобразовывает G. Она передвигает точки и изменяет их метки, создавая но-
вый граф, Я. Поскольку G и Я топологически изоморфны (т.е., это один и тот же граф), если ей известен гамильтонов цикл G, то она легко может найти гамильтонов цикл Я. Если она не сама создает Я, определение изоморфизма между двумя графами будет являться другой сложной проблемой, решение которой также потребует веков компьютерного времени. Затем она шифрует Я, получая Я'. (Должно использоваться вероятностное шифрование каждой строчки Я, то есть, шифрованный 0 или шифрованная 1 для каждой линии Я.)
(2) Пегги передает Виктору копию Я.
(3) Виктор просит Пегги либо:
(a) доказать ему, что Я - это зашифрованная изоморфная копия G, либо
(b) показать ему гамильтонов цикл для Я.
(4) Пегги исполняет его просьбу. Она либо:
(a) доказывает, что Я - это зашифрованная изоморфная копия G, раскрывая преобразования и расшифровывая все, не показывая гамильтонов цикл для G или Я, либо
(b) показывает гамильтонов цикл для Я, расшифровывая только те строки, которые образуют гамильтонов цикл, не доказывая, что Я и G топологически изоморфны.
(5) Пегги и Виктор повторяют этапы (1) - (4) п раз.
Если Пегги не обманывает, она сможет предъявить Виктору одно из доказательств на этапе (3) . Однако, если гамильтонов цикл для G ей неизвестен, она не сможет создать зашифрованный граф Я', который удовлетворяет обоим доказательствам. Лучшее, что она может сделать - это создать или граф, изоморфный G, или граф с таким же числом точек и линий и правильным гамильтоновым циклом . Хотя ее шансы угадать, какое доказательство потребует Виктор на этапе (3), составляют 50 процентов, Виктор может повторить протокол достаточное число раз, убеждаясь, что Пегги знает гамильтонов цикл для G.