Пещера нулевого разглашения (Hypyjg urlyfkik jg[ilgoyunx)

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

↑ Quisquater et al, 1990.

Литература

Quisquater J., Quisquater M., Quisquater M., Quisquater M., Guillou L. C., Guillou M. A., Guillou G., Guillou A., Guillou G., Guillou S. How to Explain Zero-Knowledge Protocols to Your Children (англ.) // Advances in Cryptology — CRYPTO ’89: 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings / G. Brassard — Berlin, Heidelberg, New York City, London: Springer New York, 1990. — P. 628—631. — (Lecture Notes in Computer Science; Vol. 435) — ISBN 978-0-387-97317-3 — ISSN 0302-9743; 1611-3349 — doi:10.1007/0-387-34805-0_60

[_06e22e6bbee44054-1] Quisquater et al, 1990.

[1]