Протокол доказательства знания
Пусть $R$ — $\mathrm{NP}$-отношение, $L_R=\{x\in\{0,1\}^*\,|\,\exists\,y\in\{0,1\}^* (x,y)\in R\}$ — соответствующий ему язык из $\mathrm{NP}$, а $\varkappa$ — функция из $\{0,1\}^*$ в $\{r\in\mathbb R\,|\, 0\leqslant r\leqslant1\}$. Говоря неформально, протокол доказательства знания для отношения $R$ с ошибкой $\varkappa$ — это протокол с двумя участниками, называемыми доказывающим и проверяющим, в котором целью доказывающего является доказать проверяющему, что он знает некоторое $\mathrm{NP}$-доказательство для общего входа $x\in L_R$ относительно $R$. При этом честный проверяющий может принимать доказательство нечестного доказывающего лишь с вероятностью не более $\varkappa(x)$.
Если $\mathfrak F$ — интерактивная вероятностная функция, а $\mathcal V$ — интерактивный алгоритм, то естественным образом определено совместное вычисление $\mathfrak F$ и $\mathcal V$ на произвольном общем входе $x\in\{0,1\}^*$; через $\pi_{\mathfrak F,\mathcal V}(x)$ будет обозначаться вероятность того, что алгоритм $\mathcal V$ возвратит $1$ в результате этого вычисления.
- для любой пары $(x,y)\in R$ всегда выполняется равенство $\langle{\mathcal P(y),\mathcal V}\rangle(x)=1$;
- существуют полином $q$ и вероятностный алгоритм $\mathcal K$ такие, что для любой интерактивной вероятностной функции $\mathfrak F=(\mathfrak F_x(y)\,|\, x,y\in\{0,1\}^*)$ и любого $x\in L_R$, удовлетворяющих неравенству $\pi_{\mathfrak F,\mathcal V}(x)>\varkappa(x)$, алгоритм $\mathcal K$ на входе $x$ с использованием оракула, возвращающего в ответ на запрос $y\in\{0,1\}^*$ случайный элемент относительно $\mathfrak F_x(y)$, находит (с вероятностью $1$) некоторое $\mathrm{NP}$-доказательство для $x$ относительно $R$ за среднее время, не превосходящее $q(\lvert{x}\rvert)/(\pi_{\mathfrak F,\mathcal V}(x)-\varkappa(x))$.
В этом определении алгоритм $\mathcal P$ является моделью честного доказывающего, алгоритм $\mathcal V$ — честного проверяющего, а интерактивная вероятностная функция $\mathfrak F$ — нечестного доказывающего. Алгоритм $\mathcal V$ возвращает на выходе $1$, если и только если доказательство принимается. Смысл условия 1 определения 1 очевиден: доказательство честного доказывающего, знающего догадку, всегда принимается честным проверяющим. Это условие аналогично условию абсолютной полноты для протокола интерактивного доказательства принадлежности языкам. Условие 2 определения 1 означает, что если доказательство нечестного доказывающего $\mathfrak F$ на общем входе $x\in L_R$ принимается честным проверяющим с вероятностью, большей $\varkappa(x)$, то этого нечестного доказывающего можно использовать для нахождения $\mathrm{NP}$-доказательства для $x$ относительно $R$. Алгоритм $\mathcal K$ из условия 2 определения 1 называется универсальным экстрактором.
Определения видов нулевого разглашения, описываемых в настоящем справочнике (а именно, вычислительно, статистически и абсолютно нулевого разглашения) непосредственно переносятся на протоколы доказательства знания. Очевидным образом определяется также протокол доказательства знания и вышеуказанные условия нулевого разглашения в модели с дополнительными входами (см. протокол интерактивного доказательства в модели с дополнительными входами, доказательство с нулевым разглашением в модели с дополнительными входами). Следует отметить, что многие описываемые в литературе протоколы интерактивного доказательства с нулевым разглашением для языков из $\mathrm{NP}$ по существу являются протоколами доказательства знания для естественных $\mathrm{NP}$-отношений, которым соответствуют эти языки.
Литература