МЕНЮ

Каталог

ЗАДАЧА О ПЕЩЕРЕ АЛИ-БАБЫ Протокол AB
Протокол интерактивного доказательства Протокол доказательства с нулевым разглашением

 

Постановка задачи

У пещеры, изображенной на рисунке, есть секрет. Этот секрет заключается в том, что тот кто знает волшебные слова может открыть потайную дверь между точками C и D. Для всех остальных оба хода пещеры ведут в тупик. Пусть Р знает волшебные слова, открывающие потайную дверь. Р хочет доказать V свое знание, не раскрывая волшебных слов.

схема пещеры Али-Бабы
Описание протокола

1) V находится в точке А.
2) P входит в пещеру и добирается либо до точки C, либо до точки D.
3) После того, как P исчезнет в пещере, V переходит в точку B, при этом не зная в какую сторону пошел P.
4) V зовет P и просит его выйти либо из правого прохода пещеры, либо из левого прохода, согласно желанию V.
5) P выполняет просьбу, используя при необходимости волшебные слова, чтобы отпереть потайную дверь.
6) P и V повторяют шаги 1) - 5) раз.

 

Основные сведения
Авторы

Jean-Jacques QuisquaterLouis GuillouЖан-Жак Кискатер (Jean-Jacques Quisquater) и Луи Гилу (Louis Guillou) изложили историю о пещере Али-Бабы в статье "How to Explain Zero-Knowledge Protocols to Your Children", Advances in Gryptology CRYPTO'89 Proceedings, Springer-Verlag, 1990, pp.628-631

 
Ссылки
  1. Jean-Jacques, Myriam, Muriel and Michael Quisquater; Louis, Marie Annick, Gaid, Anna, Gwenole and Soazing Gillou in collaboration with Tom Berson for the English version, "How to Explain Zero-Knowledge Protocols to Your Children", Advances in Gryptology CRYPTO'89 Proceedings, Springer-Verlag, 1990, pp.628-631
  2. Bruse Schneier, Applied Cryptography, Second edition: Protocols, Algorthms and Source Code in C, Wiley Computer Publishing, John Wiley & Sons, Inc.,1996,666p., - P.95-96
  3. Запечников С.В. Криптографические протоколы и их применение в финансовой и коммерческой деятельности: Учебное пособие для вузов. - М.: Горячая линия - Телеком, 2007. - 320с. - С.28-29