1.3. Вероятностные доказательства
1.3.1. Интерактивные системы доказательства
Интерактивная система доказательства (interactive proof system) - протокол, включающий двух участников: доказывающего (prover - Р) и проверяющего (verifier - V). Предварительно формули-руется некоторое утверждение S, например, утверждение о том, что некоторый объект w обладает свойством L: w є L. В ходе протокола Р и V обмениваются сообщениями. Каждый из них может генериро-вать случайные числа и использовать их в своих вычислениях. В конце протокола V должен вынести свое окончательное решение о том, является ли S истинным или ложным.
J. Базовые криптографические протоколы 23
Цель участника Р всегда заключается в том, чтобы убедить уча-стника V в том, что S истинно, независимо от того, истинно ли оно на самом деле или нет. Таким образом, Р может мошенничать в про-токоле, так как S может быть ложно, т. е. он может быть активным противником. V должен проверять аргументы участника Р. Цель участника У заключается в том, чтобы вынести решение, является ли S истинным или ложным. Как видим, интересы участников протоко-ла Р и V не совпадают.
Однако участник V имеет полиномиально ограниченные вычис-лительные возможности, а именно время его работы ограничено не-которым полиномом от длины доказываемого утверждения:
t < ?>(|w|). Это предположение является стандартным для моделирования вычислительных возможностей обычных средств вычисли-тельной техники.
В силу этого он самостоятельно, без помощи Р, не способен распознать истинность утверждения S.Вычислительные возможности Р никак не ограничиваются, что в действительности может соответствовать ситуации, когда Р владеет какой-то трудно получаемой информацией (хотя он может и обма-нывать, утверждая, что такая информация у него имеется).
Программа действий участника V должна быть устроена таким образом, чтобы:
если S истинно, Р смог бы убедить V признать это;
если S ложно, Р не смог бы убедить V в противном, какие бы аргументы он ни выдвигал, т. е. вне зависимости от получаемых от Р сообщений.
V может ошибаться, но ставится условие, чтобы вероятность принятия им неправильного решения была бы пренебрежимо мала.
Рассмотрим примеры интерактивных систем доказательства.
1. Пример из теории чисел. Зададимся натуральным числом п.
Рассмотрим мультипликативную группу Z* = [х < = l}. Обо-
значим QR = |(х, и)[* < п, (х, /і) = 1, Зу: у1 = Jtmod пJ - множество ква-дратичных вычетов числа п. Напомним, что если сравнение у1 = x(modw) имеет решение, то х называется квадратичным вычетом числа п. В противном случае х называется квадратичным невы- 24 Запечников С. В. Криптографические протоколы и их прішеиеиие
четом. Тогда L = QNR = {(.t^)|* Таблица L2. Пример интерактивной системы доказательства, основанной на задаче теории чисел
Р V
1 <г Для і — 1.,kjc = |;z| выбирает: bt є {0,1} - случайный бит, zt Є Z*, И вычисляет (Wp..., wt), где [ zf (mod л), если (bt- =l), \x¦ zf (modл),если(?f = 0)
2 Для i = l,k вычисляет (сь ск), где Ґ1 уесли(щ,/?)е QR Ci~\0,eaiu(wi,n)&QR
3 Принимает доказательство тогда и толь-ко тогда, когда для V (i = l,k) q = bj.
Во-первых, покажем, что для VxeQNR, если (*,л)є QNR, т.е. Когда bj = 1, по условию протокола 3z-: zf = w(. (modn). По оп-ределению вычета это означает, что (и>.,л)є QR, т.е. и>,- является квадратичным вычетом числа п. Когда Ък — 0, по условию протокола zf (modи). Из дока зываемого утверждения известно, что (х,п)є QNR. Может ли Wj быть квадратичным вычетом числа л? Для этого должно быть (Zj-x1'= wi (modn). Это может быть, только если х = 1. Но (1, п) = 1. Кроме того, Зу = 1: у = 1 (mod п). Следовательно, (і,л)є <2-^ - Мы пришли к противоречию с исходным утверждением. Следовательно, bt = 0 тогда и только тогда, когда (u>.,7*)6 QNR » т. е. мы установили однозначную связь: является квадратичным вычетом числа п только при = I. Распознавая QR на шаге (2) про-токола (эту задачу нельзя решить за полиномиальное время), дока-зывающий Р будет отвечать битом с, = 1 тогда и только тогда, когда Ъ\ = 1, т. е. на шаге (3) результат проверки всегда будет положительным и V всегда примет доказательство. Покажем теперь, что для Vx, если (х,п)& QNR, вероятность ошибки V составляет Р?ш =1/2*. Когда Ьі= 1, по условию протокола : zf = w. (modn). По опре-делению вычета это означает, что (w}tn)eQR, т.е. и>,- является квадратичным вычетом числа п. Когда Ь{ = 0, по условию протокола u>. = x-zf (modn). Если (х,п)ё QNR, т.е. (х,п)е QR, то (х,п) = 1,3^: у2 sx(modn). Тогда можно записать, что w{ = у2-г~(тойп), или, что то же самое, w, = (.у-^)2(пкх1п). Значит, 3v = y-zt: v2 = wf (modn) , т. e. (ил,п)є QR . Итак, Wj - случайный квадратичный вычет числа п. В любом случае: Ьх ~ 0 или b{ - 1 - участник Р на шаге (2) прото-кола всегда будет распознавать число и>,- как квадратичный вычет числа п. Следовательно, он может угадать, какой бит ?>. ={0,1} был выбран, только случайно, с вероятностью Р = 1/2. Следовательно, все k бит {b{,...,bk) он сможет угадать лишь с вероятностью 26 Запечников С. G\ (задача проверки изоморфности графов также нерешаема за по-линомиальное время). Не упрощая задачи, можно предполагать, что Go и Gx - графы на одном и том же множестве вершин N мощности т: |iV| = т. L- GNI = {(G0,G, )|VG0 ф - множество пар неизо-морфных графов. Р доказывает V утверждение S = (G0,G,)e GNI. Протокол, показанный в табл. 1.3, является интерактивной системой доказательства данного утверждения. Таблица 1.3. Пример интерактивной системы доказательства, основанной на задаче теории графов
Р V
1 Для і - 1, in берет a; Є {0,1} - слу-чайный бит, создает изоморфную / копию Ga ~ Ga путем случайной перестановки вершин:
2 Для і = 1, т вычисляет (3f Є {0,1} так, что р(=0 ,если(оа' =G0), Р,=1, если (G^ ==?,), ' -случ.,если (G0 ~ Gx), о Л К *Got\ p; = 0, если , V / отправляет p. проверяющему ->
3 Принимает доказательство тогда и только тогда, когда все биты совпали: для Va = 1, т J3,. = а;
Обобщим теперь рассмотренные примеры и сформулируем ряд определений. ]. Базовые криптографические протоколы 27 Пусть S - утверждение вида we L, где w - слово, L - язык в двоичном алфавите. Если существует интерактивная система дока-зательства для утверждений такого рода, то говорят, что язык L об-ладает интерактивной системой доказательства. Обозначается такая система Протокол между участниками Р и V называется интерактивным доказательством для языка L, если V полиномиально ограничен и выполнены следующие два условия: для \/xG L p{(p,l/)(v)=l}>l-l/2"r, где С = Const; п - число раундов протокола (т. е. вероятность принятия проверяющим доказательства истинного утверждения стремится к единице); для \/хе L и для VP' Ф Р (для любого другого участника, который действует не так, как честный участник) вероятность при-нятия проверяющим доказательства ложного утверждения исчезаю- ще мала, т. е. Р [( Р\ V )(х} = 1 j < 1 / 2"". Условие 1 называется полнотой (completeness), условие 2 - кор-ректностью (soundness) доказательства. Класс языков, обладающих интерактивными системами доказательства, обозначается IP. Теорема (A. Shamir, A. Shen, 1990). IP = PSPACE (т. е. класс за-дач, обладающих интерактивными системами доказательства, сов-падает с классом задач, решаемых с полиномиальным объемом па-мяти).