Zero Knowledge Proof

정의

증명자가 검증자에게 어떤 사항이 참이라는 것을 증명할 때 그 문장의 참 거짓 여부를 제외한 어떤 정보도 노출하지 않고 검증할 수 있는 증명법

증명자: 어떤 문장이 참이라는 것을 증명하려는 주체자 검증자: 증명 과정에 참여하여 증명자와 정보를 주고받는 주체자

비유를 통한 예시

증명자 페기는 어떤 동굴 안에 있는 비밀 문의 열쇠를 갖고 있다고 주장하고 있습니다. 동굴은 아래의 그림과 같이 고리 모양으로 되어 있고, 그 한가운데를 비밀문이 막고 있습니다. 비밀문의 반대편에는 동굴의 입구가 있고 입구에서는 비밀문의 모습이 보이지 않습니다. 페기는 빅터에게 자신이 정말로 열쇠를 갖고 있다고 증명해야 하지만 다른 사람에게 자신에 관한 비밀이 밝혀지는 것을 싫어합니다. 다음과 같은 방법으로 다른 사람에게 어떤 정보도 주지 않으면서 페기가 빅터에게 비밀문의 열쇠를 갖고 있다는 것을 증명할 수 있습니다.

먼저 페기가 아무 통로나 골라 동굴로 들어갑니다. 이때 빅터는 페기가 어떤 통로로 들어갔는지 볼 수 없습니다.

그다음 빅터가 동굴 입구로 들어와 페기에게 A나 B 중 둘 중 아무거나 골라서 페기에게 그 방향으로 나오라고 말합니다.

페기는 그 말을 듣고 빅터가 고른 통로로 나와야 합니다. 만약 페기가 비밀 문의 열쇠를 가지고 있다면 빅터가 어떤 통로를 고른다고 하더라도 페기는 어떤 통로를 골라도 그 통로로 나올 수 있습니다. 하지만 열쇠가 없다면 처음 골랐던 통로로만 나올 수 있으므로 50% 확률로 빅터에게 증명할 수 있습니다. 만약 위와 같은 예를 20번만 반복해도 페기가 열쇠를 갖고 있지 않지만 우연히 빅터에게 가지고 있다고 증명할 수 있는 확률은 100만 분의 1이하가 됩니다. 이런 실험을 아무리 반복해도 빅터와 페기 외의 다른 사람에게 어떤 정보도 주지 않습니다. 예를 들어 빅터와 페기의 실험을 전부 녹화하여 다른 사람에게 보여준다고 해도 빅터가 아닌 다른 이들에게는 어떤 증명도 될 수 없습니다. 빅터와 페기가 사전에 약속한 다음 캠코더로 녹화했다면 열쇠가 없더라고 통로를 전부 맞추는 영상을 찍을 수 있기 때문입니다. 빅터는 페기가 자신이 임의의 통로를 불러줬다는 사실을 알고 있으므로 이 증명은 빅터에게만 유효한 증명이 됩니다.

Zero-knowledge proof의 세가지 성질

1. 완전성: 어떤 문장이 참이면 정직한 증명자(페기)는 정직한 검증자(빅터)에게 이 사실을 납득시킬 수 있어야 한다. 위의 예에서는 빅터가 고른 통로로 페기가 나올 수 있음으로써 납득시킬 수 있습니다.
2. 건실성: 어떤 문장이 거짓이면 어떠한 부정직한 증명자(페기)라도 정직한 검증자(빅터)에게 이 문장이 사실이라고 납득시킬 수 없어야 한다. 위의 에를 여러 번 반복하면 속일 수 있는 확률히 현저히 낮아지므로 거짓으로 납득시킬 수 없다.
3. 영지식성: 어떤 문장이 참이면 검증자(빅터)는 문장의 참 거짓 이외에는 아무것도 알 수 없어야 한다. 검증자(빅터)는 증명자(페기)가 문을 열 수 있는지 없는지에 대한 정보 말고는 얻을 수 있는 정보가 없다.

Sources

• https://ko.wikipedia.org/wiki/%EC%98%81%EC%A7%80%EC%8B%9D_%EC%A6%9D%EB%AA%85