Triple-Hoisted Baby-Step Giant-Step Linear Transformation over CKKS Homomorphic Encryption and Hardware Accelerator

技術サマリー：CKKS 準同型暗号およびハードウェアアクセラレータにおける三重ホイスト・ベビーステップ・ジャイアントステップ線形変換

問題定義
準同型暗号（HE）、特に CKKS 方式は、医療診断、金融分析、ゲノムシーケンシングなどのアプリケーションに不可欠な、暗号化データ上でのプライバシー保護計算を可能にします。HE ベースのニューラルネットワークやトランスフォーマーにおける基本的な操作は、線形変換（HE-LT）です。対角法は、行列の対角成分を多項式にパックすることで HE-LT を可能にしますが、高次元の行列に対しては、膨大な数の暗号文回転を必要とし、実用的ではありません。これらの回転には、複雑な自己同型とキー切り替え操作が伴い、大きな計算オーバーヘッドと莫大なオフチップメモリアクセスを引き起こします。既存のハードウェアアクセラレータは、ベビーステップ・ジャイアントステップ（BSGS）分解と二重ホイスト技術を利用しているものでも、依然として大きなレイテンシとメモリ帯域幅のボトルネックに悩まされており、典型的なパラメータセットでは数百ギガバイトのオフチップデータ転送を必要とすることが多いです。

手法
本論文は、アルゴリズム的複雑性とハードウェアデータフローの両方に対処する包括的な解決策を提案します。

1. 三重ホイスト BSGS（TH-BSGS）アルゴリズム：
   著者らは、既存の二重ホイスト BSGS アルゴリズムを拡張し、「ベビーステップ」をさらに 2 層に分解することで、3 層構造（$n = n'_1 n'_2 n'_3$）を構築しました。

   • 三重ホイスト：この技術は、回転の 3 層すべてに適用されます。計算の順序を入れ替え、切り替えキーに逆自己同型を適用することで、アルゴリズムは、層内のすべての内部回転に対して「分解（Decompose）」操作（高価なキー切り替えステップ）を 1 回だけ実行することを保証します。
   • 遅延 ModDown：以前のホイスト手法と同様に、「ModDown」操作は遅延され、結合されます。提案された設計では、「ModDown」は中間積ではなく、累積された和にのみ適用され、必要なモジュラ演算の数を大幅に削減します。
   • トレードオフの柔軟性：分解因子 $n'_1, n'_2, n'_3$ を調整することで、必要な切り替えキーの数（メモリ）と計算複雑性の間の柔軟なトレードオフが可能になります。

2. メモリ最適化データパス：
   オフチップメモリアクセスに起因するレイテンシに対処するため、TH-BSGS アルゴリズムは 6 つの異なるフェーズに分割されます。

   • フェーズ分割：アルゴリズムは再構成され、オフチップメモリからデータを読み取り、中間結果をオンチップに保存・再利用し、各フェーズの終了時のみ書き戻すように設計されています。
   • データ再利用：切り替えキーと多項式の limbs の読み込みを慎重にスケジューリングすることで、オンチップメモリの再利用を最大化します。例えば、中間層では、切り替えキーをオンチップメモリに読み込み、トラフィックを最小化するために複数の反復で再利用します。
   • 並列性の調整：切り替えキー、多項式の limbs、および暗号文の処理をバランスさせるため、6 つの並列性パラメータ（$m_1$ から $m_6$）が導入され、設計が FPGA のオンチップメモリ制約（例：Xilinx U280 の 43 MB）内に収まることを保証します。

3. ハードウェアアクセラレータアーキテクチャ：
   提案されたアルゴリズムを実装するための効率的な FPGA ベースのアクセラレータが設計されました。

   • 最適化された置換回路：自己同型 $\phi_r$ を実装するための新規の置換回路が導入されました。NTT ドメインにおける自己同型の特定の性質と、係数のビット反転順序のストレージを巧みに利用することで、先行技術と比較してマルチプレクサの数を半分に削減し、スクラッチパッドメモリバッファの必要性を排除しました。これにより、置換操作のレイテンシが半減します。
   • モジュラーコンポーネント：アーキテクチャには、NTT、INTT、および係数ごとの演算をサポートする処理要素（PE）アレイ、総和用のツリー加算器（TA）アレイ、および置換回路（PC）アレイが含まれます。

主な貢献

• アルゴリズム的革新：ベビーステップをさらに分解して、二重ホイストアプローチと比較して暗号文回転と「分解」操作の数を削減する、三重ホイスト BSGS アルゴリズムの提案。
• データパス最適化：TH-BSGS アルゴリズムの再構成された計算に特化した、オンチップデータ再利用を最大化することでオフチップメモリトラフィックを劇的に削減する、フェーズベースのメモリ最適化戦略。
• ハードウェア効率：自己同型のレイテンシを 50% 削減し、追加のメモリバッファリングを排除する、簡素化された置換回路を特徴とするハードウェアアクセラレータの開発。

実験結果
本設計は Xilinx Virtex UltraScale+（U280）デバイスで合成され、128 ビットのセキュリティをサポートする 3 つの異なる HE パラメータセット（Set-A、Set-B、Set-C）の下で、最先端のハードウェアアクセラレータ（FAME、CHAM、および文献 [25] の設計を含む）と比較評価されました。

• オフチップメモリアクセス：同じパラメータ設定下で、最良の先行設計（FAME）と比較して、提案された設計はオフチップメモリアクセスを 2.9 倍から 4.2 倍削減しました。対角法と比較すると、メモリアクセス削減の改善は最大 10.6 倍に達します。
• 計算レイテンシ：提案されたアクセラレータは、先行するハードウェアアクセラレータと比較して、計算レイテンシを 2.9 倍から 10.6 倍削減しました。
• リソース利用率：本設計は、大幅な性能向上にもかかわらず、ハードウェアリソース要件（LUT、FF、DSP、BRAM）を既存のソリューションと同程度か、わずかに優れたレベルに維持しています。
• アルゴリズム比較：TH-BSGS アルゴリズムは、二重ホイスト BSGS（DH-BSGS）アルゴリズムと比較して、切り替えキーのメモリ要件を約 3.65 倍削減しますが、多項式乗算が総複雑性を支配しているため、全体的な計算複雑性は DH-BSGS や BSGS と同程度です。

重要性
本論文は、提案された TH-BSGS アルゴリズムとその関連するハードウェアアクセラレータが、HE-LT の効率において重要な進歩を表すと主張しています。キー切り替えのアルゴリズム的オーバーヘッドと、オフチップメモリアクセスのハードウェアボトルネックを同時に解決することで、この設計は、より高速でスケーラブルなプライバシー保護線形変換を可能にします。オフチップメモリトラフィックの削減は特に重要であり、データ転送は HE-LT 操作におけるレイテンシの大部分を占めています。この研究は、ベビーステップのさらなる分解を、厳密なデータパス最適化と専用ハードウェアと組み合わせることで、ハードウェアリソースコストを増加させることなく、大幅な性能向上をもたらすことを実証しています。今後の研究は、特定のアプリケーション向けの線形変換のさらなる最適化に焦点を当てることが示唆されています。