Квантовые вычисления со времен Демокрита - Скотт Ааронсон

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

Хорошо, имея зашифрованные цвета, что может сделать проверяющий? Очень просто: он может взять два соседних узла, попросить вас расшифровать цвета, а затем проверить, что (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).

Вероятностно проверяемое доказательство

Вероятностно проверяемое доказательство (PCP, Probabilistically checkable proof) — это еще одна невозможная на первый взгляд игра, в которую можно играть с концепцией «доказательства». Это доказательство, записанное таким способом, что вам, как ленивому проверяющему, достаточно вскрыть его в нескольких случайных местах, чтобы убедиться (в статистическом смысле) в его верности. Если вы хотите очень высокой уверенности в том, что это доказательство верно (скажем, с допустимой ошибкой в одну тысячную), вам никогда не придется проверять больше чем приблизительно тридцать битов. Разумеется, самое трудное здесь — закодировать доказательство так, чтобы это было возможно.

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

Во-первых, если задана произвольная пара графов G0 и G1 с n узлами каждый, то доказывающий направляет проверяющему особым образом зашифрованную строку, доказывающую, что G0 и G1 неизоморфны. Что это за строка? Ну, мы можем выбрать некоторый вариант упорядочения всех возможных графов с n узлами, поэтому назовем i-й граф Hi. Затем доказывающий записывает в i-й бит строки нуль, если Hi изоморфен G0, либо единицу, если Hi изоморфен G1; в противном случае (если Hi неизоморфен ни одному, ни другому) он произвольно ставит на это место 0 или 1. Как эта строка доказывает проверяющему, что G0 и G1 неизоморфны? Просто: проверяющий бросает монетку, чтобы получить G0 или G1, и преобразует его случайным образом, чтобы получить новый граф H. Затем он запрашивает бит доказательства, соответствующий графу H, и принимает его в том и только том случае, если запрошенный бит соответствует первоначальному графу. Если G0 и G1 в самом деле неизоморфны, то проверяющий будет принимать всегда, а если нет, то вероятность принятия составит не более 1/2.

Надо отметить, что в этом примере доказательство получается экспоненциально длинным и работает только для неизоморфности графов. Какой же результат мы получаем в общем случае? Знаменитая теорема о вероятностно проверяемом доказательстве[101] гласит, что любая задача из NP принимает вероятностно проверяемые доказательства, более того, доказательства полиномиальной длины! Это означает, что всякое математическое доказательство может быть закодировано таком образом, чтобы любая ошибка в оригинальном доказательстве транслировалась в ошибки почти повсюду в новом доказательстве.

Понять это можно, например, через 3-SAT. Теорема о вероятностно проверяемом доказательстве эквивалентна NP-полноте задачи решения 3-SAT с априорной информацией о том, что либо формула удовлетворима, либо не существует набора входных переменных, который удовлетворял бы более чем (скажем) 90 % условий формулы. Почему? Потому что можно зашифровать вопрос о том, имеет ли некоторое математическое утверждение доказательство из не более чем n символов, в виде 3-SAT-реализации таким образом, что если существует валидное доказательство, то формула удовлетворима, а если нет, то никакое присваивание не удовлетворит