技術的概要：高次元ノイズ経路空間における正確な隠れ経路の復元

1. 問題定義

本論文は、高次元離散経路空間に位置する数学的逆問題である「正確なノイズ隠れ経路復元問題（Exact Noisy Hidden Path Recovery Problem）」を導入する。フェインマン経路積分などの標準的な物理的応用が、鞍点近似や変分近似を通じて大域的振幅、支配的な巨視的挙動、または分配関数を推定することを目的とするのに対し、本研究は単一の隠れた微視的経路の正確な復元に焦点を当てる。

中心的な対象は、隠れ経路 $\gamma^\star = (x_0, x_1, \dots, x_T)$ であり、ここで $x_i \in \mathbb{Z}_q^n$ である。経路は以下の遷移モデルに従って進化する：
$$x_{i+1} = x_i + \Delta_i + \varepsilon_i + \eta_i \pmod q$$
ここで：

• $\Delta_i \in D$ は巨視的増分（粗い軌道）を表す。
• $\varepsilon_i \in E$ は微視的摂動（微細な偏差）を表す。
• $\eta_i$ は内部ノイズを表し、しばしば離散ガウス分布としてモデル化される。

公開データは経路そのものでも、短いハッシュダイジェストでもなく、観測変数 $Y = \Phi(\gamma, \varepsilon, \eta)$ の大規模ベクトルである。これらの観測変数には、射影、集約和、量子化、非線形変換、およびランダム化された観測マップが含まれ得る。目的は、$Y$ と公開パラメータから、正確な微視的対象 $X^\star = (x_0, \Delta, \varepsilon, \eta)$ を再構成することである。

重要な区別として、近似再構成（距離的に近い経路を復元すること）と正確な復元（状態と摂動の正確な系列を復元すること）がなされる。この離散的設定において、単一の誤った微視的摂動は、近似解を無効にする。

2. 手法と枠組み

本論文は、量子力学の主張を避けつつ、経路積分の概念を構造的なインスピレーションとして用いながら、有限体算術と組合せ的数え上げを用いて問題を形式化する。

2.1 数学的形式

• 状態空間: $\mathbb{Z}_q^n$（$q$ が素数の場合は $\mathbb{F}_q^n$）上で定義される。
• 経路空間: 全ての系列 $\Omega_{n,T,q}$ の集合は、基数 $q^{n(T+1)}$ を持つ。
• 観測マップ: 関数 $\Phi: \mathcal{X} \to \mathcal{Y}$ は、微視的対象を観測ベクトルに写す。「ファイバー」$\Phi^{-1}(Y)$ には、観測と整合する全ての対象が含まれる。
• 識別可能性: 本論文は、$\Phi$ が生成サポート上で単射である場合のみ、正確な復元が情報理論的に可能であることを確立する。ファイバーが大きい場合、計算能力に関わらず、追加情報なしには正確な復元は不可能である。

2.2「短いダイジェストなし」の原則

手法上の中心的な貢献は、公開観測ベクトル $Y$ は大規模でなければならないという論点である。経路空間を短いダイジェスト（例えば 256 ビットのハッシュ）に圧縮することは、逆問題を、経路構造ではなくダイジェストのエントロピーによって支配される原像探索へと縮退させる。本論文は、正確な復元の研究においては、公開鍵が、探索空間を縮退させることなく意味のある逆問題を定義するのに十分な情報を保持する、構造化された高次元ベクトルでなければならないと主張する。

2.3 攻撃分類と緩和策

本論文は、フレームワークをポスト量子暗号の候補として扱いながら、展開されたシステムの主張を明示的に避けつつ、潜在的な攻撃と構造的弱点を体系的に分類する。特定された主要な攻撃ベクトルは以下の通りである：

• 線形化: 観測変数がアフィンである場合、問題をガウス消去法に還元する。
• 格子還元: 小さなノイズを持つ近似線形構造を利用する（LWE に類似）。
• 動的計画法: 観測変数が時間的に局所的に分解され、状態空間が小さい場合、経路を解く。
• 中間相遇法: 経路を独立した半分に分割できる性質を利用する。
• SAT/SMT ソルバー: 問題を制約充足問題として符号化する。
• 近似/丸め: 鞍点法や勾配法を用いて粗い経路を見つけ、それを正確な証人に丸める。
• 統計的漏洩: 複数のインスタンス間の相関によって生成器を露呈させる。

緩和の原則には、集約前の非線形性の確保、グローバルな時間結合の追加、連続性を破壊するための量子化の使用、およびノイズと摂動分布における高エントロピーの維持が含まれる。

3. 主要な貢献

本論文は、以下の具体的な貢献を行う：

1. 問題の定式化: 微視的正確性と巨視的近似を分離する、独立した逆問題として正確なノイズ隠れ経路復元問題を定義する。
2. 情報限界: 観測変数の情報量によって実効的な復元の難易度が制限されることを示す基本的な限界を証明する。正確な復元が目的である場合、大規模な経路空間を短いダイジェストに圧縮できないことを示す。
3. 復元の階層: 復元の概念の階層（粗い記述子 $\to$ 近似 $\to$ ファイバー復元 $\to$ 正確な状態 $\to$ 正確な微視的）を確立し、近似が正確な復元を意味しないことを証明する。
4. 暗号学的仮定: 攻撃者が大規模な観測ベクトルから植え付けられた証人を復元しなければならない探索ゲームを定義する正確なノイズ隠れ経路一方向性仮定を提案する。
5. 構造的分析: 特定の構造的漏洩リスク（テレスコピック和、線形漏洩、過剰決定/不足決定システム）を特定し、緩和マトリクスを提供する。
6. 研究ロードマップ: 数学的関係から将来のプリミティブへの保守的な道筋を概説し、現在、完全な暗号方式や鍵封入機構（KEM）が定義されていないことを明示する。

4. 結果と知見

• 数え上げ推定: 本論文は、経路履歴の正確な数え上げを提供する。分岐係数 $b$、微視的摂動サイズ $r$、ノイズサポート $s$ に対して、微視的履歴の数は $(brs)^T$ である。 moderate なパラメータ（例：$b=256, r=256, T=256$）であっても、探索空間は $2^{4000}$ を超え、網羅的な列挙は不可能であるが、これは構造的攻撃を排除するものではない。
• 射影の曖昧さ: 定理 4.2 は、経路を次元 $n$ から $k$ に射影すると、単一の射影された軌道に対して $q^{(n-k)(T+1)}$ の経路の曖昧さが生じることを証明する。
• 量子化とノイズ: 本論文は、量子化が異なる対象を同じ観測ビンに統合する方法と、内部ガウスノイズが微視的曖昧さを増大させ、粗い再構成と正確な復元を分離する方法を分析する。
• ファノの不等式の適用: 本論文はファノの不等式を適用し、高い条件付きエントロピー（大きなファイバー）が、無制限のものを含め任意の復元規則のエラー確率に下限を課すことを示す。

5. 意義と主張

本論文の主張は控えめである。これは、展開可能な暗号システム、署名方式、または KEM を提案するものではない。その意義は以下の点にある：

• 候補となる困難な問題の定義: 近似と正確性の分離に動機付けられ、標準的な格子問題や符号化問題とは区別される、正確なノイズ隠れ経路復元という精密な数学的関係を特定する。
• 観測変数の役割の明確化: 根本的な難しさが大規模な経路空間の構造に依存する場合、公開鍵に短いダイジェストを使用するという暗号学的慣習に挑戦する。
• 研究枠組みの提供: 線形化、動的計画法、統計的漏洩に対する具体的なテストを含む、将来の実装のための厳密なチェックリストを提供する。
• ポスト量子への関連性: 観測変数の族が隠れた群対称性を回避する限り、アーベル群における隠れた部分群構造に依存するショアのアルゴリズムが直接適用されないかもしれないという、ポスト量子暗号の方向性を示唆する。

著者らは、この枠組みが数学的および暗号学的研究の両方の基盤として機能すると結論づけている。次の段階では、具体的な観測変数の族を構築し、それらのファイバーを分析し、粗い近似が実行可能であるが正確な微視的復元が計算量的に困難であるような領域が存在するかどうかを実証的に検証する必要がある。そのような証拠が集められるまで、この提案は安全なプリミティブではなく、候補となる関係として留まる。