Feige-Fiat-Shamir 식별 체계

이 글에는 참고문헌, 관련 독서 또는 외부 링크 목록이 수록되어 있으나 인라인 인용구가 부족하여 출처가 불분명하다. 좀 더 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오.(2014년 1월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

암호학에서 Feige-Fiat-Shamir 식별 체계는 Urige Feige, Amos Fiat, Adi Shamir가 1988년에 개발한 평행 영지식 증명의 일종이다.모든 제로 지식 증명처럼, 그것은 프로베라라는 한 당사자가 다른 당사자인 검증자에게 그들이 그 비밀 정보가 무엇인지 검증자에게 밝히지 않고 비밀 정보를 가지고 있다는 것을 증명할 수 있게 한다.그러나 Feige-Fiat-Shamir 식별 체계는 Prover와 Verifier 간의 통신 수를 제한하는 모듈식 산술과 병렬 검증 프로세스를 사용한다.

세우다

일반적인 관례에 따라 프로베서 페기와 검증자를 빅터라고 부른다.

p와 q의 큰 소수점 두 개를 선택하고 제품 n = pq를 계산한다.비밀 번호 $s{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}\cdots }$, ${\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$ coprime$$ to n.계산 $v{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle {}_{}}$ s ${\displaystyle {\mathrm{}}_{}^{}}$ ${\displaystyle 2_{}^{}{}_{}^{}}$( ${\displaystyle mod}$ n${\displaystyle }$) ${\$ $p{\displaystyle }$${\$$displaystyle p}$와 q$${\$displaysty q}$은(으)가 비밀로 유지된다.그런 다음 Peggy가 숫자 $s{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$를 전송한다$.$이것들은 그녀의 비밀 로그인 번호들이다.빅토르는 자신을 빅터에게 알리고 싶을 때 페기로부터$$ v ${\displaystyle i_{}}$ ${\$라는 번호를 받는다.빅터는 계수의 인자화를 알 수 없을 때 모듈형 제곱근을 결정하기 어려워 $v{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$ 숫자에서$$ $페기$의 ${\displaystyle i_{}}$ ${\$를 복구할 수 없다.

절차

1. 페기는 무작위 $정수{\displaystyle }$ r ${\displaystyle$ $r$$\},$ 임의 $기호{\displaystyle }$ s${\displaystyle \in \{}$- ${\displaystyle 1}$, ${\displaystyle 1}$}$${\$displaystyle$ s$\in \1\}$을(를) 선택하고$$ ${\displaystyle s\equiv }$ x ${\displaystyle {2\mathrm{}}^{}}$ r${\displaystyle {}^{}}$2 (${\displaystyle 모드}$ n${\displaystyle }$) ${\$ 페기는 x ${\displaystystystystystystystytytimestyptytimestyone$}를 빅토르로$$ 보낸다.
2. Victor는 ${\displaystyle {숫자\mathrm{}}_{}}$ $a{\displaystyle {}_{}}$ 1,${\displaystyle {}_{}\cdots ,}$ ${\displaystyle k_{}}$ ${\$를 선택하고 여기서$$ ${\displaystyle i_{}}$ ${\$는 0 또는$$ 1이다.빅터는 이 숫자들을 페기에게 보낸다.
3. 페기는 $y{\displaystyle }$ ${\displaystyle \equiv }$ ${\displaystyle r}$ s ${\displaystyle {{}_{}}_{}^{}}$ a 1 ${\displaystyle {{s\mathrm{}}_{}}_{}^{}}$ ${\displaystyle {2\mathrm{}}_{}^{}}$ ${\displaystyle {{}_{}}_{}^{}}$ ${\displaystyle {{2\mathrm{}}_{}}_{}^{}}$ ${\displaystyle {{}_{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ k ${\displaystyle {a_{}}_{}^{}}$ ${\displaystyle {{}_{}}_{}^{}}$ (${\displaystyle {{}_{}}_{}^{}\mathrm{mod}}$ $){\$ y$\equiv rs_{1}^{a_{2}^{$2}}\$cdots s_{$k}^{$k_{k}}}{\pmod{n$ 페기는 이 번호를 빅토르에게 보낸다.
4. Victor checks that ${\displaystyle y^{2}{\pmod {n}}\equiv \pm \,xv_{1}^{a_{1}}v_{2}^{a_{2}}\cdots v_{k}^{a_{k}}{\pmod {n}}}$ and that ${\displaystyle x\neq 0.}$

이 절차는 다른 $r{\displaystyle }$ ${\displaystyle r}$과($)$ i {\$displaystyle a_{i}$ 값으로$$ 반복되며, 빅토르가 페기가 실제로 v ${\displaystyle i_{}}$ ${\$의 모듈형 제곱근(${\displaystyle s_{}}$ i ${\$displaystystyle s_${$i})을 소유한다고 만족할 때까지 계속된다.

보안

이 과정에서 페기는 빅토르에게 유용한 정보를 주지 않는다.그녀는 단지 빅터에게 그 숫자가 무엇인지 밝히지 않고 비밀 번호를 가지고 있다는 것을 증명할 뿐이다.각 페기와 빅터 사이의 통신을 가로채는 사람은 같은 정보만 배우게 될 것이다.엿듣는 자는 페기의 비밀 번호에 대해 유용한 것을 배우지 않을 것이다.^{[citation needed]}

이브가 빅토르의 ${\displaystyle v_{}}$ i ${\$ 숫자를$$ 가로챘지만 페기의 ${\displaystyle i_{}}$ ${\$ 숫자가$$ 무엇인지 모른다고 가정해보자.만약 이브가 빅토르에게 자신이 페기라는 것을 납득시키려 한다면 빅토르가 어떤 ${\$의 숫자가 될 것인지 정확하게 맞혀야 할 것이다.She then picks a random ${\displaystyle y}$, calculates ${\displaystyle x\equiv y^{2}v_{1}^{-a_{1}}v_{2}^{-a_{2}}\cdots v_{k}^{-a_{k}}{\pmod {n}}}$ and sends ${\displaystyle x}$ to Victor.빅터가 ${\displaystyle i_{}}$ ${\$를 보낼 때$,$ 이브는 $간단히{\displaystyle }$ y ${\displaystyle y}$를 돌려준다$.$ 빅터는 만족하고 이브가 비밀 번호를 가지고 있다고 결론짓는다.그러나 빅토르의 ${\$가 될$$ 것을 이브가 정확하게 추측할 확률은 1 ${\displaystyle {in}^{}}$ $2k{\displaystyle {\mathrm{}}^{}}${\$displaystyle$ 2$^{k$ 절차 $t{\displaystyle }$ ${\displaystytle$ $t$$}$을 $반복$하면 2k ${\displaystyle t^{}}$ ${\$ 2$^{kt}.$ $k{\displaystyle }$= ${\displaystyle 5}$ ${\displaysty$}, t$$ = k$=$${\displaystyle 5}\},$ $t{\displaystyle }$ = t = t = t = t = t = t = t = t = ${\displaystyle t^{}}$ = t = 4${\displaystyle \}}$$\displaystyle t=4}$페기로 성공적으로 포즈를 취할 확률은$$ 100만분의 1도 안 된다.

참조

• Feige, Uriel; Fiat, Amos; Shamir, Adi (1988). "Zero-knowledge proofs of identity". Journal of Cryptology. 1 (2): 77–94. doi:10.1007/BF02351717. S2CID 2950602.
• Trappe, Wade; Washington, Lawrence C. (2003). Introduction to Cryptography with Coding Theory. Upper Saddle River: Prentice-Hall. pp. 231–233. ISBN 0-13-061814-4.
• Wong, Chung Kei; Lam, Simon S (August 1999). "Digital Signatures for Flows and Multicasts" (PDF). IEEE/ACM Transactions on Networking. 7 (4). (eFFS, 확장 Feige-Fiat-Shamir 체계)