영지식 증명 (Zero-Knowledge Proof) 가 무엇일까

 

Zero-Knowledge Proof

---

영 지식(zero-knowledge) + 증명

먼저 지식이라는 것은 결국 어떠한 정보를 의미하며

개인 정보와 밀접한 관계를 가질 수 있다.

​

하지만 앞에 zero, 즉 어떠한 정보도 들어내지 않는다는 영지식과 증명이 하나로 만난 용어이다.

결국 영 지식 증명의 의미로는 "정보를 노출하지 않고 증명하는 것" 을 의미한다.

 

가장 핵심적이고 가장 궁금한 부분은 어떻게 정보를 노출하지 않고 증명하는가에 대해서이다.

 

Prover 즉 검증받는 존재는 자신의 정보를 노출하지 않고 자신의 증거를 제출해야 하고

Verifier 즉 검증하는 존재는 Prover이 준 증거가 옳은지 옳지 않은 지 확인할 수 있어야 한다.

​

이렇게 증명하는 시스템이 2가지가 존재한다.

대화형 영지식 증명 시스템(Interactive Zero-Knowledge Proof System)

비대화형 영지식 증명 시스템(Non-Interactive Zero-Knowledge Proof System)

 

 

 

 

영지식 증명과 동굴 예시(대화형 영지식 증명 시스템)

위와 같이 두 개의 갈림길이 있는 동굴에서 두 갈림길은 결국 하나로 연결되는데 그 연결부에는 서로 지나다닐 수 있는 문이 있다.

​

이 문은 잠겨있으며 분홍색 사람은 이 문의 비밀번호를 공개하지 않고 내가 알고 있다는 것을 초록색 사람에게 증명하려 한다.

​

분홍색 사람은 A 길 혹은 B 길로 통해 동굴 안으로 들어갔을때

만약 비밀번호를 정말 알고 있다면 동굴을 나올 때 A로 나올 수도 있고 B로도 나올 수 있을 것이다.

​

이를 이용하여

초록색 사람은 분홍색 사람이 동굴을 들어가는것을 보지않고 동굴에 들어갔다면 특정한 길로 나오라고 요구를 하게 된다.

​

분홍색 사람이 만약 비밀번호를 모르고 있었을때는 운이 좋게 한두 번은 초록색 요구에 따를 수 있겠지만

이를 반복한다면 확률상 불가능에 가까워지고

​

정말 비밀번호를 알고 있었다면 초록색 사람의 요구를 모두 따를 수 있을 것이다.

이렇게 하는 것으로 내가 알고 있는 비밀번호를 노출하지 않고 내가 비밀번호를 알고 있다는 사실을 증명하는 방법이

영지식 증명이다.

 

이곳에서의 분홍색 사람은 prover , 초록색 사람은 verifier 이다.

 

 

비대화형 영지식 증명 시스템

비대화형 즉 대화형의 문제였던 많은 메시지교환의 문제를 해결할 수 있는 방법이다.

비대화형 영지식 증명에서는 메시지 교환을 한 번만 하게 된다.

​

메시지 교환을 한 번만 하기 위해서는 신뢰할 수 있는 제3자의 존재가 필요하다.

1. Prover 은 신뢰할 수 있는 제3자에게 증거를 만들 때 필요한 정보를 요청한다.

2. 신뢰할 수 있는 제3자는 Prover에게 정보를 제공한다.

3. Prover은 받은 정보를 활용하여 증거를 만든다.

4. Verifier은 Prover에게 증명을 요구한다.

5.Prover은 증명을 하기 위해 만들어준 증거를 제출한다.

6.Verifier 은 Prover의 증거를 확인하기 위해 신뢰할 수 있는 제3자에게 필요한 정보를 요구한다.

7. 신뢰할 수 있는 제3자는 Verifier에게 정보를 제공한다.

8. Verifier은 받은 정보를 활용하여 Prover의 증거를 검증한다.

​

비대화형 영지식 증명은 모두 이와 같은 방법을 사용하는 것이 아니다.

여러 방법 중 하나이며

가장 중요한 것은 대화형 영지식 증명은 확률에 의해 검증을 한다면

비 대화형 영지식 증명은 확률에 의존하지 않는다는 특징이 있다.

 

 

영지식에서의 동형 암호

동형 암호란 암호문에 대한 연산 결과가 평민의 연산 결과와 일치하는 암호화 방식을 말한다.

​

위의 이미지를 보면 mod4, mod7이라는 키를 사용해

평문 10,15를 암호문으로 만들고 이를 연산하여 다시 암호를 하는 것으로

평민의 연산 결과와 일치하는 것을 볼 수 있다.

​

이러한 성질은 영지식에서 사용이 된다.

평문을 숨기지만 결과가 일치하기 때문에 나의 평문이 참이라는 것을 증명할 수 있게 된다.

​

​

결론

---

​위에서 본 예시 대로 정보를 노출하지 않고 요구 사항을 만족시키는 것으로 증명하는 영지식 증명 방식은

많은 영역에서 사용할 수 있다.

​

만약 영지식 증명 방식으로 성인인지를 검사하게 된다면

성인 인지를 물어보고 true 혹은 false를 대답하게 되는 것으로 나의 나이를 노출하지 않고 증명하게 된다.