Rotation-Optimal Noncommutative Prefix Scans in Bit-Reversed Homomorphic Layouts

技術要約：ビット反転ホモモーフィック・レイアウトにおける回転最適化非可換プレフィックス・スキャン

問題提起

パッキングされたホモモーフィック暗号（HE）、特にCKKSスキームにおいて、SIMD演算は暗号化されたベクトル上での並列計算を可能にする。しかし、スロット間の通信には巡回回転（ガロア自己同型）が必要であり、これらはキー・スイッチングを伴うコストの高い操作である。回転のコストは、データの物理的なレイアウトに依存する。

本論文は、$n = 2^m$ 個の要素（結合的、かつおそらく非可換なモノイド）の順序付きプレフィックス計算（スキャン）を、データがビット反転順序で格納されている場合に実行する問題に取り組んでいる。このレイアウトは、高速変換やパッキング変換において一般的である。

核心となる課題は、標準的な「輸送された前置要素（transported-predecessor）」スキャンでは、論理的な前置要素への距離を再帰的に倍増させる際、ビット反転レイアウトにおいて高いルーティング・コストが発生することである。ビット反転は論理インデックスを置換するため、単一の論理シフト $2^t$ は複数の異なる巡回変位クラスへと分解される。その結果、直接的な実装では $R_{direct} = \sum_{t=0}^{m-1} (m-t) = \frac{m(m+1)}{2}$ 回の回転が必要となる。著者らは、この三角関数的なコストがビット反転レイアウトにおけるプレフィックス計算の固有の性質なのか、それとも特定のルーティング・トポロジーによる副産物なのかを調査している。

手法および構成

論文では、回転回数を二次的なものから線形へと減少させるために、**複製集約不変量（replicated-aggregate invariant）**を導入している。

1. 意味論的複製（Semantic Replication）: すべてのスロットを正確な論理的前置要素へルーティングする代わりに、この構成では、整列された論理ブロック内のすべてのスロットが、そのブロックの完全な集約値を保持するように状態を維持する。
2. 兄弟ブロック交換（Sibling-Block Exchange）: スキャンの各レベル $d$（サイズ $2^d$ のブロックを結合する段階）において、アルゴリズムは特定のオフセット $s_d = 2^{m-d-1}$ で集約状態を回転させる。
   • ビット反転下では、親ブロックの2つの子ブロックは、正確に $s_d$ だけ離れた物理的余類（coset）を占める。
   • $s_d$ による回転は、あるスロットを兄弟ブロック内の「どこか」の位置へと写す。兄弟ブロックの集約値は全スロットに複製されているため、兄弟ブロック内のどの位置であっても正しい意味論的値を提供する。
   • これにより、単一の指向性巡回回転が、両方の向きの子に対して有効な集約値を同時に供給することが可能となり、公開マスクを用いて演算子の順序を選択することで、非可換モノイドの正当性が保たれる。
3. 排他的スキャン定式化（Exclusive Scan Formulation）: 本論文では、排他的スキャン（現在の要素の「前」のプレフィックスを出力するもの）を実装している。これにより、桁修正のためのインカミング・キャリーを取得するために必要な、レイアウトに敏感なルーティング（本来なら再導入されてしまう）を回避するための最終的な論理前置要素シフトを不要にしている。
4. 下界の証明: 著者らは、このモデルにおいて $2^m$ 個の入力すべてに依存する出力を計算する回路の回転回数のグローバルな下界が $m$ であることを確立した。この証明は、部分和引数に基づいている。もし $R$ 回の回転が使用されるならば、最大で $2^R$ 個の異なる入力変位が固定された出力に到達できる。すべての $2^m$ 個の入力にカバーするためには、$R \ge m$ が必要である。さらに、この下界を達成するには、回転オフセットが完全な2進（2-adic）基底（各評価値 $0, \dots, m-1$ に対して1つのオフセット）を形成する必要があることを証明している。

主な貢献

1. 最適スキャン構成: ビット反転レイアウトにおいて、$R = m$ 回の回転と $D = m$ のモノイド深度を実現する、包含的および排他的スキャンのアルゴリズム。これにより、直接的なトポロジーにおける回転回数の $O(m^2)$ から $O(m)$ への削減を実現した。
2. 最適性の剛性（Rigidity of Optimality）: すべての最適回路の特性付け。回路がちょうど $m$ 回の回転を使用する場合、オフセットは完全な2進基底を形成しなければならない。これは、回路のトポロジーが変化しても、回転プロファイルは剛直であることを示している。
3. 回転キーのフロンティア: 直接指定されたキー・オフセットの数（$K$）と、オンラインの回転呼び出し回数（$R$）のトレードオフ分析。
   • 論文は、積の下界 $\prod (c_j + 1) \ge 2^m$ を導出している（ここで $c_j$ はキー $j$ が使用される回数）。
   • $K$ が $m$ を割り切る場合、正確なフロンティアは $R^* = K \cdot (2^{m/K} - 1)$ であると証明されている。
4. Radix-CKKSの実装: 正確なキャリーおよびボロー伝播のための排他的スキャンを、ラディックスベースのCKKSに適用。これにより、自然な順序への復元や最終的なシフトを行うことなく、整数比較および剰余演算が可能になる。
5. バッチ処理の効率性: 複製スキャンによる節約効果が、単一の暗号文の中に $g$ 個の独立した整数がパッキングされた、完全に占有された桁主要（digit-major）インターリービングにおいても保持されることを実証。これにより、回転回数を増やすことなく動作する。

結果と評価

著者らは、アルゴリズムを Lattigo (Go) で実装し、以下の2つのベースラインと比較した。

1. 直接的ビット反転前置要素（Direct Bit-Reversed Predecessor）: 素朴な $O(m^2)$ 回転アプローチ。
2. 正規化–スキャン–復元（Normalize–Scan–Restore）: データを自然な順序に変換し、スキャンを行い、再び変換するベースライン。

$m=7$ (128スロット) における主な知見:

• 回転回数: 28回（直接法）から 7回（複製法）へ減少。
• 評価キー: ストレージが 70.0% 削減（908.6 MB $\to$ 272.6 MB）。
• メモリ: ピーク・ヒープ使用量が 63.9% 減少（2.30 GB $\to$ 830.5 MB）。
• レイテンシ: 複製スキャンは、直接的な前置要素法と比較して、単独のスキャンレイテンシを 19.9% 改善した。
• エンドツーエンド・パイプライン: 深さ5のダウンストリーム・パイプラインにおいて、複製スキャンは「正規化–復元」ベースラインで必要とされるフル・ブートストラップ操作を回避した。これにより、平均 4.31倍の速度向上（95% 信頼区間 [3.69, 4.92]）が得られた。

論文によれば、$m$ が小さい場合はモノイド組成の回数が少ないため「正規化–スキャン–復元」の方が単独レイテンシは低いが、$m \ge 5$ では複製スキャンの方が高速になり、リソース効率（キー、メモリ、モジュラスレベル）においても優れている。

意義と主張

本論文は、ビット反転SIMD表現を維持することが、順序付きプレフィックス計算において回避不可能な回転オーバーヘッドを課すものではないことを主張している。その意義は以下の点にある：

• 二次的な障壁の打破: ビット反転レイアウトにおける直接的なルーティングの $O(m^2)$ コストは固有のものではなく、意味論的複製を通じて理論的な下界である $O(m)$ まで削減可能であることを証明した。
• リソースのトレードオフ: ルーティング・コスト（回転）とキー・ストレージの削減は、パッキングされたモノイド演算（$2m-1$ 回の組成 vs $m$ 回）と第2のライブ・ステート・ベクトルの増加という代償を伴う。論文では、このトレードオフは、モジュラスレベルやブートストラップがボトルネックとなる深いパイプラインにおいて有利であると論じている。
• 厳密性: ヒューリスティックな最適化を超え、特定の依存関係パターンに対する回転・キー管理のための正確な下界とフロンティアの特性付けを提供し、数学的な証明に基づいた限界を提示している。

本研究は、ビット反転レイアウトの制約に特化した最適化として提示されており、一般的なプレフィックス・ネットワーク理論とは区別され、標準的なCKKS実装における厳密な組合せ論的証明と経験的評価を通じて検証されている。