evenharder's profile image

evenharder

December 20, 2020 20:30

이전 글에서는 공개 키 암호화 시스템에서 보안을 어떻게 챙겨야 하는가를 다루었습니다. 암호화 알고리즘은 기본적으로 외부의 개입이 없습니다. 그러나 세상에는 다양한 프로토콜이 있고, 둘 이상이 통신하며 내용을 주고 받습니다. 이 글에서는 프로토콜의 보안을 어떻게 챙기고 또 암호화폐로 인해 널리 알려진 속성인 영지식성^{zero-knowledgeness}을 다루고자 합니다.

• 대화형 증명 시스템
  • NP Revisited
  • Arthur-Merlin Protocol
  • IP
• 영지식
  • 알리바바와 동굴
  • Indistinguishability Revisited
  • Fiat-Shamir Protocol
  • Hamiltonian Cycle
• 마무리
• 각주

대화형 증명 시스템

대화형 증명 시스템^{interactive proof system}은 두 개체 증명자^prover와 검증자^verifier로 이루어져 있습니다. 증명자는 특정한 명제를 증명할 수 있다고 주장하며, 검증자는 이 ‘증명’을 확인해 YES/NO로 답을 해야 합니다. 증명자는 악의적일 수도 있고, 특정한 정보를 모르면서 아는 척을 할 수도 있습니다. 이 때 증명자는 계산량에 제한이 없으며, 검증자는 계산량에 제한이 있습니다 (다항 시간).

조금 엄밀하게 이야기를 하면, 명제 $x$는 언어 $L \subseteq \{0, 1\}^{*}$의 원소로 표현할 수 있습니다. 증명자 $P$는 $x \in L$임을 보이며, 검증자 $V$는 증명자의 ‘증명’을 보고 판단해야 합니다. 단방향 증명의 경우 다음과 같이 진행됩니다.

• $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$이라 판단해야 합니다.
• 건전성^soundness: $x \not \in L$이면 $x \in L$이라 주장하는 $P$가 무슨 시도를 해도 $V$는 $x \not \in L$이라 판단해야 합니다.

NP Revisited

$\mathsf{NP}$도 일종의 기초적인 증명 시스템으로 볼 수 있습니다.

• $P(x)$ : $x \in L$를 증명하는 다항식 크기의 결과물^certificate $w \in \{0, 1\}^{\mathsf{poly}(\lvert x\rvert)}$을 $V$에게 보냅니다.
• $V(x)$ : $w$를 검증합니다. 정의상 다항 시간 안에 가능하므로 YES/NO 판별이 가능합니다.

Arthur-Merlin Protocol

위의 $\mathsf{NP}$는 단방향 프로토콜이긴 했으나, 1985년 László Babai가 Arthur-Merlin Protocol을 발표하면서 대화형 증명 시스템이 $\mathsf{NP}$ 이상을 표현할 수 있음을 밝혔습니다.¹ 여기서 증명자는 여전히 무한한 계산을 할 수 있지만 검증자는 대신 확률적 튜링 머신이 되었습니다. 때문에 완전성과 건전성의 증명도 일부 바뀌었습니다.

• 완전성^completeness: $x \in L$이면 증명 방식을 따른 $P$가 보낸 $\pi$를 보고 $V$는 2/3 이상의 확률로 $x \in L$이라 판단해야 합니다.
• 건전성^soundness: $x \not \in L$이면 $x \in L$이라 주장하는 $P$가 무슨 시도를 해도 $V$는 1/3 이하로 $x \in L$이라 판단해야 합니다.

2/3이나 1/3은 자의적인 수치로, 프로토콜을 반복하여 false positive와 false negative의 확률을 negligible하게 만들 수 있는 수준이면 됩니다.

IP

검증자가 단방향 통신이 아닌 상호작용을 할 수 있으면 이제 더 많은 문제를 해결할 수 있습니다. 이 증명 시스템을 통해 보일 수 있는 문제의 집합을 $\textsf{IP}$라 하며, Adi Shamir가 1992년에 $\textsf{IP} = \textsf{PSPACE}$임을 증명했습니다.²

영지식

증명자가 검증자에게 증명하는 과정은 보통 ‘증명이 참이다’보단 많은 정보를 내포합니다. 암호학 관점에서는 정보 노출로도 볼 수 있습니다. zero-knowledgeness^영지식성는 이 당연한 질문에서 시작합니다. ‘증명이 참이다’ 외의 그 어느 정보도 알려주지 않으면서 증명할 수 있는가? 수학적으로 정의는 어떻게 해야 하는가?

영지식성은 지난 편에서 indistinguishability를 정의한 S. Goldwasser, S. Micali와 추가로 C. Rackoff가 1985년에 발표한 “The Knowledge Complexity of Interactive Proof Systems”³에 처음 등장합니다. 한 번 생각해봅시다. 위의 질문을 고려해보면, 영지식성이 있는 프로토콜 사이에 오는 정보는 증명의 디테일과는 1도 상관이 없습니다. 그럼 거꾸로, 증명의 디테일을 1도 모르는 사람도 적당히 프로토콜을 짜집기해서 시연할 수 있으면 되지 않을까요? 자세한 정의는 영지식성의 대표적인 예시인 ‘알리바바와 동굴’을 살펴보고 다루도록 하겠습니다.

알리바바와 동굴

알리바바는 보물이 가득한 동굴의 비밀 문을 열 수 있는 암호를 알고 있습니다. 이 동굴은 입구는 하나지만 안쪽에서 두 갈래 길로 나뉘며, 비밀 문을 열어야만 양쪽에서 연결된 보물창고를 통해 반대편으로 나올 수 있습니다. 이제 알리바바는 자신이 암호를 알고 있다는 사실을 기자에게 보이고자 합니다. “열려라 참깨!”를 외치면 되지만, 이러면 암호가 의미가 없습니다. 때문에 알리바바는 다음과 같은 확인 과정을 거치고자 합니다.

• 기자는 동굴 바깥에서 기다리고, 알리바바는 두 갈래 길 중 하나를 택해 동굴 안으로 들어갑니다.
• 알리바바는 자신이 두 길 중 하나를 선택했음을 밝히고, 기자는 두 갈래 길까지 걸어들어옵니다.
• 기자는 알리바바더러 한 방향으로 나오라고 합니다.
• 알리바바는 기자가 말한 방향으로 나옵니다.

이 간단한 예시는 완전성, 건전성, 영지식성을 모두 만족합니다.

• 완전성: 알리바바는 암호를 알고 있으므로, 어느 쪽 방향으로도 나올 수 있습니다.
• 건전성: 암호를 모르는 사람은 기자가 말한 방향으로 나올 가능성이 1/2에 불과합니다.
• 영지식성: 기자는 암호에 대한 그 어떠한 정보도 얻지 못했습니다.

알리바바의 동굴 예시에서 가장 중요한 특징은 동굴이 갈래길입니다. 2가지 밖에 없습니다! 4가지나 $2^{64}$가지가 되면 안 될까요?

Indistinguishability Revisited

어떤 명제가 참이지만 부가 정보 없이 참임을 보일 수 있다면, 부가 정보를 모르는 사람도 증명자가 명제가 참임을 증명하는 과정을 (적당한 짜집기를 통해) 시연할 수 있어보입니다. 짜집기란, 증명자 $P$와 검증자 $V$가 프로토콜로 주고받는 내용을 적당히 삭제할 수 있다는 뜻입니다. 알리바바와 동굴의 예시를 들면 다음과 같습니다.

• 알리바바가 왼쪽으로 들어갑니다.
• 기자가 왼쪽으로 나오라고 합니다. 알리바바는 왼쪽으로 나올 수 있습니다.
• 알리바바가 다시 한 번 왼쪽으로 들어갑니다.
• 기자가 오른쪽으로 나오라고 합니다. 부가 정보를 모르는 시뮬레이션에선 불가능하므로 이 기록을 제거합니다. (원 논문에서는 확률적 튜링 머신의 테이프를 이어붙입니다)

$n$번의 성공적인 과정은 평균적으로 $2n$번 시뮬레이션하면 똑같이 보일 수 있습니다. 동굴의 갈래길이 4가지면 $4n$번 시뮬레이션해야 하고, $2^{64}$개면 $2^{64}n$번 시뮬레이션 해야 합니다. 갈래길이 중요한 이유입니다. 이 시뮬레이션은 다항 시간 내에 작동해야 합니다.

시뮬레이션이 왜 중요할까요? 무작위성이 가미된 프로토콜은 앙상블^ensemble로 볼 수 있습니다. 확률 변수의 집합이라고 생각하면 편합니다. 실제 프로토콜과 시뮬레이션한 프로토콜의 앙상블이 동일하거나, 아주 미세한 차이밖에 없거나, 구분이 불가능하다면, 각 수준에서는 원래 프로토콜에도 부가 정보가 들어가 있지 않음을 알 수 있습니다. 각 정의는 다음과 같습니다.

• perfect zero-knowledge: 실제 앙상블과 시뮬레이션으로 생성한 앙상블이 일치할 때.
• statistical zero-knowledge: 실제 앙상블과 시뮬레이션으로 생성한 앙상블이 negligible한 차이밖에 없을 때.
• computational zero-knowledge: 다항 시간 안에 이 두 앙상블을 구분할 수 없을 때. 지난 포스트에서 다루었던 indistinguishability가 등장하고, 보안 수준에서는 이 정도만 다루어도 충분합니다.

$\textsf{NP}$에 속하는 모든 명제는 그에 상응하는 영지식 증명(대화형 증명 시스템을 증명으로 줄여 표현합니다)이 존재하기 때문에⁴ 다양한 수학적 예시가 있습니다.

Fiat-Shamir Protocol

알리바바의 동굴과 modular square root 문제를 합친 프로토콜이 Feige–Fiat–Shamir identification scheme(Fiat-Shamir Protocol)입니다.

기본 설정은 다음과 같습니다. 두 큰 소수 $p$, $q$에 대해 $n = pq$로 삼고, $n$과 서로소인 비밀 숫자 $s_1, s_2, \cdots, s_k$를 생성합니다. $P$와 $V$ 모두 $n$과 $v_i \equiv 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$에게 $a_1, a_2, \cdots, a_k$를 보냅니다. 각 수는 $0$ 또는 $1$입니다.
• $P$는 $y \equiv r s_1^{a_1} s_2^{a_2} \cdots s_k^{a_k} \pmod n$을 $V$에게 보냅니다.
• $V$는 $y^2 \equiv \pm x v_1^{a_1} v_2^{a_2} \cdots v_k^{a_k} \pmod n$인지 확인합니다.

이 프로토콜은 세 가지 속성을 모두 만족합니다.

• 완전성: $P$는 $y$를 계산할 수 있으며, $r^2 \equiv \pm s \pmod n$이고 $s_i^{2a_i} \equiv v_i^{a_i} \pmod n$이기 때문에 $V$는 항상 $P$의 증명을 받아들입니다.
• 건전성: $s_i$를 전혀 모르는 사람 $E$가 이 이 프로토콜을 성공하려면 처음에 $V$한테 $x \equiv y^2 v_1^{-a_1}v_2^{-a_2} \cdots v_k^{-a_k} \pmod n$를 보내고 ($y$는 난수), 세 번째 단계에서 $y$를 보내면 됩니다. 그러나 아직 받지도 못한 $a_i$를 예상해서 $y$를 보내야 하기에, 통과할 확률이 $2^{-k}$에 불과합니다.
• 영지식성: 시뮬레이션에 평균 $O(2^k)$의 시간이 걸리고, $k$가 너무 크지 않다는 제약조건 하에서는 영지식성이 만족됩니다. 알리바바의 동굴 예시는 $k = 1$일 때입니다.

Hamiltonian Cycle

그래프 이론의 유명한 $\textsf{NP}$ 문제인 Hamiltonian Cycle의 존재 여부를 Graph Isomorphism을 이용해 영지식 증명을 할 수도 있습니다.

• $P$는 $V$에게 원본 그래프 $G$의 정점 번호를 뒤섞은 그래프 $H$를 생성하고 $V$에게 넘깁니다.
• $V$는 $G$와 $H$가 동형(isomorphic)임을 보이라고 묻거나, $H$의 Hamiltonian cycle을 보이라고 묻습니다.
• $P$는 전자의 경우 $H$를 $G$로 바꾸는 순열을 보내고, 후자의 경우 $H$의 Hamiltonian cycle을 보냅니다 ($G$에서의 Hamiltonian cycle을 $H$로 정점 변환만 하면 됩니다).

이 대화형 증명 방식도 세 가지 속성을 만족합니다.

• 완전성: $G$의 Hamiltonian cycle을 알고 있으면 어느 질문을 받아도 답을 할 수 있습니다.
• 건전성: 정보를 전혀 모른다면, $G$와 동형인 그래프를 보내거나 $G$와 아무 상관도 없지만 Hamiltonian cycle은 아는 그래프를 $V$에게 보낼 수 있습니다. 어느 쪽이든 1/2의 확률로밖에 성공하지 못합니다.
• 영지식성: 건전성에서 말한 대로 그래프를 생성한 다음, 짜집기를 하면 질의를 $n$번 받을 때 평균적으로 $2n$번의 질의 시뮬레이션으로 구분 불가능한 예시를 들 수 있습니다.

마무리

블록체인이나 암호화폐는 잘 모르지만, 영지식 증명이 이들 덕분에 각광받고 있습니다. 송금자와 액수 같은 부가적인 정보를 노출하지 않고 송금할 수 있으며, Proof of Work 등을 보일 수 있기 때문입니다. 흥미로운 특성임에는 분명하지만 검은 돈으로 사용되기엔 최적의 환경입니다. 하지만 수학적으로 안전함이 입증되었다고 해서 구현체나 연관 모듈이 난공불락의 요새라는 보장은 없습니다.

대화형 증명 시스템과 프로토콜의 보안은 이런 식으로 진행됩니다. 암호화 알고리즘의 indistinguishability와 비슷하면서도 타자가 있기 때문에 zero-knowledgeness가 대두됩니다. 영지식성은 뭐든지 안전하게 만드는 마법의 키워드처럼 보일 수 있지만, 전혀 그렇지 않고 철저하게 수학과 시뮬레이션에 기반한 용어입니다.

각주