Пещера нулевого разглашения — наглядный пример, описывающий доказательство с нулевым разглашением, впервые опубликованный Жан-Жаком Кискатером и Луи Гиллу (англ. 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 — проверяющий). Пегги утверждает, что знает секретную фразу, позволяющую ей открыть потайную дверь в пещере, которая имеет форму кольца, с входом с одной стороны и дверью на противоположной стороне. Она хочет убедить Виктора, что это действительно так, но при этом не собирается никому сообщать саму секретную фразу. Для доказательства своей честности Пегги входит в пещеру и идёт к двери, при этом она случайным образом выбирает один из двух возможных путей, какой именно — Виктор не знает, он ждёт в это время у входа. Как только Пегги скрывается из виду, Виктор заходит в пещеру и на разветвлении кричит: «Пегги, выйди слева!» или же «Пегги, выйди справа!». Необходимость открыть дверь, чтобы выйти в нужном направлении, покажет знание ею секретного ключа, в противном случае Пегги выйдет с той стороны, откуда пришла. Так как Виктор случайно выбирает путь, существует вероятность , что Пегги не знает фразы. Если повторить эту процедуру много раз, например, 20, то её шансы скрыть незнание фразы уменьшаются до одного к миллиону, что крайне мало. Следовательно, Пегги сможет убедить Виктора в знании пароля, не раскрывая его.
Корректность
Данный пример удовлетворяет всем трём свойствам интерактивного криптографического протокола:
- Полнота: Пегги может убедить Виктора в своей честности с любой заданной точностью.
- Корректность: если Пегги не знает как открыть дверь, то она практически (вероятность пренебрежимо мала) не сможет убедить Виктора в обратном, так как с каждым разом её шансы угадать сторону, которую назовет Виктор, падают вдвое.
- Нулевое разглашение: Виктор не может узнать ничего кроме самого факта, что Пегги действительно знает секретную фразу.
Участие третьих лиц
- Если Виктор запишет всё происходящее на камеру, то всё, что будет заснято, это как Виктор кричит «Пегги, выйди слева/справа!», и Пегги выходит слева/справа, то есть третье лицо, посмотревшее видео, не поверит до конца происходящему, так как Виктор и Пегги могли заранее договориться когда и с какой стороны ей выходить.
- Если кто-то третий будет лично присутствовать при эксперименте, то его тоже не получится убедить, так как всё происходящее может быть результатом заведомого сговора Виктора и Пегги.
Примечания
Литература
- Quisquater J., Quisquater M., Quisquater M. et al. 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 — Springer New York, 1990. — P. 628–631. — (Lecture Notes in Computer Science; Vol. 435) — ISBN 978-0-387-97317-3 — ISSN 0302-9743 — doi:10.1007/0-387-34805-0_60
 | Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .