상관 도전 기반 복제 방지: 결정적 잉여류 단일성을 통한 점 함수 등의 평문 모델 보안
Copy-Protection with Correlated Challenges: Point Functions and More via Decisional Coset Monogamy
Amit Behera, Alper Çakan, Vipul Goyal
Photo: FlyD / Unsplash양자 복제 방지를 상관·동일 도전 설정으로 확장해 점 함수 등에 대한 최초 평문 모델 결과 달성
쉽게 풀면
양자역학의 복제 불가능성 원리를 이용하면 소프트웨어를 "양자 상태"로 인코딩하여 복사할 수 없게 만들 수 있습니다. 기존 연구는 두 공격자에게 서로 다른 문제를 줄 때만 안전성을 보였지만, 이 연구는 두 공격자가 완전히 동일한 문제를 받아도 동시에 성공할 수 없음을 처음으로 증명했습니다. 디지털 저작권 관리나 양자 소프트웨어 라이선스의 이론적 토대를 크게 강화하는 성과입니다.
한국어 초록
(1) 문제: 양자 복제 방지는 기능성을 재사용 가능한 양자 상태에 인코딩하여, 두 프리로더가 이를 분할해 동시에 사용하는 것을 불가능하게 한다. 기존 평문 모델 결과는 독립 샘플링된 도전만을 다루었고, 동일·상관 도전 설정은 복제 불가능 비트 및 점 함수 복제 방지와 직결됨에도 미해결로 남아 있었다. (2) 방법: 단일 복호기 암호화(SDE)에 대해 상관 도전 보안 정의를 강화하였고, 일반 기능성에 대해서는 도전 점 간 임의 상관과 천공 비트·보조 정보의 분할 전후 공개를 허용하며 각 점에서 평균 조건부 최소 엔트로피만 요구하는 상관 도전 복제 불가능 천공 난독화(UPO)를 정의하였다. (3) 결과: iO와 일방향 함수를 가정하여 Kitagawa-Yamakawa(TCC'25) 구성이 새 SDE 강화 보안을 달성함을 증명하였다. 후양자 iO와 양자-난해 LWE를 가정하여 입력 길이 인 다항 크기 키 회로에 대한 상관 UPO를 구성하였다. (4) 의의: 점 함수·-점 함수·계산-비교 프로그램에 대한 최초 평문 모델 복제 방지를 제공하고, EUROCRYPT'26의 두 공개 문제를 해결하였다.
전문가 노트
이 논문은 양자 복제 방지 분야에서 오랫동안 미해결이었던 상관/동일 도전 보안(correlated/identical-challenge security) 을 평문 모델(plain model)에서 처음으로 확립한다.
기존 연구와의 위치
기존 SDE 및 복제 방지 연구는 두 프리로더에게 독립적으로 샘플링된 도전 을 제시하는 약한 모델만 다루었다. 동일 도전()은 복제 불가능 비트와 점 함수 복제 방지에 직결됨에도, 평문 모델 증명이 없었다. Ananth-Behera-Huang-Kitagawa-Yamakawa(EUROCRYPT'26)와 Cakan-Goyal(EUROCRYPT'26)이 각각 공개 문제로 제시한 것을 본 논문이 동시에 해결한다.
핵심 기법: 결정적 잉여류 단일성(Decisional Coset Monogamy)
도전 점들이 상관될 때에도 두 당사자가 동시에 성공할 수 없음을 증명하기 위해, 잉여류 상태의 구별 불가능성에 기반한 단일성(monogamy-of-entanglement) 게임 논증을 활용한다.
가정 구조
| 결과 | 가정 |
|---|---|
| SDE 상관 도전 보안 | + 일방향 함수 |
| 일반 상관 UPO | 후양자 + 양자-난해 LWE |
강화된 UPO의 의미
상관 UPO는 (i) 도전 점 간 임의 상관, (ii) 천공 비트·보조 정보의 분할 전·후 공개, (iii) 각 점에 대해 조건부 최소 엔트로피만 요구함으로써, 동일 도전을 포함한 극히 일반적인 상황을 포괄한다. SDE 쪽에서는 기존 여러 정의들 간의 함의 관계를 거의 완전히 규명한 점도 기여이다.
한계 및 후속 함의
라는 강력한 가정에 의존하며, 구체적 양자 하드웨어 구현 가능성은 논의되지 않는다. 입력 길이 조건도 여전히 남아 있으며, 이를 제거하는 것이 자연스러운 후속 과제다. 또한 이 프레임워크가 일반 복제 불가능 암호 원시 연산(unclonable primitives)의 구성 이론으로 확장될 수 있는지가 주목된다.
핵심 용어
원문 출처
원문 초록 (영문) 보기
Copy-protection encodes a functionality in a reusable quantum state that cannot be split into two states (freeloader adversaries) which remain simultaneously useful. Prior plain-model results handle only independently sampled challenges; the more natural identical-challenge notion, also tied to unclonable bits and copy-protection of point functions, has remained open. We strengthen these definitions and prove plain-model security for our new stronger notions. For single-decryptor encryption (SDE) we define correlated challenge security, show it implies all previous SDE notions including identical-challenge security, and prove that the construction of Kitagawa and Yamakawa (TCC'25) achieves it assuming iO and one-way functions. We also nearly fully characterize the relations among prior SDE notions. For general functionalities we define correlated challenge unclonable puncturable obfuscation (UPO), allowing arbitrary correlations among challenge points and puncturing bits plus auxiliary information before and after splitting, and requiring only conditionally uniform bits and $λ^c$ average conditional min-entropy in each point separately (thus, in particular, the points may be identical). Assuming post-quantum iO and quantum-hard LWE, we construct correlated UPO for polynomial-size keyed circuits with input length at least $λ^c$, answering an open question of Ananth, Behera, Huang, Kitagawa, Yamakawa (EUROCRYPT'26) and of Cakan-Goyal (EUROCRYPT'26). We also obtain the first plain-model copy protection for point functions, $k$-point functions, and compute-and-compare programs, and identical-challenge copy protection for general puncturable functionalities.