기술 요약: 키가 있는 오라클에 대한 구별 불가능성 리프팅, 압축된 이상적 암호, 그리고 기타 응용 분야

1. 문제 정의

암호학적 보안 증명에서, 기본 오라클(예: 각 키가 독립적인 무작위 치환을 선택하는 이상적 암호 또는 각 입력이 독립적인 무작위 문자열을 선택하는 무작위 오라클)의 수많은 독립적인 인스턴스로 구성된 **키가 있는 오라클(keyed oracles)**을 사용하여 스킴을 모델링하는 것은 일반적입니다. 양자 보안 모델으로 전환할 때 근본적인 과제가 발생합니다:

• 양자 중첩 문제: 양자 대립자는 키의 중첩 상태로 키가 있는 오라클에 쿼리를 보낼 수 있습니다. 이 단일 쿼리는 밑바탕이 되는 기본 오라클의 모든 인스턴스를 동시에 건드립니다.
• 고전적 기법의 실패: 하이브리드 논증(hybrid argument)과 같은 표준 고전적 증명 기법은 이 설정에서 실패합니다. 고전적인 경우, 기본 오라클의 인스턴스를 하나씩 교체할 수 있으며(이 과정에서 쿼리 수 $q$에 대해 선형적인 손실이 발생함), 양자 환경에서는 단일 쿼리가 모든 인스턴스에 걸쳐 있기 때문에 단순한 하이브리드 논증이 작동하지 않습니다.
• 기존 연구의 한계: 이를 처리하기 위한 기존 방법들은 정량적 비효율성(구별 우위에서 초다항식 또는 제곱근 손실을 유발)을 겪거나 범위 제한(상태가 없는(stateless) 오라클에만 적용됨)을 가집니다. Zhandry의 압축 오라클, Unruh 및 Carolan의 압축 치환 오라클과 같은 많은 유용한 오라클은 내부 메모리가 쿼리마다 진화하는 상태 유지(stateful) 방식입니다. 양자 환경에서 상태 유지 오라클을 위한 범용적인 리프팅 정리(lifting theorem)는 존재하지 않았습니다.

본 논문은 다음과 같은 일반적인 질문을 다룹니다: 두 기본 오라클 $O_0$와 $O_1$이 $q$개의 양자 쿼리 하에서 구별 불가능하다면, 그에 대응하는 키가 있는 오라클 $O_0^{\mathcal{K}}$와 $O_1^{\mathcal{K}}$도 구별 불가능한가? 그리고 그 보안 손실은 얼마인가?

2. 방법론

저자들은 범용적인 구별 불가능성 리프팅 정리를 확립하기 위해 **다항식 방법(polynomial method)**과 **마르코프 형제 부등식(Markov brothers' inequality)**을 결в힌 새로운 응용 방식을 채택했습니다.

리프팅 정리 (The Lifting Theorem)

핵심 기여는 두 기본 오라클 $O_0$와 $O_1$이 $q$개의 양자 쿼리를 사용하여 우위 $\epsilon$으로 구별 불가능하다면, 그들의 키가 있는 대응물은 최대 $8q^2 \epsilon$의 우위로 구별 불가능하다는 정리입니다.

주요 기술 단계:

1. 매개변수화된 축소(Parametrized Reduction): 증명은 기본 오라클 $O_0$와 $O_1$을 구별하는 축소 알고리즘 $\mathcal{B}$를 구축합니다. $\mathcal{B}$는 키를 $p$와 $z$라는 파라미터를 가진 베르누이 분포에서 샘플링된 비트로 매핑하는 두 개의 독립적인 함수 $H$와 $G$에 기반하여 쿼리를 라우팅함으로써 대립자를 위한 키가 있는 오라클을 시뮬레이션합니다.
2. 다항식 정식화: 대립자의 구별 우위는 $f(1) - f(0)$의 차이로 표현됩니다. 여기서 $f(p)$는 라우팅 파라미터가 $p$이고 기본 오라클이 $O_1$일 때 $\mathcal{A}$가 1을 출력할 확률입니다.
3. 도함수 연결: 저자들은 도함수 $f'(p)$가 다른 함수 $g_p(z)$의 $z=0$에서의 도함수와 관련되어 있음을 보여줍니다. 결정적으로, $g_p(z)$는 $z$에 대한 차수가 최대 $2q$인 $z$의 다항식임이 증명되었습니다.
4. 부등식을 통한 경계 설정: 마르코프 형제 부등식(및 라그랑주 보간법을 포함한 특정 변형)을 사용하여 다항식의 도함수를 제한합니다. 이를 통해 연속적인 차이 $|f(1) - f(0)|$를 축소 알고리즘 $\mathcal{B}$의 이산적인 구별 우위와 연관시키며, 이 과정에서 $O(q^2)$의 곱셈 인자가 발생합니다.

이 접근 방식은 통계적(statistical) 및 계산적(computational) 설정 모두에서 작동하며, 결정적으로 오라클이 정적(static)일 필요가 없기 때문에 상태 유지(stateful) 오라클에도 적용됩니다.

3. 주요 기여 및 결과

A. 범용 구별 불가능성 리프팅 정리

본 논문은 임의의 (잠재적으로 상태 유지인) 두 오라클 $O_0$와 $O_1$에 대해, 만약 이들이 $q$개의 양자 쿼리로 우위 $\epsilon$으로 구별 불가능하다면, 그들의 키가 있는 버전은 최대 $8q^2 \epsilon$의 우위로 구별 불가능함을 확립합니다.

• 최적성: 저자들은 특정하게 설계된 오라클 선택에 대해 $O(q^2)$ 손실이 최적임을 입증하며, 이는 표준 그로버 탐색 공격(Grover search attack)에 의해 달성 가능한 우위와 일치합니다.
• 상태 유지 지원: 기존 연구와 달리, 이 정리는 상태 유지 오라클에 적용되므로 압축 오라클과 같은 복잡한 시뮬레이터를 분석할 수 있게 합니다.

B. 압축된 이상적 암호 (Compressed Ideal Cipher)

직접적인 응용으로서, 저자들은 Carolan의 압축 치환 오라클을 이상적 암호 모델로 확장하여 효율적으로 구현 가능한 **압축된 이상적 암호(cIC)**를 생성합니다.

• 구조: 이들은 각 키에 대한 부분 치환(partial permutations)의 데이터베이스를 유지하는 상태 유지 시뮬레이터를 정의합니다.
• 보안 경계: 리프팅 정리를 사용하여, cIC가 실제 이상적 암호와 구별 불가능함을 증명합니다. 압축 치환 오라클의 단일 인스턴스 경계가 $\Delta_{cpO}(n, q)$라면, cIC의 경계는 $8q^2 \cdot \Delta_{cpO}(n, q)$입니다.
• 모듈성: 저자들은 압축 치환 오라클에 대한 향후의 어떠한 개선(예: Kim [Kim26] 및 Carolan & Majenz [CM26]의 최근 개선 사항)도 리프팅을 다시 증명할 필요 없이 자동으로 압축된 이상적 암호의 경계를 개선한다는 점을 강조합니다.

C. Davies-Meyer의 역상 저항성 (Preimage Resistance)

압축된 이상적 암호를 사용하여, 본 논문은 양자 이상적 암호 모델에서 Davies-Meyer 압축 함수의 역상 저항성을 증명합니다.

• 결과: 대립자가 역상을 찾을 확률은 $q^2/2^n$과 압축된 이상적 암호의 구별 우위를 포함하는 항들에 의해 제한됩니다.
• 기법: 이 증명은 역상 쿼리별로 압축된 데이터베이스의 크기를 제한하는 양자 무작위 오라클 모델의 기법을 모방합니다.

D. 양자 PRP를 위한 도메인 확장

본 논문은 임의의 양자 보안 강한 의사 난수 치환(strong Pseudorandom Permutation, PRP)의 메시지 길이를 $n$ 비트에서 $2n$ 비트로 확장하는 모듈형 구조를 제시합니다.

• 1단계 (PRP에서 Tweakable Cipher로): 각 튜크(tweak)에 대한 키를 생성하기 위해 (PRP로부터 PRP-PRF 전환 렘마를 통해 유도된) PRF를 사용하여 PRP를 튜커블 사이퍼(tweakable cipher)로 변환합니다. 리프팅 정리는 이 구조가 이상적 암호와 구별 불가능함을 보장합니다.
• 2단계 (Tweakable Cipher에서 2n-bit PRP로): 튜커블 사이퍼를 사용하는 2라운드 피스텔(Feistel) 유사 구조를 사용하여 최종 PRP를 구축합니다.
• 분석: 2라운드 구조의 보안은 양자 양방향 쿼리 하에서 무작위 치환으로부터의 구별 불가능성을 보이기 위해 (리프팅 정리와는 독립적인) 전용 다항식 방법 논증을 사용하여 증명됩니다. 최종 우위 경계에는 $O(q^4/2^n)$과 같은 항이 포함됩니다.

4. 의의 및 주장

본 논문은 양자 보안 증명에서 키가 있는 오라클을 다루는 데 있어 범용적이고, 최적이며, 상태 유지가 가능한 도구를 제공한다는 점에서 그 의의를 가집니다.

• 범용적 장벽의 해결: 이는 양자 환경에서 기본 오라클로부터 키가 있는 오라클으로 구별 불가능성을 리프팅하는 어려움을 해결하며, 이는 이전에는 ad-hoc 증명이나 느슨한 경계를 필요로 했던 문제였습니다.
• 최적성: $O(q^2)$ 손실은 특정 사례에서 그로버 탐색 하한과 일치하는 타이트한(tight) 결과임을 보여주며, 이는 기존의 계산적 설정에서 발견되던 느슨한 $O(q^{1.5})$ 또는 제곱근 손실과 대조됩니다.
• 상태 유지 분석 가능성: 상태 유지 오라클을 지원함으로써, 이 연구는 압축 시뮬레이션 기법에 의존하는 현대 암호학적 프리미티브의 엄격한 분석을 가능하게 합니다. 이는 이전에는 이상적 암호 모델으로 리프팅하기 어려웠던 영역입니다.
• 모듈성: 리프팅 정리는 "블랙박스" 도구로서 작동합니다. 밑바탕이 되는 기본 오라클(예: 압축 치환)의 경계가 개선되면, 리프팅된 키가 있는 오라클의 경계도 즉시 개선되어 미래의 연구를 간소화합니다.

저자들은 자신들의 접근 방식이 직접적인 분석(예: Ideal Cipher에 대한 Carolan 및 Majenz의 분석)을 보완하는 것으로 보고 있습니다. 직접적인 분석이 특정 구조에 대해 더 타이트한 상수를 제공할 수는 있지만, 리프팅 정리는 직접적인 구조적 분석이 불가능할 수 있는 임의의 (그리고 잠재적으로 상태 유지인) 기본 오라클에 적용 가능한 일반적인 프레임워크를 제공합니다.