この論文「Post-Quantum Security of Block Cipher Constructions（ブロック暗号構成のポスト量子セキュリティ）」は、対称鍵暗号、特にブロック暗号とその応用構成（鍵長拡張、ツイーク可能暗号、暗号モード）のポスト量子セキュリティに関する理論的基盤を確立し、具体的なセキュリティ証明を提供するものです。

以下に、論文の技術的概要を問題定義、手法、主要な貢献、結果、そして意義の観点から詳細にまとめます。

1. 問題定義と背景

• 背景: 公開鍵暗号のポスト量子セキュリティ（Shor のアルゴリズムによる脅威）は広く研究されていますが、対称鍵暗号（ブロック暗号など）のポスト量子セキュリティは未開拓の分野です。
• 課題:
  • 現在の対称鍵方式が量子コンピュータに対して安全かどうか、またどの程度の鍵長が必要かが明確ではありません（単に鍵長を倍にするだけでは不十分または過剰である可能性）。
  • 従来の古典的なセキュリティ証明手法（トランスクリプト解析など）は、量子アダプタがスーパーポジション状態でオラクルにアクセスできる状況では適用できません。
  • 特に、量子理想暗号モデル（QICM: Quantum Ideal Cipher Model） における厳密なセキュリティ証明が不足していました。QICM では、攻撃者が理想暗号（ランダムな置换族）に対して量子オラクル（スーパーポジションでの問い合わせ）を持ち、一方で秘密鍵を用いた構成（暗号モードなど）は古典的なオラクルとして扱われるという現実的なモデルです。

2. 手法と技術的革新

この論文は、QICM におけるセキュリティ証明を可能にするための新しい技術的ツールと枠組みを開発しました。

• 理想暗号の再サンプリング補題（Ideal Cipher Resampling Lemma）:

  • 従来の再サンプリング補題はランダム関数やランダム置换に限定されていましたが、著者はこれを理想暗号（Ideal Cipher） に一般化しました。
  • この補題は、量子攻撃者が理想暗号の内部状態をわずかに変更（リプログラミング）されたことに気づく確率が、攻撃者が事前に行った量子問い合わせ数に依存して非常に小さいことを示します。
  • これにより、証明の中で暗号器を「現実の構成」から「理想のランダム置换」へ段階的に置き換えるハイブリッド証明が、量子設定でも有効に行えるようになりました。

• ハイブリッド証明手法の拡張:

  • Alagic ら（2022）が Even-Mansour 暗号で用いた手法を、QICM に対応させ、鍵長拡張やツイーク可能暗号などのより複雑な構成に適用できるように拡張しました。
  • 攻撃者が古典的な問い合わせ（構成へのアクセス）と量子的な問い合わせ（理想暗号への直接アクセス）を混在させるモデルを厳密に扱います。

3. 主要な貢献と結果

著者は、開発した手法を用いて、以下の主要なブロック暗号構成に対して、初めてとなるポスト量子セキュリティ証明（およびtightな境界値）を導出しました。

A. FX 構成（鍵長拡張）

• 対象: FX 構成（$FX(x) = E_{k_0}(x \oplus k_1) \oplus k_2$）。PRINCE や PRIDE などの軽量暗号の基盤。
• 結果: QICM におけるセキュリティ境界を証明しました。
  • 識別利得（Advantage）は、古典問い合わせ数 $q_C$ と量子問い合わせ数 $q_Q$ を用いて、$O((q_C\sqrt{q_Q} + q_Q\sqrt{q_C}) \cdot 2^{-(m+n)/2})$ 程度に抑えられます。
  • この境界は、オフライン・サイモン攻撃（Offline-Simon attack）や Grover+BHT 攻撃などの既知の量子攻撃と一致しており、tight（最適） であることが示されました。
  • これにより、PRINCE 暗号や PRIDE 暗号のポスト量子安全性が確立されました。

B. ツイーク可能ブロック暗号（Tweakable Block Ciphers）

• 対象: LRW 構成と XEX2 構成（XTS-AES の基盤）。
• 結果:
  • LRW: 古典的なバースデー攻撃（$O(2^{n/2})$）に対応する項 $O(q_C^2 2^{-n})$ と、量子鍵探索・衝突発見に対応する項を含む新しい境界を導出しました。
  • XEX2: 同様に、XTS-AES で使用される XEX2 構成のポスト量子セキュリティを証明しました。
  • これらの結果は、QICM だけでなく、平文モデル（Plain Model）でも適用可能です。

C. ブロック暗号モード（Block Cipher Modes）

• 対象: CBC, ECBC, CMAC, GCM, GCM-SST などの主要な暗号モード。
• 結果:
  • 「リフティング定理（Lifting Theorem）」 を提案しました。これは、「構成のポスト量子セキュリティ $\le$ 基盤暗号のポスト量子 SPRP セキュリティ + 構成の情報理論的セキュリティ」という形で、古典的なセキュリティ証明をポスト量子設定へ容易に拡張できる一般則です。
  • この定理を用いることで、GCM などの広く使われているモードが、基盤となるブロック暗号（例：AES）が QICM で安全であれば、モード自体もポスト量子安全であることを示しました。

4. 結果の定量的評価

• FX 構成: 鍵長 $m$、ブロック長 $n$ の場合、攻撃者が $q_C$ 回の古典問い合わせと $q_Q$ 回の量子問い合わせを行う際の識別利得は、$O(q_C\sqrt{q_Q} 2^{-(m+n)/2})$ 程度です。これは、オフライン・サイモン攻撃の複雑性 $q_C \cdot q_Q^2 \approx 2^{m+n}$ と整合します。
• LRW/XEX2: 古典的なバースデー限界 $O(2^{-n/2})$ に加え、量子攻撃による $O(2^{-(m+n)/2})$ 程度の限界が加味されます。特に $m \gg n$ の場合、古典的な限界が支配的になりますが、$q_C \ll q_Q$ のような量子リソースが豊富な状況では、新しい量子攻撃の限界が重要になります。

5. 意義とインパクト

• 理論的基盤の確立: 対称鍵暗号のポスト量子セキュリティ研究において、QICM における厳密な証明手法を初めて体系化しました。
• 実用的な安全性の保証: 現在広く使用されている AES、XTS-AES（ディスク暗号化）、GCM（インターネット通信）などの構成が、量子コンピュータの脅威に対してどの程度の耐性を持つのか、定量的な境界値を提供しました。
• パラメータ選定の指針: 「鍵長を単純に倍にすればよい」という経験則が常に正しいわけではないことを示唆し、攻撃の複雑性に基づいたより精密なパラメータ選定を可能にします。
• 将来の研究への道筋: 開発された「理想暗号の再サンプリング補題」は、他の対称鍵構成（ハッシュ関数、認証付き暗号など）のポスト量子セキュリティ証明に応用可能な強力なツールです。

総じて、この論文は、ポスト量子時代における対称鍵暗号の安全性評価において、単なる仮説ではなく数学的に厳密な証明を提供する重要なマイルストーンとなっています。