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

#математика #криптография

Классическим примером протокола доказательства с нулевым разглашением является протокол
доказательства знания пароля к двери внутри круговой пещеры. Пусть Алиса (Alice) знает
этот пароль и хочет доказать его знание Бобу (Bob) без разглашения самого пароля. Используется
следующий протокол:
Алиса заходит в пещеру и подходит к двери с произвольной стороны так чтобы Боб не
знал с какой стороны находится Алиса.
Боб заходит в пещеру и просит выйти Алису с какой либо из сторон пещеры (слева или
справа).
Алиса зная пароль к двери всегда сможет выполнить пожелание Боба, появившись с любой
стороны.
После каждой итерации уверенность Боба в том что Алиса знает секрет увеличивается
вдвое. Таким образом после $k$ успешно выполненных операций вероятность того что Алиса
на самом деле обманывает Боба равна $1/2^k$.
Вопрос: почему важно, чтобы Боб не знал с какой стороны входит Алиса? Ведь это знание
не связано с секретом, а зная, например, что Алиса входит справа, Боб может попросить
ее выйти слева и точно убедиться в том, что у нее есть ключ.     

Ответы

Ответ 1

В оригинале немного не так. 

В начале квеста оба находятся в точке A. Далее Алиса проходит внутрь пещеры и поворачивает
либо налево, либо направо, так что Боб не знает куда она повернула (выступ между A
и B скрывает ее движение).
Далее Боб проходит к точке B и кричит Алисе выйди с левой или с правой стороны
Алиса по необходимости открывает дверь паролем и выходит либо слева либо справа.

Суть в том, что Боб не знает с какой стороны находится Алиса и наугад кричит выйди
слева или справа.
То есть вероятность того, что Алиса применила пароль для открытия двери составляет
как раз 50%. После N итераций уверенность Боба растет как (1 - 1/2^N)