技術要約：鍵付きオラクルに対する非識別性のリフティング、圧縮理想暗号、およびその他の応用

1. 問題提起

暗号学的安全性の証明において、ベースとなるオラクル（例：各鍵が独立したランダム置換を選択する理想暗号、あるいは各入力が独立したランダムな文字列を選択するランダムオラクル）の指数個の独立したインスタンスからなる鍵付きオラクルを用いてスキームをモデル化することは一般的である。古典的なセキュリティモデルから量子セキュリティモデルへと移行する際に、根本的な課題が生じる：

• 量子重ね合わせの問題： 量子アドバーサリは、鍵の重ね合わせに対して鍵付きオラクルにクエリを送ることができる。この単一のクエリは、基礎となるベース・オラクルのすべてのインスタンスに同時に接触することを意味する。
• 古典的手法の失敗： ハイブリッド引数のような標準的な古典的証明手法は、この設定では機能しない。古典的なケースでは、ベース・オラクルのインスタンスを一つずつ置き換えることができる（クエリ数 $q$ に対して線形な損失を伴う）。しかし量子の場合、単一のクエリがすべてのインスタンスにまたがるため、単純なハイブリッド引数は成立しない。
• 先行研究の限界： これらの問題を扱う既存の手法は、定量的非効率性（識別優位性に超多項式または平方根の損失を導入する）を抱えているか、あるいは適用範囲の制限（ステートレスなオラクルにのみ適用される）がある。圧縮オラクル（Zhandryの圧縮オラクル、UnruhやCarolanの圧縮置換オラクルなど）のような有用なオラクルの多くは、クエリごとに内部メモリが進化するステートフルなものである。量子設定におけるステートフルなオラクルに対する汎用的なリフティング定理は存在していなかった。

本論文は、次のような一般的な問いに取り組んでいる：もし2つのベース・オラクル $O_0$ と $O_1$ が $q$ 回の量子クエリの下で区別不能であるならば、それらに対応する鍵付きオラクル $O_0^{\mathcal{K}}$ と $O_1^{\mathcal{K}}$ もまた区別不能であり、その際のセキュリティ損失はいくらになるか？

2. 手法

著者らは、多項式法とマルコフの兄弟不等式を組み合わせた新しい手法を用いることで、汎用的な非識別性リフティング定理を確立している。

リフティング定理

核心となる貢献は、ベース・オラクル $O_0$ と $O_1$ が $q$ 回の量子クエリを用いて優位性 $\epsilon$ で区別不能であれば、それらの鍵付き対応物は最大 $8q^2 \epsilon$ の優位性で区別不能であるという定理である。

主要な技術的ステップ：

1. パラメータ化された還元： 証明は、ベース・オラクル $O_0$ と $O_1$ を区別する還元アルゴリズム $\mathcal{B}$ を構築する。$\mathcal{B}$ は、パラメータ $p$ および $z$ を持つベルヌーイ分布からサンプリングされた関数 $H$ および $G$ に基づいてクエリをルーティングすることで、アドバーサリのための鍵付きオラクルをシミュレートする。
2. 多項式定式化： アドバーサリの識別優位性は、ルーティング・パラメータ $p$ における関数 $f(p)$ の差 $|f(1) - f(0)|$ として表現される。ここで $f(p)$ は、ベース・オラクルが $O_1$ であり、ルーティング・パラメータが $p$ であるときにアドバーサリが1を出力する確率である。
3. 導関数との接続： 著者らは、導関数 $f'(p)$ が別の関数 $g_p(z)$ の $z=0$ における導関数に関連していることを示す。決定的なことに、$g_p(z)$ は $z$ に関する次数が最大 $2q$ の多項式であることが証明されている。
4. 不等式による境界設定： マルコフの兄弟不等式（およびラグランジュ補間を用いた特定の変種）を用いて、多項式の導関数を抑え込む。これにより、連続的な差 $|f(1) - f(0)|$ を、還元 $\mathcal{B}$ の離散的な識別優位性に結びつけることができ、その際に $O(q^2)$ の乗法的係数が発生する。

このアプローチは、統計的および計算論的な設定の両方で機能し、決定的に、オラクルが静的であることを必要としないため、ステートフルなオラクルにも適用可能である。

3. 主要な貢献と結果

A. 汎用的な非識別性リフティング定理

本論文は、任意の（おそらくステートフルな）2つのオラクル $O_0$ と $O_1$ について、それらが $q$ 回の量子クエリによって優位性 $\epsilon$ で区別不能であれば、それらの鍵付きバージョンは最大 $8q^2 \epsilon$ の優位性で区別不能であることを確立している。

• 最適性： 著者らは、特定の作為的な選択されたオラクルに対して、$O(q^2)$ の損失が最適であることを示しており、これは標準的なグローバー探索攻撃によって達成可能な優位性と一致する。
• ステートフルへの対応： 先行研究とは異なり、この定理はステートフルなオラクルに適用可能であり、圧縮オラクルのような複雑なシミュレータの解析を可能にする。

B. 圧縮理想暗号

直接的な応用として、著者らはCarolanの圧縮置換オラクルを理想暗号モデルへと拡張し、効率的に実装可能な圧縮理想暗号 (cIC) を作成している。

• 構成： 各鍵に対する部分置換のデータベースを保持するステートフルなシミュレータを定義する。
• セキュリティ境界： リフティング定理を用いることで、cICが真の理想暗号と区別不能であることを証明する。圧縮置換オラクルの単一インスタンスの境界が $\Delta_{cpO}(n, q)$ である場合、cICの境界は $8q^2 \cdot \Delta_{cpO}(n, q)$ となる。
• モジュール性： 著者らは、圧縮置換オラクルに関する将来のいかなる単一インスタンス境界の改善（例：Kim [Kim26] や Carolan & Majenz [CM26] による最近の改善）も、リフティングを再証明することなく、自動的に圧縮理想暗号の境界を改善することを強調している。

C. Davies-Meyer の原像耐性

圧縮理想暗号を用いて、本論文は量子理想暗号モデルにおけるDavies-Meyer圧縮関数の原像耐性を証明している。

• 結果： アドバーサリが原像を見つける確率は、$q^2/2^n$ および圧縮理想暗号の識別優位性を含む項によって抑えられる。
• 手法： 証明は、原像クエリごとに圧縮データベースの大きさを抑えるという、量子ランダムオラクルモデルのテクニックを模倣している。

D. 量子PRPのドメイン拡張

本論文は、任意の量子安全な強擬似ランダム置換 (PRP) のメッセージ長を $n$ ビットから $2n$ ビットへと拡張するためのモジュラーな構成を提示している。

• ステップ 1 (PRP から 転換可能暗号へ): 各ツイークに対して鍵を生成するために（PRPからPRP-PRFスイッチング補題を通じて得られる）PRFを用いて、PRPを転換可能暗号へと変換する。リフティング定理は、この構成が理想暗号と区別不能であることを保証する。
• ステップ 2 (転換可能暗号 から $2n$ ビット PRP へ): 最終的なPRPを構築するために、転換可能暗号を用いた2ラウンドのフェイステル風の構成を使用する。
• 解析： 2ラウンド構成の安全性は、量子双方向クエリの下でのランダム置換からの非識別性を示すために、専用の多項式法による議論（リフティング定理とは独立したもの）を用いて証明される。最終的な優位性境界には $O(q^4/2^n)$ のような項が含まれる。

4. 意義と主張

本論文の意義は、鍵付きオラクルを含む量子セキュリティ証明のための、汎用的、最適、かつステートフルなツールを提供することにある。

• 汎用的な障壁の解決： ベース・オラクルから鍵付きオラクルへの非識別性のリファリングに伴う困難（これは以前、アドホックな証明を必要としたか、あるいは緩い境界を招いていた）を解決した。
• 最適性： $O(q^2)$ の損失は特定のケースにおいてタイトであることが示されており、これはグローバー探索の低減限界と一致する。これは、従来の計算論的設定で見られた緩い $O(q^{1.5})$ や平方根の損失とは対照的である。
• ステートフル解析の実現： ステートフルなオラクルをサポートすることで、本研究は、圧縮シミュレーション技術に依存する現代的な暗号プリミティブの厳密な解析を可能にした。これは、以前は理想暗号モデルへのリフティングが困難であった。
• モジュラー性： リフティング定理は「ブラックボックス」ツールとして機能する。基礎となるベース・オラクル（例：圧縮置換）の境界の改善は、直ちにリフティングされた鍵付きオラクルの境界の改善へとつながり、将来の研究を効率化する。

著者らは、自身のアプローチを直接的な解析（CarolanやMajenzによる理想暗号の解析など）を補完するものと考えている。直接的な解析は、特定の構造に対してよりタイトな定数を導き出す可能性があるが、リフティング定理は、直接的な構造解析が不可能な、任意（かつ潜在的にステートフルな）ベース・オラクルに適用可能な一般的なフレームワークを提供する。