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

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

이 포스트에서 다루는 내용

비밀 공유: Shamir의 $(k, n)$ 임계 방식 — $k$ 명 이상이 협력하면 비밀 복원, $k-1$ 명 이하는 정보 없음
영지식 증명의 3대 성질: 완전성(Completeness), 건전성(Soundness), 영지식성(Zero Knowledge)
그래프 동형 ZKP: 대화형 프로토콜로 매핑 $\sigma$ 의 지식을 증명 — 사칭자 통과 확률 $1/2^k$
No Transfer: 시뮬레이션 논증 — V가 혼자 만든 기록과 실제 기록이 구별 불가능

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

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

Shamir의 (k, n) 임계 방식

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

구성:

신뢰 기관(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}$ 은 $\mathbb{Z}_p$ 에서 서로 독립적으로 균등하게 뽑는다.

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

p

가 만족해야 하는 조건

$p > n$ . 참여자에게 주는 평가점 $1, 2, \ldots, n$ 이 $\mathbb{Z}_p$ 에서 서로 다른 값이어야 한다. $p \le n$ 이면 두 참여자가 같은 점을 받아 지분이 겹친다.
평가점은 $0$ 이 아니어야 한다. $f(0)$ 이 비밀 자체이므로, 어떤 참여자에게도 $y = 0$ 을 주면 안 된다.
$x \in \mathbb{Z}_p$ . 비밀이 $p$ 보다 작아야 $a_0$ 에 담긴다. 큰 비밀은 $p$ 를 키우거나 조각으로 나눠 각각 공유한다.
계수는 독립 균등. 아래 안전성 논증이 쓰는 것이 이 조건이다. 계수에 편향이 있으면 $k-1$ 명이 $f(0)$ 의 분포를 좁힐 수 있다.

$a_{k-1}$ 이 $0$ 으로 뽑힐 수도 있으므로 차수는 정확히 $k-1$ 이 아니라 $k-1$ 이하다. 안전성에는 영향이 없다.

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

안전성: $(k-1)$ 명은 $(k-1)$ 개의 점만 가지고 있다. 여기에 $f(0) = c$ 라는 점을 하나 더 얹으면 $k$ 개가 되어 다항식이 유일하게 결정되므로, $\mathbb{Z}_p$ 의 각 $c$ 마다 그들의 지분과 들어맞는 다항식이 정확히 하나씩 있다. 계수가 독립 균등이므로 그 $p$ 개가 모두 같은 확률이고, 결국 $f(0)$ 의 사후 분포는 아무것도 모를 때의 균등 분포와 같다. 이것이 정보 이론적 안전성(information-theoretic security) 이다. 계산 능력과 무관하게 비밀을 알 수 없다는 뜻이다.

무한히 많은 후보가 남는 것이 아니라 정확히 $p$ 개가 남는다는 점에 유의하자. 유한체 위에서는 “가능한 값이 무한하다”가 아니라 “가능한 값이 전부 남는다”가 안전성의 내용이다.

수치 예시: (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차식을 결정할 수 없다. 두 점 $(1,1)$ , $(2,1)$ 에 $f(0) = c$ 를 더하면 $c$ 마다 다항식이 하나씩 정해지므로, $c = 0, 1, \ldots, 10$ 의 11가지가 모두 똑같이 가능하다.

Shamir 비밀 공유의 (3,5) 임계 방식. Z11 위에서 f(y) = 3y² + 2y + 7의 상수항이 비밀 7이고, 다섯 참여자가 f(1)부터 f(5)까지의 값을 지분으로 나눠 갖는다. 세 명이 모이면 2차식이 유일하게 정해져 f(0)이 복원되고, 두 명뿐이면 상수항 후보 11가지가 모두 같은 확률로 남는다

강조 색은 도식의 시각 보조이며, 본문 예시의 선택 점은 수식의 $P_i$ 표기를 따른다.

영지식 증명이란

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)$ 에 확인 가능
발견은 상대적으로 어렵다: 다항식 시간 알고리즘이 알려져 있지 않다
생성은 쉽다: $G_1$ 의 노드를 치환하면 동형 그래프 $G_2$ 를 즉시 만들 수 있다

n!

은 알려진 최선이 아니다

위 $O(n!\cdot(n+m))$ 은 나이브한 방법의 비용일 뿐, 이 문제의 난이도가 아니다. 2015년 László Babai가 준다항식 시간, 즉 $2^{O((\log n)^c)}$ 에 도는 알고리즘을 제시했다. 다항식보다는 크지만 지수보다는 훨씬 작다.

그래프 동형은 NP-완전이라고 알려져 있지 않고, 오히려 그렇지 않으리라 여겨진다. NP에도 coAM에도 속하는데, NP-완전이면 다항 계층이 붕괴한다는 결과가 있기 때문이다. 인수분해나 이산 로그처럼 “NP와 P 사이 어딘가”에 있다고 보는 대표적인 문제다.

이 글이 그래프 동형을 쓰는 이유는 난이도가 아니라 위 비대칭성의 모양이다. 프로토콜이 성립하는 데 필요한 것은 “검증은 쉽고 생성은 쉬우며 발견은 어렵다”는 구조이지, 그 어려움이 NP-완전급이라는 사실이 아니다.

그래프 동형 영지식 증명

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가 이를 검증한다.

그래프 동형 영지식 증명의 한 라운드. 증명자가 그래프를 무작위로 치환한 Gt를 보내면, 검증자가 동전을 던져 G1과 Gt 또는 G2와 Gt 중 어느 매핑을 볼지 묻고, 증명자가 요청된 매핑만 제시한다. 매핑을 모르면 두 질문 중 하나에만 답할 수 있어 통과 확률이 절반이다

왜 안전한가

건전성: $\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가 혼자 기록을 만드는 방법:

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

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

이 논증이 보인 것은 정직한 검증자에 대해서다

위 시뮬레이터는 질문을 먼저 정하고 거기에 맞는 $G_t'$ 를 만든다. 실제 프로토콜에서는 순서가 반대다. $G_t$ 가 먼저 나가고 질문이 뒤에 온다. 순서를 뒤집을 수 있었던 것은 V가 동전을 정직하게 던진다고 가정했기 때문이다. 그래서 여기까지 보인 것은 정직한 검증자에 대한 완전 영지식성(honest-verifier perfect zero knowledge) 이다.

악의적인 V는 $G_t$ 를 보고 나서 질문을 정할 수 있다. 예를 들어 $G_t$ 의 어떤 특징을 보고 항상 불리한 쪽을 고르는 V를 상상할 수 있다. 이런 V까지 포함하려면 시뮬레이터에 되감기(rewinding) 를 넣는다.

시뮬레이터가 질문 $b'$ 를 하나 추측하고, 거기에 맞는 $G_t'$ 를 만든다.
$G_t'$ 를 $V^*$ 에게 주고 $V^*$ 가 실제로 내는 질문 $b$ 를 본다.
$b = b'$ 이면 준비해 둔 응답을 기록하고 다음 라운드로 간다.
$b \neq b'$ 이면 $V^*$ 를 그 라운드 시작 시점으로 되감아 1번부터 다시 한다.

$G_t'$ 는 어느 쪽에서 만들었든 분포가 같으므로 $V^*$ 가 무엇을 보든 $b = b'$ 일 확률이 $1/2$ 이다. 따라서 한 라운드당 기대 시도 횟수가 $2$ 회이고, 시뮬레이터는 기대 다항식 시간에 끝난다. 되감기가 가능한 이유는 시뮬레이터가 $V^*$ 를 프로그램으로 들고 있어 상태를 되돌릴 수 있기 때문이다. 실제 P는 그렇게 할 수 없다.

시뮬레이션 논증. 실제 대화로 만들어진 기록과 검증자가 증명자 없이 혼자 만든 기록이 같은 확률 분포를 가지므로, 어떤 관찰자도 둘을 구별할 수 없다. 혼자 만들 수 있는 것이라면 대화에서 새로 얻은 정보가 아니다

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

쉽게 말하면

영지식성의 핵심은 "V가 P 없이도 똑같은 대화 기록을 혼자 만들 수 있다"는 것이다. 만약 V가 혼자서도 만들 수 있는 기록이라면, P와의 대화에서 새로운 정보를 얻은 것이 아니다. 마치 시험 답안지를 보여주지 않고도 "나는 답을 안다"고 증명하는 것과 같다.

라운드를 아무리 반복해도 매핑은 새지 않는다

라운드를 많이 돌리면 V가 결국 $\sigma$ 를 알아내지 않을까 싶어진다. 그렇지 않다. 매 라운드 V가 보는 것은 새로 뽑은 무작위 치환 하나이고, 그 값의 분포는 $\sigma$ 와 아무 관계가 없다. 시뮬레이션 논증이 말하는 것이 정확히 이것이다. V 혼자서도 같은 분포의 기록을 만들 수 있다면, 그 기록에는 $\sigma$ 의 정보가 애초에 담겨 있지 않다. 기록을 $n!$ 번 쌓아도 각 항목이 독립적인 무작위 치환일 뿐이라 쌓인다고 $\sigma$ 가 드러나지는 않는다.

다만 반복에도 조건이 있다.

순차 반복은 안전하다. 한 라운드를 끝내고 다음 라운드를 시작하는 방식이라면, 각 라운드의 시뮬레이터를 이어 붙여 전체 시뮬레이터를 만들 수 있다. 영지식성이 순차 합성에서 보존된다는 것은 일반 정리로 알려져 있다.
병렬 반복은 다르다. $k$ 개 라운드의 첫 메시지를 한꺼번에 보내고 질문도 한꺼번에 받는 방식에서는 위 되감기가 그대로 통하지 않는다. 한 라운드만 어긋나도 전체를 되감아야 하는데 그 확률이 $1 - 2^{-k}$ 라 시도 횟수가 폭발한다. 병렬 합성에서 영지식성이 보존된다는 보장은 일반적으로 없다.

그래서 이 프로토콜은 $k$ 번을 차례로 돌린다.

실용적 대안: RSA 기반 인증

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

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

먼저 흔한 오해 하나. “랜덤 메시지 $m$ 을 보내고 서명 $s = m^d$ 를 돌려받아 $s^e \equiv m$ 을 확인한다”는 절차는 인증이지 영지식 증명이 아니다. 두 가지가 어긋난다.

B는 프로토콜이 끝난 뒤 $m$ 에 대한 유효한 서명을 손에 쥔다. 이것은 대화 전에 없던 것이고, B가 혼자서는 만들 수 없다. 시뮬레이터가 존재할 수 없으니 영지식성의 정의가 성립하지 않는다.
게다가 이 형태(교과서 RSA)는 서명 자체가 안전하지 않다. 곱셈 성질 때문에 서명 둘을 곱하면 새 서명이 나온다.

지식을 증명하려면 시그마 프로토콜(Σ-protocol) 을 쓴다. 커밋·질문·응답 세 걸음으로 이루어지고, 지식 추출기와 시뮬레이터를 모두 갖춘 형태다.

Fiat–Shamir 식별 프로토콜: A가 $n = pq$ 를 공개하고, 비밀 $s$ ( $\gcd(s,n)=1$ )에 대해 $v = s^2 \bmod n$ 을 공개한다. 증명할 것은 “ $v$ 의 제곱근을 안다”이다.

커밋. A가 무작위 $r$ 을 골라 $t = r^2 \bmod n$ 을 보낸다.
질문. B가 $b \in \{0, 1\}$ 을 무작위로 보낸다.
응답. A가 $z = r \cdot s^b \bmod n$ 을 보낸다.
검증. B가 $z^2 \equiv t \cdot v^b \pmod{n}$ 을 확인한다.

세 성질이 모두 확인된다.

완전성. $z^2 = r^2 s^{2b} = t \cdot v^b$ 이므로 정직한 A는 항상 통과한다.
지식 추출. 같은 $t$ 에 대해 $b = 0$ 과 $b = 1$ 양쪽 응답 $z_0, z_1$ 을 얻으면 $z_1 z_0^{-1} = s$ 로 비밀이 그대로 나온다. 이것이 “안다”를 형식화하는 방식이다. 통과할 수 있는 자에게서 비밀을 뽑아낼 수 있으면, 그는 비밀을 아는 것이다. 따라서 모르는 자의 통과 확률은 라운드당 $1/2$ 이다.
시뮬레이터. 먼저 $b$ 를 정하고 $z$ 를 무작위로 고른 뒤 $t = z^2 v^{-b} \bmod n$ 으로 거꾸로 맞추면, 실제 기록과 같은 분포의 기록이 나온다. 비밀 없이 만들 수 있으므로 정직한 검증자에게는 아무것도 새지 않는다.

앞의 그래프 동형 프로토콜과 뼈대가 같다. 커밋을 먼저 던지고, 질문이 갈래를 나누고, 두 갈래 모두에 답할 수 있는 자만이 비밀을 아는 자다.

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

가림과 벗김이 모두 서명자 A의 모듈러스 $n_A$ 아래에서 일어나야 한다. B가 자기 키로 감싸고 A가 서명한 뒤 B가 자기 키로 푸는 방식은 성립하지 않는다. $m^{e_B d_B} \equiv m$ 은 $\bmod\ n_B$ 에서만 참인데 A의 서명은 $\bmod\ n_A$ 에서 이루어지므로, 두 모듈러스가 섞여 지수가 상쇄되지 않는다.

Chaum(1982)의 방식은 지수 대신 곱셈으로 가린다. A의 공개키를 $(n_A, e_A)$ , 비밀키를 $d_A$ 라 하자.

가림. B가 $\gcd(r, n_A) = 1$ 인 난수 $r$ 을 골라 $m' = m \cdot r^{e_A} \bmod n_A$ 를 A에게 보낸다.
서명. A가 $s' = (m')^{d_A} \bmod n_A$ 를 돌려준다. 지수 법칙으로

s' = m^{d_A} \cdot r^{e_A d_A} = m^{d_A} \cdot r \pmod{n_A}

벗김. B가 $s = s' \cdot r^{-1} \bmod n_A$ 를 계산하면 $s = m^{d_A}$ , 곧 $m$ 에 대한 A의 서명이다.

A가 본 것은 $m'$ 뿐이고, $r$ 이 균등 무작위이므로 $m'$ 도 $\mathbb{Z}_{n_A}^*$ 에서 균등하게 분포한다. 어떤 $m$ 에 대해서도 그것을 $m'$ 으로 만드는 $r$ 이 정확히 하나 있으므로, $m'$ 은 $m$ 에 대해 아무 정보도 주지 않는다.

$r$ 이 가역이어야 3번의 $r^{-1}$ 이 존재한다는 점, 그리고 앞 글에서 본 대로 교과서 RSA를 그대로 쓰면 안 되므로 실제로는 인코딩을 함께 써야 한다는 점이 조건이다. 이 방식은 전자 투표, 디지털 화폐 등 익명성이 요구되는 시스템에서 활용된다. 다만 A가 아무 값에나 서명해 주는 셈이므로, 일반 서명 요청과 은닉 서명 요청을 구별하는 장치를 따로 두어야 한다.

핵심 정리

Shamir의 비밀 공유는 차수 $k-1$ 이하 다항식의 보간법에 기반한다. $p > n$ 과 서로 다른 $0$ 아닌 평가점, 독립 균등 계수가 전제다. $k$ 명이면 비밀 복원, $(k-1)$ 명 이하에게는 $\mathbb{Z}_p$ 의 $p$ 개 후보가 모두 같은 확률로 남아 정보 이론적으로 안전하다.
영지식 증명은 세 성질을 만족한다: 완전성(알면 통과), 건전성(모르면 불통과), 영지식성(정보 전달 없음).
그래프 동형 ZKP에서 사칭자의 통과 확률은 $1/2^k$ 이다. 매 라운드 새로운 $G_t$ 를 생성하므로 이전 라운드의 정보가 누적되지 않는다.
시뮬레이션 논증: V가 P 없이도 동일한 분포의 기록을 만들 수 있으므로, P→V 정보 전달은 없다. 질문을 먼저 정하는 시뮬레이터는 정직한 검증자에 대한 논증이고, 악의적 검증자까지 덮으려면 되감기가 필요하다. 그래서 라운드는 병렬이 아니라 순차로 반복한다.
서명을 돌려주는 것은 인증이지 영지식 증명이 아니다. B가 대화 전에 없던 서명을 얻으므로 시뮬레이터가 존재할 수 없다. 지식 증명에는 추출기와 시뮬레이터를 갖춘 시그마 프로토콜(예: Fiat–Shamir 식별)을 쓴다.
은닉 서명은 서명자 A의 모듈러스 아래에서 곱셈으로 가린다. $m' = m r^{e_A}$ 에 서명받아 $r^{-1}$ 로 벗기면 $m^{d_A}$ 가 나온다. B의 키로 감싸는 방식은 두 모듈러스가 섞여 성립하지 않는다.

다음 포스트

Before Physics — 논리, 불완전성, 그리고 과학의 기반 — 양자역학과 상대성 이론에 들어가기 전, 논리와 물리학의 차이, 괴델의 불완전성 정리, 오컴의 면도날, 과학적 원리까지 다룬다.