A proof complexity perspective on effectively zero-knowledge proofs

논리의 비밀 수호자들

당신이 보물 상자의 비밀번호를 실제로 말하지 않고도, 그 비밀번호를 알고 있다는 사실을 증명하고 싶은 세상을 상상해 보세요. 이것이 바로 **영지식 증명(Zero-Knowledge Proofs, ZK)**의 마법입니다. 컴퓨터 과학과 암호학의 영역에서, 이것은 증명자가 검증자에게 어떤 문장이 참이라는 것을 확신시키되, 검증자는 그 외에 아무것도 알 수 없게 만드는 일종의 "마술"과 같습니다. 이는 궁극의 프라이버시 도구입니다. 자신의 정체를 밝히지 않고도 자신이 누구인지 증명하는 것이죠.

하지만 만약 그 "증명"이 단순한 마술이 아니라, 검증자가 왜 그것이 작동하는지 완전히 이해할 수는 없더라도 반드시 작동할 수밖에 없음을 알 수 있을 정도로 깊은 논리적 논거라면 어떨까요? 여기서 **증명 복잡도(Proof Complexity)**가 등장합니다. 이것을 누군가를 설득하기 위해 증명이 얼마나 길고 복받아야 하는지를 연구하는 학문이라고 생각하십시오. 만약 증명이 너무 짧다면 그것은 우연일 수 있고, 만약 불가능할 정도로 길다면 아무도 그것을 확인할 수 없을 것입니다. 당신이 읽으려는 이 논문은 이 두 세계의 교차점에 놓여 있습니다. 이 논문은 매혹적인 질문을 던집니다. 우리가 그 증명을 쉽게 찾아낼 수는 없더라도, 마치 진실된 사실처럼 보이도록 논리적으로 매우 "무겁고" 복잡한 증명을 만들어낼 수 있을까? 이는 산의 존재를 증명하기 위해, 그 산이 정말로 거기 있는지 아니면 아주 잘 그려진 그림인지 아무도 구별할 수 없을 만큼 완벽한 그림자를 보여주는 것과 같습니다.

논문의 핵심 아이디어: 증명 없는 증명

이 논문에서 얀 크라이지체크(Jan Krajíček)는 원래 일랑고(Ilango)가 발명한 새로운 유형의 영지식 증명을 순수 논리의 언어로 다시 작성합니다. 목표는 이 개념을 더 명확하게 만들고, 이 "효과적 영지식(effectively zero-knowledge)" 증명들이 정교한 수학적 도구를 사용하여 실제로 작동함을 증명하는 것입니다.

여기 핵심 이야기가 있습니다. 저자는 "증명자(Prover, 비밀을 가진 자)"와 "검증자(Verifier, 작업을 확인하는 자)"를 구축합니다. 보통 증명자는 문장을 증명하기 위해 증거(witness, 비밀)를 보여줍니다. 하지만 이 새로운 설정에서 증명자는 단순히 비밀을 보여주는 것이 아니라, 논리적 일관성을 보여줍니다. 그들은 비밀이 존재할 수 있다는 것을 실제로 드러내지 않으면서도, 비밀이 존재하는 것이 가능함을 증명합니다.

논문의 주요 발견은 그러한 시스템이 존재한다는 단순하지만 강력한 증명입니다. 저자는 두 가지 가정—하나의 암호학적 가정(특정한 "증거 구별 불가능성" 기법이 작동한다는 것)과 하나의 증명 복잡도적 가정(매우 풀기 어려운 문제들이 존재한다는 것)—을 전제로 한다면, 우리는 "이론에 대한 영지식(zero-knowledge relative to a theory)"을 갖춘 증명자를 구축할 수 있음을 보여줍니다.

이것을 쉬운 말로 설명하면 무엇일까요? 그것은 증명자가 문장이 참이라는 것을 검증자에게 확신시킬 수 있으며, 검증자가 자신의 논리 규칙을 사용하여 이를 깨뜨리려 시도하더라도 이 증명을 실제 "사실"과 구별할 수 없음을 의미합니다. 논문은 "참과 구별 불가능함"이라는 개념이 우리가 증명자에 대해 반드시 가정해야 하는 것이 아니라, 증명자가 어떻게 구축되었는지로부터 나오는 자연스러운 결과라는 점을 증명합니다. 이는 마치 로봇이 인간처럼 행동하는 능력이 너무 뛰어나서, 당신이 그 로봇이 인간이라고 가정할 필요가 없는 것이 아니라 그 행동 자체가 인간임을 증명하는 것과 같습니다.

"어려운" 부분: 왜 쉽지 않은가

논문은 이것이 모든 것을 즉시 해결하는 마법 지팡이가 아님을 주의 깊게 언급합니다. 이러한 증명의 존재는 수학자들이 참이라고 믿지만 아직 완전히 증명하지 못한 강력한 추측인 "추측(conjecture)"에 의존합니다. 구체적으로, 이 논문은 "어려운 생성기(hard generator)"—즉, 어떤 컴퓨터도 빠르게 해결할 수 없을 정도로 어려운 문제를 만들어내는 기계—가 존재한다는 아이디어에 의존합니다.

저자는 모델 이론(model theory)(수학이 어떻게 작동하는지 보기 위해 서로 다른 버전의 현실이나 "우주"를 살펴보는 것과 같은 도구)이라는 도구를 사용하여, 만 만약 이러한 어려운 문제들이 존재한다면 우리의 영지식 증명이 작동함을 보여줍니다. 논문은 만약 어떤 문제에 대한 짧은 증명을 찾을 수 없다면, 그 문제가 해결 불가능한 "비표준적(non-standard)" 세계가 반드시 존재해야 하며, 이 간극이 바로 영지식 증명이 숨기고 있는 것이라고 주장합니다.

"효과적" 영지식에서 "진정한" 영지식으로

논문은 세 번째 섹션에서 마지막으로 흥미로운 단계를 밟습니다. 이 "효과적 영지식"(논리 이론에 의존하는 것)을 "진정한 영지식"(실제 보안에 사용되는 종류)으로 바꿀 수 있을까요?

답은 "그렇다, 하지만 조건이 있다"입니다. 저자는 특정한 유형의 어려운 생성기(이를 "데미 비트(demi-bit)"라고 부름)가 존재한다고 가정하고, 증명자와 검증자가 공통 무작위 문자열(common random string)(게임이 시작되기 전에 두 사람이 함께 보유하는 비밀 코드와 같은 것)을 공유할 수 있다면, 우리는 진정으로 안전한 실세계 영지식 증명을 구축할 수 있음을 보여줍니다.

논문은 구성하기 까다로울 수 있는 일련의 어려운 문제들에 의존하는 대신, 이러한 "생성기"들을 사용하여 난이도를 만들어낼 수 있다고 제안합니다. 조건은 증명자와 검증자가 그 무작위 문자열을 공유해야 한다는 것입니다. 그것이 없다면 시스템은 완벽하게 안전하지 않을 수 있습니다. 하지만 그것이 있다면, 논문은 "효과적 영지식" 개념이 실세계에서 작동하도록 하여, 이론적인 논리 퍼즐을 실질적인 프라이버시 방패로 바꾸는 방법을 개설합니다.

요약하자면, 이 논문은 단순히 "이것이 작동한다"라고 말하는 것이 아니라, 우리가 어떤 문제들이 실제로 컴퓨터가 빠르게 깨뜨리기에는 너무 어렵다는 것을 받아들인다면, 왜 그것이 작동하는지에 대한 논리적 가교를 구축합니다. 이 논문은 복잡한 암호학적 아이디어를 논리, 그림자, 그리고 증명하기 어려운 것들의 힘에 관한 이야기로 바꿉니다.