技術要約：QROMにおける不完全な完全性を備えた鍵合意の不可能性に向けた研究

1. 問題設定

本論文は、量子ランダムオラクルモデル（QROM）における**量子計算・古典通信（QCCC）**鍵合意プロトコルの安全性に対処している。具体的には、**不完全な完全性（imperfectly complete）**を持つプロトコルの実現可能性を調査している。ここで、不完全な完全性とは、正直な当事者が確定的に（完全な完全性ではなく）逆多項式確率（$\alpha > 0$）で有効な鍵に合意できる状態を指す。

先行研究では、様々な制限下での「完全な完全性」を持つQCCC鍵合意および量子公開鍵暗号（QPKE）に対する無条件の不可能性の結果が確立されている。しかし、正直な当事者が制限のない量子オラクルアクセスを持つ場合の、不完全な完全性を備えたプロトコルのケースは未解決のままであった。Austrinら（2022年）によって特定された重要な障壁は、「シミュレーション予想（Simulation Conjecture）」が成立する場合、古典的な攻撃者はこのようなプロトコルを破ることができないことを示唆している。本論文は、正直な当事者のオラクルアクセスを特定の形式に制限することで、この予想を回避し、計算能力に制限のない量子攻撃者による無条件の攻撃を可能にする。

2. 手法および技術的アプローチ

著者らは、**ヘビー・クエリ学習（heavy-query learning）とランダム・リプログラミング（random reprogramming）**技術を組み合わせた無条件攻撃を構築している。核心となる戦略は、通信を傍受し、正直な当事者が行ったオラクルの「ヘビーな」クエリ集合を学習し、その後、部分的なオラクルを条件として正直な当事者のビューを再サンプリングすることで、鍵を復元する攻撃者（Eve）を用いるものである。

2.1 二メッセージ攻撃

最初の設定では、以下の二ラウンド・プロトコルを検討する：

• Alice は第1ラウンドにおいてオラクルに対して古典的なクエリのみを行い、Bobに古典的なメッセージ（$m_1$）を送信する。
• Bob は任意の量子計算を実行し、量子クエリを行い、量子メッセージ（$\Psi$）を送信することができる。
• Alice は最終ラウンドにおいて量子計算を行い、量子クエリを行うことができる。

攻撃メカニズム：

1. ヘビー・クエリ学習： $m_1$ を受信した際、Eveは学習アルゴリズム（AustrinらおよびKatz & Selaに基づく）を用いて、「$m_1$ を条件とした際にAliceが第1ラウンドで行う可能性が高い」ヘビーな入力（値）を特定する。彼女は、これらのヘビーな入力をクエリすることで、部分的なオラクル $h$ を構築する。
2. 条件付き再サンプリング： Aliceの第1ラウンドのクエリは古典的であるため、$m_1$ と回答のトランスクリプト $h$ が固定されると、Aliceの残存量子状態はこれらの古典的変数のみに依存する。したがって、Eveは条件付き分布 $\omega_{m_1, h}$ から新鮮なビュー $(T'_A, S'_A)$ をサンプリングできる。
3. リプログラミング： EveはBobの量子メッセージ $\Psi$ を傍受する。彼女は、サンプリングされた状態 $S'_A$ と $\Psi$ を用いてAliceの最終アルゴリズムを実行する。その際、ドメイン内ではサンプリングされたトランスクリプト $T'_A$ と一致し、それ以外では元のオラクルと同様に振る舞うリプログラムされたオラクル $H[T'_A]$ を使用する。
4. 分析： セキュリティ損失は、ランダム・リプログラミング・レマ（Random Reprogramming Lemma）（Katz & Sela）によって制限される。Aliceが学習された集合 $Dom(h)$の外側の点をクエリする確率が小さい（パラメータ$\delta$ によって制御される）ため、リプログラミングは量子アルゴリズムの受理確率を大きく変化させない。

2.2 マルチラウンド攻撃

第二の設定は、**古典的通信のプレフィックス（prefix）**が存在する場合、任意のラウンド数を持つプロトコルへと結果を拡張するものである：

• プレフィックス期間中のすべてのメッセージおよびオラクルクエリは古典的である。
• 当事者は量子状態を保持し、局所的な量子計算を行うことができる。
• 最終ラウンドには、Bobからの（おそらく量子的な）メッセージと、Aliceの最終的な量子計算が含まれる。

攻撃メカニズム：

1. 古典的シミュレーション： Eveは、古典的プレフィックスを補助的な古典プロトコルとして扱う。彼女は計算能力に制限がないため、条件付きの残存状態を含むAliceとBobの古典的ビューを正確にシミュレートできる。
2. Barak-Mahordy学習器： Eveは、シミュレートされた古典的ビューに対してBarak-Mahordy学習器（元々は古典的プロトコルのためのもの）を適用し、部分的なオラクル $h$ を学習し、$h$ を条件としたAliceとBobのビューが近似的に独立（積状態）であることを保証する。
3. 再サンプリングと結合： Eveは、$h$ を条件として、AliceとBobに対して独立したビューをサンプリングする。その後、Bobのためのベースとなるオラクルをサンプリングし、それをAliceのためにリプログラミングすることで、これら二つのビューを整合性のあるオラクルへと結合させる。
4. 最終攻撃： Eveは最終的な量子メッセージを傍受し、サンプリングされた状態とリプログラムされたオラクルを用いて、Aliceの最終アルゴリズムを実行する。

3. 主な貢献と結果

3.1 主要な定理

• 定理 1.1（二メッセージ攻撃）： Aliceの第1段階のクエリおよびメッセージが古典的であるあらゆるプロトコルに対し、Bobの鍵を確率 $> \alpha/2$ で復元する、計算能力に制限のない量子攻撃者が、$O(\text{poly}(q, 1/\alpha))$ 回のクエリを用いて存在する。この攻撃者は、Bobの応答前に古典的クエリを行い、その後に量子クエリを行う。
• 定理 1.2（マルチラウンド攻撃）： 古典的クエリ・プレフィックスを持つプロトコルに対して、同様の攻撃が存在する。クエリ複雑性は、総ラウンド数ではなく、プレフィックス内の総クエリ数に依存する。
• 定理 1.3（QPKE攻撃）： これらの結果は、古典的なメッセージ（多項式長）のための**量子公開鍵暗号（QPKE）**が、暗号化、復号、および暗号文がいずれも量子であっても、多項式回のクエリを行う計算能力に制限のない攻撃者に対してIND-CPA安全ではあり得ないことを示唆している。

3.2 具体的な適用

• OSPからの不完全な正解性を持つPKE： 本論文はその結果を、BartusekおよびKhurana（CRYPTO 2025）による盲目的状態準備（OSP）から導出されたPKEスキームに適用している。これは、もしOSPの送信者が古典的なランダムオラクルクエリのみを行う場合、導出されるPKEがQROMにおいて安全ではないことを示している（特に、基礎となるOSPプロトコルが無視可能な誤り率を持つ、すなわち不完全な完全性を持つ場合）。
• 古典的傍受： プロトコル全体（Bobの応答を含む）が古典的である場合、この攻撃は受動的な古典的傍受攻撃へと帰着する。

4. 意義と主張

本論文は、制限された設定において、正直な当事者が後の段階で制限のない量子オラクルアクセスを持つ場合でも、不完全な完全性を備えたQCCC鍵合意の不可能性に向けた進展をもたらした、最初の無条件の攻撃を提供したと主張している。

• シミュレーションの障壁の克服： 著者らは、不完全な完全性を備えたQCCCに対する完全な一般的な古典的攻撃には、シミュレーション予想の反証が必要であることを述べている。正直な当事者の「初期」のクエリを古典的に制限することで、本研究はこの障壁を回避し、予想が偽であることを仮定することなく、無条件の攻撃を可能にしている。
• 制限の厳密性： これらの結果は、重要なトレードオフを浮き彫りにしている。攻撃は、初期のオラクルアクセスが古典的であるという事実に依存している。もしプレフィックスのクエリが量子であった場合、当事者はオラクルと量子もつれ状態となり、ここで用いられている「再サンプリング」の手法が妨げられる。著者らは、プレフィックスにおける量子クエリへの拡張には新しい技術が必要であり、今後の課題であると明記している。
• セキュリティ概念： 本論文は、標準的なCC1QMセキュリティよりも強いセキュリティ概念（インターセプション・キーリカバリ）を定義している。これは、攻撃者が単に有効な状態をシミュレートするだけでなく、鍵を復元することのみを要求するという点で異なるが、導出されるQPKEスキームのIND-CPA安全性を破くには十分である。

要約すると、本論文は、鍵合意プロトコルの初期段階における古典的オラクルアクセスが、不完全な完全性を備えたスキームにとって致命的な弱点となり、プロトコルの残りの部分が完全に量子であったとしても、無制限の量子攻撃者に対してこれらを安全ではないものにすることを実証している。