지식증명서

암호학에서 지식의 증명은 프로베라가 무언가를 알고 있다는 검증자를 '공조'하는 데 성공하는 쌍방향 증거다.기계가 '무엇을 알고 있다'는 것이 의미하는 것은 계산의 관점에서 정의된다.기계는 '무엇을 알고 있다'고, 만약 이것이 계산될 수 있다면, 기계에 입력으로 주어진다.프로베라의 프로그램이 반드시 지식 그 자체를 뱉어내지는 않기 때문에(영지식 증명서의^[1] 경우처럼) 지식 추출기라 불리는 다른 프로그램을 가진 기계를 도입하여 이러한 생각을 포착한다.우리는 대부분 다항 시간 제한 기계로 증명할 수 있는 것에 관심이 있다.이 경우 지식 요소 집합은 NP에서 일부 언어의 증인 집합으로 제한된다.

$x{\displaystyle }$ ${\displaystyle x}$을(를) NP의$$ $언어{\displaystyle }$ L ${\displaystyle L}$과($와{\displaystyle }$) W${\displaystyle }$( ${\displaystyle x}$) ${\displaystyle W(x)}$에 대한 증인의$$ 집합이 증명에 수용되도록 한다.${\displaystyle 이}$를 통해 우리는${\displaystyle }다음$과${\displaystyle }$같은 관계를 정의할 수 있다${\displaystyle :}$ R = { ${\displaystyle (}$ ${\displaystyle x}$, ${\displaystyle w}$)${\displaystyle }$: ${\displaystyle x)}$ ${\displaystyle L}$ , $\$ W ( x ) } {\$displaystyle$ R$=\{(x,w)}:x\$in L$,$w$\backslash$in W$(x)\}.$

지식 오류 $\kappa {\displaystyle }$ ${\displaystyle \kappa }$을(를) 가진$$ $R{\displaystyle }$ ${\displaystyle R}$에 대한 지식 증명서는 프로베서 $P{\displaystyle }$ ${\displaystyle P}$과 검증자 V ${\displaystyle V}$을(를) 가진 양당 프로토콜로, 다음$$ 두 가지 속성이 있다$$.

1. 완전성: (${\displaystyle x}$, ${\displaystyle w}$) ${\displaystyle \{}$R {\$displaystyle (x,$w$)\backslash$$in R}$에 있는 경우, $x{\displaystyle }$ ${\displaystyle x}$에 대한 증인 w ${\displaystyle w}$을(를) 알고$$ 있는 프로베라 $P{\displaystyle }$ ${\$$displaystyty$ P$}$이 자신의$$ $지식$을 $검증$하는 데$$성공한다.좀 더 형식적으로: ${\displaystyle \mathrm{Pr}}$( ${\displaystyle P}$(${\displaystyle }$, ${\displaystyle w}$ )${\displaystyle }$V${\displaystyle }$( ${\displaystyle \mathrm{x}}$)${\displaystyle }$→ 1${\displaystyle }$)${\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle \Pr(x,w)\좌우타로우 V(x)\우타로우$ 1$)=1.$즉, 프로베베라 P와 검증자 $V$의 상호작용을 고려할 때 검증자가 확신할 확률은 1이다.
2. 유효성: 타당성을 위해서는 악의적인 $프로베라{\displaystyle \stackrel{}{}}$ P${\displaystyle \stackrel{}{}}$~ ${\$에 대한 Oracle 액세스 권한이 주어지는 경우$,$ 증인 추출 시 지식$$ $추출기{\displaystyle }$ E ${\displaystyle E}$의 성공 확률은 최소한 프로베라 $P{\displaystyle \stackrel{}{}}$~ ${\$ieca}i만큼$$ 높아야 한다.검증자를 설득하는 것.이 재산은 증인을 모르는 어떤 프로베라도 검증자를 설득하는데 성공할 수 없다는 것을 보장한다.

정의에 대한 세부 정보

이것은 유효성에 대한 보다 엄격한 정의다.^[2]

$R{\displaystyle }$ ${\displaystyle R}$을(를) 증인 관계가 되게$$ $하고{\displaystyle }$, W${\displaystyle }$(${\displaystyle }$x )$${\$displaystyle$ W$(x)}$ 공개 값 $x{\displaystyle }$ ${\displaystyle x}$ 및$$$\kappa {\displaystyle }$ ${\displaysty \kappa }$ 지식 오류에$$ 대한 모든 증인 집합이 되도록$$ 한다.A proof of knowledge is ${\displaystyle \kappa }$-valid if there exists a polynomial-time machine ${\displaystyle E}$, given oracle access to ${\displaystyle {\tilde {P}}}$, such that for every ${\displaystyle {\tilde {P}}}$, it is the case that ${\$$displaystyle E^{{\tilde {P}}(x)}(x)\in W(x)\cup \{\bot \}}$ and ${\displaystyle \Pr(E^{{\tilde {P}}(x)}(x)\in W(x))\geq \Pr({\tilde {P}}(x)\leftrightarrow V(x)\rightarrow 1)-\kappa (x).$$}$

결과 $\perp {\displaystyle \mathrm{}}$ ${\displaystyle \bot$}은(는) 튜링 시스템 $E{\displaystyle }$ {\$displaystyle E}$이(가$)$ 결론에 도달하지 않았음을$$ 의미한다$$.

지식 오류 $\kappa {\displaystyle }$( ${\displaystyle x}$) ${\displaystyle \kappa (x)}$은 $검증자{\displaystyle }$ V ${\displaystyle V}$이(가) 실제로 $w{\displaystyle }$ ${\displaystyle w}$ 증인을 알 수 없음에도 $불구하고{\displaystyle }$x {\$displaystystyle x}$을(를)할$$ 가능성을 나타낸다$$$.$지식 추출기 $E{\displaystyle }$ ${\displaystyle E}$는 튜링 시스템의 지식으로 무엇을 의미하는지 표현하기 위해 사용된다$$.$E{\displaystyle }$ ${\displaystyle E}$이(가) $P{\displaystyle \stackrel{}{}}$~ ${\$에서 w ${\displaystyle w$$}$을(를) 추출할 수 있다면$$ $P{\displaystyle \stackrel{}{}}$~ ${\${$P$$}$이(가) $w{\displaystyle }$ ${\displaystystystyle$ w}의$$ 값을 알고 있다고 말할 수 있다$.$

이러한 유효성 속성의 정의는 유효성 속성과 강력한 유효성 속성의 조합이다.^[2]예를 $들어{\displaystyle {\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$- ${\displaystyle {80}^{}}${\$displaystyle 2^{-$80$$} ${\displaystyle 또는\mathrm{}}$ ${\displaystyle \mathrm{1}}$/ p ${\displaystyle \mathrm{o}}$ l${\displaystyle }$(${\displaystyle x}$ )$${\$displaystyle$1/\$mathrm$ {$poly}(x$)과 같은 작은 지식 오류 $\kappa {\displaystyle }$ ${\displaystyle (x}$ $){\displaystystyle$ $\$$kappa (x$의 경우 일반적인$$ 대화형 교정보다 강한 것으로 볼 수 있다.

일반 대화형 교정쇄와의 관계

특정한 지식의 증거를 정의하기 위해서는 언어뿐만 아니라 검증자가 알아야 할 증인들도 정의해야 한다.어떤 경우에 특정한 증인을 계산하는 것은 어려울 수 있는 반면, 언어의 구성원 자격을 증명하는 것은 쉬울 수 있다.이는 예를 사용하여 가장 잘 설명된다.

$⟨{\displaystyle }$ ${\displaystyle g}$ ${\displaystyle ⟩}$ ${\displaystyle \langle g\angle }$을(를) 별도의 로그 문제 해결이 어렵다고 판단되는$$ 생성기 $g{\displaystyle }$ ${\displaystyle g}$을(를) 가진 순환 그룹이 되도록$$ 한다.Deciding membership of the language ${\displaystyle L=\{x\mid g^{w}=x\}}$ is trivial, as every ${\displaystyle x}$ is in ${\displaystyle \langle g\rangle }$. However, finding the witness ${\displaystyle w}$ such that ${\displaystyle g^{w}=x}$ holds corresponds to solving t별개의 로그 문제야

프로토콜

슈노르 프로토콜

가장 단순하고 자주 사용되는 지식의 증명 중 하나인 이산 로그의 지식의 증명은 슈노르 덕분이다.^[3]프로토콜은 발전기 $g{\displaystyle }$ ${\displaystyle g}$이(가) 있는 순서 $q{\displaystyle }$ ${\displaystyle q}$의 주기 그룹 $G{\displaystyle {}_{}}$ ${\displaystyle q_{}}$ ${\$에 대해 정의된다$.$

$x{\displaystyle }$= ${\displaystyle {\log }_{}}$ ${\displaystyle g_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle y}$ ${\displaystyle x=\log _{g}y}$에 대한 지식을 증명하기 위해 프로베러는 다음과 같이 검증기와 상호 작용한다$.$

1. 첫 번째 라운드에서 프로베러는 자신을 $무작위성{\displaystyle }$ r$${\$displaystyle$r}에 맡긴다$.$ 따라서 첫 번째 메시지 $t{\displaystyle }$= ${\displaystyle {}^{}}$ ${\displaystyle r^{}}$ ${\$는 약속이라고도 한다$$.
2. 검증자는 임의로 선택한$$ $챌린지{\displaystyle }$ c ${\displaystyle c}$로 응답한다.
3. $c{\displaystyle }$ ${\displaystyle c}$을$($를) 수신한 후 프로베러는 세 번째 및 마지막 메시지(응답) $s{\displaystyle }$= r${\displaystyle }$+ ${\displaystyle c}$ ${\displaystyle x}$ ${\displaystyle s=r+cx}$을(를) 전송하여 그룹의 순서를 변경한다.

${\displaystyle {검증자}^{}}$는 $g{\displaystyle {}^{}{s}^{}}$ = ${\displaystyle t}$y c {\$displaystyle g^{s}=$ty^{$c}}$을(를) 수락한다$.$

다음과 같이 작동하는 추출기가 있기 때문에 이것이 유효한 지식의 증거임을 알 수 있다.

1. proverl을 시뮬레이션하여 $출력{\displaystyle }$t = ${\displaystyle {}^{}}$ ${\displaystyle r^{}}${\$displaystyle$t=$g^{r$프로베러는 현재 상태 $Q{\displaystyle }$ ${\displaystyle Q}$ 에 있다$.$
2. 임의 값 $c{\displaystyle {}_{}}$ ${\$1}를 생성하여$$ 프로베라로 입력한다.$출력{\displaystyle {}_{}{s\mathrm{}}_{}}$ ${\displaystyle 1}$= ${\displaystyle {}_{}}$ + ${\displaystyle {c\mathrm{}}_{}}$ ${\displaystyle {}_{}}$x {\$displaystyle s_{1}=r+c_{$1}$x}$.
3. 프로베라를 $상태{\displaystyle }$ Q ${\displaystyle$ Q$}(으$)로 되감으십시오$.$ 이제 다른 랜덤 값 c ${\displaystyle {2\mathrm{}}_{}}$ ${\$}}개를 생성하고$$ 프로베레버에 입력하여 s ${\displaystyle {2\mathrm{}}_{}}$= ${\displaystyle r}$+ c ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle s_{2}=r+c_{2}x$ .
4. 출력$({\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$- ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$)${\displaystyle }$(${\displaystyle {c\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$- ${\displaystyle {c\mathrm{}}_{}}$ ${\displaystyle {}_{}{}^{}}$)${\displaystyle {}^{}}$- ${\displaystyle 1^{}}$ ${\$

Since ${\displaystyle (s_{1}-s_{2})=(r+c_{1}x)-(r+c_{2}x)=x(c_{1}-c_{2})}$, the output of the extractor is precisely ${\displaystyle x}$.

이 프로토콜은 지식의 증명에 필요한 것은 아니지만 영지식이다.

시그마 프로토콜

위의 3-이동 구조(커밋, 챌린지, 응답)를 가지는 프로토콜을 시그마 프로토콜이라고^{[citation needed]} 한다.그리스 문자 ${\displaystyle \Sigma }$는 프로토콜의 흐름을 시각화한다$$.시그마 프로토콜은 이산 로그와 관련된 것과 같은 다양한 문장을 증명하기 위해 존재한다.이러한 증거를 이용하여 프로베러는 이산 로그의 지식을 증명할 수 있을 뿐만 아니라 이산 로그가 특정한 형태라는 것도 증명할 수 있다.예를 들어 $base{\displaystyle {}_{}}$ ${\displaystyle {g\mathrm{}}_{}}$ 1 ${\$및 $g{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}에$$ 대해$$ y ${\displaystyle {1\mathrm{}}_{}}$ ${\$displaystyle $y_{2$}}의$$ 두 로그가 같거나$$ 일부 다른 선형 관계를 충족한다는 것을 증명할 수 있다.For a and b elements of ${\displaystyle Z_{q}}$, we say that the prover proves knowledge of ${\displaystyle x_{1}}$ and ${\displaystyle x_{2}}$ such that ${\displaystyle y_{1}=g_{1}^{x_{1}}\land y_{2}=g_{2}^{x_{2}}}$ and ${\displaystyle x_2=a{x}_1}$${\displaystyle {}_{}+}$ ${\displaystyle b}$ ${\displaystyle x_{2}=ax_{1}+b}$.Equality corresponds to the special case where a = 1 and b = 0. As ${\displaystyle x_{2}}$ can be trivially computed from ${\displaystyle x_{1}}$ this is equivalent to proving knowledge of an x such that ${\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}={2}^{a}}^{x}g_{2}^{b}}}}}}}}$

프로베러는 위의 관계를 충족시키는 x를 알고 있다고 진술한다.

적용들

지식의 증명서는 식별 프로토콜의 구축과 그 비 상호 작용 변종인 서명 체계에서 유용한 도구다.그러한 계획은 다음과 같다.

• 슈노르 서명

그룹 서명 및 익명의 디지털 자격 증명 시스템 구축에도 사용된다.

참고 항목

• 암호 프로토콜
• 영지식증거
• 인터랙티브 프루프 시스템
• 암호학의 주제
• 0-knowledge password proof
• 건전성(상호작용 증명)

참조