기술 요약: 퀀텀 페시랜드 (Quantum Pessiland)

1. 문제 정의 및 동기

본 논문은 임팔리아초(Impagliazzo) [Imp95]가 정의한 고전적 "페시랜드(Pessiland)"에 대응하는 이론적 세계인 "퀀텀 페시랜드(Quantum Pessiland)"의 존재를 다룬다. 고전적 페시랜드에서는 NP에 속하는 문제들이 평균적으로는 어렵지만, **일방향 함수(One-Way Functions, OWFs)**는 존재하지 않는다. 거의 모든 고전적 암호 프리미티브가 OWF의 존재를 전제로 한다는 점을 고려할 때 [IL89], 페시랜드는 평균적인 난해한 문제가 존재함에도 불구하고 본질적으로 고전 암호가 불가능한 세계를 의미한다.

양자 영역에서의 지형은 다르다. 최근 연구들 [Kre21, MY22, AQY22]은 양자 암호(예: 프라이빗 키 양자 머니, 비밀 키 암호화, 디지털 서명)가 OWF의 부재 상황에서도 존재할 수 있음을 보여주었다. 이는 대신 의사 난수 상태 생성기(Pseudorandom State Generators, PRSGs), 일방향 상태 생성기(One-Way State Generators, OWSGs), 일방향 퍼즐(One-Way Puzzles, OWPuzzs), 그리고 **EFI 쌍(Extremely Far but Indistinguishable pairs)**과 같은 더 약한 프리미티브에 의존하여 가능하다.

핵심 질문은 다음과 같다: NP(또는 관련 하위 클래스)가 평균적으로 어렵지만, 이러한 더 약한 양자 암호 프리미티브조차 존재하지 않는 세계가 존재하는가? 만약 그러한 세계가 존재한다면, 이는 양자 암호가 단순히 고전 암호의 완화된 형태가 아니라 근본적으로 다른 난해성 가정을 필요로 하거나, 혹은 특정 평균적 난해성 설정에서 양자 암호가 불가능할 수도 있음을 시사한다.

2. 방법론 및 기술 개요

저자들은 퀀텀 페시랜드의 존재를 증명하기 위해 상대화된 세계(오라클 분리)를 구축한다. 이들의 접근 방식은 무작위 치환 오라클과 PSPACE 오라클을 활용했던 Wee [Wee06]의 고전적 페시랜드 구축 방식을 변형하고 확장한 것이다.

2.1 오라클 구축

저자들은 결과가 성립하는 오라클을 다음과 같이 정의한다:

• 고전적 오라클 ($O$): 일련의 균등 무작위 치환 $\pi = (\pi_1, \pi_2, \dots)$에 대한 검증 오라클 $V^\pi$와 고정된 PSPACE 완전 오라클($QBF$)로 구성된다.
  • $V^\pi(\ell, u, v) = 1$ (단, $|u|=|v|=\ell$ 이고 $\pi_\ell(u)=v$ 인 경우), 그 외에는 $0$.
• 양자 오라클 ($U$): EFI 쌍 결과를 위해, 저자들은 회로에 의해 생성된 양자 상태를 구별하기 위해 최적의 측정을 수행하는 헬스트롬 오라클(Helstrom oracle)(유니터리 오라클)을 $V$와 함께 도입한다.

2.2 핵심 과제: 보조 입력 (Auxiliary Inputs)

보조 입력이 있는 프리미티브를 배제하는 것은 중요한 기술적 장애물이다. 고전적 설정에서 Wee [Wee06]는 무작위 치환 오라클과 PSPACE 오라클을 사용하여 보조 입력이 있는 OWF를 배제했다. 당시 그는 소수의 "헤비 쿼리(heavy queries)"에 대한 오라클 값이 하드와이어링(hardwired)될 수 있다면, 어떤 다항식 크기의 회로라도 오라클이 없는 회로로 근사될 수 있음을 보여주었다. 그러나 이 기법은 두 가지 이유로 양자 설정에서 실패한다:

1. 중첩 쿼리 (Superposition Queries): 양자 알고리즘은 중첩 상태에서 오라클을 쿼리하므로, (고전적 입력의 비율에 기반한) 고전적 "헤비 쿼리"의 개념이 정의되지 않는다.
2. 균등성 vs 비균등성 (Uniformity vs Non-uniformity): 보조 입력이 있는 양자 프리미티브는 무한한 집합의 어려운 보조 입력을 받는 균등(uniform) 공격자를 대상으로 정의된다. 비균등한 "하드와이어링" 전략(advice)은 불충분하며, 공격자는 필요한 정보를 학습하는 균등한 알고리즘에 의해 깨져야 한다.

2.3 패칭 렘마 (Patching Lemma, 핵심 기술 혁신)

이러한 장애물을 극복하기 위해, 저자들은 패칭 렘마(Patching Lemma) (정리 5.2)를 도입한다. 이 렘마는 보조 입력 $x$가 주어졌을 때, "패치" $\Gamma$ (삼중항 $(\ell, u, v)$의 유한 집합, 여기서 $V^\pi(\ell, u, v)=1$)를 학습하는 균등 양자 다항 시간(QPT) 추출기 $E$를 제공한다.

• 메커니즘: 추출기는 공격자 알고리즘 $A$를 무작위 쿼리까지 실행하고, 쿼리 레지스터를 측정하며, 고전적으로 오라클 $V^\pi$를 확인한다. 만약 쿼리가 "양수(positive)"라면 (즉, $V^\pi=1$), 이를 패치에 추가한다.
• 지수 모멘트 바운드 (Exponential Moment Bound): 모든 $2^n$개의 보조 입력에 대해 단순한 합집합 상한(union bound)을 적용하면 실패하지만, "발견(discoveries)"(패치에 요소를 추가하는 것)의 횟수는 발견 횟수가 많아질 확률이 지수적으로 작아지는 분포를 따른다는 것이 핵심 통찰이다. 저자들은 지수 모멘트를 제한함으로써, 최악의 입력에 대해서도 발견되는 기대 횟수가 입력 길이($O(n)$)에 선형임을 보여준다. 이를 통해 무작위 치환 $\pi$의 선택에 대해 확률 1로 모든 입력에 대해 동시에 식별 가능성을 유지하면서도 패치를 다항식 크기로 유지할 수 있다.

2.4 난해성 증명

• 평균적 난해성: 저자들은 양자 어드바이스를 가진 양자 치환 역전(quantum permutation inversion)에 대한 최근의 타이트한 경계 [ABC+26]를 골드라이히-레빈 정리 [KT24, AC02]와 결합하여, 치환을 역전하는 것(또는 관련 탐색 문제를 해결하는 것)이 양자 어드바이스를 가진 QPT 알고리즘에 대해서도 여전히 어렵다는 것을 보여준다.
• 프리미티브의 부재: 패칭 렘마를 사용하여, 보조 입력이 있는 임의의 OWPuzz 또는 EFI 쌍 후보가 오라클이 없는 버전(또는 PSPACE/헬스트롬 오라클만을 사용하는 버전)으로 "패치"될 수 있음을 보여준다. PSPACE/헬스트롬 오라클은 효율적인 역전 또는 식별을 허용하므로, 원래의 프리미티브는 파괴된다.

3. 주요 결과

본 논문은 퀀텀 페시랜드의 존재에 관한 두 가지 주요 정리를 확립한다:

정리 1.1 (고전적 오라클)

다음이 성립하는 고전적 오라클 $O$가 존재한다:

1. 난해성: $L_O \in UP^O \cap coUP^O$인 언어가 존재하며, 이는 다항식 크기의 오라클 의존 양자 어드바이스를 가진 QPT 알고리즘에 대해 강력하게 평균적으로 어렵다. (결과적으로 $NP \cap coNP$ 또한 어렵다.)
2. 탐색 난해성: $R_O \in TFUP^O$인 전체 유일 탐색 관계가 존재하며, 이는 동일한 클래스의 알고리즘에 대해 평균적으로 어렵다.
3. 양자 이점 없음: $SampBQP^O = SampBPP^O$이다. 즉, 샘플링 기반의 양자 이점은 존재하지 않는다.
4. 암호 부재: 고전적으로 안전한 보조 입력 일방향 퍼즐(OWPuzzs)은 존재하지 않는다.

정리 1.2 (양자 오라클)

다음이 성립하는 양자 유니터리 오라클 $U$와 고전적 오라클 $V$가 존재한다:

1. 난해성: $L_V \in UP^V \cap coUP^V$와 관계 $R_V \in TFUP^V$는 양자 어드바이스를 가진 QPT 알고리즘에 대해 평균적으로 어렵다.
2. 암호 부재: 보조 입력이 있는 EFI 쌍은 존재하지 않는다.

따름정리

• 따름정리 1.3: 고전적 오라클에 대해, $PP$는 양자 어드바이스를 가진 QPT에 대해 강력하게 평균적으로 어렵지만, OWPuzzs는 존재하지 않는다. 이는 $P^{\#P} \not\subseteq_{i.o.} BQP/qpoly$임을 시사한다.
• 따름정리 1.4: 고전적 오라클에 대해, $UP \cap coUP$의 평균적 난해성에도 불구하고 비효율적 검증자 양자성 증명(Inefficient-Verifier Proofs of Quantumness, IV-PoQ)은 존재하지 않는다.

4. 의의 및 시사점

본 논문은 다음과 같은 의의를 주장한다:

1. 퀀텀 페시랜드의 존재: 평균적 난해성(특히 $UP \cap coNP$에 대해)은 존재하지만 양자 암호(고전적 보안 또는 양자 보안 변형인 OWPuzzs 및 EFI 쌍 모두)가 불가능한 세계가 존재함을 증명한다. 이는 고전적 사례에서 OWF의 부재가 모든 고전 암호의 부재를 의미하는 것과 대조적이다. 여기서는 $UP \cap coUP$가 어려움에도 불구하고 양자 프리미티브의 부재가 보여진다.
2. 양자 이점의 한계: 이 세계에서의 결과인 $SampBQP = SampBPP$는$UP \cap coUP$의 평균적 난해성만으로는 샘플링 기반 양자 이점을 보장하기에 불충분함을 나타낸다.
3. 기법의 분리: 본 논문은 $P^{\#P} \not\subseteq_{i.o.} BQP/qpoly$로부터 OWPuzzs를 구축하는 문제에 대한 답을 다룬다. 이 분리가 성립함에도 불구하고 이들의 오라클 세계에서는 OWPuzzs가 존재하지 않으므로, 저자들은 OWPuzzs를 오직 이 복잡도 이론적 가정으로부터 구축하기 위해서는 비상대화적(non-relativizing) 증명 기법이 필요하다는 결론을 내린다. 이는 Khurana와 Tomer [KT25]가 제기한 열린 문제에 대한 부분적인 부정적 답변을 제공한다.
4. 기술적 진보: **패칭 렘마(Patching Lemma)**는 중첩 쿼리가 존재하는 환경에서 보조 입력을 가진 균등 공격자를 처리하기 위해 특별히 설계된, Wee의 근사 렘마에 대한 균등한 양자 아날로그로 제시된다.

저자들은 자신들의 결과가 오라클에 상대적이며, 이러한 세계가 실제(unrelativized) 세계에 존재하는지에 대한 질문을 해결하는 것은 아니라고 명시하며 겸허한 입장을 유지한다. 이들은 본 연구가 상대화된 설정에서 평균적 난해성과 양자 암호 프리미티브의 존재 사이의 **분리(separation)**를 명확히 한다는 점을 강조한다.