Fiat-Shamir Protocol

이전 포스팅에서 Zero Knowledge(영지식)에 대해 포스팅한 적이 있습니다. 

(잘 모르시는 분은 이전 포스팅을 참고하시길...)

Fiat-Shamir Protocol은 영지식 증명 방법 중 하나입니다. 영지식 증명체계(Zero Knowledge Proof System)란 한 사람이 다른사람에게 사실의 증명에 관한 어떤 정보도 보이지 않고 사실의 증명을 알고 있음을 확신하도록 만드는 방법으로 다시 말해서, 정보를 전혀 주지 않고 상대방에게 정보를 알고 있음을 증명하는 방법입니다.

Fiat-Shamir Protocol은 1986년 이스라엘의 수학자 Adi Shamir와 Amos Fiat가 고안한 사용자 인증에 대한 새로운 프로토콜입니다.

이 프로토콜은 충분이 큰 두 소수의 곱 n이 있다고 가정할 때, x = s^2 (mod n) 에서 s를 찾기란 사실상 불가능하다는 것에 기초를 두고 있습니다.

인증 시스템에서는 보통 두 소수는 인증센터만 알고 있고 n은 공개됩니다. 여기서 n은 보통 200자리정도의 숫자를 사용합니다. 

s값을 찾기가 힘들기 때문에 s를 secret key로 사용하는 경우가 많고 x는 사용자의 ID로 사용하여 인증을 합니다.

그럼 이쯤에서 Fiat-Shamir Protocol을 살펴봅시다.

프로토콜은 간단합니다. P는 랜덤 값 r을 선택해서 x를 계산하고, 비밀 값 S로 I를 계산하여 V에게 보냅니다. V는 0 또는 1중 랜덤하게 선택을 해서 e값을 P에게 보냅니다. P는 각 경우에 대해 y값을 계산해서 V에게 다시 보내게 되구요, V는 이 값들을 가지고 증명을 하게 됩니다. 

여기서 악의적인 사용자가 V를 속일 확률은 (1/2)^t가 됩니다. 따라서 이 과정을 여러번 반복할 수록 악의적인 사용자가 공격할 확률은 무쟈게 작아지게 되는 것이죠.

앞서 설명했던 영지식 증명체계와 결부시켜서 의미를 따져보면 V는 P의 S값을 모르지만 P가 S값을 가지고 있다는 것은 증명할 수 있는 것입니다.

참 쉽죠?