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

interactive proof protocol

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

Связанные статьи: интерактивная система доказательства (справочник), доказательство интерактивное (словарь)

Пусть $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].

Определение 1 протокол интерактивного доказательства

Пусть $\alpha$ и $\beta$ — функции из $\mathbb N$ в $\mathbb R$. Пара интерактивных вероятностных алгоритмов $(\mathcal P,\mathcal V)$, в которой $\mathcal V$ полиномиален, называется протоколом интерактивного доказательства для языка $L$ с границей полноты $\alpha$ и границей корректности $\beta$, если

$\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$ (очевидно, что число раундов произвольного протокола интерактивного доказательства не превосходит значения некоторого полинома, зависящего от протокола, на длине общего входа).

Используя известную оценку Чернова и многократную параллельную композицию протокола с самим собой, нетрудно получить следующее

Предложение 2 см. также [4], [1]

Для произвольного языка $L\subseteq\{0,1\}^*$ следующие условия эквивалентны:

$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}$ может быть охарактеризован следующим образом.

Теорема 3 см. [5], [6], [7], [8], [4], [1]

$\mathrm{IP}=\mathrm{PSPACE}$.

Рассмотрим теперь класс $\mathrm{IP}[O(1)]=\bigcup_{c=1}^\infty\mathrm{IP}[c]$ всех языков, для которых существует протокол интерактивного доказательства с границей полноты $2/3$ и границей корректности $1/3$, выполняющийся ограниченное число раундов.

Теорема 4

$\mathrm{IP}[O(1)]=\mathrm{IP}[d]\subseteq\Pi_2^{\mathrm P}$ для любой константы $d\in\mathbb N$ такой, что $d\geqslant2$.

Подробнее об этом см. игра Артура и Мерлина. Кроме того, имеет место

Теорема 5 см. [9]

Если $\mathrm{coNP}\subseteq\mathrm{IP}[O(1)]$, то $\mathrm{PH}=\Sigma_2^{\mathrm P}\cap\Pi_2^{\mathrm P}$.

Литература

[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

Математическая криптография

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

Литература