영지식 증명 : Completeness

이제 영지식 증명의 수학적인 정의도 알아보고자 한다. 우선 첫번째 조건인 Completeness 완정성을 충족해야 한다. 

 

완전성 Completeness

진짜로 비밀 번호, 정답을 알고 있는 사람이라면, 검증을 항상 통과해야 한다는 뜻이다. 수식으로 적으면 아래와 같다. 

Pr[V(x,π)=1]≈1

 

• V: 검증자
• x: 공개된 문제
• π: 증명
• V(x,π)=1 : 검증자가 “맞다”고 판단
• ≈1 거의 항상 통과

 

 

 

수식 

 

1. Pr

Probability, 즉 확률이다. 확률이 나오는 이유는 영지식 증명에는 랜덤성이 들어가는 경우가 많기 때문이야. 예를 들어 증명 과정에서 검증자가 무작위 질문을 던지거나 증명자가 무작위 값을 섞어서 증명을 요구할 수 있다.

---

 

2. V

Verifier, 즉 검증자다. 검증자는 증명자가 제출한 증명을 보고

• 이 증명이 맞는가?
• 이 사람이 진짜 알고 있는가?

를 판단한다.

---

3. x

공개된 문제 이다. 

예를 들어:

• “이 해시값을 만든 원래 비밀번호를 나는 알고 있다”

라고 할 때 공개되는 해시값이 x가 된다. 즉, xxx는 모두가 볼 수 있는 정보다.

---

4. π

Proof, 증명 이다. 증명자가 검증자에게 제출하는 결과물이다. 중요한 것은 π 안에 비밀 정보 자체가 들어가선 안 된다는 것이다.  예를 들어 비밀번호를 증명한다고 해서 π에 실제 비밀번호를 넣으면 그건 영지식 증명이 아니게 된다.

---

5. V(x,π)

V(x,π) 는 검증자가 공개 입력한 x와 증명 π를 보고 판단하는 과정이다. 

검증자 V가 공개 정보 x와 증명 π를 보고이 증명이 맞는지 검사한다는 뜻이다.

---

6. V(x,π)=1

V(x,π)=1, 여기서 1은 accept, 통과를 뜻한다. 

그러나 반대로 V(x,π)=0이면 reject, 거절이다. 

 

그래서 V(x,π)=1은 검증자가 이 증명을 맞다고 받아들였다는 뜻이다. 

---

7. ≈1

거의 1에 가깝다는 뜻이다. 즉, 확률이 거의 100%에 가깝다는 의미이다. 증명자가 진짜 비밀 정보를 알고 있다면 검증자는 그 증명을 거의 항상 받아들여야 해.

---

전체를 다시 읽으면

• Pr[V(x,π)=1]≈1

검증자 V가 공개 입력 x와 증명 π를 보고 받아들일 확률은 거의 1이다.