Пещера нулевого разглашения

Пещера нулевого разглашения — наглядный пример, описывающий доказательство с нулевым разглашением, впервые опубликованный Жан-Жаком Кискатером и Луи Гиллу (англ. Louis Guillou) в статье Advances in Cryptology в 1990 году под названием «Как объяснить протокол доказательства с нулевым разглашением вашим детям» (англ. How to Explain Zero-Knowledge Protocols to Your Children).

Содержание оригинала

В своей работе Жан-Жак Кискатер проводит аналогию с восточной сказкой про Али-Бабу и сорок разбойников.

В городе Багдад живет старец по имени Али-Баба, которого многократно обкрадывают воры во время его походов по базару и всё время убегают в одну и ту же пещеру, которая разветвляется на два прохода, оканчивающихся тупиком. Али-Баба каждый раз преследует вора и идёт по одному из направлений, но вора обнаружить никак не получается. После сорокового случая Али-Баба приходит к выводу, что успешное бегство 40 разбойников подряд не может быть делом исключительно удачи. Он решает спрятаться в правом тупике и подождать одного из воров. Вскоре один из них появляется и подойдя к стене произносит волшебную фразу «Сим-сим, откройся» (от англ. «Open sesame»), после чего стены пещера разошлись в разные стороны, вор побежал дальше, а проход тут же закрылся. Али-Баба был очень рад открытию секрета пещеры, ведь теперь он понял, что этот тайный проход связывал левый и правый туннель. Он стал экспериментировать с магическими словами и сумел заменить кодовую фразу на другую. Буквально на следующий день вор был пойман. Али-Бабе записал эту историю в свою рукопись, но не записал саму секретную фразу, только оставил несколько подсказок.

Спустя много лет рукопись нашлась в США близ Бостона. Ученые смогли разгадать подсказки, оставленные Али-Бабой, и узнали кодовые слова. Археологические экспедиции в руинах старого Багдада обнаружили ту самую пещеру из рукописи, она не была мифом! Магические слова по-прежнему работали и позволяли пройти из одного туннеля в другой. Весть об этом быстро дошла до телевизионных компаний. Один из исследователей по имени Мик Али — возможный потомок Али-Бабы — решил продемонстрировать, что он знает секрет пещеры, не раскрывая самой секретной фразы. Для этого он пригласил съемочную группу, которая подробно изучила пещеру, а затем все вышли из пещеры. Мик Али зашел в пещеру и пошел по одному из туннелей, за ним пошел репортер. У развилки он подбросил монету, чтобы выбрать между левым и правым туннелем, откуда он хотел бы, чтобы вернулся Мик. Выбор пал на правый путь, он крикнул: «Мик, выходи справа!». Мик Али непременно вышел оттуда. Эксперимент повторили 40 раз, каждый раз Мик успешно справлялся с задачей. Таким образом он доказал репортеру, что действительно знает секрет пещеры, не раскрывая его. <…>

- перевод с англ. «How to Explain Zero-Knowledge Protocols to Your Children»

Криптографическая интерпретация

Действующими лицами являются Пегги (от англ. prover — доказывающий) и Виктор (от англ. verifier — проверяющий). Пегги утверждает, что знает секретную фразу, позволяющую ей открыть потайную дверь в пещере, которая имеет форму кольца, с входом с одной стороны и дверью на противоположной стороне. Она хочет убедить Виктора, что это действительно так, но при этом не собирается никому сообщать саму секретную фразу. Для доказательства своей честности Пегги входит в пещеру и идёт к двери, при этом она случайным образом выбирает один из двух возможных путей, какой именно — Виктор не знает, он ждёт в это время у входа. Как только Пегги скрывается из виду, Виктор заходит в пещеру и на разветвлении кричит: «Пегги, выйди слева!» или же «Пегги, выйди справа!». Необходимость открыть дверь, чтобы выйти в нужном направлении, покажет знание ею секретного ключа, в противном случае Пегги выйдет с той стороны, откуда пришла. Так как Виктор случайно выбирает путь, существует вероятность 50 % {displaystyle 50%} , что Пегги не знает фразы. Если повторить эту процедуру много раз, например, 20, то её шансы скрыть незнание фразы уменьшаются до одного к миллиону, что крайне мало. Следовательно, Пегги сможет убедить Виктора в знании пароля, не раскрывая его.

Корректность

Данный пример удовлетворяет всем трём свойствам интерактивного криптографического протокола:

Участие третьих лиц

• Если Виктор запишет всё происходящее на камеру, то всё, что будет заснято, это как Виктор кричит «Пегги, выйди слева/справа!», и Пегги выходит слева/справа, то есть третье лицо, посмотревшее видео, не поверит до конца происходящему, так как Виктор и Пегги могли заранее договориться когда и с какой стороны ей выходить.
• Если кто-то третий будет лично присутствовать при эксперименте, то его тоже не получится убедить, так как всё происходящее может быть результатом заведомого сговора Виктора и Пегги.