От: | Khimik | ||
Дата: | 11.11.23 10:14 | ||
Оценка: |
Впервые данный пример был написан в хорошо известной работе по доказательству с нулевым разглашением «Как объяснить протокол доказательства с нулевым разглашением вашим детям» Жан-Жаком Кискатером (англ.)рус.[30].
В данном случае Пегги выступает в качестве Доказывающего утверждение, и Виктор — в качестве Проверяющего (в англоязычной литературе обычно используются наименование сторон Пегги и Виктор (от «Prover» и «Verifier» соответственно). Пегги знает магическое слово («ключ»), ввод которого позволяет открыть ей дверь между C и D. Виктор хочет узнать, действительно ли Пегги знает пароль, при этом Пегги не хочет выдавать сам пароль. Пещера имеет круглую форму, как представлено на рисунке. Для того чтобы решить проблему, они поступают следующим способом. Пока Виктор находится в точке А, Пегги идёт к двери, и после того, как она исчезает из виду, Виктор идёт к разветвлению, то есть в точку B, и кричит оттуда: «Пегги нужно выйти справа» или «Пегги нужно выйти слева». Получаем каждый раз вероятность того, что Пегги не знает пароль, равна 50 %. Если же повторить процесс k раз, то вероятность будет
1
2
�
{\frac {1}{2^{k}}}. При 20 же повторениях эта вероятность будет порядка 10−6, что является достаточным для справедливости предположения о том, что Пегги знает ключ[30].
Если Виктор запишет все происходящее на камеру, то полученная видеозапись не будет являться доказательством для какой-либо другой стороны. Ведь они могли заранее сговориться, откуда будет выходить Пегги. Соответственно, она сможет найти выход, не зная при этом самого ключа. Существует ещё один способ: Виктор просто вырезает все неудачные попытки Пегги. Эти описанные выше действия доказывают, что пример с пещерой удовлетворяет свойствам: полноты, корректности и нулевому разглашению[31].