Hybrid privacy-aware semantic search: SVD-truncated document geometry and CKKS-encrypted query reranking under a restricted threat model

問題提起

現代のセマンティック検索および検索拡張生成（RAG）は、高密度ベクトル埋め込みに依存している。しかし、近年の研究により、これらの埋め込みは元のテキストへと高い忠実度で逆変換可能であることが示されている（例：Vec2Textは〜97%のBLEUを達成）。これは重大な脆弱性を生み出す。すなわち、ベクトルデータベースが漏洩した場合、その背後にあるドキュメントの内容が事実上、侵害されるということである。

既存の防御策には両極端な手法が存在するが、いずれも産業規模のデプロイメントには適していない：

1. 完全準同型暗号 (FHE): 暗号学的には堅牢であるが、数百万のドキュメントを検索するには計算コストが極めて高い。
2. 差分プライバシー (DP): ノイズの付加は、意味のあるプライバシー保護を提供する前に、ランキングの品質を著しく低下させる。

本論文は、プライバシー、検索精度、および$10^6$のドキュメント規模におけるレイテンシのバランスを取るための「中間的な道」の必要性に取り組んでいる。

手法

著者らは、静的なドキュメントコレクションと動的なユーザークエリを異なるものとして扱う、非対称なハイブリッドアーキテクチャを提案している。システムは、制限された脅威モデルの下で動作する：信頼できるクライアント、誠実だが好奇心旺盛な（honest-but-curious）サーバー、および非適応的な攻撃者（秘密の回転に関する事前知識を持たずに、市販のインバージョンツールを使用する攻撃者）を想定している。

1. ドキュメント保護 (静的側)

ドキュメントベクトルは、暗号化ではなく幾何学的変換によって保護される：

• SVD 截断 (SVD Truncation): 中心化されたドキュメントコーパスは、特異値分解（SVD）を用いて低次元の部分空間（$k = d/2$）に投影される。この截断は、相対的な再構成誤差（$\sigma_{rec}$）を少なくとも0.10にすることを保証するように選択されており、これが情報損失のプロキシ（代理指標）として機能する。
• 秘密の回転 (Secret Rotation): 截断されたベクトルは、秘密の、Haar分布に従う一様ランダム直交行列 $R$ によって回転される。この回転により、 $R$ を持たない攻撃者から基底の方向性が隠蔽される。
• 公開プロダクト量子化 (Public Product Quantization - PQ): クライアントがサーバーにクエリを送信することなく、ローカルで候補のフィルタリング（ステージ1）を実行できるように、回転後の空間においてPQインデックス（コードブック + コード）が学習される。著者らは、このPQのアーティファクトは「損失のある圧縮されたビュー」であり、近傍構造を漏洩させるため、露出したチャネルとして扱われることを明記している。

2. クエリ保護 (動的側)

クエリは暗号学的に保護される：

• CKKS 暗号化: クライアントは、回転されたクエリベクトルをCKKS準同型暗号スキームを用いて暗号化する。
• 暗号文-平文 (ct-pt) リランキング: サーバーは、短縮リストされた候補（例：上位40件）に対し、暗号化されたクエリと平文の回転済みドキュメントベクトルとの内積を計算することで、リランキングを行う。
• 最適化: 暗号文同士の乗算（ct-ct multiplication）を避けることで、コストのかかるリリニアライゼーション（再線形化）ステップを排除している。これにより、サーバーはサブ秒単位のレイテンシで類似度スコアを計算できる。

3. パラメータ選択

手動チューニングの代わりに、著者らは、CKKSパラメータ（多項式モジュラス次数、係数モジュラスチェーン、スケール）の離散的なグリッドに対する再現可能なオフライン・マイクロベンチマークを採用し、セキュリティテーブル（tc128）と精度許容範囲を満たしつつ、レイテンシを最小化する構成を選択している。

主な貢献

理論的貢献:

• 補題1 (Lemma 1): 本論文は、その像が截断された部分空間内に制約されている任意のデコーダに対する、$L_2$ 再構成誤差のタイトな下限を証明している。これにより、投影によって失われる情報を形式的に定量化しているが、著者らはこれが「投影の境界」であり、一般的なインバージョン・セキュリティの定理ではないことを明確にしている。
• 経験的仮説1 (Empirical Hypothesis 1): 再構成誤差のプロキシ（$\sigma_{rec}$）と、市販のインバージョン攻撃によるBLEUスコアとの関係を定式化し、数値的に検証している。

経験的およびエンジニアリング的貢献:

• スケール評価: 5つの最新のテキストエンコーダ（多言語E5およびBGE-M3を含む）を用い、100万ドキュメントのコーパス（ロシア語Wikipedia）を用いて実験を行った。
• レイテンシ: システムは、$10^6$のドキュメントに対して、エンドツーエンドのクエリレイテンシを十分に1秒未満（p95 $\approx$ 370 ms）に抑えている。
• CKKS 最適化: 選択された構成（$N_{poly}=8192$、特定のモジュラスチェーン）は、同一のセキュリティ境界を維持しながら、標準的なTenSEALの設定と比較して1.7倍の高速化を実現している。
• デノイジング効果: 次元 $d \ge 768$ のリトリーバル訓練済みエンコーダの場合、SVDの截断は線形デノイザーとして機能し、末尾の特異方向にあるノイズをフィルタリングすることで、生のベースラインと比較してランキング指標（Acc@1, NDCG）をわずかに向上させる。

結果とセキュリティ分析

本論文は、意図された脅威モデルおよびより強力な攻撃者に対して、システムを厳密にテストしている：

• 非適応的攻撃者に対して: 制限されたモデル（未知の $R$、市販のVec2Text）の下では、秘密の回転によりBLEUスコアはノイズフロア（$\approx 0.007$）まで低下し、テキストの復元を事実上阻止する。
• 既知平文攻撃者に対して: 攻撃者が $\approx k$（保持された次元数）個の（元のテキスト、回転済みベクトル）のペアを保有している場合、直交プロクラスティス（Orthogonal Procrustes）を用いて秘密の回転 $R$ を復元できる。一旦 $R$ が判明すれば、保護はSVDの截断のみに限定される。
• 参照コーパスの漏洩: 保護されたコレクションが公開または漏洩した参照コーパスと重複している場合、攻撃者は復元された回転を用いて、正確なパラグラフの検索を行うことができる。
• PQ アーティファクトの漏洩: 公開されているPQコードは、回転済みベクトルに対して $\approx 95\%$ のコサイン類似性を保持しており、上位10個の近傍の大部分を保持している。これは、PQのアーティファクションが構造的情報を漏洩させる露出したチャネルであることを裏付けている。
• エンコーダへの依存性: 「デノイジング」の恩恵は、リトリーバル訓練済みエンコーダに特有のものである。コンパクトなモデル（例：e5-small）やパラフレーズ蒸留モデルは、$k=d/2$ の截断によって精度が低下する。

意義と主張

本論文は、デプロイ可能な製品やシステムエンジニアリングの報告書ではなく、科学的研究として位置づけられている。その意義は以下の点にある：

1. 境界の定義: 脅威モデルを明示的に限定している。ドキュメントの保護は（CKKSによる）暗号学的なクエリの機密性は保証するが、（SVD + 秘密の回転による）ドキュメントの保護は経験的な難読化であると主張している。これは、ドキュメント層が適応的または既知平文の攻撃者に対して暗号学的に安全であるとは主張していない。
2. トレードオフの定量化: プライバシー、精度、およびレイテンシがバランスされた測定可能な動作点を提示している。プライバシーを考慮した截断が、偶然にも検索品質を向上させ得ることを示している。
3. 再現性: 決定論的なパラメータ選択方法を提供し、すべてのスクリプトと設定を公開している。

著者らが認めている限界:

• ドキュメントのプライバシーは暗号学的ではなく、既知平文攻撃や適応的攻撃に対しては脆弱である。
• アクセスパターン（どのドキュメントがリランキングされるか）およびPQコードは露出している。
• システムは、精度を維持するために特定のクラスのエンコーダ（リトリーバル訓練済み、$d \ge 768$）に依存している。
• 主要な未解決の課題は、回転された空間に特化して学習されたエンドツーエンドの学習済みデコーダに対する堅牢性であり、本研究では完全には評価されていない。

結論として、本論文は、クエリ側には暗号学的なプライバシー（CKKS）を、ドキュメント側には幾何学的な難読化（SVD + 秘密の回転）を割り当てる、高性能で実用的なハイブリッド・アプローチを提示しており、幾何学的難読化レイヤーの失敗モードを透明性を持って定量化している。