Доказательство с нулевым разглашением

Предположим, что Алиса знает доказательство некоторой теоремы и желает убедить Боба в том, что теорема верна. Конечно, Алиса может просто передать доказательство Бобу на проверку. Но тогда впоследствии Боб сможет сам, без помощи Алисы, доказывать третьим лицам эту теорему. А может ли Алиса убедить Боба так, чтобы он не получил при этом никакой информации, которая помогла бы ему восстановить доказательство теоремы? Этим двум, казалось бы взаимно исключающим требованиям, удовлетворяют протоколы доказательства с нулевым разглашением. Последнее понятие было введено Гольдвассер, Микали и Ракоффом в 1985 г.

Рассматривается следующая модель протокола. В распоряжении Алисы и Боба имеются вероятностные машины Тьюринга P и V соответственно. Вычислительные ресурсы, которые может использовать Алиса, неограничены, в то время как машина V работает за полиномиальное время. Машины P и V имеют общую коммуникационную ленту для обмена сообщениями. После записи сообщения на коммуникационную ленту машина переходит в состояние ожидания и выходит из него, как только на ленту будет записано ответное сообщение. Машины P и V имеют также общую входную ленту, на которую записано входное слово . Утверждение, которое доказывает Алиса, суть `` '', где - некоторый фиксированный (известный и Алисе, и Бобу) язык. Чтобы избежать тривиальности, язык должен быть трудным (например, NP-полным), иначе Боб сможет самостоятельно проверить, что . По существу, протокол доказательства состоит в том, что Боб, используя случайность, выбирает некоторые вопросы, задает их Алисе и проверяет правильность ответов. Выполнение протокола завершается, когда машина V останавливается, при этом она выдает 1, если доказательство принято, и 0 - в противном случае.

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

Определение 4. Интерактивным доказательством для языка называется пара интерактивных машин Тьюринга такая, что выполняются следующие два условия.

1. (Полнота). Для всех

2. (Корректность). Для любой машины Тьюринга , для любого полинома и для всех достаточно большой длины

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

Определение 5. Интерактивный протокол доказательства для языка называется доказательством с абсолютно нулевым разглашением, если, кроме условий 1 и 2, выполнено еще и следующее условие.

3. (Свойство нулевого разглашения). Для любой полиномиальной вероятностной машины Тьюринга существует вероятностная машина Тьюринга , работающая за полиномиальное в среднем время, и такая, что для всех

Машина называется моделирующей машиной для . Предполагается, что математическое ожидание времени ее работы ограничено полиномом от длины . Это означает, что в принципе может, в зависимости от того, какие значения примут используемые в ее работе случайные переменные, работать достаточно долго. Но вероятность того, что время ее работы превысит некоторую полиномиальную границу, мала. Для каждой машины строится своя моделирующая машина; последняя может использовать как подпрограмму. Через обозначается случайная величина - выходное слово машины , когда на входе она получает слово .

Свойство нулевого разглашения защищает Алису от нечестного Боба, который, произвольно отклоняясь от действий, предписанных протоколом (используя вместо V), пытается извлечь из его выполнения дополнительную информацию. Условие 3 означает, что Боб может при этом получить только такую информацию, которую он смог бы вычислить и самостоятельно (без выполнения протокола) за полиномиальное время.

Одним из примеров протокола доказательства с абсолютно нулевым разглашением является протокол для языка ИЗОМОРФИЗМ ГРАФОВ из работы Гольдрайха, Микали и Вигдерсон.