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

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

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

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

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

Подробная информация об определении [ править ]

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

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

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

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

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

Отношение к общим интерактивным доказательствам [ править ]

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

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

Протоколы [ править ]

Протокол Шнорра [ править ]

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

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

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

Проверяющий принимает, если .${\displaystyle g^{s}=ty^{c}}$

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

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

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

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

Сигма-протоколы [ править ]

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

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

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

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

Приложения [ править ]

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

• Указатели по криптологии Хельгера Липмаа