Post-Quantum Security of Block Cipher Constructions

1. 문제 제기 (Problem)

• 배경: 블록 암호 (AES 등) 는 인터넷 보안, 디스크 암호화 등 현대 암호학의 핵심 요소입니다. 쇼어 (Shor) 알고리즘으로 인해 공개키 암호의 포스트 양자 보안이 활발히 연구되고 있지만, 대칭키 암호의 보안은 여전히 불확실합니다.
• 현재의 한계:
  • 기존 대칭키 암호의 보안 증명은 고전적인 트랜스크립트 (transcript) 기반 기법에 의존하며, 양자 공격자 (중첩 상태에서의 쿼리) 에게는 적용되지 않습니다.
  • 양자 공격 시나리오에서 "이상적인 블록 암호 (Ideal Cipher)" 모델을 어떻게 정의하고 분석할지에 대한 엄격한 프레임워크가 부족했습니다.
  • 현재 실무에서는 Grover 알고리즘의 위협을 피하기 위해 단순히 키 길이를 두 배로 늘리는 것을 가정하지만, 이는 과잉 (overkill) 이거나 오히려 부족할 수 있음을 시사하는 결과들이 존재합니다.
• 목표: 블록 암호 및 이를 기반으로 한 다양한 구성 (Key-length extension, Tweakable cipher, Modes of operation) 에 대한 엄격한 포스트 양자 보안 이론을 정립하고, 구체적인 보안 상한 (Security Bounds) 을 증명하는 것입니다.

2. 방법론 (Methodology)

이 논문은 **양자 이상 블록 암호 모델 (Quantum Ideal Cipher Model, QICM)**을 기반으로 분석을 수행합니다. 이 모델에서 공격자는 이상적인 블록 암호 $E$에 양자 오라클 (중첩 상태) 로 접근할 수 있지만, 키가 숨겨진 구성 (Construction) 에는 고전적 오라클로만 접근할 수 있습니다 (Q1 모델).

주요 방법론적 혁신은 다음과 같습니다:

1. 이상 블록 암호 재샘플링 보조정리 (Ideal Cipher Resampling Lemma):
   • 기존 연구 (Even-Mansour 등) 에서는 무작위 함수 (Random Function) 에 대한 재샘플링 보조정리만 존재했습니다.
   • 저자들은 **이상 블록 암호 (Ideal Cipher)**에 대해 새로운 재샘플링 보조정리를 개발했습니다. 이는 양자 공격자가 이상 블록 암호의 특정 위치를 수정 (Resampling) 하는 것을 감지하지 못함을 보장하며, 보안 증명에서 하이브리드 증명의 핵심 도구로 작용합니다.
2. 하이브리드 증명 기법 (Hybrid Technique) 의 확장:
   • [ABKM22] 등의 기존 기법을 QICM 환경에 맞게 적응화했습니다.
   • 공격자의 고전적 쿼리를 하나씩 이상적인 랜덤 함수로 바꾸는 과정에서, 이상 블록 암호 $E$의 내부 상태를 미세하게 수정하고 나중에 이를 되돌리는 (Reset) 과정을 통해 공격자의 식별 능력을 제한합니다.

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

이 논문은 다음과 같은 주요 구성 요소들에 대해 최초의 포스트 양자 보안 증명을 제시합니다.

A. FX 구성 (Key-Length Extension)

• 대상: FX 구성 (블록 암호의 키 길이를 늘리는 방식: $FX(x) = E_{k_0}(x \oplus k_1) \oplus k_2$).
• 결과: QICM 하에서 FX 구성의 포스트 양자 보안이 증명되었습니다.
  • 식별 우위 (Distinguishing Advantage) 상한: $O((q_C\sqrt{q_Q} + q_Q\sqrt{q_C}) \cdot 2^{-(m+n)/2})$.
  • 여기서 $q_C$는 고전 쿼리 수, $q_Q$는 양자 쿼리 수, $m$은 키 길이, $n$은 블록 크기입니다.
  • ** Tightness ( Tightness):** Grover 알고리즘과 BHT (Brassard-Høyer-Tapp) 충돌 찾기 알고리즘을 결합한 공격이 이 상한과 일치함을 보여, 증명된 보안 상한이 최적임을 입증했습니다.
• 응용: 경량 블록 암호 PRINCE와 PRIDE의 포스트 양자 보안이 이 결과를 통해 즉시 유도됩니다.

B. 가변 블록 암호 (Tweakable Block Ciphers)

• 대상: LRW 및 XEX2 (XTS-AES 디스크 암호화의 기반).
• 결과:
  • LRW: 고전적 충돌 공격 ($q_C^2 \cdot 2^{-n}$) 과 양자 키 탐색/충돌 공격이 결합된 새로운 보안 상한을 도출했습니다.
  • XEX2: LRW와 유사한 분석을 통해 포스트 양자 보안을 증명했습니다.
  • 기존 고전적 "생일 공격 (Birthday Bound)" 한계 ($2^{-n/2}$) 가 양자 환경에서 어떻게 변형되는지 명확히 했습니다.

C. 블록 암호 모드 (Block Cipher Modes)

• 대상: CBC, ECBC, CMAC, GCM, GCM-SST 등 대부분의 표준 블록 암호 모드.
• 일반 정리 (General Lifting Theorem):
  • 블록 암호 모드 $Con[E]$의 포스트 양자 보안은 하부 블록 암호$E$의 SPRP-PQ 보안과 구성의 고전적 정보이론적 보안 ($\delta(q)$) 의 합으로 상한이 결정됨을 보였습니다.
  • 공식: $\text{Adv}_{Con[E]}^{PQ} \leq \text{Adv}_{E}^{SPRP-PQ} + \delta(q)$.
  • 이 정리를 통해 기존 고전적 보안 증명이 포스트 양자 환경으로 자연스럽게 확장됨을 보였습니다.
  • QICM 환경에서는 $E$에 대한 양자 쿼리 수 ($q_Q$) 에 비례하는 항 ($q_Q^2 / 2^m$) 이 추가됩니다.

4. 의의 및 중요성 (Significance)

1. 이론적 기반 정립: 대칭키 암호의 포스트 양자 보안에 대한 체계적인 이론적 토대를 처음으로 마련했습니다.
2. 실무적 지침 제공: 단순히 키 길이를 두 배로 늘리는 것이 항상 최선인지에 대한 정량적 분석을 제공합니다. 특정 구성 (예: FX) 에서는 기존 분석보다 더 정교한 공격 (Grover+BHT 등) 이 가능하므로, 파라미터 선택 시 이를 고려해야 함을 시사합니다.
3. 표준 암호 평가: 현재 널리 사용되는 AES 기반의 XTS-AES (디스크 암호화), GCM (인터넷 통신) 등의 포스트 양자 보안 수준을 엄밀하게 평가할 수 있는 도구를 제공합니다.
4. 기술적 혁신: 이상 블록 암호 모델에서의 재샘플링 보조정리는 향후 다양한 대칭키 암호 구조의 양자 보안 증명을 위한 강력한 도구로 활용될 수 있습니다.

결론

이 논문은 양자 컴퓨팅 시대에 대비하여 블록 암호 및 그 파생 구조의 보안성을 재평가하고, 엄밀한 수학적 증명을 통해 안전한 파라미터 설정을 위한 기준을 제시한 획기적인 연구입니다. 특히, FX, LRW, XEX2, GCM 등 실제 시스템에 적용된 암호들의 포스트 양자 보안 상한을 최초로 도출했다는 점에서 암호학계와 보안 실무계에 큰 영향을 미칠 것으로 예상됩니다.