기술 요약: 상관된 챌린지를 이용한 복사 방지 (Copy-Protection)

1. 문제 정의

양자 복사 방지는 기능(functionality)을 재사용 가능한 양자 상태로 인코딩하여, 두 명의 "프리로더(freeloader)" 적대자가 각각 보유한 두 개의 별개 상태가 동시에 유용하게 남을 수 없도록 만드는 것을 목표로 한다. 일반적인 기능 및 복호 키(decryption keys)에 대한 복사 방지 체계를 구축하기 위해 상당한 진전이 있었으나, 이 분야는 두 가지 결정적인 한계에 직면해 있다:

1. 정의적 파편화 (Definitional Fragmentation): 단일 복호 암호화(Single-Decryptor Encryption, SDE)와 같은 근본적인 프리미티브의 경우, 문헌에 7개의 서로 다른 보안 개념이 존재한다. 이러한 개념들 사이의 관계는 불분명하며, 모든 다른 개념을 함의하는 단일한 "골드 스탠다드" 정의는 알려져 있지 않다. 특히, 표준적인 식별 불가능성(indistinguishability) 보안이 SDE에 대한 탐색 보안(search security)을 함의하는지는 알려져 있지 않다.
2. 동일 챌린지 간극 (The Identical-Challenge Gap): 기존의 구성 방식은 주로 독립적으로 샘플링된 챌린지에 대한 보안을 달성한다. 그러나 더 자연스럽고 실질적으로 관련성이 높은 보안 개념은 두 적대자가 정확히 동일한 챌린지(예: 동일한 암호문 또는 동일한 입력 지점)를 받는 *동일 챌린지 보안(identical-challenge security)*이다. 이 개념은 복제 불가능한 비트(unclonable bits) 및 점 함수(point functions)의 복사 방지와 연결되어 있다. Georgiou와 Zhandry(2020) 이후 오픈 문제로 남아있던 이 질문에 대해, 평범한 모델(plain model)에서 동일 챌린지 SDE 또는 일반적인 복사 방지를 위한 증명 가능한 보안 구성은 아직 존재하지 않는다.

핵심 문제는 자연스러운 사용 사례(동일 챌린지 포함)를 포착할 수 있는 통일되고 강력한 보안 개념을 정의할 수 있는지, 그리고 이 개념을 만족하는 구성을 평범한 모델에서 달성할 수 있는지 여부이다.

2. 방법론 및 기술적 핵심

저자들은 정의의 통합과 새로운 양자 정보 이론적 도구의 결합을 통해 이 문제들을 해결한다.

A. 정의적 통합

본 논문은 SDE와 복제 불가능한 펑처블 옵퍼스케이션(Unclonable Puncturable Obfuscation, UPO) 모두에 대해 **상관된 챌린지 보안(Correlated-Challenge Security)**을 도입한다.

• 상관된 챌린지 SDE (SDE-CORR): 이 정의는 두 적대자의 챌린지 비트가 주변 분포(marginal distributions)가 균등하다는 조건 하에 임의로 상관될 수 있도록 허용한다. 이는 독립 챌린지 및 동일 챌린지 설정을 모두 포괄한다.
• 상관된 챌린지 UPO: 마찬가지로, 이 정의는 챌린지 지점과 보조 정보(auxiliary information)가 임의로 상관될 수 있도록 허용한다. 이는 보조 정보 누출을 포함하도록 이전의 UPO 정의를 일반화한 것으로, 컴퓨트-앤-컴페어(compute-and-compare) 프로그램과 같은 응용에 필수적이다.

저자들은 SDE-CORR가 오랫동안 갈구해 온 동일 챌린지 보안을 포함하여 기존의 7가지 SDE 보안 개념을 모두 함의함을 증명함으로써 정의의 계층 구조를 확립한다. 또한, 표준적인 식별 불가능성(CPA) 보안이 일반적으로 탐색 보안을 함의하지 않으며, 독립 챌린지 보안이 동일 챌린지 보안을 함의하지 않음을 명확히 한다.

B. 결정적 코셋 모노가미 정리 (The Decisional Coset Monogamy Theorem)

이 논문의 기술적 핵심은 새로운 결정적 코셋 모노가미-엔탱글먼트(Decisional Coset Monogamy-of-Entanglement, MOE) 정리이다.

• 설정: 적대자는 코셋 상태 $|A_{s,t}\rangle$(이동된 부분 공간 $A+s$ 위의 중첩이며, 위상 변화는 $t$에 의해 결정됨)를 받는다. 적대자는 이 상태를 통신하지 않는 두 당사자 B와 C 사이로 분할한다.
• 챌린지: 챌리저(challenger)는 0이 아닌 벡터 $u \in A$와 0이 아닌 벡터 $v \in A^\perp$를 샘플링하여 B와 C에게 동일한 쌍 $(u, v)$를 보낸다.
• 목표: B와 C는 단일 비트 $e = \langle u, t \rangle \oplus \langle v, s \rangle$를 출력해야 한다.
• 결과: 저자들은 B와 C가 올바른 비트를 출력할 확률이 최대 $1/2 + 2^{-\Omega(n)}$임을 증명한다.

증명의 주요 혁신:

1. 결정적 vs 탐색적 (Decisional vs. Search): 전체 벡터의 출력을 요구하는 이전의 "탐색 스타일" MOE 정리(예: Culf와 Vidick)와 달리, 본 연구는 당사자들이 단일 비트를 출력하는 "결정적 게임"이다.
2. 동일 챌린지: 챌린지 $(u, v)$는 두 당사자에게 동일하다. 이전의 결정적 MOE 결과들은 학습 가능한 상태(예: BB84)나 독립적인 챌린지에 의존했다. 이것은 학습 불가능한 상태 패밀리(코셋 상태)에 대한 최초의 동일 챌린지 결정적 MOE 정리이다.
3. 추출 생략 (No Extraction): 본 증명은 탐색 보장을 결정적 보장으로 변환하기 위해 필요한 복잡한 "추출(extraction)" 기법(임계값 측정, 리와인딩 등)을 피한다. 대신, 키와 메시지가 조건부되었을 때 암호문이 특정 고유 공간(eigenspace) 상의 최대 혼합 상태(maximally mixed state)임을 보여주는 정보 이론적 논증을 사용하며, 파울리 연산자의 구조를 활용한다.
4. 계산적 변형: 저자들은 상관된 보조 정보를 처리하면서, 식별 불가능성 옵퍼스케이션(iO) 및 서브스페이스-하이딩 옵퍼스케이션(Subspace-Hiding Obfuscation)을 사용하여 이를 계산적 설정으로 확장한다.

C. 구성 전략

새로운 결정적 코셋 MOE 정리를 사용하여 저자들은 다음을 구성한다:

1. 상관된 챌린지 SDE: Kitagawa-Yamakawa (2025)의 구성을 변형한다. 숨겨진 동일 비트와 상관 매개변수를 사용하여 챌린지 비트를 재작성함으로써, SDE 스킴의 보안을 결정적 코셋 MOE 게임으로 직접 환원한다.
2. 상관된 UPO: 임의의 다항식 크기 키드 회로(keyed circuits)에 대한 UPO를 구성한다. 보안 증명은 챌린지 지점이 펑처링(punctured)되고, 값이 단사(injective)/손실(lossy) 함수 및 유니버설 해싱을 사용하여 사전 분할된 보조 정보를 시뮬레이션하도록 교체되는 일련의 하이브리드 과정을 포함한다. 최종 하이브리드는 계산적 결정적 코셋 MOE 게임으로 환원된다.

3. 주요 결과

본 논문은 평범한 모델에서 다음과 같은 구체적인 결과를 제공한다:

• SDE 보안: 포스트 퀀텀 식별 불가능성 옵퍼스케이션(iO)과 일방향 함수(OWF)를 가정할 때, SDE-CORR를 만족하는 SDE 스킴이 존재한다. 이는 표준 가정으로부터 동일 챌린지 보안을 만족하는 최초의 클래식 암호문 SDE 구성이다.
• UPO 보안: 포스트 퀀텀 iO와 LWE(Learning With Errors)의 양자적 어려움을 가정할 때, 임의의 다항식 크기 회로에 대한 상관된 UPO 스킴이 존재한다. 이 스킴은 높은 최소 엔트로피를 가진 임의의 상관된 챌린지 분포에 대한 보안을 만족한다.
  • 참고: 동일한 균등 챌린지 분포의 경우, LWE 가정을 포스트 퀀텀 OWF로 대체할 수 있다.
• 복사 방지 응용: UPO 프레임워크를 통해 저자들은 다음 기능들에 대한 평범한 모델에서의 첫 번째 복사 방지 스킴을 도출한다:
  • 점 함수 (Point Functions): 자연스러운 동일 챌린지 분포를 포함한다 (Aaronson의 2009년 문제를 해결함).
  • $k$-점 함수 ($k$-Point Functions): 점 함수의 일반화.
  • 컴퓨트-앤-컴페어 프로그램 (Compute-and-Compare Programs): 자연스러운 동일 챌린지 분포를 포함한다.
  • 일반적인 펑처블 기능 (General Puncturable Functionalities): 동일 챌린지에 대해 예측 불가능성 스타일 및 의사 난수성 스타일의 보안을 포함하는, 예측 불가능성 스타일의 보안을 제공한다.

4. 의의 및 주장

본 논문은 양자 암호학의 몇 가지 오랜 미해결 과제들을 해결한다고 주장한다:

1. 동일 챌린지 미해결 문제 해결: 평범한 모델에서 점 함수 및 복호 키에 대한 최초의 증명 가능한 보안 복사 방지를 제공하며, 이는 10년 넘게 열려 있던 문제였다.
2. 정의적 명확성: 모든 이전 정의를 포괄하는 "골드 스탠다드" 정의(SDE-CORR)를 확립하여, 보안 개념의 계층 구조를 명확히 하고, 이전의 정의들이 자연스러운 보안 직관(예: CPA가 탐색 보안을 함의하지 않음)을 포착하기에 불충분했음을 증명하였다.
3. 기술적 진보: 새로운 결정적 코셋 모노가미 정리는 독립적인 관심사로서 제시된다. 이는 모노가미 게임, 언클러너블 암호화, 복사 방지 연구를 통합하며, 복잡한 추출 기법을 제거함으로써 향로의 증명을 단순화하는 결정적 보장을 제공한다.
4. 모듈형 프레임워크: 상관된 UPO를 도입함으로써, 저자들은 보조 정보 누출을 필요로 하는 자연스러운 보안 정의 하에서 광범위한 기능(단순 점 함수 이상)을 달성하기 위한 모듈형 경로를 제공한다.

저자들은 자신의 결과가 표준적인 포스트 퀀텀 가정(iO, OWF, LWE)에 기반하고 있으며, 이러한 결과들을 위해 양자 랜덤 오라클 모델(QROM)과 같은 이상화된 모델에 의존하지 않고 평범한 모델에서 작동한다는 점을 강조한다.