Quantum Oracle Distribution Switching and its Applications to Fully Anonymous Ring Signatures

이 논문은 양자 랜덤 오라클 모델 (QROM, Quantum Random Oracle Model) 하에서 완전 익명성 (Fully Anonymous) 을 보장하는 링 서명 (Ring Signatures) 의 보안성을 증명하는 것을 목표로 합니다. 특히, 양자 컴퓨팅 시대에 필수적인 '부인 가능한 인증 키 교환 (Deniable Authenticated Key Exchange, DAKE)'을 위한 Signal 프로토콜의 후속 양자 버전 구현에 핵심적인 역할을 하는 두 가지 주요 링 서명 구성 방식에 대한 QROM 보안 증명을 제시합니다.

다음은 논문의 상세 기술 요약입니다.

1. 연구 배경 및 문제 제기 (Problem)

• 링 서명의 중요성: 링 서명은 그룹 구성원이 자신의 신원을 드러내지 않고 그룹을 대표하여 메시지를 서명할 수 있게 해주는 암호학적 원시 (Primitive) 입니다. 이는 Signal 프로토콜과 같은 엔드 - 투 - 엔드 암호화 메신저의 '부인 가능한 인증 키 교환 (DAKE)' 구현에 필수적입니다.
• 양자 위협: 현재 널리 사용되는 Signal 프로토콜 (X3DH 등) 은 양자 컴퓨터 공격에 취약합니다. 이를 해결하기 위해 양자 내성 (Post-Quantum, PQ) 링 서명이 필요하지만, 기존 제안된 대부분의 PQ 링 서명 구성 (AOS 프레임워크 기반, 링 트랩도어 기반 등) 은 고전적인 랜덤 오라클 모델 (ROM) 에서만 보안이 증명되었습니다.
• ROM 의 한계: ROM 은 양자 공격자 (오라클에 양자 쿼리를 수행할 수 있는 공격자) 에 대해 보안성을 보장하지 않습니다. 따라서 PQ 환경에서 안전한 DAKE 를 구축하려면 QROM에서의 보안 증명이 필수적입니다.
• 핵심 문제: 기존에 ROM 에서만 증명된 두 가지 주요 링 서명 방식 (AOS 변환 기반, 링 트랩도어/함수 기반) 을 QROM 에서 어떻게 안전하게 증명할 것인가? 특히, 기존 ROM 증명에서 사용되던 'Rényi 발산 (Rényi Divergence)' 기반의 도메인 균일성 (Domain Uniformity) 논리가 QROM 에서 무효화될 수 있다는 점이 큰 장애물이었습니다.

2. 주요 방법론 (Methodology)

저자들은 두 가지 주요 접근법을 사용하여 QROM 보안 증명을 수행했습니다.

A. 양자 오라클 분포 전환 (Quantum Oracle Distribution Switching)

QROM 에서 오라클의 출력 분포를 변경할 때 발생하는 차이를 정량화하기 위한 새로운 기술적 도구를 개발했습니다.

• 통계적 거리 (Statistical Distance) 기반: 압축 오라클 (Compressed Oracle) 기법을 사용하여, 두 다른 분포 $P$와 $Q$를 가진 오라클에 대한 양자 알고리즘의 출력 간 통계적 거리를 $O(q\sqrt{\epsilon})$로 엄밀하게 bound 했습니다.
• Rényi 발산의 한계와 해결책:
  • 문제: 고전적인 Rényi 발산 기반의 bound 는 양자 쿼리 환경에서는 성립하지 않습니다. 저자들은 Deutsch-Jozsa 알고리즘을 이용한 반례를 제시하여, Rényi 발산만으로 전체 오라클 분포를 교체하는 것이 불가능함을 보였습니다.
  • 해결: 전체 분포를 교체하는 대신, 적응형 재프로그래밍 (Adaptive Reprogramming) 기법을 활용하여 서명 오라클이 사용하는 일부 위치 (Salt 가 포함된 입력) 만을 다른 분포로 재샘플링하는 방식을 제안했습니다. 이를 통해 Rényi 발산의 성질을 부분적으로만 적용하여 유효한 보안을 유도했습니다.

B. 두 가지 링 서명 구성에 대한 적용

1. 링 트랩도어 함수 (Ring Preimage Sampleable Functions, RPSF) 기반:

   • Gandalf, FalconRS 등의 구성을 일반화한 새로운 원시인 RPSF를 정의했습니다.
   • History-Free Reduction: 통계적 거리 논리를 사용하여 서명 오라클과 랜덤 오라클을 시뮬레이션하는 증명 기법을 QROM 으로 확장했습니다.
   • 적응형 재프로그래밍: Salt 를 사용하여 입력의 최소 엔트로피를 확보한 후, 서명 오라클의 특정 위치만 재프로그래밍하여 RPSF 의 속성 (역상 샘플링 불가탐지성 등) 을 이용해 보안성을 증명했습니다.

2. AOS (Abe-Ohkubo-Suzuki) 프레임워크 기반:

   • $\Sigma$-프로토콜을 링 서명으로 변환하는 AOS 변환에 대한 QROM 증명을 제시했습니다.
   • 일반적인 $\Sigma$-프로토콜: '측정 및 재프로그래밍 (Measure-and-Reprogram)' 기법을 사용하여 UF-NRA(No-Ring Attack) 보안성을 증명했습니다. (링 크기에 따라 지수적 손실이 발생하지만, 링 크기가 2 인 Signal 용도로는 유효함).
   • Commit-and-Open (C&O) $\Sigma$-프로토콜: 압축 오라클 데이터베이스 속성과 양자 전이 용량 (Quantum Transition Capacity) 프레임워크를 활용하여, Merkle 트리 기반 프로토콜까지 포함하는 곱셈적으로 Tight 한 (Multiplicatively Tight) 보안 증명을 제시했습니다.

3. 주요 기여 (Key Contributions)

1. QROM 하의 첫 번째 완전 익명 링 서명 증명: Signal 프로토콜에 적합한 두 가지 주요 링 서명 구성 (AOS 기반, RPSF 기반) 에 대해 QROM 보안성을 최초로 증명했습니다.
2. 양자 오라클 분포 전환 이론의 정립:
   • 통계적 거리에 대한 Tight 한 bound 를 제시했습니다.
   • Rényi 발산을 QROM 에 적용할 수 없는 이유를 반례로 증명하고, 적응형 재프로그래밍을 통한 우회 방법을 제시했습니다. 이는 Falcon 등 다른 PQ 암호 체계의 QROM 분석에도 중요한 시사점을 줍니다.
3. RPSF (Ring Preimage Sampleable Functions) 의 형식화: Gandalf 등의 구체적인 구성을 포괄하는 일반적인 RPSF 원시를 정의하고, 이를 기반으로 한 범용 링 서명 구성 및 보안 증명을 제시했습니다.
4. AOS 링 서명의 Tight한 증명: C&O 구조를 가진 $\Sigma$-프로토콜에 대해 링 크기에 비례하지 않는 Tight 한 보안 bound 를 유도했습니다.

4. 결과 및 성능 (Results)

• 보안성: 제안된 모든 구성은 QROM 하에서 강한 부인 불가능성 (Strong Unforgeability) 과 완전 익명성 (Full Anonymity, Full Key Exposure 하에서도) 을 만족함이 증명되었습니다.
• Falcon 암호 체계에 대한 시사점: 논문의 분석은 NIST 표준 후보인 Falcon 서명의 현재 QROM 보안 증명 (Rényi 발산 기반) 이 양자 환경에서 유효하지 않을 수 있음을 시사합니다. 저자들은 Falcon 의 실제 구현이 Salt 와 PFDH(Probabilistic Full-Domain Hash) 구조를 사용하므로, 제안된 적응형 재프로그래밍 기법을 통해 QROM 보안을 재검토할 수 있음을 언급했습니다.
• 효율성:
  • AOS 기반의 일반적 bound 는 링 크기에 따라 지수적으로 감소하지만, 링 크기가 2 인 Signal 용도에서는 의미 있는 보장을 제공합니다.
  • C&O 기반의 bound 는 Tight 하여 실제 적용 시 더 유리합니다.
  • RPSF 기반 구성은 기존 ROM 증명과 유사한 수준의 효율성을 유지하면서 QROM 보안을 달성했습니다.

5. 의의 및 결론 (Significance)

이 논문은 양자 내성 (Post-Quantum) 암호학의 중요한 이정표입니다.

• Signal 프로토콜의 양자 내성화: 현재 전 세계적으로 사용되는 Signal 프로토콜을 양자 공격으로부터 안전하게 만들기 위해 필수적인 '부인 가능한 링 서명'에 대한 QROM 보안 증명을 제공함으로써, PQ Signal 프로토콜 구현의 이론적 기반을 확고히 했습니다.
• QROM 증명 기법의 발전: Rényi 발산과 통계적 거리를 QROM 환경에서 어떻게 다뤄야 하는지에 대한 깊은 통찰과 새로운 기법 (분포 전환, 적응형 재프로그래밍) 을 제시하여, 향후 다른 PQ 암호 원시들의 보안 분석에 귀중한 도구를 제공합니다.
• 실용적 적용: Gandalf, Erebor, MayoRS 등 기존에 제안된 구체적인 링 서명 schemes 들이 QROM 하에서도 안전함을 보장받게 되어, 실제 양자 내성 메시징 시스템 구축에 직접적으로 활용될 수 있게 되었습니다.

요약하자면, 이 논문은 양자 컴퓨팅 시대에 안전한 익명 통신을 위한 핵심 기술인 링 서명의 보안성을 이론적으로 완성하고, 이를 실제 표준화 및 구현에 적용할 수 있는 길을 열었다는 점에서 매우 중요한 의미를 가집니다.