技術要約: HE-LRM

問題提起

完全準同型暗号（FHE）は、暗号化されたデータに対するプライバシー保護型のニューラル推論を可能にするが、既存のソリューションは主に高密度な入力（例：CNN、MLP）を扱うモデルを対象としている。深層学習推薦モデル（DLRM）は、大規模で疎なカテゴリカル入力が膨大な埋め込みテーブルを通じて処理されるという、特有の課題を抱えている。

標準的なDLRMでは、疎な特徴量は埋め込みテーブルのルックアップを通じて密なベクトルにマッピングされる。FHEの文脈（具体的にはCKKSスキーム）において、直接的なインデックス参照はネイティブにはサポートされておらず、SIMD加算、乗算、および巡回回転のみが利用可能である。ナイーブなアプローチによる暗号化ルックアップは、深刻なスケーラビリティの問題に直面する：

1. 通信オーバーヘッド： 行数 $k$ のテーブルに対してインデックスの「ワンホット」エンコーディングを行うには、$k$ サイズのベクトルが必要となる。Criteoのような業界規模のデータセット（3,380万行）の場合、推論ごとに1,000個以上の暗号文（1 GiB超）をアップロードする必要がある。
2. サーバー側の計算コスト： 先行研究（Kimら [10] など）は、アップロードコストを軽減するために、サーバー側で暗号化されたインデックスからワンホットセレクターを構築しようと試みている。しかし、これには深い算術回路（指示関数）が必要となり、多大な乗算深度を消費するため、高価なブートストラップ操作を必要とすることが多い。
3. メモリと構造の漏洩： 既存の圧縮技術は、クライアントが学習済みのコードマッピング（埋め込みの相関関係を明らかにするもの）を保持する必要があったり、あるいはサーバー上のメモリ使用量やスロット利用効率を低下させたりする。

手法: HE-LRM

著者らは、DLRM推論に最適化されたエンドツーエンドのFHEシステムである HE-LRM を提案している。このソリューションは、以下の3つの核心的な技術革新を通じて、埋め込みルックアップのボトルネックに対処する。

1. クライアント側での桁分解圧縮（Digit Decomposition Compression）

サーバー側でのワンホットベクトルの構築や、構造を漏洩させる学習済みコードマッピングに頼るのではなく、HE-LRMは**桁分解（digit decomposition）**に基づく決定論的なクライアント側圧縮技術を採用している。

• メカニズム： サイズ $k \times d$ の元の埋め込みテーブルを、$\ell$ 個のより小さなサイズ $p \times d$ のテーブル（ここで $k \approx p^\ell$）に分解する。
• プロセス： クライアントはカテゴリカルインデックス $i$ を取り、それを底 $p$ の数字のタプル $(i_0, i_1, \dots, i_{\ell-1})$ に分解する。
• プライバシー： クライアントはこれらの小さな数字に対するワンホットエンコーディングをローカルで構築し、それらを暗号化する。サーバーは元のインデックスを見ることはできず、高価なホモモルフィック指示関数を実行する必要もない。この圧縮は、クライアントにマッピング構造を明かすことなく、トレーニング中にエンドツーエンドで学習される。

2. ブロック対角パッキング戦略

DLRMは通常、複数の埋め込みテーブル（例：Criteoでは26個）を利用する。HE-LRMは、これらを同時に扱うためのブロック対角パッキング戦略を導入している。

• 実装： 複数の埋め込みテーブルを、単一の大きな重み行列内に対角線状に連結する。
• 利点： これにより、クライアントは全特徴量のワンホットエンコーディングを単一のベクトルに連結できる。サーバーは、単一のBaby-Step Giant-Step (BSGS) 行列・ベクトル乗算を実行することで、すべてのテーブルの埋め込みを並列に取得できる。これにより、暗号文のスロット利用率を最大化し、テーブルを逐次的に処理するオーバーヘッドを回避できる。

3. 最適化された線形変換

本システムは、行列・ベクトル乗算のためにダブル・ホイスティッド（double-hoisted）BSGSアルゴリズムを活用している。

• 従来の「Table-Mult」アプローチは、埋め込みベクトルの各次元に対して個別の回転を必要とし（余分な乗算レベルを消費する）、BSGSアプローチはルックアップを標準的な線形変換として扱う。
• これにより、操作を単一の乗算レベルに削減し、ルックアップフェーズにおける中間ブートストラップの必要性を排除する。

主な貢献

1. 初のエンドツーエンドFHE DLRM： HE-LRMは、FHE下でDLRMの密な特徴量と疎な特徴量の両方をサポートする初のシステムであり、UCI Heart DiseaseおよびCriteoデータセットで検証されている。
2. 56倍の高速化： 提案されたクライアント側桁分解およびBSGSルックアップ戦略は、大きな埋め込み次元（768）において、最先端のCodedHeLUTに対して56倍の高速化を達成した。これは、サーバー側の指示関数を回避し、乗算深度の消費を（約10レベルから1レベルへ）削減し、ルックアップフェーズ中のブートストラップを不要にしたことによるものである。
3. 並列マルチテーブルルックアップ： ブロック対角パッキング戦略により、複数の埋め込みテーブルにわたる効率的な並列ルックアップが可能になり、テーブルを個別に処理する場合と比較して、通信および計算のオーバーヘッドを大幅に削減できる。
4. クリーンな漏洩プロファイル： 本手法は、クライアントは入力の次元とテーブルのサイズのみを知っているが、埋め込みの値、相関、またはモデルパラメータについては何も知らないというセミ・ホネスト（半誠実）脅威モデルに従っている。

実験結果

著者らは、単一スレッドCPU（Intel Xeon Gold 5218）上でオープンソースのOrion FHEフレームワークを使用して、HE-LRMを評価した。

• UCI Heart Disease： エンドツーエンドの推論レイテンシとして24秒を達成した。
• Criteoデータセット： 圧縮率（$10\times$ から $10^5\times$ の範囲）に応じて、228秒から489秒のレイテンシを達成した。
  • 高度に圧縮されたモデル（$\approx 10^3\times$ から $10^5\times$）は、埋め込みルックアップ時間がネットワークの他の部分と比較して無視できる程度（3〜5秒）であり、BSGS操作を単一の暗号文で行えるため、同様のレイテンシ（約230秒）を示した。
  • 低圧縮のモデルはより多くの暗号文を必要とし、行列・ベクトル積のレイテンシが増大した。
• ハードウェア予測：
  • GPU： Cheddarアクセラレータを用いた予測では、CPUに対して約200倍の高速化を実現し、Criteoの推論を約1秒に短縮する。
  • ASIC： Osirisコストモデルを用いた予測では、圧縮モデルに対して1秒未満のレイテンシ（約0.037秒）を実現する。

意義と主張

本論文は、HE-LRMがプライバシー保護推論における重要なギャップを埋めるものであることを主張しており、プライバシー保護型の推薦システムが実用的な展開に近づいていることを示している。

• スケーラビリティ： 本研究は、「埋め込みボトルネック」が、プライバシーを損なうことなく、またクライアントがモデルの重みを保持する必要もなく解決できることを証明している。
• システム効率： インデックスのエンコーディングの複雑さを（決定論的な分解によって）クライアント側に移し、サーバー側で効率的な線形代数（BSGS）を利用することで、本システムは、ナイーブなワンホットエンコーディングに関連する過度なブートストラップのコストと膨大な通信オーバーヘッドを回避している。
• 幅広い適用性： 著者らは、暗号化された埋め込みルックアップのプリミティブはDLRMに限定されず、Transformerベースのモデルにも関連しており、将来のプライベート推論システムのための再利用可能な抽象化であることを指摘している。

著者らは、現在のCPUパフォーマンス（大規模モデルで数分）については謙虚な姿勢を保っており、実世界のプロダクション環境へのデプロイには、示されたGPUおよびASICハードウェアによる高速化が不可欠であることを強調している。