Доказательство знаний

В криптографии доказательство знаний — это интерактивное доказательство , в котором доказывающему удается «убедить» проверяющего в том, что доказывающий что-то знает. То, что для машины означает «знать что-то», определяется с точки зрения вычислений. Машина «что-то знает», если это что-то можно вычислить, учитывая машину в качестве входных данных. Поскольку программа доказывающего не обязательно выдает само знание (как в случае с доказательствами с нулевым разглашением). ) для реализации этой идеи введена машина с другой программой, называемой экстрактором знаний. Нас больше всего интересует то, что можно доказать с помощью полиномиальных машин с ограниченным временем. В этом случае набор элементов знания ограничивается набором свидетелей некоторого языка в NP .

Позволять $x$ быть высказыванием языка $L$ в НП и $W(x)$ набор свидетелей для x, который должен быть принят при доказательстве. Это позволяет определить следующее соотношение: $R=\{(x,w):x\in L,w\in W(x)\}$.

Доказательство знаний для связи $R$ с ошибкой в ​​знаниях $\kappa$ это двапартийный протокол с доказывающим $P$ и проверяющий $V$ со следующими двумя свойствами:

1. Полнота : Если $(x,w)\in R$, то доказывающий $P$ кто знает, свидетель $w$ для $x$ удается убедить проверяющего $V$ его знаний. Более формально: $\Pr(P(x,w)\leftrightarrow V(x)\rightarrow 1)=1$, т. е. учитывая взаимодействие между доказывающим P и проверяющим V, вероятность того, что проверяющий будет убежден, равна 1.
2. Валидность : Валидность требует, чтобы вероятность успеха извлечения знаний $E$ при извлечении свидетеля, учитывая доступ оракула к возможно злонамеренному доказывающему ${\tilde {P}}$, должно быть не меньше вероятности успеха доказывающего. ${\tilde {P}}$ чтобы убедить проверяющего. Это свойство гарантирует, что ни один доказывающий, не знающий свидетеля, не сможет убедить проверяющего.

Подробности об определении

Это более строгое определение валидности :

Позволять $R$ быть свидетелем, $W(x)$ набор всех свидетелей общественной ценности $x$, и $\kappa$ ошибка в знаниях.Доказательством знаний является $\kappa$-действительно, если существует машина полиномиального времени $E$, учитывая доступ оракула к ${\tilde {P}}$, такой, что для каждого ${\tilde {P}}$, дело в том, что $E^{{\tilde {P}}(x)}(x)\in W(x)\cup \{\bot \}$ и $\Pr(E^{{\tilde {P}}(x)}(x)\in W(x))\geq \Pr({\tilde {P}}(x)\leftrightarrow V(x)\rightarrow 1)-\kappa (x).$

Результат $\bot$ означает, что машина Тьюринга $E$ не пришел к выводу.

Ошибка в знаниях $\kappa (x)$ обозначает вероятность того, что верификатор $V$ мог бы принять $x$, хотя доказывающий фактически не знает свидетеля $w$. Экстрактор знаний $E$ используется для выражения того, что подразумевается под знанием машины Тьюринга . Если $E$ может извлечь $w$ от ${\tilde {P}}$, мы говорим, что ${\tilde {P}}$ знает цену $w$.

Это определение свойства достоверности представляет собой комбинацию свойств достоверности и строгой достоверности. За небольшие ошибки в знаниях $\kappa (x)$, например, $2^{-80}$ или $1/\mathrm {poly} (|x|)$ его можно рассматривать как более сильное, чем надежность обычных интерактивных доказательств .

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

Чтобы определить конкретное доказательство знания, необходимо не только определить язык, но и свидетелей, которых должен знать проверяющий. В некоторых случаях доказать принадлежность к языку может быть легко, тогда как вычислить конкретного свидетеля может быть сложно. Лучше всего это объяснить на примере:

Позволять $\langle g\rangle$ — циклическая группа с генератором $g$ в котором решение задачи дискретного логарифма считается трудным. Определение принадлежности языка $L=\{x\mid g^{w}=x\}$ тривиально, как и все $x$ находится в $\langle g\rangle$. Однако найти свидетеля $w$ такой, что $g^{w}=x$ соответствует решению задачи дискретного логарифмирования.

Протоколы

Протокол Шнорра

Одно из самых простых и часто используемых доказательств знания — доказательство знания дискретного логарифма — принадлежит Шнорру. Протокол определен для циклической группы $G_{q}$ порядка $q$ с генератором $g$.

Чтобы доказать знание $x=\log _{g}y$, доказывающий взаимодействует с проверяющим следующим образом:

1. В первом раунде доказывающий берет на себя обязательство использовать случайность. $r$; поэтому первое сообщение $t=g^{r}$ также называется обязательством .
2. Верификатор отвечает вызовом $c$ выбрано случайно.
3. После получения $c$, доказывающий отправляет третье и последнее сообщение ( ответ ) $s=r+cx$ уменьшен по модулю порядка группы.

Верификатор принимает, если $g^{s}=ty^{c}$.

Мы видим, что это действительное доказательство знаний, поскольку оно имеет экстрактор, который работает следующим образом:

1. Имитация доказывающего устройства для вывода $t=g^{r}$. Доказывающая сейчас в состоянии $Q$.
2. Создать случайное значение $c_{1}$ и введите его в доказывающую программу. Он выводит $s_{1}=r+c_{1}x$.
3. Перемотайте доказывающее, чтобы заявить $Q$. Теперь сгенерируйте другое случайное значение $c_{2}$ и введите его в программу доказательства, чтобы получить $s_{2}=r+c_{2}x$.
4. Выход $(s_{1}-s_{2})(c_{1}-c_{2})^{-1}$.

С $(s_{1}-s_{2})=(r+c_{1}x)-(r+c_{2}x)=x(c_{1}-c_{2})$, выход экстрактора точно $x$.

Этот протокол является протоколом с нулевым разглашением , хотя это свойство не требуется для доказательства знания.

Сигма-протоколы

Протоколы, которые имеют вышеуказанную трехходовую структуру (обязательство, вызов и ответ), называются сигма-протоколами . Название происходит от Sig, обозначающего зигзаг, символизирующий три хода протокола, и MA, аббревиатуры от «Мерлин-Артур». Сигма-протоколы существуют для доказательства различных утверждений, например, относящихся к дискретным логарифмам. Используя эти доказательства, доказывающий может не только доказать знание дискретного логарифма, но и то, что дискретный логарифм имеет определенную форму. Например, можно доказать, что два логарифма $y_{1}$ и $y_{2}$ по поводу баз $g_{1}$ и $g_{2}$ равны или удовлетворяют некоторому другому линейному соотношению . Для a и b элементов $Z_{q}$, мы говорим, что доказывающий доказывает знание $x_{1}$ и $x_{2}$ такой, что $y_{1}=g_{1}^{x_{1}}\land y_{2}=g_{2}^{x_{2}}$ и $x_{2}=ax_{1}+b$. Равенство соответствует частному случаю, когда a = 1 и b = 0. Поскольку $x_{2}$ может быть тривиально вычислено из $x_{1}$ это эквивалентно доказательству знания такого x , что $y_{1}=g_{1}^{x}\land y_{2}={(g_{2}^{a})}^{x}g_{2}^{b}$.

Это интуиция, лежащая в основе следующих обозначений: который обычно используется для выражения того, что именно доказано доказательством знаний.

$PK\{(x):y_{1}=g_{1}^{x}\land y_{2}={(g_{2}^{a})}^{x}g_{2}^{b}\},$

утверждает, что доказывающему известен x , удовлетворяющий приведенному выше соотношению.

Приложения

Доказательства знаний являются полезным инструментом для создания протоколов идентификации и, в их неинтерактивном варианте, схем подписи. Такие схемы:

• подпись Шнорра

Они также используются при создании систем групповой подписи и анонимных цифровых учетных данных .

См. также

• Криптографический протокол
• Доказательство с нулевым разглашением
• Интерактивная система доказательств
• Темы криптографии
• Подтверждение пароля с нулевым разглашением
• Обоснованность (интерактивное доказательство)