[암호학] 7. 영지식 증명 (1)

Soowon Jeong·2022년 1월 24일

암호학

목록 보기

8/9

앞서 살펴봤던 은닉 전자서명(Blind Signature)은 보통의 디지털 서명과 달리 내용을 공개하지 않고 서명을 얻을 수 있었습니다. 송신자와 서명자, 수신자 모두 구분되어 있는 경우에 서명자가 데이터를 모르는 상태로 유효한 서명을 할 수 있었는데, 이렇게 어떠한 정보를 모르지만 유효성을 보장받을 수 있다는 점이 영지식 증명의 조건 중 하나인 영지식성(Zero-knowledgeness)을 가지고 있다고 설명했습니다. 이 글에서는 영지식성을 포함한 영지식 증명의 조건과 이론적 기반, 영지식 증명의 기초적 구현에 대해 설명하겠습니다.

NP 증명 시스템

증명 체계, 증명 시스템에서 중심이 되는 개념은 결정 문제(decision problem)입니다. 결정 문제란 예/아니오 중 하나로 답이 존재하는 질문을 말합니다. 예를 들어 "두 숫자 $x$ 와 $y$ 가 있을 때, $x$ 는 $y$ 로 나누어떨어지는가?"라는 질문은 $x$ 와 $y$ 값에 따라 '예' 또는 '아니오'로 답할 수 있습니다.

NP 증명 시스템은 대화형 통신이 가능한 증명자(Prover)와 검증자(Verifier)로 구성됩니다. 증명자와 검증자는 하나의 문제를 같이 받고 증명자가 그 문제의 해를 전송하면 그 해가 정말 문제의 해가 맞는지 판단합니다. 정리하면, 증명자는 특정 명제를 증명할 수 있다고 주장하고 검증자는 이 증명에 대해 예/아니오로 대답해야합니다. 해 자체를 보내는 방식이 암호학적으로 활용하기에는 잘 맞지 않아 적용 분야가 한정적이었지만, 이후에 이 증명 시스템을 기반으로 대화형 증명 시스템, 영지식 대화형 증명 시스템까지 발전하게 됩니다.

엄밀하게는 명제 x를 언어 $L⊆\{0,1\}^∗$ 의 원소로 표현할 수 있습니다. 증명자 P는 $x∈L$ 임을 보이며 검증자 V는 증명자의 증명을 보고 판단합니다.
NP 증명 시스템의 증명자 $P$ 와 검증자 $V$ 는 결정론적(deterministic) 튜링 기계로 볼 수 있습니다. 결정론적 튜링 기계는 NP 문제를 다항 시간 내에 검증할 수 있습니다. 또한 $P$ 에게는 무한한 계산 시간이 주어지고 $V$ 에게는 다항 시간만이 주어집니다. 따라서 증명자 $P$ 는 어떠한 명제 $x$ 에 대해 $x \in L$ 을 증명하는 결과물 $w$ 를 $V$ 에게 보내고 $V$ 는 다항 시간 내에 예/아니오를 판별합니다.

언어 $L$ 은 형식 언어(formal language)를 말합니다. $*$ 첨자는 클레이니 스타(Kleene Star)로 문자의 집합에 대해 0개 이상의 임의 원소의 연쇄를 뜻합니다. 따라서 위의 $\{0, 1\}^*$ 은 $\{ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, \dots \}$ 를 뜻합니다. 따라서 $L$ 은 $\{0, 1\}^*$ 의 부분집합이며 특정 결정 문제의 답 집합이라고 이해할 수 있습니다.

NP 문제는 비결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제의 집합입니다. NP에 속하는 문제는 결정론적 튜링 기계로 다항 시간에 검증이 가능합니다.

결정론적 튜링 기계에 대한 자세한 설명은 위키백과의 튜링 기계 항목을 참고해주시기 바랍니다.

대화형 증명 시스템

영지식 증명은 대화형 증명 시스템에 기반을 두고 있습니다. 대화형 증명 시스템은 NP 증명 시스템과 같이 두 참여자가 필요합니다. 증명자는 특정한 지식을 알고 있다는 것을 검증받고 싶어하는 참여자이고 검증자는 증명자가 해당 지식을 알고 있다는 사실을 증명해주는 참여자입니다. 증명자는 악의적일 수도 있고, 특정한 정보를 모르면서 아는 척을 할 수도 있는 신뢰할 수 없는 존재로 봅니다. 또한 증명자는 계산량에 제한이 없으며, 검증자는 다항 시간 내에 계산이 완료되어야 합니다.

대화형 증명 시스템의 단방향 증명의 경우 다음과 같이 진행됩니다.

$P$ 와 $V$ 모두 명제 $x$ 를 받습니다.

$P$ 는 계산 후 $V$ 에게 결과물 $\pi$ 를 보냅니다.

$V$ 는 $\pi$ 를 보고 $x\in L$ 이라고 생각하면 'YES'를, 아니라고 생각되면 'NO'를 보냅니다.

이러한 $P$ 와 $V$ 또한 확률적 튜링 기계로 볼 수 있습니다. 따라서 대화형 증명 시스템은 다음과 같은 두 속성을 만족해야 합니다.

완전성 (completeness)
$x\in L$ 이면 증명 방식을 따른 $P$ 가 보낸 $\pi$ 를 보고 정직한 $V$ 는 $x\in L$ 이라 판단해야 합니다. 이 증명이 받아들여질 확률은 아주 큰 $n$ 과 모든 $k$ 에 대해 최소 $1-\frac{1}{n^k}$ 이상이어야 합니다.

건전성 (soundness)
$x\notin L$ 이면 $x\in L$ 이라 주장하는 $P$ 가 무슨 시도를 해도 정직한 $V$ 는 $x\notin L$ 이라 판단해야 합니다. 이 증명이 받아들여질 확률은 아주 큰 $n$ 과 모든 $k$ 에 대해 최대 $\frac{1}{n^k}$ 이하입니다.

Arthur-Merlin Protocol

아서-멀린 프로토콜은 대화형 증명 시스템이 NP 문제를 넘어선 문제를 표현할 수 있게 해줍니다. 증명자는 무한한 계산이 가능하고 검증자는 난수 생성 기계입니다. 증명자를 멀린, 검증자를 아서로 정하겠습니다. 멀린은 정직할 필요가 없으며 아서는 멀린이 제공한 정보를 문제에만 기대 검증해야합니다. 만약 정당한 증명을 제공한다면 아서가 멀린이 제공한 답변을 $\frac{2}{3}$ 이상의 확률로 판단해야하며 정당하지 않은 증명을 제공한다면 아서가 멀린이 제공한 답변을 $\frac{1}{3}$ 이하의 확률로 유효하다고 판단해야 합니다. 아서가 멀린이 제공한 답변에 대해 판단하는 것은 아서의 무작위 선택에 달려있습니다.

완전성과 건전성의 조건도 변경되었습니다. 아서-멀린 프로토콜의 완전성과 건전성의 조건은 다음과 같습니다.

완전성
$x\in L$ 이면 $P$ 가 보낸 $\pi$ 를 보고 $V$ 는 $\frac{2}{3}$ 이상의 확률로 $x\in L$ 이라 판단해야 합니다.

건전성
$x\notin L$ 이면 $x\in L$ 이라 주장하는 $P$ 가 무슨 시도를 해도 $V$ 는 $\frac{1}{3}$ 이하로 $x\in L$ 이라 판단해야 합니다.

대화형 증명 시스템에서 증명자는 무한한 계산능력을 가지고 있으므로 아서왕 전설의 등장인물인 마법사 멀린의 이름을 따 멀린이라 불리고 검증자는 아서라고 부릅니다.

IP

이러한 상호작용이 여러번에 걸쳐 일어나면 더 효과적인 시스템을 만들 수 있을 것입니다. 확률적 튜링 기계인 검증자와 무한한 계산 능력을 가진 증명자가 다항 횟수의 상호작용이 가능할 때 풀 수 있는 결정 문제의 집합을 IP(Interactive Polynomial time)이라고 합니다.

1992년 발표된 Adi Shamir의 논문 'IP = PSPACE'는 제목 그대로 IP가 PSPACE 집합과 같다는 것을 증명하는 내용이었습니다. PSPACE는 결정론적 튜링 기계, 비결정론적 튜링 기계가 무한한 계산 시간과 다항 공간을 이용해 풀 수 있는 결정 문제의 집합입니다. 현재 알려져있는 복잡도 종류의 관계는 다음과 같습니다.
$\begin{aligned} \text{P}\subseteq \text{NP} \subseteq \text{PSPACE} \end{aligned}$
모든 $\subseteq$ 가 $\subsetneq$ 라고 추측하고 있지만 아직 증명된 것은 없습니다. 첫번째 $\subseteq$ 가 $\subsetneq$ 인지 아닌지 묻는 문제가 널리 알려진 P-NP 문제 입니다.

Zero knowledge

대화형 증명 시스템은 '증명이 참이다'라는 것을 검증자에게 검증받기 위해서 너무 많은 정보를 제공합니다. 그렇다면 아무 정보 없이도 무엇인가를 알고 있다는 사실을 검증 받을 수 있을까요?

The Ali Baba Cave

영지식성을 설명할 때 가장 많이 쓰이는 비유인 알리바바의 동굴을 예로 들겠습니다.
동굴에는 두 출입구 A, B가 있어서 둘 모두로 들어가고 나갈 수 있습니다. 그런데 그 가운데에 벽이 있는데 이 벽은 특정한 암호를 사용해야만 열린다고 합니다. 따라서 암호를 안다면 A로 들어가 B로 나오거나 B로 들어가 A로 나올 수 있지만 모른다면 A로 들어가 A로 나오거나 B로 들어가 B로 나오는 것밖에 할 수 없을 것입니다. 당연히 암호를 알아도 들어갔던 곳으로 다시 나오는 것은 가능합니다.

페기는 암호를 알고 있고, 빅터에게 암호를 알고 있다는 것을 증명하고 싶다고 가정합니다.

먼저 페기는 A와 B 가운데 무작위로 하나의 입구로 들어갑니다.

빅터는 페기에게 특정 출입구로 나오라고 말합니다.

페기는 그 출구로 나옵니다.

페기가 암호를 모른다면 확률적으로 빅터가 무작위로 제시한 요구사항을 절반만 충족시킬 것입니다. 그렇다면 이 과정을 여러번 반복한다면 암호를 모르는 페기가 빅터의 요구사항을 모두 충족시키는 것은 매우 낮은 확률로 가능할 것입니다. 따라서 이 과정을 통해 빅터는 페기가 가지고 있는 암호를 몰라도 페기가 암호를 알고 있다는 것을 검증할 수 있습니다.

영지식 증명의 조건

대화형 영지식 증명은 대화형 증명 시스템의 기본 조건인 완전성과 건전성 또한 만족해야합니다. 추가적으로 영지식성을 만족해야합니다.

완전성
만약 명제가 참이라면 정직한 증명자는 정직한 검증자에게 이 사실을 납득시킬 수 있어야 합니다.

건전성
만약 명제가 거짓이라면 어떠한 시도를 하더라도 검증자는 사실로 판단하지 않아야 합니다.

영지식성
만약 명제가 참이라면 검증자는 명제의 참과 거짓 외에는 아무것도 알 수 없어야 합니다.

영지식 증명의 구현

영지식 증명의 구현은 여러 예시로 설명하겠습니다.

그래프 3색 색칠하기

이 문단에서는 그래프를 이미 알고 있다고 가정하고 설명하겠습니다. 3색 문제는 그래프에서 간선으로 연결된 인접한 정점끼리는 같은 색으로 칠해지지 않으면서 총 3가지 색을 써서 그래프를 색칠하는 방법에 관한 문제입니다. 그 방법을 찾는 알고리즘은 NP-완전에 속한다는 사실이 알려져 있습니다. 증명자 $P$ 는 그래프를 3가지 색으로 칠하는 법을 알면서 검증자 $V$ 에게 그 방법에 대해 공개하고 싶지 않다고 가정합니다.

먼저 $P$ 가 3가지 색으로 그래프를 칠합니다.
$P$ 는 $V$ 에게 각 정점의 색을 약속합니다. 약속한다는 것은 추후에 변경이 불가능하게 고정했다는 뜻입니다.

$V$ 는 특정 간선에 대해 질문합니다.

$P$ 는 그 간선에 대해 양쪽 정점의 색을 공개합니다. 만약 두 정점의 색이 같다면 3색 문제의 조건을 만족하지 못했으므로 답을 모른다고 판단할 수 있습니다.

이러한 과정을 반복하면 확률적으로 $P$ 가 3가지 색으로 그래프를 칠하는 방법을 아는지 검증할 수 있습니다. 그러나 여기서 절차마다 2개 정점의 색을 알 수 있는데 그것이 영지식성을 만족한다고 할 수 있을까요?

증명을 생략하고 결론만 정리하자면 영지식성을 만족합니다. $V$ 가 유의미하게 모든 정점을 어떻게 칠하는지(약속된 색칠법)를 알아내는 다항 시간 알고리즘이 없습니다. 이러한 영지식성을 computational zero-knowledge 라고 합니다. 현실적으로 영지식 증명을 구현하는 것에는 이정도 수준을 요구합니다.

모든 NP 문제는 그래프 3색 문제로 환원됩니다. 따라서 NP에 속하는 모든 명제는 대응되는 대화형 영지식 증명 시스템을 만들 수 있습니다.

이산 대수 문제

먼저 대화형 증명을 시작하기 전에 증명자 $P$ 는 소수 $p$ , $p - 1$ 이하의 정수 $a$ , $p-2$ 이하의 비밀 난수 $x$ 를 선택해 $b = a^x\pmod p$ 를 계산합니다. 증명자 $P$ 는 $x$ 를 보관하고 $\{a, b, p\}$ 를 검증자 $V$ 에게 전송합니다.

$P$ 는 무작위 난수 $r$ 을 이용해 $R = a^r\pmod p$ 을 계산해 $V$ 에게 전송합니다.
$V$ 는 이진수 $e = 0$ 또는 $1$ 을 무작위로 선택해 $P$ 에게 전송합니다.
$P$ 는 $e$ 를 수신한 후 $e = 0$ 이면 $t = r$ 을 전송합니다. $e = 1$ 이면 $t = x + r\pmod{p - 1}$ 을 $V$ 에게 전송합니다.
$V$ 는 $e = 0$ 인 경우 $a^t = R\pmod p$ 을 검사하고 $e = 1$ 인 경우 $a^t = bR\pmod p$ 를 검사합니다.
성립하지 않는 경우 종료합니다. 성립하면 1번부터 4번까지의 과정을 반복해 신뢰도를 높입니다.

Fiat-Shamir Protocol

알리바바의 동굴과 modular square root 문제를 합친 프로토콜입니다. 두 큰 소수 $p$ , $q$ 에 대해 $n = pq$ 를 구하고 서로소인 비밀 숫자 $s_1, s_2, \cdots , s_k$ 를 생성합니다. $P$ 와 $V$ 는 $v_i = s_i^2\pmod n$ 을 알고 $P$ 만 $s_i$ 를 알고 있다고 가정합니다.

$P$ 는 무작위 정수 $r$ , 무작위 부호 $s \in {-1, 1}$ 를 생성하고 $x\equiv s\cdot r^2\pmod n$ 을 $V$ 에게 보냅니다.
$V$ 는 $P$ 에게 0 또는 1인 수 $a_1, a_2, \cdots , a_k$ 를 보냅니다.
$P$ 는 $y\equiv rs_1^{a_1}s_2^{a_2}\cdots s_k^{a_k}\pmod n$ 을 $V$ 에게 보냅니다.
$V$ 는 $y^2 \equiv \pm xv_1^{a_1}v_2^{a_2}\cdots v_k^{a_k}\pmod n$ 인지 확인합니다.

알리바바의 동굴의 경우는 $k = 1$ 인 때입니다.

Non-Interactive Zero Knowledge

앞서 살펴본 영지식 증명은 대화형 증명 시스템에 기반을 두고 있습니다. 대화형 증명은 완전성과 건전성을 만족하기 위해 여러번의 상호작용이 필수적입니다. 당연히 반복되는 통신은 비효율적입니다. 실제로 영지식 증명을 사용하기 위해서 검증자와 증명자가 동시에 통신하는 상황을 만드는 것은 쉽지 않은 일입니다. 따라서 검증자 없이 증명자 혼자 증명을 할 수 있는 비대화형 영지식 증명(Non-Interactive Zero Knowledge, NIZK)이 필요합니다.

Fiat-Shamir Heuristic

원래 대화형 영지식 증명은 검증자의 특정한 요구에 따라 증명자가 답안을 제출하는 형태를 띠고 있습니다. 검증자의 특정한 요구가 없다면 증명자의 문제 조작이 가능해져 거짓을 말하는 증명자를 찾아낼 수 없어 건전성을 만족하지 못합니다. 비대화형 영지식 증명 시스템을 만들기 위해서는 이 문제를 해결해야 합니다. Fiat-Shamir Heuristic이라는 NIZK 시스템은 검증자는 없지만 검증자의 역할을 하는 어떤 존재를 만들어 이 문제를 해결했습니다.

Random Oracle

랜덤 오라클이라는 가상의 프로그램은 검증자가 내는 문제를 대체합니다. 증명자는 랜덤 오라클에게 무작위 값을 받아 증명을 제출해야하고, 증명에 참여하지 않는 모든 사람들은 그 무작위 값이 랜덤 오라클에서 생성되었다는 것을 확인할 수 있어야 합니다. 따라서 증명자는 증명과 함께 랜덤 오라클이 생성한 값을 증거로 제출합니다.

다음 글에서는 영지식 스나크, zk-SNARKs에 대해 알아보겠습니다.