[암호학] 23. Zero Knowledge Proof

우리는 암호를 왜 사용할까? 어떠한 정보에 도달하기 위해 내가 그 정보에 도달할 수 있는 유효한 사람임을 증명하기 위해 사용할 것이다. 예를 들어 웹사이트에서 나의 정보를 얻기 위해 나라는 것을 증명하기 위해 로그인을 하는 행위가 있을 것이다. 굉장히 심플한 방법이지만 보통 로그인을 할 때 패스워드를 서버에 보내서 서버에 있는 패스워드와 일치하는지 확인하는 방법을 사용하기 때문에 서버에 패스워드를 보내는 행위 자체가 찝찝할 수 있다.

 

Zero Knowledge Proof

어떤 문제를 해결하려는 사람 $P$(Prover)와 $P$가 제출한 데이터가 유효한지 검증하는 $V$(Verifier)가 있다고 하자. $P$는 $V$에게 어떤 데이터 $X$를 알고있다는 사실을 알려주고 싶다. 여기에서 $X$에 대한 정보가 오가지 않으면서 $P$가 $X$를 알고있다는 것을 $V$가 납득할 수 있도록 증명하는 과정을 Zero Knowledge Proof라고 한다.

 

속임수

$P$와 $V$는 서로를 속일 수 있다. 

$X$를 모르는 $P$가 $X$를 아는 것처럼 속일 수 있다. 로그인 예제에서 우연히 아무 패스워드나 입력했는데 낮은 확률이지만 성공할 수 있다. 여기에서 $P$는 접근해서는 안되는 정보에 접근할 수 있기 때문에 문제가 생긴다. 이것이 $P$가 $V$를 속이는 경우이다.

$V$는 $P$가 $X$를 알고 있다는 것을 증명하는 과정에서 데이터를 조금씩 수집해 $X$에 대한 정보를 알아내는 것을 $V$가 $P$를 속이는 경우이다. $V$는 $X$를 알아내면 $P$인척 할 수 있기 때문에 문제가 생긴다.

 

다시말해 목표는 $P$는 $V$에게 $X$를 안다는 사실을 알려주고 싶은데 다음 조건을 만족해야 한다.

• $V$는 $P$가 아는 척을 할 때 넘어가면 안된다.
• $V$는 $X$에 대해 알아내면 안된다.
• $X$는 전달되면 안된다.

과정

$V$는 $P$에게 어떤 문제를 낸다. 그 문제의 답은 $X$이고 $P$가 해당 문제를 해결해서 $X$를 알고있다는 것을 $V$에게 보이면 된다. 여기서 $V$도 그 문제를 해결하는 법을 모르고 $X$도 뭔지 모른다. 단지 문제만 낼 뿐이다. 그리고 정답을 아는 $P$외의 사람($V$를 포함하여)이 해결하기 힘들도록 $NP$인 문제를 출제한다.

 

Graph Isomorphism

$V$가 문제로 사용할 수 있는 예시인 Graph Isomorphism을 사용해보자. $G_1 = (V_1, E_1), G_2=(V_2, E_2)$가 존재하여 $V_1$과 $V_2$에 어떤 mapping이 존재한다면 $G_1$과 $G_2$는 isomorphic하다고 한다.

G1, G2

위 두 그래프는 달라보이지만 $0 \rightarrow 1, 1\rightarrow 2, 2 \rightarrow 3, 3 \rightarrow 4, 4 \rightarrow 0$으로 mapping하면 같은 그래프가 된다는 것을 알 수 있다.

그래프 동형 문제의 특징은 다음과 같다.

• 어떤 그래프가 주어졌을 때 동형인 그래프를 만드는 것은 쉽다.
• 두 그래프가 동형인지 판단하기 위한 mapping을 구하는 것은 어렵다.
• mapping이 주어진다면 동형인지 판단하는 것은 쉽다.

동형인 그래프를 만드는 것은 단지 현재 노드 집합의 아무 permutation을 하나 구해서 mapping시키면 만들 수 있으므로 매우 쉽다. mapping을 구하는 것은 어렵기 때문에 $P$가 두 그래프의 mapping을 알고 있다면 문제를 해결했다고 보면 된다. 여기에서 $G_1 \leftrightarrow G_2$간의 mapping이 $X$가 된다. 물론 mapping을 직접 제공하면 안되기 때문에 다음 과정을 거친다고 하자.

 

정보 전달 과정

$G_1 \leftrightarrow G_2$의 mapping을 알고 있는 $P$가 $G_1$과 동형인 그래프 $G_{temp}$를 만든다. ($G_2$로부터 $G_{temp}$를 만들어도 된다.) 여기에서 $P$는 $G_1 \leftrightarrow G_{temp}, G_1 \leftrightarrow G_2, G_{temp} \leftrightarrow G_{2}$ 모두의 mapping을 알 수 있다. (잘 생각해보면 $G_1\leftrightarrow G_2$의 mapping을 알고있을 때 $G_2 \leftrightarrow G_{temp}$의 mapping을 아는 것도 쉽다.)

$P$는 만든 $G_{temp}$를 $V$에게 전달한다.

여기에서 $V$는 $G_{temp}$를 받고 두 가지 선택지가 생긴다.

1. $P$에게 $G_1 \leftrightarrow G_{temp}$의 mapping을 묻는다.
2. $P$에게 $G_2 \leftrightarrow G_{temp}$의 mapping을 묻는다.

$G_1 \leftrightarrow G_2$의 mapping을 아는 $P$라면 두 질문 중 어떤 것이 들어오더라도 정확히 답할 수 있을 것이다.

$G_1 \leftrightarrow G_2$의 mapping을 모르는 $P$라면 1번 질문이 들어오면 정확히 답할 수 있지만 2번 질문이 들어오면 정확히 답할 수 없을 것이다.

1. $P$가 $G_1$에서 $G_{temp}$를 만들었고 $V$는 $G_1 \leftrightarrow G_{temp}$의 mapping을 묻는다.
2. $P$가 $G_1$에서 $G_{temp}$를 만들었고 $V$는 $G_2 \leftrightarrow G_{temp}$의 mapping을 묻는다.
3. $P$가 $G_2$에서 $G_{temp}$를 만들었고 $V$는 $G_1 \leftrightarrow G_{temp}$의 mapping을 묻는다.
4. $P$가 $G_2$에서 $G_{temp}$를 만들었고 $V$는 $G_2 \leftrightarrow G_{temp}$의 mapping을 묻는다.

$X$를 아는 $P$는 모든 문제를 해결할 수 있지만 $X$를 모르는 $P$는 1, 4번 케이스만 해결할 수 있다. 따라서 이 과정을 한 번 진행하면 $V$는 $\frac{1}{2}$확률로 $P$가 $X$를 아는지 확인할 수 있다. 이 과정을 $k$번 반복하면 $1-\frac{1}{2^k}$의 확률로 $P$가 아는지 검증할 수 있게 된다. 이 과정에서 $G_1 \leftrightarrow G_2$에 대한 mapping정보는 전달되지 않았기 때문에 $V$는 이 mapping을 여전히 모른다. 이 $k$가 너무 커지게 된다면 확실한 검증이 가능하겠지만 검증 과정이 길어지게 돼서 UX관점에서 사용자가 서비스를 사용하지 않을 수 있다. 

 

여기에서 $P$는 주의할 것이 있다. $G_{temp, i}$를 $i$번째 전달 과정에서 만든 $G_{temp}$라고 하자. 만약 다음 과정에서 $G_{temp, i+1} = G_{temp, i}$로 만들게 된다면 안된다. $V$가 $i$번째 과정에서 $G_{temp, i} \leftrightarrow G_1$의 mapping을 물어보고 $G_{temp, i+1} \leftrightarrow G_2$의 mapping을 물어보면 $V$가 $G_1 \leftrightarrow G_2$에 대한 mapping, 즉 $X$를 알게되는 것이기 때문이다. $P$는 이전에 만든 $G_{temp}$를 다음 과정에서 제공하면 안된다. (유사해도 안된다.)

 

Why zero knowledge?

사실 저 위의 과정을 정말 많이 하면 $V$는 $X$를 알아낼 수 있다. $G_1$의 노드 개수가 $N$개라고 하자. $P$는 $V$를 permutation하여 동형인 $G_{temp}$를 만들 것이기 때문에 만들 수 있는 동형 그래프의 개수는 $N!$개가 된다. 그렇다면 $V$가 검증할 때 위 과정을 $N! + 1$번을 하게 된다면? 비둘기집 원리에 의해 적어도 동일한 $G_{temp}$가 한 번 이상 나오게 되고 $V$는 $X$를 알게 된다. 그래서 검증을 진행할 때마다 $V$는 $X$를 알아낼 수 있는 아주 적은 양의 정보가 전달된다. 하지만 여전히 $X$에 대한 사실은 전달되지 않는다.

 

그렇다면 $P$가 $G_{temp}$를 만들지 않고 $V$ 혼자서 위 과정을 진행하여 $X$를 알아낼 수 있는 것 아닌가? 이것도 맞다. $V$가 $N!$번 혼자 $G_{temp}$를 만들어서 $X$를 알아낼 수도 있다. 즉 실제 $P$가 없어도 가능한 과정이다. 이 말은 $P$와 $V$사이에 어떠한 정보가 전달되지 않았다는 의미이기 때문에 Zero Knowledge Proof가 된다.