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

Интуитивно это представляется невозможным, но я проиллюстрирую на примере. Предположим, у нас имеется два графа. Если они изоморфны, то доказать это легко. Но предположим, они не изоморфны. Как доказать это кому-то, если представить, что вы — всемогущий маг?

Очень просто: предложите человеку, которого вы пытаетесь убедить, выбрать один из двух графов случайным образом, затем случайно его преобразовать и переслать вам то, что получилось. И пусть затем этот человек спросит: «С каким графом я работал?» Если два графа не были изоморфны, то вы должны быть в состоянии уверенно ответить на этот вопрос. В противном случае вы сможете ответить на него только с вероятностью 1/2. Таким образом, вы почти наверняка ошибетесь, если этот тест будет повторен некоторое небольшое число раз.

Это пример интерактивной доказательной системы. Делаем ли мы при этом какие-то допущения? Мы предполагаем, что вы не знаете, с какого именно графа начинал проверяющий, и не имеете прямого доступа к его мозгу, то есть не можете определить это непосредственно. Или, как сказали бы специалисты по теоретической информатике, мы предполагаем, что вы не имеете доступа к «частным случайным битам» проверяющего.

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

Такое доказательство, где проверяющий не узнает ничего, кроме истинности доказываемого утверждения, называется доказательством с нулевым разглашением. Ну да, хорошо, вам нужно еще немного поработать, чтобы определить, что, собственно, означает для проверяющего «ничего не узнать». По существу, это означает, что, если бы проверяющий с самого начала был убежден в истинности доказываемого утверждения, он мог бы просто самостоятельно имитировать весь протокол, без всякой помощи со стороны доказывающего.

При определенном вычислительном допущении, а именно что односторонние функции существуют, можно показать, что доказательства с нулевым разглашением существуют для любой NP-полной задачи. Именно такое замечательное открытие сделали Голдрейх, Микали и Вигдерсон в 1986 г.[100]

Поскольку все NP-полные задачи сводятся одна к другой (то есть представляют собой «одну и ту же задачу в разных обличьях»), достаточно привести протокол с нулевым разглашением для одной NP-полной задачи. И оказывается, что удобно выбрать для этой цели задачу раскраски графа в три цвета, в которой каждый узел графа окрашивается в красный, синий или зеленый цвет так, чтобы никакие два соседние узла не оказались одного цвета. У вас в руках черно-белая книга, но вы можете воспользоваться своим воображением и представить, что в изображенном на рисунке-графе имеется по два узла каждого цвета — красных, синих и зеленых.

Вопрос в том, как убедить кого-то, что любой граф можно раскрасить в три краски, не сообщая этому кому-то ничего о раскрашивании?

А вот как. Если наш граф раскрашен в три цвета, то сначала мы случайным образом переставим цвета: к примеру, заменим все синие области на зеленые, все зеленые на красные, а все красные на синие. (Существует 3! = 6 возможных перестановок.) Затем пошлем проверяющему зашифрованные сообщения, в которых будут закодированы все цвета — это, по существу, обеспечит «цифровую привязку» вас к этим цветам. Говоря более подробно, эти сообщения должны обладать следующими свойствами:

1. Проверяющий не может прочесть их (то есть взлом шифра вычислительно невозможен), но

2. Если вы позже расшифруете сообщения для проверяющего, он с легкостью сможет проверить для себя, что вы все сделали корректно, то есть что вы не обманули его, подставив не те цвета, к которым были ранее привязаны.

Есть один технический факт, который я просто приведу без всякого доказательства: при наличии односторонней функции можно добиться такого рода привязки (хотя, возможно, таким способом, который потребует множество циклов обмена сообщениями). Если вы не хотите принять это утверждение на веру, существует множество более простых способов получить цифровую привязку, но тогда вам придется использовать более сильные криптографические допущения. К примеру, если вы готовы считать разложение на простые множители трудной задачей, то зашифрованные сообщения могут представлять собой гигантские составные числа, а цвета могут быть зашифрованы различными свойствами факторизации этих чисел. Тогда вы получаете привязку к цветам, послав проверяющему эти составные числа, и можете затем «отвязаться» (то есть раскрыть цвета), выслав ему готовые разложения на простые множители, которые он сможет без труда самостоятельно проверить.

Хорошо, имея зашифрованные цвета, что может сделать проверяющий? Очень просто: он может взять два соседних узла, попросить вас расшифровать цвета, а затем проверить, что (1) расшифровки верны и (2) цвета действительно разные. Обратите внимание: если бы граф нельзя было корректно раскрасить в три цвета, то либо две соседние области получили бы один и тот же цвет, либо какая-то область оказалась бы окрашена не в красный, не в синий и не в зеленый цвет. В том и другом случае поверяющий поймает вас на вранье с вероятностью по крайней мере 1/m, где m — число ребер в графе.

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

Но почему считается, что это протокол «с нулевым разглашением»? Интуитивно сие «очевидно»: когда вы расшифровываете два цвета, проверяющий узнает только о том, что два соседних узла окрашены по-разному, но ведь они и должны быть окрашены по-разному, если речь идет о правильной раскраске в три цвета, разве не так? Ну хорошо, если подойти чуть более формально, вам нужно доказать, что проверяющий «ничего не узнает»; под этим подразумевается, что проверяющий сам по себе, за полиномиальное время, мог бы получить распределение вероятностей на последовательности сообщений, неотличимое при помощи какого бы то ни было алгоритма полиномиального времени от настоящей последовательности сообщений, которыми проверяющий обменялся с вами. Сами можете представить, что это довольно заумная штука.

Есть ли какая-то разница между двумя примерами с нулевым разглашением, которые я только что вам продемонстрировал? Конечно: доказательство с нулевым разглашением для раскраски карты в три цвета принципиально зависело от допущения о том, что проверяющий не может за полиномиальное время расшифровать карту самостоятельно. (Если бы мог, он смог бы узнать и вариант раскраски!) Это называется доказательством с вычислительно нулевым разглашением, а класс всех задач, принимающих такое доказательство, получил название CZK (computational zero knowledge). Напротив, в доказательстве неизоморфности графа проверяющий не мог бы смошенничать, даже если бы обладал неограниченными вычислительными возможностями. Это называется доказательством со статистически нулевым разглашением; в нем распределения, данные честным доказывающим и доказывающим-мошенником, должны быть близки друг другу в статистическом смысле. Класс всех задач, принимающих доказательство такого рода, называется SZK (statistical zero-knowledge).

Ясно, что SZK ⊆ CZK, но является ли принадлежность строгой? Интуитивно мы догадываемся, что класс CZK больше, поскольку наш протокол должен быть с нулевым разглашением только для проверяющих полиномиального времени, а не для проверяющих с неограниченными вычислительными возможностями. И в самом деле, установлено, что если односторонние функции существуют, то CZK = IP = PSPACE, иными словами, CZK «насколько велик, насколько это возможно». С другой стороны известно также, что SZK входит в полиномиальную иерархию. (Более того, при допущении дерандомизации SZK водит даже в NP ∩ co-NP).