피아트-샤미르(Fiat-Shamir)프로토콜

피아트-샤미르프로토콜은 영지식증명의 한 종류의 프로토콜입니다.

이것을 사용하는 이유는 어떤사실을 상대방에게 전달하지않고 본인이 가지고있다는것을 증명하는것 입니다.

A와 B가 서로 피아트-샤미르 프로토콜을 사용해 영지식증명을 한다고 생각해봅시다.

A와 B 사이의 공개값 N과 V=(S^2  mod N)

A만 가지고있는 값은 S

B는 A가 S를 알고 있는지 증명하려고합니다.

1.A가 난수 r을 골라 r^2  mod N를 계산해 B에게 보내줍니다.

2.B가 e값 을 A에게 보냅니다 (0 또는 1)

3.A가 난수 r과 자신이알고 있던 S를 이용해  y=r×S^e  mod N 을 전송합니다.

4.B는 y^2와 (r^2 (S^e)^2=r^2 (S^2)^e=)xv^(0 or 1)  mod N 을 비교한다

A가 B를 속였을 확률은 1/2이지만 위같은 프로토콜을 여러번 시행하여 속일확률을 줄일수 있다.