[암호학 둘러보기](12)[대화형 ZKP]

영지식 증명: 상대에게 구체적인 내용은 알리지 않은 채 어떤 주장을 참이라는 걸 증명하는 방법

• 완전성: 주장이 참이라면 항상 증명을 받아들일 수 있다
• 건실성: 주장이 거짓이라면 증명자가 검증자를 속일 확률이 매우 낮다
• 영지식성: 검증자는 주장이 참이라는 사실만 알 수 있지 그 외의 정보는 모른다

대화형 ZKP: 지식을 증명할 때 상호작용 있음 (증거를 여러번 전송)

• 과정
  p는 매우 큰 소수, g는 Zp의 생성자
  B = g^a (mod p)로
  공개 피라미터 (p, g, B)를 합의한다증명자는 w = (k - a*r) (mod p-1)을 통해 w를 계산하고 전달한다.
  
  만약 V = g^w * B^r (mod p)가 만족한다면 검증 성공
  이 과정을 여러번 반복해 증명자가 a를 알고 있을 확률을 높인다.
  
  증명자는 임의의 정수 k (단, 1 <= k <= p-1) 선택 후
  V = g^k (mod p)를 계산해 검증자에게 전달한다.
  검증자는 임의의 정수 r (단, 1 <= r <= p-1)을 선택해 전달한다.
• 예)
  페기는 p = 5, g = 3, a = 6이고
  B = 3^6 (mod 5) = 4로
  공개 피라미터는 (5, 3, 4)로 했다.페기는 w = (2 - 6*1) (mod 4) = 0을 전달한다.
  
  페기는 k = 2를 선택하고
  V = 3^2 (mod 5) = 4를 빅터에게 전송했다.
  빅터는 1을 선택해 페기에게 전달했다.
  
  3^0 * 4^1 (mod 5) = 4
  V = 4 이므로 검증 성공!
  이후 빅터가 다른 정수도 보내며 계속 검증하기