영지식 증명

영지식 증명(零知識 證明, 영어: zero-knowledge proof) 또는 제로 널리지 프로토콜(영어: zero-knowledge protocol)은 암호학에서 누군가가 상대방에게 어떤 사항(statement)이 참이라는 것을 증명할 때, 그 문장의 참 거짓 여부를 제외한 어떤 것도 노출되지 않는 interactive한 절차를 뜻한다.

어떤 문장이 참이라는 것을 증명하려는 쪽을 증명자(證明者, prover)라 하고, 증명 과정에 참여하여 증명자와 정보를 주고 받는 쪽을 검증자 (檢證者, verifier)라고 한다. 영지식 증명에 참여하는 당사자들이 상대방을 속이려는 목적으로 프로토콜을 임의로 변경하는 경우, 당사자들이 부정직하다 또는 정직하지 않다 (dishonest, 혹은 cheating)고 한다. 그 외의 경우에는, 정직하다고 한다.

영지식 증명은 다음과 같은 세가지 성질을 만족시켜야 한다.

1. 완전성(完全性, completeness): 어떤 문장이 참이면, 정직한 증명자는 정직한 검증자에게 이 사실을 납득시킬 수 있어야 한다.
2. 건실성(健實性, soundness): 어떤 문장이 거짓이면, 어떠한 부정직한 증명자라도 정직한 검증자에게 이 문장이 사실이라고 납득시킬 수 없어야 한다.
3. 영지식성 (零知識性, zero-knowledgeness): 어떤 문장이 참이면, 검증자는 문장의 참 거짓 이외에는 아무것도 알 수 없어야 한다.

위의 성질 중 완전성 및 건실성은 증명 과정에서 보편적으로 요구되는 성질이며, 영지식성 (零知識性, zero-knowledgeness)은 영지식 증명 과정에서 추가적으로 요구되는 성질이다.

비유를 통한 예시

빅터가 밖에서 기다리는 동안, 페기는 A나 B 중 아무 방향을 골라 동굴에 들어간다

빅터가 A나 B 중 아무 출구를 골라 페기에게 외친다

페기는 빅터가 말한 출구로 나온다

영지식 증명을 쉽게 이해하기 위해 다음과 같은 비유를 들 수 있다. 이 비유는 장 자크 키스케다(Jean-Jacques Quisquater)가 "어린이를 위한 영지식 증명"이라는 논문에서 사용한 것이다.

증명자 페기는 어떤 동굴 안에 있는 비밀 문의 열쇠를 갖고 있다고 하자. 동굴은 그림과 같이 고리 모양으로 되어 있고, 그 한가운데를 비밀 문이 막고 있다. 비밀 문의 반대편에는 동굴의 입구가 있고, 입구에서는 비밀 문의 모습이 보이지 않는다. 페기는 빅터에게 자기가 정말로 열쇠를 갖고 있다는 것을 알려줘야 하지만, 다른 사람에게 자신에 관한 비밀이 알려지는 것은 싫어한다.

다음과 같은 방법으로, 다른 사람에게 어떤 정보도 주지 않으면서 페기가 비밀 문의 열쇠를 갖고 있다는 것을 증명할 수 있다.

먼저 페기가 A와 B 가운데 아무 통로나 골라 동굴로 들어간다. 이때 빅터는 입구 밖에 서 있어서 페기가 어떤 통로로 들어갔는지 볼 수 없다. 그 다음 빅터가 입구로 들어와 A나 B 가운데 아무 통로나 골라 페기에게 외친다. 페기는 그 말을 듣고 빅터가 고른 통로로 나타난다.

만약 페기에게 비밀 문의 열쇠가 있다면, 빅터가 어떤 통로를 골라도 페기는 그 통로로 나올 수 있다. 그러나 페기에게 비밀 문의 열쇠가 없다면 페기는 처음 골랐던 통로로만 나올 수 있으므로, 50% 확률로 빅터의 요구를 만족할 수 없다. 만약 위와 같은 실험을 여러번 반복한다면 페기가 빅터의 요구를 전부 만족할 수 있을 확률은 매우 낮다. 예를 들어 위와 같이 20번만 반복해도, 페기가 열쇠를 갖고 있지 않으면서 빅터의 답을 모두 맞출 수 있는 확률은 100만분의 1 이하가 된다.

그러나 이런 실험을 아무리 반복해도, 페기는 빅터 외의 다른 사람에게 어떤 정보도 주지 않는 셈이 된다. 예를 들어 빅터가 페기와의 실험을 전부 캠코더로 녹화해 다른 사람에게 보여준다고 해도, 빅터가 아닌 다른 이들에게는 어떤 증명도 될 수 없다. 빅터와 페기가 사전에 어떤 통로로 나올지를 약속한 다음 캠코더로 녹화했다면 열쇠가 없더라도 통로를 전부 맞추는 영상을 찍을 수 있기 때문이다. 반면 빅터는 자신이 임의의 통로를 불러줬다는 사실을 알고 있으므로, 이 증명은 빅터에게만 유효한 증명이 된다.

영지식 증명의 활용

2016년 개발된 암호화폐인 지캐시(또는 제트캐시)에는 영지식 증명 방식이 사용되었다. 그에 따라 지캐시를 소유한 사람들끼리 일체의 개인정보를 노출하지 않고, 상호간에 코인을 전송할 수 있다.