Протокол интерактивного доказательства
Пусть $L\subseteq\{0,1\}^*$. Говоря неформально, протокол интерактивного доказательства для языка $L$ — это протокол с двумя участниками, называемыми доказывающим и проверяющим, в котором целью доказывающего является доказать проверяющему, что их общий вход $x\in\{0,1\}^*$ принадлежит $L$. При этом вычислительные возможности доказывающего не ограничиваются. Протокол должен удовлетворять следующим условиям.
- Условие полноты: если $x\in L$, то честный доказывающий успешно докажет это честному проверяющему.
- Условие корректности: если $x\notin L$, то нечестный доказывающий не может доказать честному проверяющему, что $x\in L$.
Мы дадим определение протокола интерактивного доказательства в несколько более общем виде, чем это принято. А именно, в следующем определении протокол интерактивного доказательства может иметь произвольные границы полноты и корректности (см. также [1]). Часто эти границы предполагаются равными $2/3$ и $1/3$ соответственно. См. также пионерские работы [2], [3].
- $\Pr(\langle{\mathcal P,\mathcal V}\rangle(x)=1)\geqslant\alpha(\lvert{x}\rvert)$ для любого $x\in L$ (условие полноты протокола);
- $\Pr(\langle{\mathcal P’,\mathcal V}\rangle(x)=1)\leqslant\beta(\lvert{x}\rvert)$ для любого $x\in \{0,1\}^*\setminus L$ и для любого интерактивного вероятностного алгоритма $\mathcal P’$ (условие корректности протокола).
См. также протокол интерактивного доказательства в модели с дополнительными входами.
В определении 1 алгоритм $\mathcal P$ является моделью честного доказывающего, алгоритм $\mathcal V$ — честного проверяющего, а алгоритм $\mathcal P’$ — нечестного доказывающего. Алгоритм $\mathcal V$ возвращает на выходе $1$, если и только если доказательство принимается.
Пусть $k$ — произвольная функция из $\mathbb N$ в $\{r\in\mathbb R\,|\, r\geqslant0\}$. Класс $\mathrm{IP}[k]$ определяется как класс всех языков, для которых существует протокол интерактивного доказательства с границей полноты $2/3$ и границей корректности $1/3$, выполняющийся не более $k$ раундов. Класс $\mathrm{IP}$ — это класс всех языков, для которых существует протокол интерактивного доказательства с границей полноты $2/3$ и границей корректности $1/3$ (без ограничения на число раундов). Другими словами, $\mathrm{IP}$ — это объединение классов $\mathrm{IP}[p]$ по всем полиномам $p$ (очевидно, что число раундов произвольного протокола интерактивного доказательства не превосходит значения некоторого полинома, зависящего от протокола, на длине общего входа).
Используя известную оценку Чернова и многократную параллельную композицию протокола с самим собой, нетрудно получить следующее
- $L\in\mathrm{IP}[k]$;
- существуют полином $p$ и функция $\gamma\colon\mathbb N\to\mathbb Q$, вычислимая детерминированным алгоритмом за полиномиальное от аргумента время, такие, что имеется протокол интерактивного доказательства для языка $L$ с границей полноты $\gamma+1/p$ и границей корректности $\gamma-1/p$, выполняющийся не более $k$ раундов;
- для любого полинома $q$ существует протокол интерактивного доказательства для языка $L$ с границей полноты $1-2^{-q}$ и границей корректности $2^{-q}$, выполняющийся не более $k$ раундов.
Убрав ограничения на число раундов в условиях 2 и 3 этого предложения, мы получим условия, эквивалентные принадлежности языка $L$ классу $\mathrm{IP}$.
Класс $\mathrm{IP}$ может быть охарактеризован следующим образом.
Рассмотрим теперь класс $\mathrm{IP}[O(1)]=\bigcup_{c=1}^\infty\mathrm{IP}[c]$ всех языков, для которых существует протокол интерактивного доказательства с границей полноты $2/3$ и границей корректности $1/3$, выполняющийся ограниченное число раундов.
Подробнее об этом см. игра Артура и Мерлина. Кроме того, имеет место
Литература
- [1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)
- [2] Goldwasser, S. and Micali, S. and Rackoff, C. «The knowledge complexity of interactive proof systems» 1985
- [3] Goldwasser, S. and Micali, S. and Rackoff, C. «The knowledge complexity of interactive proof systems» 1989
- [4] Arora, S. and Barak, B. «Computational complexity: A modern approach» 2007
- [5] Shamir, A. «IP=PSPACE» 1990
- [6] Shamir, A. «IP=PSPACE» 1992
- [7] Shen, A. «IP=PSPACE: Simplified proof» 1992
- [8] Goldreich, O. «Computational complexity: A conceptual perspective» 2008
- [9] Boppana, R. B. and H\aastad, J. and Zachos, S. «Does co-NP have short interactive proofs?» 1987