영지식 증명이란 무엇인가?
영지식 증명 이해 및 수학적 구현
본 글에서는 영지식 증명의 정의와 수학적 구현에 대해 살펴볼 것이다. 영지식 증명을 활용하면 블록체인 상에서의 민감한 정보에 해당하는 거래 내역을 은닉할 수 있고, 그럼에도 검증할 수 있다. 가령 비트코인에서는 특정 주소에 대한 모든 거래 내역을 추적할 수 있으며 잔고가 얼마인지도 모두 드러난다. 그러나 Z-CASH와 같이 영지식 증명을 활용한 블록체인에서는 내역 및 잔고를 임의로 파악할 수 없다. 또한, 검증에 필요한 데이터 및 절차가 줄어 확장성 문제의 해결책으로도 응용할 수 있다.
영지식 증명이란 무엇인가?
영지식 증명(zero-knowledge proof)이란 암호학에서 누군가가 상대방에게 어떤 문장(statement)이 참이라는 것을 증명할 때, 그 문장의 참/거짓 여부를 제외한 다른 어떠한 정보도 노출되지 않는 상호 절차를 의미한다. 이를 영지식성이라 하며, 영지식증명은 본 영지식성을 포함해 다음의 세 가지 성질을 만족시켜야 한다. 어떤 문장이 참이라는 것을 증명하려는 측을 증명자(prover)라 하고, 증명 과정에 참여하여 정보를 교환하는 측을 검증자(verifier)라 한다. 즉, 해당 문장이 참이라는 사실을 검증하고자 하는 측이다.
1. 완전성(completeness): 어떤 문장이 참이면, 정직한 증명자는 정직한 검증자에게 이 사실을 납득시킬 수 있어야 한다.
2. 건실성(soundness): 어떤 문장이 거짓이면, 어느 부정직한 증명자라도 정직한 검증자에게 이 문장이 사실이라고 납득시킬 수 없어야 한다.
3. 영지식성(zero-knowledgeness): 검증자는 어떤 문장의 참/거짓 이외에는 아무것도 알 수 없어야 한다.
이 영지식성에서 ‘알 수 없어야 하는 정보’는 실로 그 폭이 넓은데, 가령 A라는 검증자가 어떤 문장을 검증했더라도 B라는 검증자는 그 사실을 활용할 수 없다. 왜냐하면 증명자와 A 사이의 검증이 B로부터 활용되는 순간 ‘정보’로 기능하기 때문이다. 따라서 B가 해당 문장의 참/거짓 여부를 알고자 한다면 증명자와 검증하는 방법밖에 없다.
어린이를 위한 영지식 증명
수학적 구현에 앞서, 장 자크 키스케다의 ‘어린이를 위한 영지식 증명’법을 통해 이해를 더해보도록 하자. 증명자 페기(Peggy)는 어떤 동굴 안에 설치된 비밀 문의 열쇠(“열려라 참깨”)를 알고 있다. 이 동굴은 도넛과도 같은 모양으로 되어 있어, 비밀 문에 도달하기 위해서는 A 통로나 B 통로 둘 중 하나로 접근할 수 있다. 비밀 문의 반대편에는 동굴의 입구가 있고, 입구에서는 비밀 문의 모습이 보이지 않는다. 검증자 빅터(Victor)는 페기가 비밀 문을 열 수 있다는 것을 검증하고 싶어 한다. 그러나 페기는 자신이 열쇠를 알고 있다는 사실은 증명하고 싶지만, 암호 그 자체는 알려주기 싫으며, 심지어 (검증자를 제외한 다른 사람에게) 자신이 열쇠를 가지고 있다는 사실을 알리기도 싫다. 이런 경우에 영지식 증명이 크게 활약할 수 있다.
다음과 같은 방법으로 페기가 비밀 문의 열쇠를 갖고 있음을 빅터에게 증명할 수 있다. 우선 페기가 A 통로 혹은 B 통로 중 무작위로 아무 통로나 골라 비밀 문으로 이동한다. 이때 빅터는 동굴 입구 밖에 있으므로 페기가 어떤 통로를 선택하였는지 알 수 없다. 이후 빅터가 동굴 입구로 들어와, A 통로 혹은 B 통로 중 무작위로 아무 통로나 골라 페기에게 외친다. 페기는 그 말을 듣고 빅터가 선택한 통로로 나타난다.
만일 페기에게 비밀 문의 열쇠가 없다면, 페기는 처음 선택한 통로로만 나올 수 있다. 따라서 50% 확률로 빅터의 요구를 만족시킬 수 없다. 만일 위와 같은 실험을 여러 번 반복한다면 페기가 빅터의 요구를 모두 만족시킬 확률은 크게 줄어든다. 가령 20번 반복할 경우의 확률은 100만 분의 1이 된다. 이런 경우 페기에게 비밀 문의 열쇠가 있다고 생각하는 편이 자연스러울 것이다.
또한 페기는 빅터에게 문장의 참/거짓 정보 외에 다른 어떠한 정보도 누설하지 않았으며, 빅터 이외의 다른 모든 사람에게는 어떠한 정보도 주지 않았다. 만일 빅터가 페기와의 실험을 모두 녹화하여 제삼자에게 보여준다 하더라도 증빙자료로 사용될 수 없는데, 왜냐하면 사전에 페기와 빅터가 어떤 통로로 나올지를 약속하고 사기를 쳤을 수도 있기 때문이다. 따라서 본 증명은 빅터에게만 유효한 증명이다.
영지식 증명의 수학적 구현
영지식 증명의 수학적 구현에서는 일방향 함수(one-way function)가 핵심 요소이다. 일방향 함수란 계산은 쉬우나 그 역에 해당하는 역함수는 계산이 어려운 함수를 의미한다. 가령 두 소수를 곱하여 큰 수를 도출하기는 아주 쉬우나, 그 수를 소인수분해 하는 것은 매우 어려운 것과 같다. 이번에 소개할 영지식 증명에서는 일방향 특성을 가지는 이산 로그 문제(Discrete Logarithm Problem, DLP, 이산 대수 문제라고도 함)를 다룬다.
이를 위해 간단히 대수 구조의 전반을 학습해보도록 하자. 암호학에서는 정수의 집합(set)과, 그들 사이에서 정의되는 연산(operation)이 요구된다. 일련의 연산들이 주어진 집합을 대수 구조(algebraic structure)라 한다. 특히 자주 활용되는 대수 구조인 군(group), 환(ring), 체(fields)에 대하여 살펴볼 필요가 있다.
군
군(group)은 가장 기초적인 대수 구조로써 하나의 이항연산(binary operation)만을 가진다. 이항연산이란 피연산자를 두 개 가지는 연산이다. 흔히 생각할 수 있는 덧셈, 곱셈 등이 이항연산에 속한다.
군 <G, +>은 다음의 네 가지 공리(axiom)를 만족한다.
1. 이항연산 ‘+’에 대하여 닫혀있다(closure).
2. 이항연산 ‘+’에 대하여 결합법칙(associativity)이 성립한다.
3. 이항연산 ‘+’에 대하여 항등원(identity)이 존재한다.
4. 이항연산 ‘+’에 대하여 역원(inverse)이 존재한다.
결합법칙이란 한 식에서 연산이 두 번 이상 연속될 때, 연산 계산의 순서가 달라도 그 결과는 동일하다는 법칙이다.
참고로, 공리 1)과 2)만 만족한다면 이를 반군(semigroup)이라 하며, 1), 2), 그리고 3)을 만족한다면 모노이드(monoid)라 한다. 1)부터 4)까지를 모두 만족하여야 군이 된다. 또한, 군의 네 가지 공리와 더불어 교환법칙(commutativity)까지 성립한다면 이를 아벨군(abelian group) 혹은 가환군(commutative group)이라 한다. 교환법칙이란 이항연산의 결과가 두 원소의 순서에 관계가 없다는 법칙이다.
부분군(subgroup)은 어느 군의 원소의 부분집합을 원소로 가지며, 본래의 군과 동일한 연산을 가진다. 집합과 부분집합의 관계를 상기하라. 모든 집합이 자기 자신 및 공집합(empty set)을 반드시 부분집합으로 갖는 것처럼, 모든 군은 자기 자신 및 항등원을 부분군으로 가진다.
환
환(ring)은 두 개의 이항연산을 가지는 대수 구조이다. 환 <R, +, ⋅>은 다음의 공리들을 만족한다.
이항연산 ‘+’에 대하여
1. 이항연산 ‘+’에 대하여 닫혀있다.
2. 이항연산 ‘+’에 대하여 결합법칙이 성립한다.
3. 이항연산 ‘+’에 대하여 교환법칙이 성립한다.
4. 이항연산 ‘+’에 대하여 항등원(0)이 존재한다.
5. 이항연산 ‘+’에 대하여 역원이 존재한다.
즉, <R, +>은 아벨군이다. 이어 이항연산 ‘⋅’에 대하여
1. 이항연산 ‘⋅’에 대하여 닫혀있다.
2. 이항연산 ‘⋅’에 대하여 결합법칙이 성립한다.
즉, <R, ⋅>은 반군이다. 나아가 다음을 만족한다.
1. 이항연산 ‘+’에 대한 ‘⋅’의 분배법칙(distributive)이 성립한다.
혹자는 상기한 공리들을 만족하는 대수 구조를 유사환(rng 또는 pseudoring)으로 엄밀히 구분하며, 이항연산 ‘⋅’에 대하여 항등원(1)이 존재하는 경우에만 환으로 취급한다. 단위화 과정을 통해 유사환을 환(단위환)으로 표준화할 수 있다. 항등원이 존재하는 환에서 <R, ⋅>은 모노이드가 된다.
또한, 위 공리들과 더불어 이항연산 ‘⋅’에 대하여 교환법칙(commutativity)까지 성립한다면 이를 가환환(commutative ring)이라 한다. 만일 환에서 모든 0이 아닌 원소가 ‘⋅’에 대하여 역원을 가지면 이를 나눗셈환(division ring)이라 한다. 어느 환이 가환환이자 나눗셈환이면 아래서 살펴볼 체(field)가 된다.
체
체(field)는 쉽게 말해 덧셈, 뺄셈, 곱셈, 나눗셈의 사칙연산을 소화할 수 있는 대수 구조이다. 체 <F, +, ⋅>는 다음의 공리들을 만족한다.
이항연산 ‘+’에 대하여
1. 이항연산 ‘+’에 대하여 닫혀있다.
2. 이항연산 ‘+’에 대하여 결합법칙이 성립한다.
3. 이항연산 ‘+’에 대하여 교환법칙이 성립한다.
4. 이항연산 ‘+’에 대하여 항등원(0)이 존재한다.
5. 이항연산 ‘+’에 대하여 역원이 존재한다.
즉, <F, +>은 아벨군이다. 이어 이항연산 ‘⋅’에 대하여
1. 이항연산 ‘⋅’에 대하여 닫혀있다.
2. 이항연산 ‘⋅’에 대하여 결합법칙이 성립한다.
3. 이항연산 ‘⋅’에 대하여 교환법칙이 성립한다.
4. 이항연산 ‘⋅’에 대하여 항등원(1)이 존재한다.
5. 0이 아닌 모든 원소에서, 이항연산 ‘⋅’에 대하여 역원이 존재한다.
즉, 0이 아닌 모든 원소들의 집합(F*)에서 <F*, ⋅>은 아벨군이다. 나아가 다음을 만족한다.
1. 이항연산 ‘+’에 대한 ‘⋅’의 분배법칙(distributive)이 성립한다.
다른 관점에서, 체 <F, +, ⋅>는 가환환인 나눗셈환이다.
유한체(finite field) 또는 갈루아 체(Galois field)라 불리는 대수 구조는 유한개의 원소로 한정된 체이다. 이 유한체는 암호학에서 널리 활용된다. 갈루아는 체가 유한하기 위하여 원소의 개수가 소수의 거듭제곱꼴이야 함을 밝힌바 있다. GF(p^n)으로 표기한다.
이산 로그 문제
유한체에서 곱셈이 잘 정의되므로 어느 수의 거듭제곱을 생각할 수 있다. 이런 연산을 이산 거듭제곱(discrete exponentiation)이라 한다. 가령 Z_7에서 3의 5제곱을 생각해보자. 3의 5제곱을 계산해보면 243이고, 7로 나눈 나머지는 5이므로 Z_7에서 3^5 = 5이다.
이산 거듭제곱을 정의하면 자연스럽게 이산 로그(discrete logarithm)를 생각할 수 있다. 가령 3^k≡5 (mod 7)를 만족하는 가장 작은 정수 k는, 곧 Z_7에서 밑이 3인 5의 이산 로그 값이다. 본 예시에서는 5에 해당한다. GF(p)소수 p가 충분히 크면 이산 로그를 구하기가 어렵다는 점을 이용해 암호 시스템을 구축할 수 있다. 이를 이산 로그 문제(Discrete Logarithm Problem, DLP)라 한다.
이산 거듭제곱은 간단히 구할 수 있으나, 이산 로그 문제를 효율적으로 해결하는 알고리즘은 알려지지 않았다. 이러한 일방향 함수의 아이디어로부터 영지식 증명을 구현할 수 있다.
페기는 빅터에게 주어진 값에 대한 이산 로그 값(x)을 알고 있음을 증명하고자 한다. 그러나 그 값을 알려주기는 싫은 상황이다. 어떻게 하면 주어진 y와 생성자 g로부터 y=g^x mod p를 만족시키는 x를 알고 있음을 증명할 수 있을까?
페기는 우선 y=g^x mod p를 계산하고 그 값을 빅터에게 전송한다. 또한 페기는 랜덤하게 고른 r 값을 이용해 C=g^r mod p를 계산하고 그 값을 빅터에게 전송한다. 빅터는 페기에게 (x+r) mod (p-1)의 값이나 r 값 중 하나를 요구한다. 만일 전자를 요구했을 경우, 빅터는 (C∙y) mod p ≡ g^((x+r) mod (p-1)) mod p로부터 C∙y를 검증할 수 있으며, 후자인 경우 C ≡ g^r mod p로부터 C를 검증할 수 있다.
각 라운드마다 C∙y 혹은 C를 검증할 확률은 50%에 해당하며, 많은 라운드를 모두 통과했을 경우에는 페기가 거짓말을 할 확률이 크게 줄어든다. 따라서 페기는 y를 올바르게 구할 수 있으며 계산에 필요한 x를 알고 있다고 생각함이 자연스럽다.
References
Z-CASH: https://z.cash/
DLP: https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%82%B0_%EB%A1%9C%EA%B7%B8
Edit by.
박상현(Luke Park) | 서강대학교 컴퓨터공학과 학사과정 | twodude@naver.com
관심분야: 블록체인, 인공지능, 시뮬레이션
