Интерактивные системы доказательств

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

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

Пусть V — полиномиальная вероятностная машина Тьюринга, Р — вероятностная машина Тьюринга без ограничений на сложность^[1]. Машины V и Р имеют общую входную ленту, на которой записывается входное слово w и с которой они могут только считывать информацию. Кроме того, они имеют общую ленту для обмена сообщениями. Каждая из машин V и Р считывает предыдущую запись, сделанную другой из них, и делает собственную очередную запись (т.е. машины V и Р работают в режиме диалога — после отправки сообщения каждая из них переходит в состояние ожидания до получения ответа). Под очередным раундом понимается очередная передача сообщения машиной V машине Р, а затем и сообщения машины Р машине V (или наоборот, в зависимости от того, кто согласно протоколу инициирует диалог). Если в результате описанных обменов сообщениями машина V останавливается в принимающем состоянии (выдает положительный ответ), то мы говорим, что Р «убеждает» V.

Система (V, Р) является интерактивной системой доказательств для языка L (распознает язык L), если выполнены следующие условия.

• 1. Условие полноты. Если w е L, то Р убеждает V с вероятностью не менее 2/3.
• 2. Условие корректности. Если w , то какова бы ни была машина Р, она убеждает V с вероятностью не более чем 1/3.

Определение останется эквивалентным исходному, даже если потребуется ограничить вероятность ошибки экспоненциально малой величиной, скажем ½^N< для некоторой константы с. Это следует из возможности применения стандартного преобразования вероятностного алгоритма, когда по всякой полиномиальной вероятностной машине Тьюринга М можно построить полиномиальную вероятностную машину М распознающую тот же язык, по с вероятностью ошибки менее чем ½р (п) для заданного полинома р (п). Тогда на входе w работа машины М моделируется 2Ар (п) раз, каждый раз с независимым выбором случайного слова.

Дадим определения интерактивных систем доказательств с нулевым разглашением для языка L.

Система (V, Р) называется интерактивной системой доказательств с вычислительно нулевым разглашением для языка L> если она является интерактивной системой доказательств для L, т. е. выполнены условия 1 и 2 и, кроме этого, выполняется следующее условие (условие 3).

3. Условие нулевого разглашения. Для любой полиномиальной вероятностной машины Тьюринга V* существует вероятностная машина Тьюринга М_г*, работающая за полиномиальное в среднем время и такая, что семейства случайных величин, полученных во время взаимодействия машин V* и Р и полученных во время работы машины Му*, вычислительно неразличимы.

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

Для сведения С прикладной точки зрения интересны интерактивные системы доказательств с нулевым разглашением знания {zero-knowledge of knowledge), интерактивные системы доказательств с нулевым разглашением обладания информацией {zero-knowledge of possession of information) и схемы с сокрытием свидетельства {witness hiding schemes).

К другим классам систем вероятностных доказательств относятся:

• • интерактивные системы доказательств;
• • мультиинтерактивные системы доказательств;
• • интерактивные доказательства со многими доказывающими;
• • интерактивные системы доказательств со многими проверяющими;
• • интерактивные системы доказательств с распределенными доказывающими;
• • неинтерактивные системы доказательств;
• • неинтерактивные системы метадоказательств;
• • неинтерактивные системы доказательств с нулевым разглашением для многих языков;
• • интерактивные системы би-доказательств.

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

Краткое описание и определения указанных систем доказательств можно найти в монографии [7].

• [1] См. приложение Г.