Zero Knowledge Proof — 전달 없이 입증하기

비밀번호를 알고 있음을 증명하려면 비밀번호를 입력해야 한다. 하지만 상대방에게 비밀 자체를 건네지 않고도 “나는 이것을 알고 있다”고 증명할 수 있다면? 영지식 증명(Zero Knowledge Proof)은 정보의 전달 없이 지식의 소유를 입증하는 수학적 프로토콜이다.

비밀 공유 (Secret Sharing)

영지식 증명에 앞서, “비밀을 안전하게 분산시키는” 문제를 먼저 살펴보자.

상황: $n$명이 비밀 $x$를 공유한다. $k$명 이상이 협력하면 $x$를 복원할 수 있지만, $(k-1)$명 이하는 $x$에 대한 어떤 정보도 얻을 수 없어야 한다.

Shamir의 (k, n) 임계 방식

Adi Shamir(1979)의 해법은 다항식 보간법(Lagrange Interpolation) 에 기반한다.

구성:

1. 신뢰 기관(Trusted Party)이 소수 $p$ 위에서 $(k-1)$차 다항식을 만든다

$$f(y) = a_{k-1}y^{k-1} + \cdots + a_1 y + a_0 \pmod{p}$$

여기서 $a_0 = x$(비밀), 나머지 계수 $a_1, \ldots, a_{k-1}$은 무작위로 선택한다.

2. $i$번째 참여자에게 지분(share) $f(i)$를 전달한다.

복원: $(k-1)$차 다항식은 $k$개의 점으로 유일하게 결정된다. $k$명이 자신의 지분을 모으면 라그랑주 보간법으로 $f$를 복원하고, $f(0) = a_0 = x$를 얻는다.

안전성: $(k-1)$명은 $(k-1)$개의 점만 가지고 있다. $(k-1)$차 다항식의 마지막 점이 결정되지 않았으므로, $f(0)$은 $\mathbb{Z}_p$의 어떤 값이든 될 수 있다. 이것은 정보 이론적 안전성(information-theoretic security) 이다 — 계산 능력과 무관하게 비밀을 알 수 없다.

수치 예시: (3, 5) 방식

$p = 11$, 비밀 $x = 7$, $k = 3$, $n = 5$로 설정한다.

다항식: $f(y) = 3y^2 + 2y + 7 \pmod{11}$

지분 배포:

참여자	$f(i)$	계산
$P_1$	$f(1) = 3 + 2 + 7 = 12 \equiv 1$	$\bmod 11$
$P_2$	$f(2) = 12 + 4 + 7 = 23 \equiv 1$	$\bmod 11$
$P_3$	$f(3) = 27 + 6 + 7 = 40 \equiv 7$	$\bmod 11$
$P_4$	$f(4) = 48 + 8 + 7 = 63 \equiv 8$	$\bmod 11$
$P_5$	$f(5) = 75 + 10 + 7 = 92 \equiv 4$	$\bmod 11$

$P_1$, $P_3$, $P_4$가 협력하면 점 $(1, 1)$, $(3, 7)$, $(4, 8)$로 2차 다항식을 확정하고 $f(0) = 7$을 복원한다. 반면 $P_1$, $P_2$ 두 명만으로는 2차식을 결정할 수 없으므로 $f(0)$이 $0$부터 $10$까지 어떤 값이든 가능하다.

영지식 증명이란

P(증명자) 가 V(검증자) 에게 “나는 비밀 $X$를 알고 있다”고 증명하되, $X$에 대한 어떤 정보도 V에게 전달하지 않는 프로토콜이다.

가장 직관적인 방법은 $X$를 직접 보여주는 것이다. 비밀번호 인증이 이 방식이다 — 비밀번호를 서버에 전송해 “본인임”을 증명한다. 하지만 이 방법은 $X$ 자체가 노출된다. 서버가 악의적이거나(피싱 사이트), 통신이 도청되면 비밀이 유출된다.

영지식 증명은 이 문제를 해결한다. 프로토콜이 만족해야 할 세 가지 성질이 있다:

완전성 (Completeness): P가 실제로 $X$를 알고 있으면, V는 항상 납득한다.

건전성 (Soundness): P가 $X$를 모르면, V를 속일 확률이 무시할 수 있을 만큼 작다.

영지식성 (Zero Knowledge): V는 프로토콜을 통해 $X$에 대한 어떤 정보도 얻지 못한다. “$X$를 안다”는 사실만 알게 된다.

그래프 동형 문제 (Graph Isomorphism)

영지식 증명의 대표적인 예시는 그래프 동형(Graph Isomorphism) 문제다.

두 그래프 $G_1$, $G_2$가 주어졌을 때, 노드 이름만 다르고 구조가 같은지(동형인지) 판별하는 문제다. $n$개의 노드가 있으면 가능한 치환이 $n!$개이므로, 나이브하게는 $O(n! \cdot (n + m))$ 시간이 필요하다.

핵심은 비대칭성에 있다:

• 검증은 쉽다: 매핑 $\sigma$가 주어지면 $O(n + m)$에 확인 가능
• 발견은 어렵다: $\sigma$를 찾는 효율적 알고리즘이 알려져 있지 않다
• 생성은 쉽다: $G_1$의 노드를 치환하면 동형 그래프 $G_2$를 즉시 만들 수 있다

이 비대칭성이 영지식 증명을 가능하게 한다.

그래프 동형 영지식 증명

P는 $G_1 \cong G_2$의 매핑 $\sigma$를 알고 있음을 V에게 증명하되, $\sigma$ 자체는 전달하지 않는다.

한 라운드의 진행:

Step 1 (P → V): P가 $G_1$(또는 $G_2$)의 노드를 무작위로 치환해 새로운 그래프 $G_t$를 만들고 V에게 보낸다. P는 $\sigma$를 알고 있으므로 $G_1 \leftrightarrow G_t$와 $G_2 \leftrightarrow G_t$ 매핑을 모두 계산할 수 있다.

Step 2 (V → P): V가 동전을 던져 ”$G_1 \leftrightarrow G_t$ 매핑을 보여라” 또는 ”$G_2 \leftrightarrow G_t$ 매핑을 보여라” 중 하나를 랜덤으로 질문한다.

Step 3 (P → V): P가 요청된 매핑을 제시하고, V가 이를 검증한다.

왜 안전한가

건전성: $\sigma$를 모르는 사칭자가 $G_1$에서 $G_t$를 만들었다면, $G_1 \leftrightarrow G_t$ 매핑은 답할 수 있지만 $G_2 \leftrightarrow G_t$ 매핑은 답할 수 없다($\sigma$를 모르므로). 반대로 $G_2$에서 만들었다면 $G_2$ 쪽만 답할 수 있다. 어느 쪽이든 V의 질문을 통과할 확률은 $1/2$이다.

$k$ 라운드를 반복하면 사칭자의 통과 확률은

$$\left(\frac{1}{2}\right)^k$$

$k = 30$이면 약 $10^{-9}$로, 실질적으로 사칭이 불가능하다.

완전성: $\sigma$를 아는 P는 어떤 질문이든 항상 올바른 매핑을 제시할 수 있다.

No Transfer — 영지식성의 증명

가장 미묘한 부분이다. V가 프로토콜을 통해 $\sigma$에 대한 정보를 정말 얻지 못하는가?

시뮬레이션 논증

핵심 아이디어: V가 P 없이도 동일한 확률 분포의 기록(transcript)을 생성할 수 있다면, P로부터 V에게 정보가 전달된 것이 아니다.

V가 혼자 기록을 만드는 방법:

1. V가 먼저 질문을 결정한다: ”$G_1 \leftrightarrow G_t$ 매핑을 물어보겠다”
2. $G_1$을 무작위로 치환해 $G_t'$를 생성한다
3. $G_1 \leftrightarrow G_t'$ 매핑을 응답으로 기록한다

이 과정을 $k$번 반복하면 기록 $T'$가 만들어진다. 실제 대화 기록 $T$와 시뮬레이션 기록 $T'$는 확률 분포가 동일하다 — 둘 다 랜덤 치환 그래프, 랜덤 질문, 올바른 매핑으로 구성되며, 어떤 관찰자도 $T$와 $T'$를 구별할 수 없다.

따라서 P와의 대화에서 V가 얻는 정보는, V가 혼자서도 만들 수 있는 정보와 같다. P에서 V로의 정보 전달(transfer)은 없다.

주의: V가 매핑을 알아내는 경우

$n$개 노드의 그래프에서 가능한 치환은 $n!$개다. 만약 $(n! - 1)$번의 라운드를 진행해 모든 치환을 다 본다면, V는 $G_1$과 $G_2$ 사이의 매핑을 유추할 수 있다. 하지만 이것은 V가 계산을 통해 스스로 알아낸 것이지, P가 전달한 것이 아니다. 영지식 증명에서 “전달 없음”은 “V가 절대 모른다”가 아니라 “P로부터 추가 정보가 흘러가지 않는다”는 의미다.

실용적 대안: RSA 기반 인증

그래프 동형 ZKP는 이론적으로 우아하지만, 라운드 수가 많고 그래프 크기에 따라 통신량이 급증해 실용적이지 않다.

현실에서는 RSA의 수학적 구조를 활용한 인증이 더 널리 쓰인다.

RSA 기반 지식 증명:

1. A는 공개키 $(n, e)$를 공개하고 비밀키 $d$를 보유
2. B가 랜덤 메시지 $m$을 A에게 보냄
3. A가 서명 $s = m^d \bmod n$을 계산해 반환
4. B가 $s^e \equiv m \pmod{n}$을 확인

A가 $d$를 알지 못하면 유효한 서명을 만들 수 없으므로, 서명 제시가 곧 $d$의 지식 증명이 된다. 다만, 이것이 엄밀한 영지식 증명인지에 대한 형식적 보장은 별도의 분석이 필요하다.

은닉 서명 (Blind Signature)

RSA 인증의 확장으로, 서명자가 내용을 보지 않고 서명하는 프로토콜이 있다.

1. B가 메시지 $m$을 자신의 키 $e_B$로 암호화: $m^{e_B}$
2. A가 암호문에 서명: $(m^{e_B})^{d_A}$
3. B가 복호화: $((m^{e_B})^{d_A})^{d_B} = m^{d_A}$

B는 $m$에 대한 A의 서명 $m^{d_A}$를 얻었지만, A는 $m$의 내용을 알지 못한다. 이 방식은 전자 투표, 디지털 화폐 등 익명성이 요구되는 시스템에서 활용된다. 단, 일반 RSA 메시지가 은닉 서명 요청으로 위장될 수 있으므로, 실무에서는 메시지에 특정 패턴을 삽입해 구별한다.