1. Борис стоит в точке A.

2. По своему выбору Антон подходит к двери либо со стороны точки C, либо со стороны точки D.

3. Борис перемещается в точку B.

4. Борис приказывает Антону появиться или (а) - через левый проход к двери, или (б) - через правый проход к двери.

5. Антон подчиняется приказу Бориса, в случае необходимости используя волшебные слова, чтобы пройти через дверь.

6. Шаги 1-5 повторяются n раз, где n - параметр протокола.

Допустим, что у Бориса есть видеокамера, с помощью которой он фиксирует все исчезновения Антона в недрах пещеры и все его последующие появления с той или иной стороны. Если Борис покажет записи всех n экспериментов, произведенных им совместно с Антоном, смогут ли эти записи послужить доказательством знания Антоном волшебных слов для другого человека (например, для Владимира)?

Вряд ли. Владимир никогда не сможет полностью удостовериться в том, что Антон каждый раз предварительно не сообщал Борису, с какой стороны он направится к двери, чтобы потом Борис приказывал ему выходить именно с той стороны, с какой Антон зашел. Или что из сделанной видеозаписи не вырезаны все неудачные эксперименты, в ходе которых Антон появлялся совсем не с той стороны, с какой ему приказывал Борис.

Это означает, что Борис не в состоянии убедить Владимира, лично не присутствовавшего при проведении экспериментов в пещере, в том, что Антон действительно подтвердил там свое знание секрета. А значит, использованный Антоном протокол доказательства характеризуется именно нулевым разглашением конфиденциальной информации. Если Антон не знает волшебные слова, открывающие дверь в пещере, то, наблюдая за Антоном, не сможет ничего узнать и Борис. Если Антону известны волшебные слова, то Борису не поможет даже подробная видеозапись проведенных экспериментов. Во-первых, поскольку при ее просмотре Борис увидит только то, что уже видел живьем. А во-вторых, потому что практически невозможно отличить сфальсифицированную Борисом видеозапись от подлинной.

Протокол доказательства с нулевым разглашением срабатывает в силу того, что, не зная волшебных слов, Антон может выходить только с той стороны, с которой зашел. Следовательно, только в 50 % всех случаев Антон сумеет обмануть Бориса, сумев выйти именно с той стороны, с которой тот попросит. Если количество экспериментов равно n, то Антон успешно пройдет все испытания только в одном случае из 2n. На практике можно ограничиться n=16. Если Антон правильно исполнит приказ Бориса во всех 16 случаях, значит, он и вправду знает волшебные слова.

Пример с пещерой является очень наглядным, но имеет существенный изъян. Борису будет значительно проще проследить, как в точке B Антон поворачивает в одну сторону, а потом появляется с противоположной стороны. Протокол доказательства с нулевым разглашением здесь попросту не нужен.

Поэтому предположим, что Антону известны не какие-то там волшебные слова типа "Сезам, откройся". Нет, Антон владеет более интересной информацией - он первым сумел справиться с труднорешаемой задачей. Чтобы доказать этот факт Борису, Антону совсем не обязательно публично демонстрировать свое решение. Ему достаточно применить следующий протокол доказательства с нулевым разглашением конфиденциальной информации:

1. Антон использует имеющуюся у него информацию и сгенерированное случайное число, чтобы свести труднорешаемую задачу к другой труднорешаемой задаче, изоморфной исходной задаче. Затем Антон решает эту новую задачу.

2. Антон задействует протокол предсказания бита для найденного на шаге 1 решения, чтобы впоследствии, если у Бориса возникнет необходимость ознакомиться с этим решением, Борис мог бы достоверно убедиться, что предъявленное Антоном решение действительно было получено им на шаге 1.

3. Антон показывает новую труднорешаемую задачу Борису.

4. Борис просит Антона

или (а) - доказать, что две труднорешаемые задачи (старая и новая) изоморфны,

или (б) - предоставить решение, которое Антон должен был найти на шаге 1, и доказать, что это действительно решение задачи, к которой Антон свел исходную задачу на том же шаге.

5. Антон выполняет просьбу Бориса.

6. Антон и Борис повторяют шаги 1-6 n раз, где n - параметр протокола.

Труднорешаемые задачи, способ сведения одной задачи к другой, а также случайные числа должны по возможности выбираться так, чтобы у Бориса не появилось никакой информации относительно решения исходной задачи даже после многократного выполнения шагов протокола.

Не все труднорешаемые задачи могут быть использованы при доказательстве с нулевым разглашением конфиденциальной информации, однако большинство из них вполне пригодны для таких целей. Примерами могут служить отыскание в связном графе цикла Гамильтона (замкнутого пути, проходящего через все вершины графа только один раз) и определение изоморфизма графов (два графа изоморфны, если они отличаются только названиями своих вершин).

Параллельные доказательства с нулевым разглашением конфиденциальной информации

Обычный протокол доказательства с нулевым разглашением конфиденциальной информации требует, чтобы Антон и Борис последовательно повторили его шаги n раз. Можно попробовать выполнять действия, предусмотренные этим протоколом, одновременно:

1. Антон использует имеющуюся у него информацию и n сгенерированных случайных чисел, чтобы свести труднорешаемую задачу к n другим труднорешаемым задачам, изоморфным исходной задаче. Затем Антон решает эти n новых задач.

2. Антон задействует протокол предсказания бита для найденных на шаге 1 n решений, чтобы впоследствии, если у Бориса возникнет необходимость ознакомиться с этими решениями, Борис мог бы достоверно убедиться, что предъявленные Антоном решения действительно были получены им на шаге 1.

3. Антон показывает n новых труднорешаемых задач Борису.

4. Для каждой из n новых труднорешаемых задач Борис просит Антона

или (а) - доказать, что она изоморфна исходной труднорешаемой задаче,

или (б) - предоставить решение этой задачи, которое Антон должен был найти на шаге 1, и доказать, что оно действительно является ее решением.

5. Антон выполняет все просьбы Бориса.

На первый взгляд параллельный протокол обладает тем же свойством нулевого разглашения конфиденциальной информации, что и обычный. Однако строгого доказательства этого факта еще не найдено. А пока с полной определенностью можно сказать лишь одно: некоторые интерактивные протоколы доказательства с нулевым разглашением в некоторых ситуациях можно выполнять параллельно, и от этого они не утрачивают свойство нулевого разглашения конфиденциальной информации.

Неинтерактивные протоколы доказательства с нулевым разглашением конфиденциальной информации

Постороннее лицо, не участвующее в выполнении шагов интерактивного протокола доказательства с нулевым разглашением конфиденциальной информации, невозможно убедить в том, в чем в ходе реализации протокола убеждается Борис, а именно - что Антон действительно владеет конфиденциальной информацией. Чтобы преодолеть этот недостаток, потребуется применить неинтерактивный протокол, в котором вместо Бориса используется однонаправленная функция: