技術要約：マイクロクリプト（Microcrypt）の構築における失敗例

1. 問題提起

量子暗号の分野は近年、「マイクロクリプト（Microcrypt）」に焦点を当てている。これは、古典的な一方向関数（OWF）よりも弱い仮定に基づいた暗号プリミティブ（擬似ランダム状態（PRS）、擬似ランダムユニタリ（PRU）、一方向状態生成器（OWSG）など）の構築を指す。具体的には、研究者たちは、NPオラクルを備えた敵対者に対しても安全性を維持できるプリミティブを模索している。

いくつかの候補となる構成（ハミルトニアン位相状態、IQP群作用、および様々なクリフォード・モノミアル・クリフォード（CMC）アーキテクチャなど）が提案されてきたが、NP支援型のアドバーサリに対する系統的な暗号解読は欠如していた。中心となる課題は、これらの構成が意図せずして古典的な一方向関数の存在を内包してしまい、それによってマイクロクリプトとして不適切になってしまうのではないかという点である。本論文は、次のような問いに取り組む：「一方向関数やNP困難性を内包してしまうために、PRSやPRUを構築するための自然なレシピとはどのようなものか？」

2. 手法

著者らは、候補となる構成を分析し、打破するための2つの主要な技術的フレームワークを開発している。

A. 計算可能な状態に対するNP支援シャドウ・トモグラフィ

著者らは、NPオラクルを用いて量子状態を学習する効率的なアルゴリズムを導入している。

• 計算可能な状態（Computable States）: キー $k$ が与えられたとき、計算基底の任意の振幅と位相が古典的に効率よく計算できる場合、状態の族 $\{|\psi_k\rangle\}$ は「計算可能」であると定義される。
• 攻撃戦略: アルゴリズムは以下の2段階で進行する。
  1. 基底分布のマッチング: 未知の状態のコピーを計算基底で測定し、古典的なトランスクリプト（記録）を得る。NPオラクルを用いて、観測されたトランスクリプトの尤度を最大化する候補キー $k_0$ を探索する。これにより、未知の状態の振幅分布を近似するキーを復元する。
  2. 干渉による位相抽出: 基底測定では破棄されてしまう位相情報を復元するために、「参照状態」 $|\psi_{k_0}^+\rangle$（候補キーの正の振幅を持つ状態）を構築する。次に、未知の状態とこの参照状態との間で制御SWAP干渉実験を行う。これにより、相対的な位相情報の抽出が可能になる。
  3. 最終的なキー復元: この干渉分布からのサンプルを収集し、第2のNPクエリを用いて、これらの位相に敏感なサンプルに対する尤度を最大化するキー $h$ を見つけ出す。
• 結果: 計算可能な状態を持つあらゆるOWSGの族に対して、NPオラクルを持つアドバーサリは、多項式時間で生成器を反転（高い忠実度を持つ状態を生成するキーを見つけること）できる。

B. ユニタリ体の学習に関するNP支援（CMC攻撃）

著者らは、$U_k = C_{2,k} M_k C_{1,k}$ という形式のユニタリ体（$C$ はクリフォード・ユニタリ、$M$ はモノミアル層（置換と位相））に対する特定の攻撃を開発した。

• 戦略: この攻撃はベル状態測定を利用する。ベル状態 $|\beta_{a,c}\rangle$ を準備し、両方のレジスタに未知のユニタリ $U$ を適用し、ベル基底で測定することで、アドバーサリは「変位（displacement）」の制約を得る。
• クリフォード補正: 外側の層がクリフォードであるため、アドバーサリはこれらの層がベル基底のラベルをどのように置換するかを古典的に計算できる。これらのクリフォード層を古典的に「元に戻す」ことで、問題は、観測された変位が中間のモノミアル層 $M_k$ と矛盾しないかを確認することへと還元される。
• NPクエリ: アドバーサリはNPオラクルに対し、「すべての観測された変位制約を説明できる単一のキー $h$ と一連のウィットネス文字列が存在するか？」と問いかける。
• 結果: いかなるCMC構成においても、NPオラクルは多項式回のクエリを用いて、当該ユニタリ体をハール乱数ユニタリと区別できる確率が高い。さらに、探索から決定への還元（search-to-decision reduction）により、アドバーサリはキーを学習することができる。

3. 主な貢献と結果

A. 計算可能なOWSGの反転

本論文は、計算可能な状態を持つすべてのOWSGの族は、BQPNP（NPへのアクセスを持つ量子多項式時間）において反転可能であることを証明している。

• 一方向関数への含意: もしあるOWSGが計算可能であるだけでなく、サンプリング可能（すなわち、キーが与えられたときに状態の測定分布から古典的に効率よくサンプリングできること）であるならば、そのようなOWSGの存在は古典的な一方向関数の存在を内包する。
• 具体的な破壊事例: この結果は、以下のセキュリティを打破する：
  • ハミルトニアン位相状態 (HPS): 一方向関数よりも弱い仮定に依存すると推測されていたが、著者らはこれらがOWFを内包することを示した。
  • IQP群作用状態: MorimaeとXagawaによって提案された困難性仮定は、OWFを内包することが示された。

B. 擬似ランダムユニタリ (PRU) の破壊

本論文は、多くの著名なPRUアーキテクチャがNP支援型のアドバーサリに対して脆弱であることを示している：

• PFCおよびC2PFC1: クリフォード層の間に置換/位相層を挟んだ構成（例：$C_2 P F C_1$）は、ハール乱数と区別され、学習される。
• LRFCおよびブロック化されたバリアント: クリフォードの端点を持つ様々なLuby-Rackoff関数構成が破壊される。
• 一般化: この攻撃は、「中間」の層がモノミアルであり、端点が効率的に記述可能なクリフォードであるあらゆるユニタリ族に適用される。

C. 生き残った候補の特定

論文では、現在の手法では攻撃を提供できない構成を明示的にリストアップしており、これらがマイクロクリプトの妥当な（ただし未証明の）ルートとして残っていることを述べている。これらには以下が含まれる：

• 多くの混合ラウンドを持つ完全なPRSS（擬似ランダム状態スクランブラー）ウォーク。
• 長いKacウォーク。
• 重複するブロックまたはモノミアル層の間に中間クリフォードを持つ構成（例：第3のブロック化LRFC形式）。
• 隠れた基底のハミルトニアン力学。

4. 意義と主張

著者らは、本研究をマイクロクリプトの分野における「ガードレール（防護柵）」を確立するものとして位置づけている。主な主張は以下の通りである：

1. 系統的な暗号解読: 彼らは、アドホックな攻撃を超えて、マイクロクリプトの候補を評価するための一般的な手法（NP支援シャドウ・トモグラフィおよびCMC解析）を提供する。
2. ノーゴー（No-Go）結果: 彼らは、自然な構成の大部分（具体的には、計算可能な振幅やクリフォード・モノミアル・クリフォード構造に依存するもの）は、意図せずして古典的な一方向関数を内包しているか、あるいはNPオラクルによって打破されるため、マイクロクリプトを実現できないことを示す。
3. 将来の研究への方向付け: どのアーキテクチャが失敗するかを特定することで、彼らは実現可能なマイクロクリプト・プリミティブの探索範囲を狭めている。これは、将来の構成が、おそらくNPの複雑性クラスの外側にある仮定に依拠し、かつ著者らが脆弱であると示した特定の構造的パターン（計算可能な振幅、単純なクリフォード・モノミアル・クリフォード形式）を避ける必要があることを示唆している。

結論として、マイクロクリプトの展望は依然として開かれているものの、計算可能かつサンプリング可能な状態構成、および標準的なCMCユニタリアーキテクチャといった「低い位置にある果実（容易な対象）」は、一方向関数を伴わない暗号の候補としては排除された。