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

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

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

1. Полнота : Пегги может убедить Виктора в своей честности с любой заданной точностью.
2. Корректность : если Пегги не знает как открыть дверь, то она практически ( вероятность пренебрежимо мала) не сможет убедить Виктора в обратном, так как с каждым разом её шансы угадать сторону, которую назовет Виктор, падают вдвое.
3. Нулевое разглашение : Виктор не может узнать ничего кроме самого факта, что Пегги действительно знает секретную фразу.

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

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

Примечания

Литература

• , , , , , , , , , (англ.) // : 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings / G. Brassard — Berlin, Heidelberg, New York City, London: , 1990. — P. 628—631. — ( ; Vol. 435) — ISBN 978-0-387-97317-3 — ISSN ; —