Протоколы неинтерактивных доказательств

Вопрос. Существует ли протокол неинтерактивного доказательства?

Ответ. Видимо, речь идет о протоколах интерактивного доказательства.

Заметим, что здесь присутствует некая терминологическая несуразность: неинтерактивный протокол — частный случай интерактивного, выполняемый за один раунд (посылка одного сообщения от доказывающего проверяющему).

Неинтерактивные протоколы доказательства, очевидно, существуют. Просто из определений следует, что такие доказательства существуют для всех языков из классов NP и BPP.

Более интересен вопрос о неинтерактивных доказательствах с нулевым разглашением. Здесь имеется весьма сильный отрицательный результат. Орен [1] доказал, что если для данного языка существует двухраундовый протокол доказательства с нулевым разглашением, то этот язык принадлежит классу BPP.

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

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

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

В модели с предобработкой (preprocessing), предложенной де Сантисом и др. [3], взаимодействие доказывающего и проверяющего делится на два этапа. На первом этапе (предобработка) участники выполняют специальный интерактивный протокол, результаты которого используются на втором этапе, который и представляет собой собственно неинтерактивное доказательство. Этот вариант доказательства становится нетривиальным, если, например, потребовать независимость этапа предобработки от доказываемого утверждения. Более того, установлено, что при некоторых предположениях существуют протоколы, позволяющие после однократного выполнения этапа предобработки выполнять полиномиальное (от параметра стойкости) количество неинтерактивных доказательств.

Исследование неинтерактивных доказательств во многом повторяло изучение общего случая: были определены понятия вычислительно, статистически и абсолютно нулевого разглашения, понятия доказательства знания и т.д. Cуществование неинтерактивных доказательств с нулевым разглашением для всего класса NP было изначально установлено в обеих моделях исходя из теоретико-числовых предположений. В дальнейшем эти результаты были усилены: оказалось, что достаточно общих криптографических предположений (о существовании односторонних перестановок).

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

Литература

  • [1] Yair Oren «On the cunning power of cheating verifiers: Some observations about zero knowledge proofs», FOCS 1987
  • [2] Manuel Blum, Paul Feldman, Silvio Micali «Non-interactive zero-knowledge and its applications», STOC 1988
  • [3] Alfredo De Santis, Silvio Micali, Giuseppe Persiano «Non-Interactive Zero-Knowledge Proof Systems», CRYPTO 1987

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна