🤖 AI

SHARD: cell-keyed residual splitting for alignment-resistant private dense retrieval

本論文は、埋め込みを公開プレフィックスと、複数のセルにシャード化された秘密鍵付きの残差に分割することで、グローバルな幾何学的整列攻撃を阻止しつつ、準同型暗号ベースのリランキングを通じて高いランキング精度を維持する、高密度検索におけるプライバシーを強化する検索保存型埋め込み変換であるSHARDを紹介する。

原著者： Sergey Kurilenko

公開日 2026-06-29

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Sergey Kurilenko

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

SHARDの解説：シンプルで日常的な比喩を用いた説明

大きな問題：検索における「ガラスの家」

想像してみてください。あなたは、秘密の文書（顧客サポートのチケットやプライベートなメールなど）が詰まった巨大な図書室を持っています。これらを検索可能にするために、各文書を「埋め込み（embedding）」と呼ばれる長い数字のリストに変換します。この数字のリストは、その文書のユニークな「指紋」のようなものだと考えてください。

現在、もし誰かがこの指紋のリストを盗んだ場合、コンピュータを使って元のテキストを逆生成（リバースエンジニアリング）できてしまうことがよくあります。これはまるで「ガラスの家」のようです。たとえドアに鍵をかけても、壁が透明であるため、中の様子が丸見えなのです。

旧来の手法：「回転する部屋」

この論文が登場する前、一般的な防御策は、指紋を部屋に入れ、部屋全体を回転させること（「秘密の回転」）でした。

欠陥： この論文では、これは「一つの鍵で回転する部屋」のようなものだと主張しています。もし泥棒が、わずかな「前後」のデータ（既知のテキストとその指紋のペア）を盗み出したとしても、部屋がどのように回転したかを簡単に突き止め、回転を元に戻すことができます。一度回転の仕組みが分かってしまえば、再びすべてが見えてしまいます。
トレードオフ： これをより安全にするために、人々は指紋を半分に切り捨てることがありました（データの半分を捨てる）。これにより逆生成は難しくなりますが、同時に検索エンジンが適切な文書を見つける能力も低下してしまいます。

新しい解決策：SHARD

著者らは、SHARD（Cell-keyed Residual Splitting）を紹介しています。部屋全体を回転させる代わりに、指紋を二つの部分に分け、それぞれを異なる方法で扱います。

1. 「公開ポストカード」（接頭辞 / Prefix）

彼らは、文書の最も重要で大まかな特徴（メインのトピックなど）を取り出し、短い「公開ポストカード」に載せます。

比喩： 図書館のカードに単に「フィクション」や「料理」とだけ書かれているようなものです。これは秘密ではありません。
目的： これにより、検索エンジンが候補となる小さなグループを素早く見つけることができます（例：「料理」セクションを探す）。多少の粗い情報（トピック）は漏れますが、細かい詳細までは漏らしません。

2. 「プライベートなパズルピース」（残差 / Residual）

指紋の残りの部分（その文書をユニークにする詳細な情報）が「残差」です。ここで魔法が起こります。

分割： 著者らは、このプライベートな部分を多くの小さな塊（セル）に切り刻みます。
鍵：各々の塊には、独自の秘密の鍵でロックがかかっています。
比喩： 文書のプライベートな詳細がジグソーパズルのだと想像してください。従来の手法では、パズル全体が一つの箱に入り、一つの鍵でロックされていました。しかしSHARDでは、パズルは256個の別々のピースに切り分けられ、それぞれのピースが異なる鍵を持つ、別々の金庫の中に保管されています。

実践的な仕組み

検索を行うとき：

ステップ1（ポストカード）： システムは公開された「ポストカード」を使用して、40個程度の有力な一致候補のリストを作成します。
ステップ2（パズル）： これら40個のマッチングの順位を決定するために、システムはプライベートなパズルピースを見る必要があります。システムはサーバーに対して暗号化されたリクエストを送り、サーバーはそれら40個の候補に必要な特定のパズルピースを解錠し、比較を行い、スコアを返します。
結果： 検索エンジンは、暗号化されていないフルデータを使用した場合と全く同じ精度を得られますが、サーバーはフルデータの中身を見ることはありません。

なぜこれが優れているのか？（3つの勝利）

1. 検索エンジンを壊さない
システムは最終的なランキングを行うために全体の絵を再構成するため、精度を損なうことがありません。データを半分に切るという旧来の手法は、検索結果の質を下げてしまいましたが、SHARDは完璧な検索結果を維持します。

2. ハッキングを極めて困難にする
これが最大の勝利です。

旧来の手法： もし泥棒が200個の「前後」の例を盗んだとしても、回転の仕組みを解明できてしまいます。
SHARDの手法： プライベートなデータが256個の異なるセルと異なる鍵に分割されているため、泥棒が仕組みを解明するには、各特定のセルに対して200個の例を盗む必要があります。
数学的根拠： 256個のセルがある場合、システムを破るために必要な盗まれた例の数は、200個ではなく、およそ256倍（200個ではなく10万個以上）になります。これは、一つの鍵を開けるのではなく、256個の異なる鍵穴をピッキングしようとするようなものです。

3. トピックを知っていても保護される
たとえ泥棒が「ポストカード」（トピック）を知っていたとしても、詳細な情報はプライベートなパズルピースの中にロックされているため、中身を見ることはできません。

SHARDが「できないこと」（限界）

著者らは、このシステムができないことについても非常に正直に述べています。

魔法の盾ではない： もし泥棒が、公開データベース（リークされたニュースアーカイブなど）に既に元のテキストを持っており、それを「ポストカード」と照合できた場合、どの文書がどれであるかを特定できてしまいます。SHARDは、数字からテキストを「再構築」することからは守りますが、既知のリーク情報との「照合」からは守りません。
誰が何を検索しているかは隠せない： システムは、あなたがどの文書にアクセスしているか（アクセスパターン）を知っています。もしあなたが毎日「心臓発作」について検索していれば、サーバーは具体的な文書の内容は読めなくても、あなたが心臓発作に関心を持っていることは知ることになります。
絶対に破られないわけではない： もし泥棒が、ある特定の文書だけに全力を注ぎ、その特定の「セル」に関する十分な例を盗み出した場合、その一つの文書を解読することは可能です。しかし、図書室全体を一気に解読することはできません。

まとめ

SHARDは、プライベートな検索データを保護するための新しい手法です。部屋全体を回転させる（解除が容易）のでも、家具の半分を捨て去る（部屋として機能しなくなる）のでもなく、秘密の詳細を何百もの小さな、個別にロックされた箱へと分割します。これにより、検索の速さと正確さを維持したまま、ハッカーが秘密を再構築することを極めて困難かつ高コストなものにします。

技術要約: SHARD – アライメント耐性を備えたプライベートな高密度検索のためのセル・キー付き残差分割

1. 問題提起

高密度埋め込み（Dense embeddings）は、現代のセマンティック検索および検索拡張生成（RAG）の基盤である。しかし、ベクトルストアが漏洩した場合、最近の攻撃（few-shotアライメント、zero-shotインバージョン、および非教師ありクロス空間変換を含む）が示しているように、基礎となるテキストが事実上侵害される。これらの攻撃は、既存の軽量な防御策の根本的な弱点、すなわち「保護されたベクトルストアが単一のグローバルな幾何構造を持つ」という点を利用している。

現在の防御策は、SVD（特異値分解）による次元削減、単一の秘密直交回転の適用、およびインデックス作成のためのプロダクト量子化（PQ）を用いる「グローバル・リニア」なアプローチに依存することが多い。本論文は、このアプローチが脆弱であると主張している。なぜなら、単一のグローバルな幾何構造は、既知のリファレンス空間へとアライメント（整列）される可能性があるからである。一度攻撃者が秘密の回転を復元すると（Orthogonal Procrustes法を用い、約 $k = d/2$ 個の既知の平文ペアを使用）、保護は崩壊し、テキストのほぼ正確な復元が可能になる。さらに、標準的な防御策はトレードオフに直面する。差分プライバシー（DP）は、意味のあるプライバシーを提供する前に検索の有用性を破壊してしまい、完全準同型暗号（FHE）は大規模な top- $k$ 検索に対して計算コストが高すぎる。

2. 手法：Shard の構成

本論文では、歪みを隠蔽するのではなく、「グローバルな弱軸」を排除するように設計された、検索性能を維持する埋め込み変換手法である Shard を導入する。Shard は埋め込み空間を2つのコンポーネントに分割し、それぞれに異なる保護を適用する：

パブリック・プレフィックス ( $u$ ): 埋め込みは中心化および回転される。上位 $d_{pub}$ 個の主成分（高分散方向）が短いパブリック・プレフィックスを形成する。これは、パブリックなプロダクト量子化インデックスを介した第1段階の粗い検索（ANN）に使用される。
プライベート残差 ( $r$ ): 残りの次元 ( $d_{priv} = d - d_{pub}$ $d_{p r i v} = d - d_{p u b}$ ) がプライベート残差を形成する。
- セル・キー付き分割: 残差空間は、 $C$ 個の粗いセル（パブリック・プレフィックス $u$ によって定義される）に分割される。
- ローカル・キー: 各セル $c$ には、一意の秘密直交キー $H_c$ （ハウスホルダー反射の積）が割り当てられる。
- 格納: サーバーは、プレフィックス $u_i$ と、キー付き残差シャード $z_i = H_{c(i)} r_i$ を格納する。
- クエリ処理:
  - ステージ 1: クライアントは、パブリック・プレフィックス $u_q$ を使用して、ローカルに候補のショートリストを検索する。
  - ステージ 2 (リランキング): 各候補に対し、クライアントはクエリ残差 $r_q$ を CKKS（準同型暗号）を用いて $H_{c(i)} r_q$ として暗号化する。サーバーは、暗号文・平文モードで内積 $\langle H_{c(i)} r_q, H_{c(i)} r_i \rangle$ を計算する。
  - 正確な復元: $H_c$ は直交行列であるため、キーは相殺される： $\langle H_c r_q, H_c r_i \rangle = \langle r_q, r_i \rangle$ 。サーバーは、元の残差の正確な内積に復号される暗号化されたスコアを返す。

パラメータ $C$ は、グローバルなベースライン（ $C=1$ 、単一のグローバルキー）と、ドキュメントごとのマイクロキー（ $C=N$ 、1ドキュメントにつき1つのキー）の間を補間する。

3. 主な貢献

本論文の具体的な貢献は、著者らの以前のグローバル・リニア・ハイブリッドシステムと比較して以下の通りである：

セル・キー付き残差分割: 単一のグローバルな幾何構造を $C$ 個のローカルにキー付けされた部分空間に置き換える構成であり、単一のアライメント攻撃によって全ストアが復元されることを防ぐ。
全次元リランキング: SVDによる次元削減ベースラインが縮退した空間でリランキングを行うのに対し、Shard は全次元空間（プレフィックス + 残差）でリランキングを行い、次元削減によって失われる生の検索品質を回復する。
スケーラブルなアライメント耐性: 本論文は、拡散型の既知平文アライメント攻撃のコストが、因子 $\approx C$ で増大するというスケーリング則を確立している。ネイティブなフレームを復元するには、 $O(d)$ ではなく $O(C \cdot d_{priv})$ 個のアンカーが必要となる。
公開リークの低減: 半分の空間ではなく、短いプレフィックス ( $d_{pub} \ll d$ ) のみを公開することで、パブリック・インデックスによる近傍構造のリークを大幅に抑制する。
攻撃を意識した評価: Shard を、より強力な攻撃者ファミリー（学習済みリニア、非線形MLP、および非教師あり攻撃者）に対して評価し、歪み重視の防御策（DPノイズ）と比較することで、キー付けがノイズよりも高い耐性を提供することを実証した。

4. 実験結果

実験は、BEIR、MIRACL、および100万件のロシア語 Wikipedia コーパスにおける5つのエンコーダー（multilingual-E5 および BGE-M3 を含む）のキャッシュされた埋め込みに対して行われた。

有用性 (nDCG@10): Shard は生の空間のランキング天井（ceiling）を回復する。SVDによる次元削減が nDCG@10 において 2～8 ポイントの低下を引き起こした BEIR タスクにおいて、Shard は生のベースラインと一致した（例：0.638 vs 0.637 raw）。その際、公開チャネルの幅は 1/4 から 1/2 に抑えられている。
アライメント耐性:
- グローバル・ベースライン: 約200個のアンカーで復元された（ $d=384$ の場合）。
- Shard ( $C=64$ ): 約25,600個のアンカーを必要とした。
- Shard ( $C=256$ ): 約102,400個のアンカー（中央値）を必要とした。
- 攻撃者の堅牢性: 学習済みリニア、非線形MLP、および非教師あり攻撃者は、標準的な Orthogonal Procrustes 攻撃よりも優れた性能を示さず、いずれも単一セルの $d_{priv}$ アンカー閾値を超えることはできなかった。
パブリック・インデックスのリーク: パブリック・プレフィックスは、ベースラインよりも大幅に少ない近傍構造を明らかにした。 $d/4$ プレフィックスにおいて、NN-overlap@10 は 0.76（ベースライン）から 0.55（Shard）へと低下した。
マイクロキーの限界: $C=N$ （ドキュメントごとのキー）の場合、残差グラフのリークは 0.00 になり、システムは連結不可能となる（再キー付け AUC $\approx 0.5$ ）。
DPノイズとの比較: 歪み重視の DP 防御策は、 $\sigma=0$ （ノイズなし）の時のみ Shard の有用性と一致したが、その時点ですでに脱匿名化は100%であった。脱匿名化を減らすためにノイズを加えると、Shard の性能を下回るレベルまで有用性が低下した。Shard は高い有用性と 0% の脱匿名化を両立させた。
観察された限界:
- 標的型攻撃: 特定の被害者のセルにアンカーを集中させる標的型攻撃者は、 $C$ に依存せず、わずか $\approx d_{priv}$ 個のアンカーを必要とする。
- オーバーラップ参照: 攻撃者が重複するリファレンス・コーパスを保有している場合、パブリック・プレフィックス（たとえ単一のグローバルキーでキー付けされていても）により、そのキーが復元されると脱匿名化が可能になる。
- アクセスパターン: ベースラインと同様に、Shard はアクセスパターン（どのドキュメントがリランキングされているか）を隠さない。

5. 意義と主張

本論文は、Shard を 攻撃を意識した幾何学的防御（attack-aware geometric defense） と位置づけており、それが格納されたドキュメントに対する暗号学的な保証ではないことを明示している。

核心的な成果: Shard は、「単一のグローバルな幾何構造」という脆弱性を排除することで、プライバシーと精度のトレードオフを変化させた。これにより、拡散型の攻撃者に対してはアライメントを計算量的に困難にしつつ、正確で全次元のリランキング（有用性の維持）を可能にしている。
設計思想: 本研究は、埋め込みのプライバシーを、歪みのサロゲート（ $\sigma_{rec}$ ）の最適化から、特定の攻撃対象（アライメントおよびインデックス・リーク）に対する硬化へと移行させるものである。
控えめな主張: 著者らは、Shard が行わないことについても明示している：
- 単一のセルにアンカーを集中させる標的型攻撃からは保護しない。
- パブリック・プレフィックスのキーが復元された場合、重複するリファレンス・コーパスを介した脱匿名化を防がない。
- アクセスパターンを隠さない。
- 秘密の回転は経験的な難読化レイヤーであり、暗号プリミティブではない。

結論として、Shard は（パラメータ $C$ を通じて）セルレベルで取り消し可能なチューナブルな変換ファミリーを提供し、アクセスパターンやリファレンスの重複を扱うために他のプリミティブ（PIR など）と組み合わせることを前提とした、現代的なアライメント攻撃に対する実用的かつ測定可能な防御策を提供する。