Deterministic Johnson--Lindenstrauss Projections from Pisot $\beta$-Transformations for Zero-Knowledge Private Routing

技術要約：ゼロ知識プライベート・ルーティングのための、ピソット $\beta$ 変形に基づく決定論的ジョンソン＝リンデンシュトラウス投影

1. 問題提起

ゼロ知識（ZK）証明システムを用いたプライベート・ルーティングにおいて、証明者は、メッセージの埋め込み $v \in \mathbb{R}^d$ が、公開されたセントロイドの集合 $C = \{c_1, \dots, c_N\}$ によって定義される許可されたセマンティック・クラスに属していることを証明しなければならない。これは通常、最近傍セントロイド・テストを介して行われるが、これには $O(Nd)$の算術制約が必要となる。現代的な埋め込み次元（$d \in [768, 4096]$）を考慮すると、この制約数は証明サイズと証明者の計算時間を支配する要因となる。

標準的な解決策は、次元を $m \ll d$ に削減するためのジョンソン＝リンデンシュトラウス（JL）投影である。しかし、古典的なJL行列はランダムである。ZKの文脈では、ランダム行列を使用すると、回路がその行列をコミットし、そのサンプリングの正当性を証明する必要が生じ、投影によって排除しようとしたはずの計算コストが再導入されてしまう。さらに、ランダム行列はサンプリング過程の証明を要求するため、リークのリスクを生じさせる。課題は、以下の条件を満たす公開、決定論的、かつ固定された投影行列を構築することである：

1. 距離の保存を数学的に保証すること。
2. 回路の有限体（finite field）にネイティブであること。
3. 回路内でのランダム性やサンプリングの証明を必要としないこと。

2. 手法

著者らは、投影行列 $A$ を、標準化されたピソット $\beta$ 変形の軌道から構築することを提案している。

• 写像: 単位区間上の $\beta$ 変形 $T_\beta x = \beta x - \lfloor \beta x \rfloor$。ここで $\beta > 1$ はピソット数（ガロア共役が単位円の内部に厳密に存在する代数的整数。例：黄金比）である。
• 力学系: この写像は、決定論的な「引き伸ばしと折り畳み」を行うカオス系であり、一意なパリー測度 $\mu$ を持つ。極めて重要な点として、$\beta$ がピソット数であるため、写像の転送作用素（transfer operator）はスペクトルギャップを有しており、観測量間の相関が幾何級数的に減衰する（$|r_k| \le C\theta^k$）。
• 行列の構築:
  • 公開シード $x_0$ を選択する。
  • 相関時間（correlation time）を超えてサンプルが取得されることを保証するために、サンプリング・ギャップ $g$ を固定する。
  • 行列の要素 $A_{ij}$ を、正規化された軌道値 $z_p = \psi(T_\beta^{pg} x_0)$ を用いて逐次的に埋める。
  • 投影は $\Phi(v) = Av/\sqrt{m}$ となる。
• 有限体における再現性: 一般的なカオス写像とは異なり、ピソット特性により、その軌道は有限体において正確に再現可能である。$k$ ステップの生成コストは $k$ に対して線形（具体的には $O(k \log_2 \beta)$ ビット）であるが、一般的なカオス写像（ロジスティック写像など）は、正確な算術を維持するために指数的なビット増大（$O(2^k)$）を必要とする。

3. 主な貢献

本論文は、主に4つの理論的および実用的な貢献を示している。

1. 次元に依存しないバイアスおよび分散の境界:

   • バイアス: 著者らは、二乗ノルム推定量のバイアスが、次元 $d$ に依存せず、サンプリング・ギャップ $g$ とともに幾何級数的に減衰する項によって抑えられることを証明している（補題1）。これは、$\beta$ 写像のスペクトルギャップから導出されており、標準的な一様分布の議論よりも強力な保証を提供している。
   • 分散: 推定量の分散が $V_0/m$ でスケールすることを示す。決定的な点として、ある表明された集中不等式の下で、定数 $V_0$ は次元フリー（$d^2$ に依存しない）である。これは、粗雑な境界が $O(d^2)$ を示唆するのと対照的である。これは、元の次元 $d$ がどれほど大きくなっても、固定された投影次元 $m$ が十分であることを意味する。

2. 単一の公開シードの存在:

   • 定理1は、$\binom{N}{2}$ 個の全ペアのセントロイド間距離を $(1 \pm \varepsilon)$ 以内に保持する単一の公開シード $x_0$ が存在することを証明している。
   • このシードは、効率的なオフライン探索によって見つけることができる。一度見つかれば、行列は固定され、公開され、ZK証明中のランダム性へのコミットメントを必要としなくなる。

3. ピソット特性による正確な再現性:

   • 論文では、ピソット特性（単なる一般的なカオスではない）がZK展開において不可欠であることを指摘している。これは、軌道が固定された有限体において、ステップあたりの線形コストで正確に再現できることを保証する。一般的なカオス写像は、浮動小数点の発散を避けるために必要な精度（分母）が指数関数的に増大するため、ここで失敗する。

4. 堅牢性と探索:

   • 証明可能な堅牢性半径（Proposition 1）が提供されており、クエリが最近傍の投影セントロイドを変更することなく耐えうる最大摂動を定義している。
   • シードの探索は無条件（分散境界により保証される）であるが、特定のスペクトルギャップ写像に対する集中不等式が成り立つならば、$\log N$ への対数依存性を伴う改善が可能である。

4. 実験結果

本構成は、6つの標準的な投影法（ガウス、ラデマッハー、アキロプタス・スパース、サブサンプリング・ランダム化アダマール変換（SRHT）、およびカオス系列行列（Yu et al.））に対して評価された。

• 統計的品質: ピソット投影は、ランダム投影と同等の統計的品質を持つ。
  • 分散率: 推定量の分散は $1/m$ の法則に従い、ガウス型JLの $2/m$ の参照値と重なっている。
  • 次元独立性: $d$ が64から1024に増加しても、分散定数 $V_0$ は2付近で平坦であり、次元フリーの理論的予測を裏付けている。
  • 歪み: 全セントロイドペアに対する最悪ケースの相対歪みは、ガウス型JLのベースラインを追跡している。
• タスク性能: $d=256$ の24クラス最近傍セントロイド・ルーティング・タスクにおいて、ピソット投影は $m=32$（8倍の圧縮）で100%の精度を回復し、他の手法と同一の結果を示した。
• 再現性: シミュレーションにより、浮動小数点実装は（リアプノフ予測通り）約50〜70ステップ後に正確な軌道から乖離するが、ピソット $\beta$ 表現は正確かつコンパクト（200ステップに対して139ビット。ロジスティック写像の $1.66 \times 10^6$ ビットと比較）に保たれることが確認された。

5. 意義と主張

本論文は、この構成が、以下の3つの重要な要件を同時に満たす唯一の方法であると主張している：

1. 回路内のランダム性を排除している: ランダム行列のサンプリングをコミットしたり証明したりする必要がない。
2. 固定された有限体で正確に再現可能である: ピソット特性を通じて達成され、ステップあたりのコストは $\log_2 \beta$ であり、一般的なカオス写像のような $O(2^k)$ のコストを回避できる。
3. ランダム投影と統計的に等価である: 標準的なJL行列の分散率および歪みの特性と一致する。

著者らは、統計的品質は証明されているものの、無条件の $O(N^2)$ シード探索境界を、条件付きの $O(\log N)$ 境界へとアップグレードする理論的ステップは、転送作用素に関する特定の集中不等式に依存しており、依然として未解決の理論的ステップであると述べている。実用面では、本手法により、証明生成の時間を「分・ギガバイト単位」から「秒単位」へとシフトさせることが可能となり、高次元埋め込みの検証可能なプライベート・ルーティングを実現している。