Unclonable Encryption in the Haar Random Oracle Model

이 논문은 일방향 함수가 존재하지 않을 수도 있는 '마이크로크립트' 환경에서 해라 무작위 오라클 모델을 기반으로 키 재사용이 가능한 암호문 복제 방지 (Unclonable Encryption) 방식을 최초로 제시하며, 이를 위해 경로 기록 프레임워크를 활용한 새로운 '유니터리 재프로그래밍 보조정리'를 증명했습니다.

핵심

1. 핵심 아이디어: "복제할 수 없는 비밀 편지"

상상해 보세요. 당신이 친구에게 아주 중요한 비밀 편지 (메시지) 를 보냅니다. 하지만 이 편지는 양자 (Quantum) 상태로 되어 있어서, 누군가가 이 편지를 훔쳐서 두 개의 똑같은 사본을 만들어 내는 것이 물리적으로 불가능합니다.

• 기존 암호: 열쇠 (비밀키) 가 있으면 암호를 풀 수 있습니다. 하지만 해커가 암호문을 복사해서 두 명에게 나누어 주고, 각자 열쇠로 풀면 둘 다 원본을 알아낼 수 있습니다.
• 이 논문의 암호 (UE): 해커가 암호문을 복사하려고 시도하면, 양자 물리 법칙 때문에 원본이 망가집니다. 해커가 두 명의 동업자 (A 와 B) 에게 암호문을 나누어 주더라도, 둘 중 한 명만 열쇠를 가지고 있어도 둘 다 원본 메시지를 알아낼 수 없습니다. 오직 한 명만 성공할 뿐입니다.

이 기술은 "지금 암호를 훔쳐두었다가, 미래에 슈퍼컴퓨터가 개발되면 해독하자"는 저장 후 해독 (Store-now, decrypt-later) 공격을 막아주는 만능 방패가 될 수 있습니다.

2. 문제 상황: "마법 같은 도구가 필요할까?"

지금까지 이 기술을 만들기 위해서는 **'일방향 함수 (One-way Function)'**라는 복잡한 수학적 도구가 필요하다고 믿어졌습니다.

• 일방향 함수: "오븐에 넣으면 빵이 되지만, 빵을 다시 오븐에 넣어서 밀가루로 되돌릴 수 없는" 그런 함수입니다. (쉽게 말해, 암호는 쉽게 만들지만 해독은 매우 어렵다는 것).

하지만 연구자들은 의문을 가졌습니다. "정말 그런 복잡한 수학적 도구가 꼭 필요한 걸까? 아니면 양자 물리 자체의 힘만으로도 가능하지 않을까?"

이 논문은 **"아니요, 복잡한 수학 도구가 없어도 됩니다!"**라고 말합니다. 대신에 **'하드 (Haar) 무작위 오라클'**이라는 아주 강력한 양자 도구를 사용하면 된다고 주장합니다.

3. 해결책: "무작위 양자 오라클"과 "재프로그래밍"

이 논문은 두 가지 주요 기여를 통해 이 문제를 해결했습니다.

① "하드 무작위 오라클" (Haar Random Oracle)

이것은 마치 완벽하게 무작위로 섞인 거대한 양자 카드 덱이라고 생각하세요.

• 모든 사람이 이 덱을 볼 수는 있지만, 그 순서를 예측하거나 조작할 수는 없습니다.
• 이 논문은 이 '완벽한 무작위 덱'만 있으면, 복잡한 수학적 도구 없이도 '복제 불가능한 암호'를 만들 수 있음을 보였습니다.

② "유니터리 재프로그래밍 보조정리" (Unitary Reprogramming Lemma)

이것은 논문의 가장 창의적인 부분인데, "변신하는 마법사" 비유로 설명할 수 있습니다.

• 상황: 해커가 어떤 양자 장치 (오라클) 를 계속 조작하고 있습니다.
• 문제: 해커가 그 장치를 조작하는 동안, 우리가 그 장치의 내부 설정을 몰라서 암호를 만들 수 없습니다.
• 해법 (재프로그래밍): 연구자들은 해커가 장치를 조작하는 동안, 그 장치가 실제로는 우리가 원하는 대로 변신하고 있다고 증명했습니다.
  • 마치 해커가 "이 기계는 A 를 입력하면 B 가 나온다"고 생각하며 조작하는 동안, 실제로는 우리가 몰래 기계의 내부를 살짝 바꿔서 "A 를 입력하면 우리가 원하는 C 가 나오게" 만드는 것과 같습니다.
  • 해커는 전혀 모른 채로 우리가 설정한 대로 움직이게 됩니다. 이를 통해 해커는 암호를 복제할 수 없게 됩니다.

4. 결론: "마이크로크립트 (Microcrypt)"의 탄생

이 논문의 가장 큰 의미는 암호학의 세계를 새롭게 정의했다는 점입니다.

• 미니크립트 (Minicrypt): 복잡한 수학적 난제 (일방향 함수) 가 있어야만 가능한 암호학의 세계. (기존의 생각)
• 마이크로크립트 (Microcrypt): 수학적 난제가 없어도, 양자 물리 법칙과 무작위성만으로 가능한 암호학의 세계. (이 논문의 발견)

연구자들은 "복제 불가능한 암호"가 마이크로크립트 세계에 존재함을 증명했습니다. 즉, 우리가 아직 발견하지 못한 복잡한 수학 공식이 없더라도, 양자 컴퓨터의 기본 원리만으로도 완벽한 보안 시스템을 만들 수 있다는 희망을 제시한 것입니다.

요약

1. 목표: 해커가 암호문을 복사해서 여러 명이 동시에 해독하는 것을 막는 '복제 불가능 암호' 만들기.
2. 기존 생각: 이를 위해선 복잡한 수학적 난제 (일방향 함수) 가 필수였다.
3. 이 논문의 발견: 복잡한 수학은 필요 없다! 완벽한 무작위 양자 도구만 있으면 된다.
4. 기술적 비결: 해커가 암호를 조작하는 동안, 우리가 몰래 그 도구를 재프로그래밍해서 해커가 원하지 않는 방향으로 움직이게 했다.
5. 의미: 양자 물리 법칙만으로도 완벽한 보안이 가능하다는 것을 증명하여, 미래 양자 시대의 보안 기준을 높였다.

이 논문은 **"복잡한 수학이 없어도, 양자의 마법만으로도 우리는 절대 뚫리지 않는 비밀 상자를 만들 수 있다"**는 것을 보여주는 획기적인 연구입니다.

기술 요약

1. 문제 제기 및 배경 (Problem Statement)

• 복제 불가능 암호화 (UE): Broadbent 과 Lord [BL20] 가 제안한 UE 는 비밀 키 $k$와 메시지 $m$을 양자 암호문 $\rho_{k,m}$으로 인코딩하는 방식입니다. 보안 요구사항은 어떤 적대자도 암호문을 두 개의 레지스터 (A, B) 로 복제하여, 키 $k$와 함께 각 레지스터만으로도 원래의 메시지 비트 $b$를 성공적으로 추측할 확률이 $1/2$에 근접하도록 제한하는 것입니다 (Unclonable Indistinguishability).
• Minicrypt vs Microcrypt:
  • 기존 UE 구성 (예: [AKL+22, AKL23]) 은 무작위 오라클 모델 (Random Oracle Model, ROM) 을 사용하며, 이는 최소한 일방향 함수 (OWF) 의 존재를 전제로 합니다. 이는 'Minicrypt' 영역에 해당합니다.
  • 반면, 'Microcrypt'는 OWF 가 존재하지 않아도 양자 난수 상태 (Pseudorandom States) 나 양자 난수 유니타리 (Pseudorandom Unitaries) 와 같은 양자적 난수성만으로도 암호학적 원시를 구성할 수 있는 영역을 의미합니다.
  • 핵심 질문: "재사용 가능한 (Reusable) UE 는 일방향 함수를 필요로 하는가?" 즉, UE 를 Microcrypt 영역 (OWF 없이) 에 위치시킬 수 있는가?
• 현재의 한계: 기존 연구들은 대부분 ROM 에 의존하거나, 정보이론적 보안 (One-time) 에 국한되었습니다. 재사용 가능한 UE 를 OWF 없이 구성하는지에 대한 명확한 답은 없었습니다.

2. 주요 기여 및 결과 (Key Contributions & Results)

이 논문은 다음과 같은 주요 결과를 도출했습니다.

1. Haar Random Oracle Model (HROM) 에서의 UE 구성:

   • 모든 당사자가 Haar 확률 분포에서 샘플링된 유니타리 연산자 $U$와 그 켤레 전치 ($U^\dagger, U^*, U^T$) 에 쿼리 접근 권한을 가진 Haar Random Oracle Model을 가정합니다.
   • 이 모델 내에서 재사용 가능한 (Reusable) 복제 불가능 암호화 (Unclonable Indistinguishability 보안) 를 구성했습니다.
   • 이는 OWF 가 존재하지 않는 세계에서도 UE 가 존재할 수 있음을 보여주는 첫 번째 증거로, UE 가 Microcrypt 원시임을 입증합니다.

2. 보편적 컴파일러 (General Compiler):

   • 임의의 유니타리 오라클 분포에 대해 재사용 가능한 UE 가 존재한다면, Haar Random Oracle Model 에서도 존재함을 보이는 일반적인 컴파일러를 제시했습니다.
   • 이를 통해 기존에 QROM (Quantum Random Oracle Model) 에서 안전성이 증명된 UE 구성 ([AKL+22, AKL23]) 을 HROM 으로 변환하여 재사용 가능한 UE 를 얻을 수 있음을 보였습니다.

3. 유니타리 재프로그래밍 보조정리 (Unitary Reprogramming Lemma):

   • 이 논문의 핵심 기술적 기여입니다.
   • 내용: 전체 공간 $H([N])$에 대한 단일 Haar 랜덤 유니타리 $U$를 쿼리하는 것과, 두 개의 "불연속"인 Haar 랜덤 유니타리 $U_1$ (부분 공간 $S_2$에서 작동) 과 $U_2$ (나머지 공간에서 작동) 의 곱 $U_2 U_1$을 쿼리하는 것을 구별하는 것은 불가능함을 증명합니다.
   • 단, $S_1 \subset S_2$이고 $|S_2|/N$과 $|S_1|/|S_2|$가 무시할 수 있을 정도로 작아야 합니다.
   • 이 보조정리는 경로 기록 (Path Recording) 프레임워크를 확장하여 증명되었으며, 독립적으로 중요한 의미를 가질 수 있습니다.

4. Oracle 분리 결과:

   • HROM 에서 재사용 가능한 UE 가 존재하지만, 일방향 함수가 존재하지 않는 오라클 $O$가 존재함을 보였습니다 (Corollary 1.2). 이는 $BQP^O = QMA^O$가 성립하는 세계를 구성하여, OWF 가 존재하지 않음을 의미합니다.

3. 방법론 및 기술적 접근 (Methodology & Techniques)

A. 구성 (Construction)

• 기본 아이디어: 공개적으로 쿼리 가능한 Haar 랜덤 유니타리 $U$를 사용하여 힐베르트 공간을 여러 부분 공간으로 분할합니다.
• 암호화 과정:
  • 메시지 $m$과 무작위성 $r$을 입력받아 상태 $|m, r\rangle$을 준비합니다.
  • 비밀 키 $k$에 따라 비트 플립을 적용하는 연산자 $X_k$를 적용합니다.
  • 최종 암호문은 $X_k U |m, r\rangle$입니다.
  • $U$는 $m$마다 고유한 부분 공간을 정의하고, $X_k$는 이 부분 공간들을 키 $k$에 의해 시프트 (shift) 하여 복제 공격자가 접근하지 못하게 합니다.

B. 보안 증명 전략 (Security Proof Strategy)

1. 하이브리드 게임 (Hybrid Games):
   • 실제 보안 게임에서 해커가 접근하는 오라클 $U$를 $U_2 U_1$ 형태로 분해하여 시뮬레이션합니다.
   • $S_1$은 암호화 쿼리에 사용되는 무작위성 $r$의 집합에 대응하고, $S_2$는 이를 포함하는 더 큰 집합입니다.
   • $U_1$은 $S_2$ 위에서 작동하고, $U_2$는 나머지 공간에서 작동합니다.
2. 재프로그래밍 (Reprogramming):
   • 해커가 암호화 쿼리를 할 때, $U_1$ 내부의 특정 부분 ($S_2$) 만을 사용하여 응답합니다.
   • 해커는 $X_k$로 인해 $S_2$의 구조를 알 수 없으므로, 복제 단계 (Cloning Phase) 동안 $S_2$ 내부에 대해 쿼리할 확률이 무시할 수 있음을 보입니다.
   • 따라서 감별 단계 (Distinguishing Phase) 에서만 $U_1$의 구조를 알 수 있게 되어, 보안 증명이 가능해집니다.
3. 경로 기록 프레임워크 (Path Recording Framework):
   • [MH25, SML+25] 에서 제안된 프레임워크를 확장하여, 해커의 쿼리를 내부 상태 (Database) 를 통해 효율적으로 시뮬레이션합니다.
   • $U_1 U_2$의 쿼리와 단일 $U$의 쿼리가 내부 상태의 정보 이론적 특성 (S2 레지스터가 D1 레지스터에 의해 결정됨) 으로 인해 구별 불가능함을 보입니다.

C. 재사용 가능성 (Reusability)

• 기존 QROM 기반의 One-time UE 구성을 "Pure" (순수) 한 형태로 변환하고, 이를 위 컴파일러에 적용하여 Many-time (재사용 가능) 보안을 달성합니다.
• 이는 키를 재사용하더라도 암호문의 무작위성 ($r$) 을 재샘플링하여 보안이 유지됨을 보장합니다.

4. 의의 및 결론 (Significance & Conclusion)

• 이론적 진전: 복제 불가능 암호화가 정보이론적 보안이 아닌 계산적 보안 (OWF 없이도) 으로 존재할 수 있음을 처음으로 보였습니다. 이는 양자 암호학의 기초 이론을 'Microcrypt' 영역으로 확장하는 중요한 이정표입니다.
• 기술적 도구: "Unitary Reprogramming Lemma"는 Haar 랜덤 유니타리를 다루는 향후 양자 보안 증명에 강력한 도구가 될 것입니다. 특히, 오라클의 부분 집합을 재프로그래밍하는 기법은 양자 암호 분석에서 새로운 패러다임을 제시합니다.
• 실용적 함의: "Store-now, decrypt-later" 공격과 같은 미래의 양자 컴퓨팅 위협에 대비할 수 있는 새로운 암호학적 원시의 가능성을 제시합니다.

요약하자면, 이 논문은 Haar Random Oracle이라는 강력한 양자적 난수성을 활용하여, 일방향 함수가 존재하지 않는 환경에서도 재사용 가능한 복제 불가능 암호화를 구성할 수 있음을 증명함으로써 양자 암호학의 지평을 넓혔습니다.