EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity

기술 요약: 일방향 퍼즐(One-Way Puzzles)이 없는 EFI 쌍

1. 문제 정의 및 동기

양자 암호학은 현재 고전 암호학의 일방향 함수(OWF)와 유사한 단일 최소 원시 함수(minimal primitive)가 결여되어 있습니다. 이러한 최소 가정에 대한 두 가지 주요 후보가 등장했습니다:

1. EFI 쌍 (Efficiently preparable, Statistically far, Computationally Indistinguishable): 효율적으로 생성 가능하고, 통계적으로는 멀리 떨어져 있으나, 계산적으로는 구별 불가능한 혼합 양자 상태의 쌍입니다. EFI 쌍은 양자 비트 커미트먼트(quantum bit commitment)와 동등하며, 안전한 다자간 계산을 가능하게 합니다.
2. 일방향 퍼즐 (OWPuzzs): 샘플러(sampler)가 클래식 퍼즐 $s$와 키 $k$를 생성하고, 무제한 능력을 가진 검증자(verifier)가 키를 확인하는 쌍 $(Samp, Ver)$입니다. OWPuzzs는 EFI 쌍을 함의하지만, 그 역은 미해결 문제입니다.

핵심적인 미해결 문제는 EFI 쌍에 필요한 난해함(양자 상태의 구별 불가능성)이 OWPuzzs에 필요한 클래식 평균 사례 난해함(탐색 문제의 역산)을 반드시 함의하는가 하는 것입니다. 구체적으로, EFI 쌍은 존재하지만 OWPuzzs(비효율적인 검증자를 포함하더라도)는 존재하지 않는 오라클이 존재하는가 하는 문제입니다.

2. 방법론 및 오라클 구성

저자는 이러한 원시 함수들을 분리하는 단일 결정론적 클래식 오라클 $\mathcal{O}'$를 구성합니다. 이 오라클은 두 개의 층으로 구성됩니다:

1. 상태 소스 ($R$): 입력 $(b, 1^\lambda)$에 대해, 새로운 혼합 상태 $\rho_{b,\lambda}$의 복사본을 반환합니다. 이 상태들은 하르-무작위(Haar-random) 절반 차원 부분 공간 $H \subseteq \mathbb{R}^n$ (여기서 $n=2^\lambda$)으로부터 구성됩니다. 구체적으로, $\rho_0$는 $H$ 상의 최대 혼합 상태(maximally mixed state)이고, $\rho_1$은 $H^\perp$ 상의 최대 혼합 상태입니다.
2. **카운팅 오라클 ($Count$):** 클래식 출력을 갖는 오라클 보조 샘플러$C$의 기술(description)이 주어졌을 때, 출력 확률 $\Pr[C^{\mathcal{O}}(1^\lambda) = x]$의 정확한 비트를 반환하는 클래식 오라클입니다. 순환 참조를 피하기 위해, 쿼리는 **계수(rank)**에 따라 계층화됩니다: 계수 $r$인 쿼리는 계수가 $r$보다 엄격히 낮은 샘플러들의 오라클 호출에 대해서만 질문할 수 있습니다.

접근 모델 (Coherent-Last): EFI 쌍의 보안은 coherent-last access를 가진 구별자(distinguisher)에 대해 증명됩니다. 이 모델은 다음을 허용합니다:

• 다항 길이의 클래식 조언(advice) (또는 $O(\lambda)$ 큐비트의 양자 조언).
• 오라클에 대한 다항 개의 적응적 클래식 쿼리.
• 상호작용의 맨 마지막 단계에서 수행되는 정확히 한 번의 코히어런트(superposition) 쿼리.
• (공개된 소스로부터 생성된) 도전 상태(challenge states)의 다항 개수 참조 복사본.

3. 주요 기여 및 결과

A. 일방향 퍼즐의 부재 (정리 A(i))
$\mathcal{O}'$에 대하여, OWPuzzs는 존재하지 않습니다 (무제限 검증자를 고려하더라도).

• 메커니즘: $Count$ 오라클을 통해 공격자는 지수 정밀도로 임의의 샘플러의 출력 확률을 추정할 수 있습니다.
• 공격: 공격자는 키의 조건부 분포를 비트 단위로 재구성할 수 있습니다. 이러한 추정된 조건부 확률로부터 샘в링함으로써, 공격자는 확률 $1 - \text{negl}(\lambda)$로 검증자에 의해 수락되는 키를 생성합니다.
• 범위: 이 공격은 순수하게 클래식하며, 오라클에 대한 **전체 코히어런트 접근(full coherent access)**을 가진 공격자에게도 적용됩니다 (공격이 양자 쿼리에 의존하지 않기 때문). 결과적으로, OWPuzzs가 함의하는 모든 원시 함수(다중 복사 의사 난수 상태, 순수 출력 일방향 상태 생성기, 양자 머니 등) 또한 $\mathcal{O}'$에 대해 존재하지 않습니다.

B. EFI 쌍의 존재 (정리 A(ii))
$\mathcal{O}'$에 대하여, 절반 부분 공간(half-subspace) 쌍 $(\rho_0, \rho_1)$은 정의된 접근 모델에 대해 안전한 EFI 쌍을 형성합니다.

• 클래식 쿼리 (통신 복잡도 감소): 클래식 쿼리에 대한 보안은 부분 공간 내 벡터(Vector-in-Subspace, VSP) 문제로 환원됩니다. VSP에서 밥(Bob)은 부분 공간 $H$를 보유하고, 앨리스(Alice)는 $H$ 또는 $H^\perp$에 속할 것이 약속된 벡터를 보유합니다.
  • 양자: VSP는 쉽습니다 (앨리시는 $O(\log n)$ 큐비트로 벡터를 보내고, 밥은 이를 측정합니다).
  • 클래식: VSP는 어렵습니다. $\Omega(n^{1/3})$ 비트의 통신을 요구합니다 (Klartag–Regev 경계).
  • 저자는 $H$에 대한 길이 $L$의 클래식 트랜스크립트가 상태를 구별하는 데 있어 최대 $O(L/n^{1/3})$의 이득만을 제공함을 보여줍니다. 공격자가 다항 개의 클래식 비트에 제한되므로, 이 이득은 무시할 수 있는 수준(negligible)입니다.
• 참조 복사본: 공격자에게는 상태의 참조 복사본이 부여됩니다. 저자는 이 복사본들이 해당 스팬(span)의 클래식 기술로 대체될 수 있음을 보여줍니다. 이 스팬들에 대해 조건화(conditioning)하면, 문제는 직교 보공간에서의 더 작은 VSP 인스턴스로 축소되며, 보안상의 손실은 무시할 수 있는 수준입니다.
• 코히어런트 쿼리 (행렬 집중 현상): 마지막 단계에서 허용된 단 하나의 코히어런트 쿼리는 무작위 행렬 이론 도구를 사용하여 제한됩니다. 일회 쿼리 공격자의 편향(bias)은 $O(\sqrt{\log M / n})$으로 나타나며, 이는 다항 너비 $M$에 대해 무시할 수 있는 수준입니다. 참고: EFI 보안 주장은 이 "coherent-last" 모델로 구체적으로 제한됩니다; 이 분리는 (클래식 오라클에 대한 여러 번의 적응적 중첩 쿼리를 사용하는) 전체 코히어런트 접근을 가진 공격자에 대해서는 아직 성립하지 않습니다.

C. 상호작용 붕괴 (정리 B)
$\mathcal{O}'$에 대하여, 클래식 메시지를 가진 프로토콜에 대한 양자성(quantumness)의 증명은 존재하지 않습니다. 클래식 메시지와 출력을 갖는 프로토콜 내의 임의의 양자 다항 시간 당사자는 $\mathcal{O}'$에 대한 클래식 쿼리를 수행하는 클래식 다항 시간 당사자로 시뮬레이션될 수 있습니다. 이는 이 오라클 세계에서 양자 다항 시간(QP)이 클래식 입출력을 갖는 작업에 대해 클래식 다항 시간(P)에 비해 어떠한 이점도 제공하지 못함을 의미합니다.

D. 원시 함수의 분리
본 논문은 블랙박스 장벽을 설정합니다. 정의된 구별자 클래스 내에서 EFI 쌍으로부터 OWPuzzs를 구성하는 완전한 블랙박스 구성은 존재하지 않습니다. 이는 "NanoCrypt" 세계(EFI 쌍은 존재하나 OWPuzzs는 존재하지 않음)와 "CountCrypt" 세계(OWPuzzs가 존재함)를 분리합니다.

4. 의의 및 한계

의의:

• 난해함의 분리: 본 연구는 양자 상태를 구별하는 난해함(EFI)이 반드시 클래식 탐색 문제(OWPuzzs)의 난해함을 함의하지는 않는다는 것을 보여줍니다. 이는 양자 암호학의 최소 가정이 클래식 평균 사례 난해함보다 더 약할 수 있음을 시사합니다.
• 새로운 증명 기법: 본 논문은 양자 상태 구별성을 클래식 통신 복잡도 하한(특히 VSP)으로 환원하는 새로운 방법을 도입합니다.
• 오라클 구성: 클래식 출력의 난해함(탐색, 결정, 상호작용)을 제거하면서도 (coherent-last 제한 하에서) 양자 상태 구별성은 보존하는 구체적인 단일 클래식 오라클을 제공합니다.

한계 및 미해결 과제:

• 코히어런트 접근: EFI 보안 증명은 마지막에 단 한 번의 코히어런트 쿼리를 허용하는 제한에 의존합니다. 본 논문은 (클래식 오라클에 대한 여러 번의 적응적 중첩 쿼리를 사용하는) 전체 코히어런트 접근을 가진 공격자에 대해서도 이 분리가 성립하는지에 대한 의문(Conjecture 8.2)을 남겨둡니다.
• 조언(Advice): 보안은 $O(\lambda)$ 큐비트의 양자 조언에 대해 성립하지만, 클래식 쿼리와 결합된 다항 크기의 양자 조언(이는 공격자가 클래식 트랜스크립트 전에 임의의 양자 사이드 정보를 합성할 수 있게 함)은 배제하지 않습니다.
• 상대화(Relativization): 결과는 오라클 분리입니다. 이들은 비상대화적(unrelativized) 세계에서 EFI 쌍으로부터 OWPuzzs가 구성될 수 있는지 여부를 해결하지 않으며, $P \neq PSPACE$를 함의하지도 않습니다.

요약하자면, 본 논문은 양자 암호학이 일방향 퍼즐에 필요한 클래식 평균 사례 난해함에 의존하지 않고도 양자 상태의 구별 가능성(EFI 쌍)에 기반할 수 있는 오라클 세계를 구축함으로써, 양자 암호학의 최소 가정 지형을 명확히 합니다.