A Complexity-Theoretic Approach to Proofs of Space

기술 요약: 공간 증명(Proof of Space)에 대한 복잡도 이론적 접근

문제 정의
Dziembowski 등[DFKP15]에 의해 도입된 공간 증명(PoS)은 증명자(Prover)가 상당한 양의 지속적인 메모리를 할당했음을 효율적인 검증자(Verifier)에게 확신시키기 위한 2단계 프로토콜이다. 이 프로토콜은 증명자가 데이터를 저장하는 초기화 단계(긴 기간)와 검증자가 데이터가 여전히 저장되어 있는지 도전하는 실행 단계(짧은 기간)로 구성된다.

기존 PoS 프로토콜의 결정적인 한계는 그 보안 증명이 무작위 오라클 모델(Random Oracle Model, ROM)이나 임의적인 암호학적 가정에 크게 의존한다는 점이다. 구체적으로, 이들은 무작위 오라클 쿼리의 동시적인 압축 불가능성(incompressibility)과 추출 가능성(extractibility)에 의존한다. 현재까지, 표준 암호학적 가정만을 기반으로 플레인 모델(plain model, 무작위 오라클 없이)에서 안전한 것으로 알려진 구성은 존재하지 않는다. 이러한 구성의 증명 가능한 보안을 위해 충분한 암호학적 해시 함수에 관한 깨끗하고 반증 가능한(falsifiable) 가정이 부족한 실정이다.

방법론 및 프레임워크
본 논문은 **결정론적 난해화 가정(derandomization assumptions)**과 **암호학적 가정(cryptographic assumptions)**을 결합하여 플레인 모델에서 PoS를 구축하기 위한 기초적인 프레임워크를 제시한다. 핵심 통찰은 PoS가 역설적으로 짧은 설명(충분한 시간 $T$가 주어졌을 때)으로부터는 압축 가능하면서도, 약간 더 짧은 설명(짧은 시간 $t$ 내에서)으로부터는 압축 불가능한 문자열 $\sigma$를 필요로 한다는 것이다.

저자들은 이를 계산적 깊이(computational depth)(Antunes 등[AFvMV06]이 도입함)라는 복잡도 이론적 개념을 사용하여 정식화한다. 이들은 높은 계산적 깊이를 가진 함수 $f$를 찾고자 한다:

1. 장기 압축 가능성: $f(x)$는 짧은 시드 $x$로부터 시간 $T$ 내에 계산될 수 있다.
2. 단기 압축 불가능성: $f(x)$는 $x$가 주어지더라도 시간 $t$ 내에서는 $f(x)$보다 짧은 어떠한 설명으로부터도 재구성될 수 없다.

구성은 다음 세 가지 주요 단계를 거친다:

1. 고깊이 함수(High-Depth Functions) 구축:
   저자들은 **비결정론적 구별자(nondeterministic distinguishers)에 대한 시드 확장 의사 난수 생성기(seed-extending PRGs)**를 활용한다. $E = \text{DTIME}[2^{O(n)}]$가 지수 크기의 비결정론적 회로를 필요로 한다는 가정( $\text{AM} = \text{NP}$를 보여주는 데 사용되는 표준 가정) 하에, 저자들은 비결정론적 회로에 대해 어려운 PRG를 구축한다.

   • 압도적인 확률의 압축 불가능성을 달ras하기 위해(단순히 눈에 띄는 오차 수준이 아닌), 저자들은 비결정론적 구별자에 대한 **곱셈적 PRG(multiplicative PRGs)**를 채택한다. 이는 무시할 수 있는 사건의 확률을 보존하여, PRG의 출력이 압도적인 확률로 압축 불가능하게 유지되도록 한다.
   • 근사적 압축 불가능성(해밍 거리 오차에 대한 탄력성)을 처리하기 위해, 저자들은 PRG를 **리스트 디코딩 가능한 오류 정정 코드(list-decodable ECC)**와 결합한다. 이는 공격자가 $f(x)$와 유사한 문자열을 복구하더라도 원래의 문자열이 압축 불가능하게 유지되도록 보장한다.

2. 추출 레마(The Extraction Lemma):
   중심적인 기술적 기여는 추출 레마(Extraction Lemma)(Lemma 11)이다. 이는 만약 증명자가 작은 상태 $S$를 유지하며 비무시적인 확률로 검증 챌린지에 성공적으로 응답할 수 있다면, 기저의 문자열 $y = f(x)$는 근사적으로 압축 가능하다는 것을 명시한다.

   • 이 레마는 **해팅 셋 생성기(Hitting Set Generator, HSG)**를 사용하여 "유용한" 챌린지 인덱스 집합을 결정론적으로 선택함으로써, 저장된 문자열의 큰 부분을 커버하도록 한다.
   • 이를 통해 추출기(extractor)는 시간 $t$ 내에 증명자의 작은 상태로부터 $y$의 대부분의 비트를 복구할 수 있으며, 이는 $f$의 가정된 압축 불가능성에 모순된다.

3. 프로토콜 인스턴스화(Protocol Instantiation):
   프레임워크는 두 가지 특정 PoS 프로토콜로 인스턴스화되며, 이들은 암호학적 가정과 저장 공간 오버헤드에서 차이를 보인다:

   • 구성 1 (SNARG 기반): $P$를 위해 **준유니버설 비상호작용 증명(Semi-Universal Non-Interactive Argument, SNARG)**을 사용한다. 증명자는 $f(x)$의 머클 루트(Merkle root)와 해당 루트가 $f(x)$에 대응한다는 간결한 증명을 저장한다. 이는 $P$에 대한 SNARG의 존재(강한 가정)에 의존하지만, 정직한 증명자를 위해 최적에 가까운 저장량($N$ 비트)을 제공한다.
   • 구성 2 (Kilian 기반): PCP에 기반한 Kilian의 상호작용 증명 시스템과 **충돌 저항 해시 함수(CRHF)**를 사용한다. 증명자는 $f(x)$의 계산에 대한 PCP 문자열을 저장해야 하므로 더 높은 정직한 저장 요구량($N + \tilde{O}(T)$)을 갖지만, 더 약한 암호학적 가정(CRHF + 결정론적 난해화)에 의존한다.

주요 결과
본 논문은 다음의 정리들을 (비형식적으로) 확립한다:

• 정리 1: $E$가 지수 크기의 비결정론적 회로에 대해 어렵다고 가정할 때, 시간 $t$ 내에 $N - O(\rho N \log(1/\rho))$ 크기에 대해 압축 불가능한 명시적 함수들이 존재한다.
• 정리 2 (SNARG 인스턴스화): $E$가 지수 크기의 비결정론적 회로에 대해 어렵고, 일방향 함수(one-way functions) 및 $P$에 대한 준유니버설 SNARG가 존재한다고 가정할 때, 정직한 증명자가 $N$ 비트를 저장하고, $(1-o(1))N$ 비트를 사용하는 모든 증명자에 대해 안전한 PoS가 존재한다.
• 정리 3 (CRHF 인스턴스화): $E$가 지수 크기의 비결정론적 회로에 대해 어렵고 충돌 저항 해시 함수(CRHF)가 존재한다고 가정할 때, 정직한 증명자가 $N$ 비트를 저장하고, $N^{1/c}$ 비트(어떤 상수 $c$에 대해)를 사용하는 모든 증명자에 대해 안전한 PoS가 존재한다.

의의 및 주장
저자들은 자신들의 연구가 플레인 모델에서 PoS를 위한 교육적으로 깔끔하고 일반적인 가능성(generic feasibility) 결과를 제공한다는 점을 강조한다.

• ROM 장벽 타파: 저자들은 무작위 오라클 없이, 대신 표준적인 결정론적 난해화 가정(비결정론적 회로에 대한 $E$의 어려움)과 표준 암호학적 프리미티브를 결합하여 PoS를 구축할 수 있음을 입증한다.
• 트레이드오프(Trade-offs): 본 논문은 암호학적 가정과 저장 효율성 사이의 트레이드오프를 조명한다. SNARG 기반 접근 방식은 정직한 증명자의 저장량을 최소화하지만 더 강한 가정을 요구한다. Kilian 기반 접근 방식은 더 약한 가정(CRHF)을 사용하지만, 정직한 증명자가 $f(x)$의 PCP를 저장해야 하므로 저장량이 크게 증가한다.
• 한계: 저자들은 자신들의 초점이 정교한 위협 모델이나 실제적인 프로토콜이 아닌 이론적 가능성에 있음을 명시적으로 밝힌다. 또한, 이러한 아이디어들을 ROM 기반 PoS에서 자주 파생되는 관련 객체인 **메모리 하드 함수(Memory-Hard Functions, MHFs)**를 구축하는 데 적용하는 것이 즉각적으로 명확하지 않다는 점을 언급한다. 아울러, 단일 증명자가 여러 검증자와 상호작용하는 구성(composition)을 다루는 경우 저장 비용이 분할(amortize)되지 않도록 보장하기 위해서는 추가적인 작업이 필요함을 인정한다.

요약하자면, 본 연구는 복잡도 이론과 암호학적 프로토콜 사이의 간극을 메우며, PoS에 필요한 "어려움"이 휴리스틱한 무작위 오라클 모델이 아니라 근본적인 결정론적 난해화 가정으로부터 도출될 수 있음을 보여준다.