Список обозначений

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

protocol for proofs of knowledge
Синонимы: система доказательства знания

Пусть $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$ в результате этого вычисления.

Определение 1 протокол доказательства знания; см. также [1], [2]
Пара интерактивных полиномиальных вероятностных алгоритмов $(\mathcal P,\mathcal V)$, называется протоколом доказательства знания для отношения $R$ с ошибкой $\varkappa$, если выполнены следующие условия:
  1. для любой пары $(x,y)\in R$ всегда выполняется равенство $\langle{\mathcal P(y),\mathcal V}\rangle(x)=1$;
  2. существуют полином $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}$-отношений, которым соответствуют эти языки.

Теорема 2 см. также [2]
Предположим, что существуют односторонние функции. Пусть $R$ — $\mathrm{NP}$-отношение, $L_R=\{x\,|\,\exists\,y (x,y)\in R\}$ — соответствующий ему язык, а $q$ — произвольный полином. Тогда существует протокол доказательства знания для отношения $R$ с ошибкой $0$, удовлетворяющий условиям вычислительно нулевого разглашения и корректности с границей $2^{-q}$. Последнее условие означает, что если $\mathcal V$ — честный проверяющий, то $\Pr(\langle{\mathcal P’,\mathcal V}\rangle(x)=1)\leqslant2^{-q(\lvert{x}\rvert)}$ для любого $x\in \{0,1\}^*\setminus L_R$ и для любого интерактивного вероятностного алгоритма $\mathcal P’$.

Литература

  • [1] Bellare, M. and Goldreich, O. «On defining proofs of knowledge» 1992
  • [2] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)

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