2025-11-15T00:07:12.138794

Multi-Copy Security in Unclonable Cryptography

Ãakan, Goyal, Kitagawa et al.

Unclonable cryptography leverages the quantum no-cloning principle to copy-protect cryptographic functionalities. While most existing works address the basic single-copy security, the stronger notion of multi-copy security remains largely unexplored. We introduce a generic compiler that upgrades collusion-resistant unclonable primitives to achieve multi-copy security, assuming only one-way functions. Using this framework, we obtain the first multi-copy secure constructions of public-key quantum money (termed quantum coins), single-decryptor encryption, unclonable encryption, and more. We also introduce an extended notion of quantum coins, called upgradable quantum coins, which allow weak (almost-public) verification under weaker assumptions and can be upgraded to full public verification under stronger assumptions by the bank simply publishing additional classical information. Along the way, we give a generic compiler that upgrades single-copy secure single-decryptor encryption to a collusion-resistant one, assuming the existence of functional encryption, and construct the first multi-challenge secure unclonable encryption scheme, which we believe are of independent interest.

academic

복제 불가능 암호학에서의 다중 복사본 보안

기본 정보

논문 ID: 2510.12626
제목: Multi-Copy Security in Unclonable Cryptography
저자: Alper Çakan, Vipul Goyal, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa
분류: quant-ph cs.CR (양자물리학, 암호학 및 보안)
발표 시간: 2024년 10월 14일 (arXiv 사전인쇄본)
논문 링크: https://arxiv.org/abs/2510.12626v1

초록

복제 불가능 암호학은 양자 복제 불가능 원리를 활용하여 암호학적 기능이 복제되는 것을 방지한다. 기존 연구의 대부분이 기본적인 단일 복사본 보안성을 다루었지만, 더욱 강력한 다중 복사본 보안성 개념은 여전히 대부분 미탐색 상태이다. 본 논문은 단방향 함수의 존재만을 가정하여 공모 저항성 복제 불가능 원시 함수를 다중 복사본 보안성으로 업그레이드할 수 있는 범용 컴파일러를 제시한다. 이 프레임워크를 활용하여 저자들은 공개키 양자 화폐(양자 동전이라 칭함), 단일 복호화기 암호화, 복제 불가능 암호화 등의 첫 번째 다중 복사본 보안 구성을 획득했다. 본 논문은 또한 양자 동전의 확장 개념인 업그레이드 가능한 양자 동전을 소개하며, 이는 더 약한 가정 하에서 약한 검증을 허용하고 은행이 추가 고전 정보를 발행함으로써 더 강한 가정 하에서 완전한 공개 검증으로 업그레이드될 수 있다.

연구 배경 및 동기

핵심 문제

본 논문이 해결하고자 하는 핵심 문제는 단일 복사본 보안성에서 다중 복사본 보안성으로의 업그레이드 문제이다. 복제 불가능 암호학에서 전통적인 연구는 주로 1→2 복제 불가능성 설정(적대자가 하나의 순수 양자 상태 복사본을 획득하지만 두 개의 복사본을 생성할 수 없음)에 초점을 맞추었으며, 더 일반적인 q→q+1 설정(적대자가 q개의 복사본을 획득하지만 q+1개를 생성할 수 없음)에 대한 연구는 상대적으로 적다.

문제의 중요성

다중 복사본 보안성은 다음과 같은 이유로 중요하다:

운영상 이점: 순수 상태의 동등성은 SWAP 테스트를 통해 효율적으로 검증할 수 있으며, 이는 응용에서 매우 유용하다
익명성: 동일한 순수 상태의 여러 복사본은 자연스럽게 익명성 보장을 제공한다
개념적 동기: 여러 순수 상태 복사본은 동일한 물리적 객체에 대응되며, 동일 분포에서 샘플링된 상태는 서로 다를 수 있다

기존 방법의 한계

기존 다중 복사본 보안성 결과는 매우 제한적이다:

Mosca와 Stebila가 양자 동전 개념을 제시했으나 양자 오라클 모델에서만 구성
일부 연구는 약한 오라클 보안성 개념만 구현
공모 저항성 보안성에서 다중 복사본 보안성으로의 범용 변환 방법 부재

핵심 기여

범용 컴파일러 제시: 공모 저항성 복제 불가능 원시 함수를 다중 복사본 보안성으로 업그레이드하는 범용 컴파일러 제시 (단방향 함수만 가정)
첫 번째 다중 복사본 보안 구성: 양자 동전, 단일 복호화기 암호화, 복제 불가능 암호화 등의 첫 번째 다중 복사본 보안 구성 획득
업그레이드 가능한 양자 동전: 서로 다른 가정 강도 하에서 다양한 수준의 보안 보장을 제공하는 새로운 개념 도입
기술적 도구: 단일 복사본에서 공모 저항성으로의 단일 복호화기 암호화 컴파일러 및 첫 번째 다중 도전 보안 복제 불가능 암호화 방안 구성

방법론 상세 설명

작업 정의

다중 복사본 보안성: 임의의 다항식 t에 대해, 동일한 순수 상태의 t개 복사본이 주어졌을 때, 적대자는 t+1개의 유효한 복사본을 생성할 수 없다. 이는 t개의 독립적으로 생성된 상태가 주어지는 공모 저항성과 다르다.

핵심 기술: 정제 컴파일러 (Purification Compiler)

주요 정리 (Theorem 7)

GenState를 고전적 결정론적 출력을 가진 QPT 알고리즘이라 하고, 난수 길이를 r(λ)라 하자. PRS 키 k와 PRF 키 K에 대해 다음을 정의한다:

$|ψ_{z,k,K}⟩ = \sum_x α_{k,x}|x⟩ ⊗ |φ_{z,F(K,x)}⟩$

여기서 $\sum_x α_{k,x}|x⟩$ 는 PRS 방안이 생성한 상태이고, $|φ_{z,F(K,x)}⟩$ 는 GenState(z;F(K,x)) 호출로 얻은 상태이다.

핵심 아이디어: PRS와 PRF를 통해 t개의 독립적으로 생성된 상태를 t개의 동일한 상태 복사본으로 변환할 수 있으며, 계산상 구별 불가능하다.

컴파일러 작동 원리

상태 쿼리 단계: 챌린저가 적대자가 요청한 수량 t를 수신하고, 원래는 독립적인 난수를 사용하여 GenState(st)를 t번 실행
수정 후: 챌린저가 t개의 동일한 상태를 출력: $\sum_x α_{k_i,x}|x⟩ ⊗ |φ_x⟩$ 여기서 $|φ_x⟩ = \text{GenState}(st; F(K_i,x))$
보안성: PRS와 PRF의 보안성을 기반으로, 수정된 실험과 원래 실험은 계산상 구별 불가능하다