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

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

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

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

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

• 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

Эта страница в последний раз была отредактирована 24 мая 2021 в 23:41.