Experimental asymmetric relativistic zero-knowledge proofs with unconditional security

본 논문은 특수 상대성 이론과 양자 비국소성을 활용하여 이전의 대칭적 방식이 가진 비실용적인 라운드 복잡성을 극복함으로써, 양자 공격에 대해 무조건적 보안을 달성하는 효율적이고 실험적으로 검증된 비대칭 상대론적 영지식 증명 프로토콜을 제시한다.

핵심

개요: 비밀을 말하지 않고도 당신이 알고 있음을 증명하기

당신에게 보물 지도가 있다고 상상해 보세요. 당신은 의심 많은 경비병에게 당신이 실제로 그 지도를 가지고 있다는 것을 증명하고 싶습니다. 하지만 지도를 보여주고 싶지는 않습니다(지도를 훔쳐갈 수도 있으니까요). 또한 보물이 어디에 있는지도 알려주고 싶지 않습니다. 당신은 그저 "나는 길을 알고 있다"는 사실만을 증명하고 싶을 뿐입니다.

디지털 세상에서는 이를 **영지식 증명(Zero-Knowledge Proof, ZKP)**이라고 부릅니다. 이것은 당신의 비밀번호나 은행 잔고를 밝히지 않고도, 당신이 누구인지 또는 거래를 위한 충분한 돈을 가지고 있는지 증명할 수 있게 해주는 마법 같은 기술입니다.

문제점: 양자 괴물

수십 년 동안 이러한 디지털 마법 기술들은 인간에게는 풀기 어렵지만 컴퓨터에게는 쉬운 수학 퍼즐에 의존해 왔습니다. 하지만 과학자들은 양자 컴퓨터라는 초고속 괴물을 만들어내고 있습니다. 이 괴물들은 기존의 수학 퍼즐들을 거의 즉시 풀어버려 현재의 디지털 자물쇠 보안을 무너뜨릴 수 있습니다.

우리는 더 이상 수학 퍼즐에 의존하지 않는 새로운 종류의 자물쇠가 필요합니다. 우리는 물리학 법칙에 기반한 자물쇠가 필요합니다.

해결책: "빛의 속도" 자물쇠

이 논문은 **상대론적 영지식 증명(Relativistic Zero-Knowledge Proof)**이라는 새로운 유형의 증명을 소개합니다. 어려운 수학에 의존하는 대신, 이 방식은 빛의 속도에 의존합니다.

비유: 머리가 두 개 달린 용
머리가 두 개 달린 용(A 머리와 B 머리라고 부릅시다)이 있다고 상상해 보세요. 당신은 판사에게 이 용이 진짜임을 증명하고 싶지만, 두 머리가 서로 대화하게 해서는 안 됩니다.

• 판사는 A 머리로부터 멀리 떨어져 서 있습니다.
• 또 다른 판사는 B 머리로부터 멀리 떨어져 서 있습니다.
• 그 거리는 너무 멀어서, 빛(우주에서 가장 빠른 것)조차 질문에 답하는 시간 동안 A 머리에서 B 머리로 이동할 수 없습니다.

A 머리와 B 머리는 거짓말을 맞추기 위해 서로 통신할 수 없기 때문에, 그들은 진실을 말할 수밖에 없습니다. 만약 그들이 속임수를 쓰려고 한다면, 물리학의 법칙(특히 빛보다 빠르게 움직일 수 없다는 법칙)이 그들을 잡아낼 것입니다.

연구팀의 성과

연구진은 이 "빛의 속도" 증명의 작동하는 버전을 구축했습니다. 이들은 다음과 같이 개선했습니다:

1. 기존 방식은 너무 느렸습니다: 이전의 이 "두 머리 달린 용" 증명 시도들은 마치 거대한 미로를 모든 경로를 하나씩 걸어가며 푸는 것과 같았습니다. 만약 지도(그래프)가 크다면, 증명을 마치는 데 수천 년이 걸릴 수도 있었습니다. 이론적으로는 가능했지만 실제로는 쓸모가 없었습니다.
2. 새로운 방식은 빠릅니다: 연구팀은 더 똑똑한 비대칭(asymmetric) 버전을 설계했습니다. 이것은 용의 한쪽 머리가 모든 힘든 일을 다 하고, 다른 쪽 머리는 그저 지켜보기만 하는 것과 같습니다.
   • 결과: 그들은 소요 시간을 "수천 년"에서 0.22초로 단축했습니다.
   • 비용: 이들은 약간 더 많은 "무작위성"(마치 카드 덱을 더 많이 섞는 것과 같은)을 사용했지만, 전체 데이터 양은 현대의 하드 드라이브에 들어갈 정도로 충분히 작았습니다(약 430MB).

실험

이것이 현실 세계에서 작동함을 증명하기 위해, 연구진은 난징 대학교에서 실험을 설정했습니다:

• 두 대의 컴퓨터("머리")를 300미터 떨어진 서로 다른 건물에 배치했습니다.
• 고속 레이저와 GPS 시계를 사용하여 컴퓨터들이 빛보다 빠르게 서로 통신할 수 없도록 했습니다.
• 컴퓨터들에게 복잡한 지도를 단 세 가지 색으로 칠하는 방법(고전적인 수학 퍼즐)을 색깔을 보여주지 않고도 알고 있음을 증명하도록 요청했습니다.
• 결과: 컴퓨터들은 전체 증명을 0.22초 만에 완료했습니다.

이것이 중요한 이유

이 논문은 다음과 같은 이유로 이것이 중요한 진전이라고 주장합니다:

• 양자 내성(Quantum-Safe): 양자 컴퓨터가 코드를 깨려고 시도하더라도, 물리 법칙(빛의 속도)을 깰 수는 없기 때문에 속일 수 없습니다.
• 실용성: 실제로 사용하기에는 너무 느렸던 이전 버전들과 달리, 이 방식은 온라인 뱅킹이나 투표와 같은 실제 생활에서 사용할 수 있을 만큼 빠릅니다.
• 무조건적 보안(Unconditional): "우리는 이 수학이 어렵다고 생각한다"는 추측에 의존하는 것이 아니라, "빛에는 속도 제한이 있다는 것을 우리는 알고 있다"는 사실에 의존합니다.

요-약

연구진은 거짓말쟁이를 막기 위해 빛의 속도를 이용한다는 이론적인 아이디어를 가져와서, 이를 순식간에 수행하는 작동하는 기계를 만들어냈습니다. 그들은 한쪽 시스템이 더 많은 일을 하게 함으로써 속도가 너무 느리다는 문제를 해결했고, 이를 통해 전체 과정을 매우 빠르고 양자 컴퓨터로부터 안전하게 만들었습니다.

기술 요약

기술 요약: 실험적 비대칭 상대론적 영지식 증명 (Unconditional Security를 갖춘)

문제 정의

영지식 증명(ZKP)은 암호화폐 및 스마트 계약과 같은 디지털 경제에서 신뢰와 프라이버시를 구축하는 데 필수적입니다. 그러나 고전적인 ZKP 프로토콜은 계산적 가정(예: 일방향 함수의 존재)에 의존하며, 이는 미래의 양자 공격에 취약하게 만듭니다. 양자 ZKP가 잠재적인 대안을 제시할 수 있지만, 복제 불가능성 정리(no-cloning theorem)로 인한 양자 리와인딩(rewinding)의 어려움과 무조건적으로 안전한 양자 비트 커밋먼트(bit commitment) 구현의 불가능성 등 상당한 구현상의 난관에 봉착해 있습니다.

상대론적 ZKP(RZKP)는 계산적 가정 대신 특수 상대성 이론의 원리(특히 신호 전달 불가 원리, no-signaling principle)를 활용함으로써 해결책으로 부상했습니다. 최근의 한 돌파구는 그래프 3-채색 문제(graph three-coloring problem)에 대한 대칭적 RZKP를 입증했습니다. 그러나 이 대칭적 프로토콜은 양자 상관관계가 있는 증명인(prover)들에 대한 양자 건전성(quantum soundness)을 보장할 때 과도한 비효율성을 겪습니다. 양자 건전성을 달-성하기 위해, 대칭적 프로토콜은 그래프의 간선 수 $|E|$에 대해 $O(|E|^4)$의 라운드 복잡도를 요구하며, 이는 현실적인 크기의 그래프에 대해서는 실현 불가능한 실행 시간과 막대한 무작위성 비용을 초래합니다.

방법론

저자들은 이전의 대칭적 접근 방식이 가진 효율성 한계를 극복하면서도, 양자 얽힘을 공유하는 증명인들에 대해 무조건적 보안을 유지하도록 설계된 비대칭 상대론적 GMW ZKP 프로토콜을 제안하고 실험적으로 구현하였습니다.

프로토콜 설계

프로토콜은 두 개의 공간적으로 분리된 증명인-검증인 쌍($P_1-V_1$ 및 $P_2-V_2$)을 포함하며, 그래프 $G(V, E)$가 채색 정보를 드러내지 않고 3-채색 가능함을 증명하기 위해 $m$개의 대화형 라운드에 걸쳐 작동합니다.

1. 준비 단계 (Preparation): 증명인 $P_1$과 $P_2$는 무작위 색상 치환 $\pi$와 무작위 값들의 집합 $B = \{b_k\}$를 공유합니다.
2. 쿼리 단계 (Query Phase): 검증인 $V_1$은 $P_1$에게 무작위 쿼리 $X = \{x_k\}$를 보냅니다.
3. 커밋 단계 (Commit Phase): $P_1$은 $a_k = x_k \cdot y_k - b_k$ (여기서 $y_k$는 색상)인 커밋먼트 $A = \{a_k\}$를 계산하여 $V_1$에게 보냅니다.
4. 챌린지 단계 (Challenge Phase): 검증인 $V_2$는 무작위 간선 $C = \{i, j\}$를 선택하여 $P_2$에게 보냅니다.
5. 공개 단계 (Reveal Phase): $P_2$는 색상 $Y(C)$와 그에 대응하는 값 $B(C)$를 $V_2$에게 공개합니다.
6. 체크 단계 (Check Phase): 검증인들은 상대론적 제약 조건(시간 지연 $|t_1 - t_4| < \tau$ 및 $|t_2 - t_3| < \tau$, 여기서 $\tau = d/c$를 만족하여 $P_1$과 $P_2$ 사이의 신호 전달이 없음을 보장)과 논리적 일관성(색상이 서로 다르고 커밋먼트와 일치하는지 여부)을 확인합니다.

이론적 분석

저자들은 양자 건전성 문제를 다룹니다. 클래식 프로토콜에서는 비트 커밋먼트가 강력하게 결합(binding)되는 것과 달리, 상대론적 비트 커밋먼트는 "합-결합(sum-binding)"만을 보장합니다. 저자들은 악의적인 양자 증명인들이 유효하지 않은 간선에 대해 속임수를 쓸 확률이 비국소적 CHSH$_{Q(2)}$ 게임의 양자 값에 의해 상한선이 정해짐을 입증했습니다. 이 게임과 프로토콜의 건전성 오차를 연관시킴으로써, 저자들은 엄격한 양자 건전성 오차 $\delta$의 상한을 도출했습니다.

실험적 구현

연구팀은 다음을 사용하여 개념 증명 실험을 구현했습니다:

• 하드웨어: 저지연 처리를 위한 FPGA(Field-Programmable Gate Arrays) 및 고정밀 GPS 시간 동기화 서버(원자 시계 포함).
• 설정: 300미터 떨어진 두 증명인-검증인 쌍 (이는 시간 차이 $\tau = 1000$ ns에 해당함).
• 그래프: $|V| = 588$개의 정점과 $|E| = 1097$개의 간선을 가진 3-채색 가능 그래프.
• 실행: 실험은 모든 필요한 대화형 라운드를 약 0.22초 만에 완료했습니다.

주요 기여

1. 효율적인 비대칭 프로토콜: 저자들은 이전의 양자 건전한 대칭 프로토콜의 라운드 복잡도를 $O(|E|^4)$에서 $O(|E|)$로 줄인 비대칭 상대론적 GMW ZKP를 설계했습니다. 이는 GMW 프레임워크 내에서 두 증명인 상대론적 비트 커밋먼트를 활용하여 증명과 일관성 체크가 단일 라운드 내에서 동시에 발생할 수 있도록 함으로써 달성되었습니다.
2. 양자 건전성 증명: 비국소적 CHSH$_{Q(2)}$ 게임과 증명인의 속임수 확률을 연관시켜, 계산적 가정을 배제하고 양자 건전성의 상한을 설정하는 엄격한 양자 건전성 증명을 제공했습니다.
3. 실험적 실현: 300미터 분리 거리에서 프로토콜을 성공적으로 실행하여, 요구되는 실행 시간과 무작위성 비용이 실제 배포 가능한 수준임을 입증했습니다.

결과

• 라운드 복잡도: 프로토콜은 건전성 오차 $e^{-k}$를 달로 하기 위해 $m = 2k|E|$ 라운드를 요구합니다. 실험 파라미터($|E|=1097, k=100$)의 경우, 약 $2.2 \times 10^5$ 라운드가 소요되었습니다.
• 실행 시간: 전체 실험은 0.22초 만에 완료되었습니다. 대조적으로, 이전의 양자 건전한 대칭 프로토콜 [23]은 동일한 그래프에 대해 동일한 보안 수준을 달성하기 위해 약 6.72만 년이 필요했을 것입니다.
• 무작위성 비용: 실험의 전체 무작위성 비용은 430.81 MB였습니다. 대칭 프로토콜 [23]은 동일한 작업을 위해 약 **5.92 x $10^9$ GB (5.92 엑사바이트)**가 필요했을 것입니다.
• 보안성: 시간 차이 $|t_1 - t_4|$와 $|t_2 - t_3|$는 GPS 동기화 오차를 고려하더라도 일관되게 1000 ns 임계값 미만으로 측정되어, 상대론적 신호 전달 불가 제약 조건을 충족했습니다.

의의 및 주장

본 논문은 특수 상대성 이론과 양자 이론을 통합하여 계산적 어려움 가정에 의존하지 않고도 양자 공격에 안전한 무신뢰(trustless) 암호 시스템을 구축할 수 있는 강력한 잠재력을 보여준다고 주장합니다.

주요 의의에 대한 핵심 주장은 다음과 같습니다:

• 실질적 실현 가능성: 라운드 복잡도를 $O(|E|^4)$에서 $O(|E|)$로 줄임으로써, RZKP를 이론적 구성물에서 적절한 크기의 그래프를 다루는 실제 상황에 배치 가능한 기술로 변모시켰습니다.
• 무조건적 보안: 프로토콜은 신호 전달 불가 원리에 기반한 양자 건전성과 영지식 특성을 제공하며, 따라서 미래의 양자 컴퓨팅 발전에도 견고합니다.
• 확장 가능성 잠재력: 비대칭적 특성으로 인해 한쪽 증명인-검증인 쌍($V_1-P_1$)에 더 높은 계산 부하가 걸리지만, 저자들은 이것이 실행 가능한 실행 시간을 달-성하기 위한 필연적인 트레이드오프라고 주장합니다. 그들은 이 프로토콜이 스마트폰과 같은 일상적인 기기에서도 구현될 수 있다고 제안합니다.
• 미래 응용 분야: 저자들은 블록체인, 스마트 계약, 익명 전자 투표, 온라인 경매와 같은 프라이버시 민감 분야에서의 잠재적 응용을 강조합니다. 또한, 신원 확인을 위한 지식의 영지식 증명(ZKPoK)으로 이 프레임워크를 확장할 가능성도 언급했습니다.

저자들은 실용적 배포를 위한 과제에 대해 겸허한 태도를 유지하며, 증명인의 정확한 위치를 검증하고 계산 부하를 관리하는 등의 광섬유 네트워크 기반의 실질적 구현 문제는 향후 연구를 위한 열린 문제로 남겨두었습니다.