ИНФОРМАТИКА

После примерно 10-ти вопросов Борис сможет твердо узнать, обманывает ли его Антон. При этом шансы Бориса извлечь для себя какую-либо полезную информацию о сути самого секрета практически равны нулю. - Протокол доказательства с нулевым разглашением конфиденциальной информации
Использование доказательства с нулевым разглашением конфиденциальной информации можно пояснить на конкретном примере. Предположим, что имеется пещера. Вход в пещеру находится в точке А, а в точке В пещера разветвляется на две половины — С и D. У пещеры есть секрет: только тот, кто знает волшебные слова, может открыть дверь, расположенную между С и D.
Антону волшебные слова известны, Борису — нет. Антон хочет доказать Борису, что знает волшебные слова, но так, чтобы Борис по-прежнему оставался в неведении относительно этих слов. Тогда Антон может воспользоваться следующим протоколом:
1. - Борис стоит в точке А.
2. - По своему выбору Антон подходит к двери либо со стороны точки С, либо со стороны точки D.
3. - Борис перемещается в точку В.
4. - Борис приказывает Антону появиться или через левый проход к двери, или через правый.
5. - Антон подчиняется приказу Бориса, в случае необходимости используя волшебные слова, чтобы пройти через дверь.
6. - Шаги 1—5 повторяются n раз, где n — параметр протокола.
Допустим, что у Бориса есть видеокамера, с помощью которой он фиксирует все исчезновения Антона в недрах пещеры и все его последующие появления. Если Борис покажет записи всех n экспериментов, произведенных им совместно с Антоном, могут ли эти записи послужить доказательством знания Антоном волшебных слов для другого человека (например, для Владимира)?
Вряд ли. Владимир никогда не сможет удостовериться в том, что Антон каждый раз предварительно не сообщал Борису о своих намерениях, чтобы потом Борис приказывал ему выходить именно с той стороны двери, с какой Антон зашел. Или что из сделанной видеозаписи не вырезаны все неудачные эксперименты, в ходе которых Антон не смог выполнить распоряжения Бориса.