증명 없는 증명

Zero Knowledge Proof / 영지식증명

‘미션 임파서블’ 시리즈를 아는가? ‘미션 임파서블’은 톰 크루즈가 주연을 맡고 있는 첩보 영화로 각 영화마다 한시도 눈을 땔 수 없는 화려한 액션과 우리의 상상력을 자극하는 첨단 기술들을 보여주며 엄청난 인기를 얻고 있다. 이러한 ‘미션 임파서블’ 시리즈 말고도 ‘007’ 시리즈, ‘킹스맨’과 같은 수많은 첩보 영화가 나오고 있으며 이 영화들도 많은 인기를 끌었다. 그렇다면 앞서 말한 영화들의 스파이들의 공통점은 무엇일까? 다른 말로 스파이에게 중요한 것은 무엇일까? 이런 질문을 받으면 ‘적지에서 임무를 수행하고 빠져 나올 수 있을 만큼 전투를 잘하며, 온갖 첨단 장비를 지니고 있어야 한다.’ 라고 생각할 것이다. 하지만 현실에서는 영화와는 달리 이런 전투 능력이나 기술력보다는 들키지 않고 임무를 수행하는 것이 최우선이 되어야만 할 것이다. 그렇다면 우선 스파이와 스파이 사이의 신원 확인이나 스파이와 본국 사이의 신원 확인에서 자신의 정체를 들킬 위험을 최소화 시켜야 할 것이다. 이러한 위험을 최소화 시키기 위해서는 신원 확인 과정에서 자신의 정보가 최소한으로 드러나는 것이 중요하다. 하지만 상식적으로 생각해보면 자신의 정보를 드러내지 않으면서 자신의 신원을 증명한다는 것은 불가능해 보인다. 그럼 지금부터 불가능처럼 보이는 일을 현실로 만들어주는 암호 기법 중 하나인 영지식증명에 대해서 소개하고자 한다.

우선 이 글을 읽을 대부분의 사람들에게 이름조차 생소할 영지식증명의 개념부터 설명하고자 한다. 영지식증명은 영어로 Zero-Knowledge Proof로 어떤 명제의 증명을 prover가 가지고 있다는 것을 proof에 대한 어떠한 정보도 verifier에게 넘기지 않고 verifier에게 확인시키는 암호 기법을 의미한다. 이해를 돕기 위해 예시를 들자면 Peggy라는 사람이 어떤 소고기가 미국산인지 한우인지 구별할 수 있는 기술을 개발했다고 하자. Peggy는 Victor에게 자신의 기술을 팔기 위해서 Victor에게 자신의 기술이 정확하다는 것을 보이고 싶지만 기술 그 자체를 알려주고 싶지 않아 한다. 이러한 상황을 해결하기 위해서 Victor가 미국산 소고기와 한우중 하나를 무작위로 가져오고 Peggy가 자신의 기술을 사용해서 그 고기가 한우인지 미국산인지 판단하여 Victor에게 말해준다. 이 Test를 시행하여 Peggy가 맞춘다면 Victor는 Peggy의 기술을 믿을 수 있을 것이다.

하지만 위의 예시를 읽다가 2가지 의문점이 생겼을 수도 있다. 우선 첫 번째는 과연 Peggy가 기술을 실제로 개발한 것이 아니라 단지 개발했다고 거짓말을 하고 있는 경우는 위의 test로 Peggy가 거짓말을 하고 있다고 판별할 수 있을까? 이며, 두 번째는 Victor가 테스트 과정에서 Peggy의 기술에 대한 정보를 얻을 수도 있지 않을까? 라는 의문일 것이다. 첫 번째 경우에서의 prover를 cheating하는 prover이므로 fake prover라 하고 두 번째 경우의 verifier를 cheating하는 verifier이므로 fake verifier라고 하자.

Fake prover의 cheating을 막기 위해서 어떻게 하면 될까? Fake prover의 목적은 자신이 기술을 가지고 있지 않지만 자신이 기술을 가지고 있는 것처럼 verifier에게 속이는 것이다. 그럼 fake prover와 prover를 구별해 낼 수 있는 둘의 차이를 생각해보자. Prover는 Victor가 준 어떤 소고기에 대해서 그 소고기의 원산지를 맞출 확률이 100%이지만 fake prover는 찍어서 맞출 확률이 50%라는 차이점이 있다. 이러한 차이점을 이용하여 Victor가 시행하는 test의 횟수를 늘려보자. 만약 Victor가 test를 시행하는 횟수를 n이라고 했을 때, fake prover가 모든 n번의 test를 찍어서 통과할 확률은 (0.5)$^n$이 되어 매우 작아진다는 것을 확인할 수 있다. 즉, 충분히 많은 test를 시행한다면 fake prover의 cheating이 성공할 확률을 0으로 수렴시킬 수 있어 cheating을 막을 수 있다.

그렇다면 fake verifier의 cheating은 어떻게 막을 수 있을까? Fake verifier의 목적은 자신이 서로가 합의를 한 test를 여러 번 시행하여 Peggy의 기술에 대한 정보를 알아내려는 것으로, fake verifier는 test의 결과를 분석하여 자신이 원하는 바를 이루어 내는 것을 막아야 한다. 사실 위의 예시의 경우에는 fake verifier의 cheating을 막기 쉽다. Prover인 Peggy가 fake verifier에게 소고기를 받아 자신의 기술을 써서 판별한 다음, 사용한 소고기는 버리는 식으로 (소고기 아깝다…..) fake verifier에게 fake verifier가 원래 알고 있었던 정보인 소고기의 원산지에 대한 정보만 넘겨줄 수 있다. 즉, fake verifier가 새로이 알게 되는 정보가 없으므로 Peggy의 기술에 대한 정보를 알 수 없다.

위의 예시에서 볼 수 있듯이 영지식증명은 다음의 3가지의 조건을 가지고 있으며, 다음의 조건들은 각각 completeness, soundness, zero-knowledge라고 불린다.

• Prover가 proof를 가지고 있을 경우에 verifier에게 그것을 확신시킬 수 있어야 한다.
• Fake prover가 proof를 가지고 있다고 거짓말을 할 경우 verifier는 proof를 가지고 있지 않다는 것을 알 수 있어야 한다.
• Fake verifier가 proof에 대해 추가로 알아낼 수 있는 정보는 없어야 한다.

지금까지 영지식증명이 무엇인지 알아보았고, 영지식증명이 사용될 수 있는 간단한 예시도 살펴보았다. 하지만 과연 위와 같은 실생활 속의 예시에서 잘 성립이 된다고 해서 수학적 명제들이나 과학적 명제들에 대해서도 영지식증명이 잘 활용될 수 있을까? 라는 의문이 들 것이다. 수학적 명제들의 경우 전제와 결론 사이의 과정을 확인해야지만 그 명제의 증명을 알고 있다는 것을 보일 수 있으며, 과학적 명제의 경우에도 실험 결과를 제시하거나 증명을 제시해야 하기 때문이다. 그래서 앞에서 든 간단한 예시 이외에도 수학적 명제에 영지식증명을 활용하는 예시를 소개하고자 한다.

수학적 명제의 경우에는 유명한 문제인 그래프 3색 문제, Graph 3-colorability (앞으로는 G3C라고 표기하자)의 영지식증명을 소개하고자 한다. 우선 G3C 문제는 다음과 같이 정의된다.

• $f_{G3C}:G=(V,E) rightarrow {True, False}$
  where $f_{G3C}(G=(V,E))=True$ if $^{exists} phi:Vrightarrow[3]$, $^{forall}(u,v)in E$, $phi(u)nephi(v)$

쉽게 풀어 쓰자면 G3C는 어떤 그래프가 있을 때, 3개의 색만을 사용하여 그래프의 모든 인접한 node들을 서로 다른 색으로 칠할 수 있는지를 묻는 문제이다.

우선 prover와 verifier에게 동시에 주어진 정보가 $G=(V,E)$이고, prover에게 따로 주어진 정보인 valid 3-coloring인 $phi : rightarrow [3]$ of G. 이제 verifier가 다음 단계를 $|V||E|$번 반복하자.

1. Prover는 random permutation $pi in S_{3}$을 고르고 verifier에게 $(C_{v}(pi (phi (v))))_{vin V}$를 보낸다. (각각의 $C_{v}$ 는 각 node에 해당하는 commitment라고 불리는 암호이다.)
2. Verifier는 prover에게 무작위 edge $(u,v) in E$를 보낸다.
3. Prover는 $C_{u}(cdot)$과 $C_{v}(cdot)$를 열 수 있는 key를 보낸다.
4. Verifier는 암호를 풀어 $a_{u} = pi(phi(u))$와 $a_{v} = pi(phi(v))$를 구한다.
5. Verifier는 $a_{u} ne a_{v}$인지 확인한다.

만약 $|V||E|$번의 test동안 $a{u} ne a{v}$인 것을 확인한다면 verifier는 prover가 증명을 알고 있다고 믿을 수 있다.

위에서 서술한 과정이 과연 영지식증명의 3가지 조건을 만족할까? 우선 completeness부터 살펴보자. Completeness가 성립하기 위해서는 만약 prover가 valid 3-coloring을 알고 있다면 그것을 verifier에게 확신시킬 수 있어야 한다. 즉, 어떠한 edge $(u,v) in E$를 골라도, $pi(phi(u)) ne pi(phi(v))$이어야 한다. 그런데 Prover가 가지고 있는 $phi$는 valid 3-coloring이므로 $phi(u)nephi(v)$이므로 앞의 조건을 만족시켜줄 수 있다.

그렇다면 soundness를 만족할까? Soundness를 만족하기 위해서는 fake prover가 모든 test를 찍어서 통과할 확률을 충분히 작게 만들어야 한다. 그럼 우선 fake prover가 한 번의 test를 찍어서 통과할 확률은 얼마일까? Commitment scheme의 성질에 의하여 fake 3-coloring $phi^{*}$을 가지고 있는 fake prover의 cheating이 걸릴 확률이 $frac{1}{|E|}$이상이다. 그러므로 fake prover가 $|V||E|$번의 test를 모두 통과할 확률은 $(1-frac{1}{|E|})^{|V||E|} leq e^{-|V|}$보다 작고, $|V|$의 크기에 따라 확률이 충분히 작아질 수 있다. 즉, fake prover의 cheating을 막는 soundness를 만족한다.

마지막으로 Zero-knowledeness를 만족한다는 것을 보이기 전에 zero-knowledgeness의 비교적 엄밀한 정의를 설명하고자 한다. 모든 fake verifier에 대하여 어떤 TM(turing machine)이 존재하여 ${langle P, V^{} rangle (x)}_{x in L}$과 ${M^{}(x)}_{xin L} $가 computationally indistinguishable 하다면 computational zero-knowledge라고 한다. 이걸 좀 더 쉽게 설명하자면 어떤 simulator M이 있어서 fake verifier가 prover와 주고 받는 모든 내용을 simulate할 수 있다는 것이다. 즉, proof를 모르고 있는 어떤 simulator가 대화를 완벽히 재현할 수 있으므로 fake verifier가 영지식증명 과정에서 proof에 대한 아무런 정보도 얻을 수가 없다는 것이다.

다시 G3C문제로 돌아와서 위의 과정이 (computational) zero-knowledge를 만족한다는 것을 보이자. 어떤 fake verifier $V^{*}$에 대하여 다음을 과정으로 simulate한다면 fake verifier와 prover의 영지식증명을 simulate할 수 있다는 것을 알 수 있다.

1. 무작위로 $(u’,v’)in E$를 고른다.
2. 무작위로 $a’_{u} ne a’_{v}$인 $a’_{u}, a’_{v} in [3]$을 고른다.
3. $^{forall} w in Vsetminus{u’,v’}$에 대하여 $a’_{w}$를 1로 설정한다.
4. $(u,v)$를 $V^{*}$으로부터의 대답으로 설정한다.
5. 만약 $(u,v) = (u’, v’)$이라면 두 색을 공개한다.
6. 다르다면 위의 과정을 처음부터 다시 시행한다. 단 총 횟수가 $|V||E|$를 넘지 않게 한다.
7. $|V||E|$번의 반복 후에 simulator 과정에서 실패한 경우가 있다면 F를 return한다.

예시로 사용된 Graph 3-colorability처럼 수많은 수학적 명제는 이와 같은 방식으로 영지식증명을 사용할 수 있다.

사실 영지식증명의 엄밀한 정의는 zero-knowledge의 조건을 설명할 때 사용한 probability를 이용하여 정의한다. 확률공간을 사용하여 정의된 영지식증명은 매우 어렵지만 관심이 있다면 밑의 첨부파일을 참고하길 바란다.

첨부파일 ∣ lec12_zkp.pdf ∣ prob_basic.pdf
위 파일의 모든 저작권은 한국과학영재학교 윤상현 선생님께 있습니다.
위 파일들은 허가 없이 변형, 복제 및 배포 등의 사용을 할 수 없습니다.