ИНФОРМАТИКА

Это означает, что Борис не в состоянии убедить Владимира, лично не присутствовавшего при проведении экспериментов в пещере, в том, что Антон действительно подтвердил свое знание секрета. А значит использованный Антоном протокол доказательства характеризуется именно нулевым разглашением конфиденциальной информации. Если Антон не знает волшебные слова, открывающие дверь в пещере, то, наблюдая за Антоном, не сможет ничего узнать и Борис. Если Антону известны волшебные слова, то Борису не поможет даже подробная видеозапись проведенных экспериментов. Во-первых, поскольку при ее просмотре Борис увидит только то, что уже видел живьем. А во-вторых, потому что практически невозможно отличить сфальсифицированную Борисом видеозапись от подлинной.
Протокол доказательства с нулевым разглашением срабатывает в силу того, что не зная волшебных слов, Антон может выходить только с той стороны, с которой зашел. Следовательно лишь в 50% всех случаев Антон сумеет обмануть Бориса, догадавшись, с какой именно стороны тот попросит его выйти. Если количество экспериментов равно n, то Антон успешно пройдет все испытания только в одном случае из 2n. На практике можно ограничиться n=16. Если Антон правильно исполнит приказ Бориса во всех 16-ти случаях, значит он и правда знает секрет волшебных слов.
Пример с пещерой является наглядным, но имеет существенный изъян. Борису значительно проще проследить, как в точке В Антон поворачивает в одну сторону, а потом появляется с противоположной стороны. Протокол доказательства с нулевым разглашением здесь попросту не нужен.
Поэтому предположим, что Антону известны не какие-то там волшебные слова, типа "Сезам, откройся". Нет, Антон владеет более интересной информацией — он первым сумел найти решение этой труднорешаемой задачи. Чтобы доказать данный факт Борису, Антону совсем не обязательно всем и каждому демонстрировать свое решение. Ему достаточно применить следующий протокол доказательства с нулевым разглашением конфиденциальной информации:
1. - Антон использует имеющуюся у него информацию и сгенерированное случайное число, чтобы свести труднорешаемую задачу к другой труднорешаемой задаче, изоморфной исходной задаче.