영지식 증명

- 가명성 : 이름을 거짓으로 구성

- 연결불가성 : 동일한 사람에 의해 수행된 것인지 다른 사람에 의해 수행된 것인지 알 수 없음

ex) 2명이 있지만 누가 수행 했는지는 모르는 상태

- 익명성 : 가명성, 연결불가성 모두 충족

즉 <비트코인>은 익명성이 충족되지 않는다.
// 가명성은 성립하나 연결 불가성은 성립하지 않는다.
-> 누가 보낸 건지는 거래 내역으로 확인 가능하기 때문이다.

영지식 증명을 써야하는 이유

가명성으로 가짜 이름을 주더라도 특정 어느 사람인지는 유추 가능한 문제가 있다.
그래서 영지식 증명으로 제 3자가 보기에는 어느 사람이 수행했는지를 아예 모르게 할 수 있다.
그리고 수행 여부만 확인할 수 있게 된다.

영지식 증명

• all partial information(부분정보) 성립X
  // 제 3자한테 어떠한 정보도 노출 X
• Semantic Security(= Polynomial Security)
  무한은 현실상 불가능, 유한한 계산능력을 가진
  제 3자가 있어도 어떠한 정보도 노출 X
  
  
  영지식 증명 핵심 :
  제 3자한테 어떠한 정보도 노출하지 않은 채,
  대상한테 수행 완료 했다는 것만 증명하면 됨

영지식 증명 종류

• 대화형 영지식 증명
• 비 대화형 영지식 증명
• zk-snarks

대화형 영지식 증명

View A와 View A' 간의 차이점을 찾지 못해서 어떤 Prover가 진짜인지 판단을 못함

이 과정에서 어떠한 치명적인 부분 정보도 노출되지 않음

정보를 주고받을 때는
처음에 공개하는 공개 정보,
중요한 정보는 암호화된 정보
(암호화된 정보 + 공개 정보로 구성)

View A와 View A' 가 같다는 것은
앙상블 (확률모델)을 이용하여 증명가능

Semantic Security(= Polynomial Security)
View A와 View A' 로부터 얻을 수 있는 정보가 같다면
암호화된 정보로부터 얻을 수 있는 정보는 '0'에 가깝다.
// partial information 이 없다.
실제로 쓰일 때는 무수히 많은 View를 만들어서
아예 확률을 0에 수렴하게 만든다.

대화형 영지식 증명 단점

• 검증을 하기 위해서는 Prover와 Verifier가 항상 온라인 상태로 유지,
• Network(View)가 2개 이상 필요-> cost
• 통신량, 계산량이 많음

비 대화형 영지식 증명

대화형 영지식 증명은 확률을 높이기 위해 많은 양의 계산이 필요 하지만 witness를 한번 주는 것으로 해결
Prover는 메시지를 보낸 후 온라인 상태를 유지할 필요가 없어짐
Verifier는 그래도 항상 온라인 상태
그러나 witness인 증거의 크기가 매우 커지게 되는 문제가 있음

zk – snarks

영지식을 사용
witness의 길이가 짧음
비 대화형의 장점만 가져옴

zk-SNARKS 이용평가자가 Verifier(검증자)한테 witness를 주면 검증자는 수행 완료 여부만 출력한다.
제 3자가 보기에는 노출된 정보 없이 수행 완료 여부만 확인 가능