💻 computer science

Private Embedding Lookup with Encrypted Compact Queries under Fully Homomorphic Encryption

本論文は、高コストなワンホットベクトルの生成を線形独立な表現に置き換えることで、完全準同型暗号下におけるプライベートな埋め込みルックアップのための新しい手法であるIndependent Vector Evaluation (IVE) を提案し、償却ルックアップ時間において最大78.4倍の高速化を実現する。

原著者： Daehyun Jang, Jaehee Kang, Hanee Rhee, Jung Hee Cheon

公開日 2026-06-03

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

CC BY 4.0

原著者： Daehyun Jang, Jaehee Kang, Hanee Rhee, Jung Hee Cheon

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

巨大なサーバーに保管された、膨大な秘密の図書室（埋め込みテーブル）を想像してみてください。各本は特定の単語や概念を表しており、その中には、コンピュータがその単語の意味を理解するためのユニークな「指紋」（埋め込みベクトル）が入っています。

通常、サーバーに質問したいときは、単語を送ります。サーバーはその単語を図書室の中から探し出し、その指紋を取り出して、答えを返してくれます。

プライバシーの問題：
あなたは、サーバーに「どの」単語について尋ねているのかを知られたくありません。例えば、医学的な症状、金融に関する秘密、あるいはデリケートな内容について尋ねているかもしれません。もし単語をそのまま送ってしまうと、サーバーにはそれが分かってしまいます。しかし、代わりに秘密のコードを送ってしまうと、サーバーはそれを読み取って正しい本を見つけることができません。

従来の方法（「ワンホット」方式）：
かつて、質問を秘密にするためには、特別な暗号化されたリストを送る必要がありました。想像してみてください。このリストには、図書室にあるすべての単語（数百万個の枠）に対応するスロットがあります。あなたの単語に対応するスлоットにだけ「1」を、それ以外のすべての場所に「0」を暗号化して書き込みます。

問題点： サーバーは、どのスロットが「1」であるかを確認するために、すべてのスロットをチェックしなければなりません。これは、膨大な図書室のすべての通路を歩き回り、すべての本を一つずつチェックして、目的の本を探すようなものです。これには膨大な時間と計算能力が必要であり、プロセスを非常に低速にします。

新しい方法（IVE — 独立ベクトル評価）：
この論文は、巧妙なショートカットを提案しています。クライ est は、大量の「1と0」のリストを送る代わりに、サーバーがそのコードを正しい指紋へと翻訳する方法さえ知っていれば、正しい本を指し示す「何らかのユニークなコード」さえ送ればよいことに気づきました。

次のように考えてみてください：

従来の方法： あなたは、特定の家だけに巨大な赤い「×」印があり、他の場所は空白である巨大な地図を送ります。サーバーはその地図全体をスキャンして「×」を探さなければなりません。
新しい方法（IVE）： あなたは、簡潔な座標（例：「左に曲がって、3ブロック進む」）を送ります。サーバーは、その座標を、あなたが求めている家の正確な住所へと即座に変換する秘密の公式（基底変換）を知っています。

仕組み（マジック・トリック）：

秘密のコード： クライアントは、「1と0」のリストの代わりに、コンパクトに暗号化された数値（番号）を送ります。
数学のマジック： サーバーは、**離散コサイン変換（DCT）**と呼ばれる数学的ツールを使用します。これは特別な翻訳機のようなものです。これは、重くて遅いチェックを行う代わりに、単純な数学（数の累乗）を用いて、あなたのシンプルな暗号化された数値を、ユニークな「指紋」コードへと素早く変換します。
翻訳： サーバーは、あなたの新しい「指紋」コードを、従来の方法で見つかったはずの正確な本の指紋へと戻す方法を知っている「辞書」（基底変換行列）をあらかじめ計算して持っています。

なぜこれが重要なのか：

スピード： 従来の方法は、すべての通路を歩き回るようなものでした。新しい方法では、GPSを使うようなものです。論文によれば、この手法により検索が最大78倍高速化されます。
効率性： 大量のコンピューターエネルギーを節約します。テストでは、単に「本を見つける」ために費やされる時間が、全体の99.6%から66.3%へと減少しました。
プライバシー： サーバーは依然としてあなたの特定の単語について何も学習しませんが、より速く答えを得ることができます。

要約すると：
著者たちは、サーバーにあなたの秘密の単語を見つけるための何百万もの小さなチェックを行わせる方法を止める方法を見つけました。代わりに、シンプルな暗号化された手がかりと、魔法の翻訳キーを与えたのです。これにより、サーバーはあなたの秘密を守りつつ、コンピューターを待ちぼうけにさせることなく、情報をほぼ瞬時に見つけることができます。

技術要約：完全準同型暗号下における暗号化されたコンパクトなクエリを用いたプライベート埋め込みルックアップ

問題提起

完全準同型暗号（FHE）を用いたプライバシー保護機械学習（PPML）において、離散的な入力を利用するモデル（自然言語処理（NLP）や推薦システムなど）の推論時に、極めて重要なボトルネックが生じる。これらのモデルは通常、離散的なインデックス（例：単語トークン）を連続的なベクトルへと写像する**埋め込み層（embedding layer）**から始まる。

FHEの下では、サーバーは暗号化されたインデックスに基づいた標準的なメモリ・アクセスを行うことができない。そのため、ルックアップは同型演算を通じて実現される必要がある。既存のアプローチには以下のトレードオフが存在する：

クライアント側ルックアップ： クライアントが暗号化された埋め込みベクトルを送信する。これは埋め込み次元（ $d$ ）に比例する膨大な通信オーバーヘッドを招き、大規模なテーブル（例：190万トークンを持つGloVe）においては実行不可能である。
ワンホット生成を用いたサーバー側ルックアップ： クライアントがコンパクトな暗号化スカラー・インデックスを送信する。サーバーは、そのインデックスに対応するワンホット・ベクトルを同型的に構築しなければならない。先行研究（Kim et al., ICML 2024）では、暗号化指示関数（EIF）を用いてこれを実現しているが、これは $O(p \log p)$ （ $p$ はテーブルサイズ）の同型演算を必要とし、多項式乗算の深さ（multiplicative depth）を大幅に消費し、推論パイプラインにおける支配的なコストとなる。

目標は、コンパクトなクライアント通信（スカラー・インデックスのみの送信）を維持しつつ、サーバー側の同型演算コスト（高価なワンホット生成ステップ）を最小限に抑える**プライベート埋め込みルックアップ（PEL）**を実現することである。

手法：独立ベクトル評価（IVE）

著者らは、ワンホット・ベクトルの構築を完全に回避する手法として、**独立ベクトル評価（Independent Vector Evaluation: IVE）**を提案する。

コアとなる洞察

サーバーは、埋め込み $M_j$ を取得するために、厳密にはワンホット・ベクトル ( $e_j$ ) を必要とするわけではない。サーバーが必要としているのは、異なるインデックス間で線形独立であるようなインデックス $j$ の表現である。もしベクトル集合 $\{v_j\}$ が線形独立であれば、基底変換行列 $L$ が存在して $L v_j = e_j$ となる。したがって、埋め込みの取得は次のように書き換えることができる：
$M_j = M e_j = M (L v_j) = (M L) v_j$
$M$ と $L$ は平文として既知であるため、サーバーは事前計算された行列 $M' = ML $を保持できる。これにより、オンラインのタスクは、ワンホット・ベクトルの生成から、ベクトル$ v_j$ の評価へと移行する。

ベクトル構築と安定性

CKKSスキーム（近似演算をサポート）における効率性と数値的安定性を確保するために、以下の手法を用いる：

効率性： ベクトル $v_j$ は、単一の暗号化された値 $\alpha_j$ の累乗を用いて構築される。これにより、サーバーは複雑な等価判定ではなく、標準的な算術演算（乗算）を用いてベクトル成分を生成できる。
安定性： 基底変換に伴う誤差増幅を防ぐため、行列 $L$ は良条件（理想的には直交）である必要がある。著者らは、**離散コサイン変換（DCT）**行列を利用する。単位根を用い、実部と虚部を分離することで、CKKSの複素演算能力に適合した直交基底を構築する。

アルゴリズムの流れ

クライアント： インデックス $j$ を $\alpha_j$ （単位根から導出）へと暗号化し、コンパクトなスカラー・クエリとして送信する。
サーバー（IVEフェーズ）：
- 暗号化された $\alpha_j$ を受信する。
- 乗算ツリー（対数深度）を用いて、累乗 $\alpha_j^0, \alpha_j^1, \dots, \alpha_j^{p/2}$ を計算する。
- 共役を用いて実部と虚部を分離し、ベクトル $v_j$ を形成する。
- このプロセスは $O(p)$ の同型演算を必要とし、ワンホット生成に必要な $O(p \log p)$ よりも大幅に削減される。
サーバー（PCMMフェーズ）：
- 事前計算された行列 $M' = ML $と生成されたベクトル$ v_j$ との間で、平文・暗号文行列乗算（PCMM）を実行する。
- これにより、暗号化された埋め込みベクトルが得られる。

主な貢献

独立ベクトル評価（IVE）： 暗号化されたワンホット生成を、線形独立なベクトル族の評価に置き換える新しいアルゴロリズム。これにより、ベクトル生成の複雑さを $O(p \log p)$ から $O(p)$ の同型演算へと低減させた。
DCTによる直交基底： IVEをDCTベースの直交行列によってインスタンス化することで、基底変換時にCKKSの近似に起因する誤差増幅を抑制し、数値的安定性を確保した。
統合されたPELパイプライン： バッチ処理されたクエリを効率的に扱うために、IVEをPCMMと統合した。このパイプラインは、CKKSのSIMDスロットを利用して複数のトークン・クエリを同時に処理できる。
エンドツーエンドの実装： 本手法をFastTextスタイルのテキスト分類パイプライン内に実装し、プライバシーに配慮した推論タスクにおける実用性を実証した。

実験結果

著者らは、3つの埋め込みデータセット（GloVe.6B.50d, Glove.42B.300d, GPT-2）およびEnron-Spamデータセットに対するエンドツーエンドのFastText推論を用いて、IVE-PELを先行研究（Kim et al.）と比較評価した。

ベクトル生成の高速化： IVE-PELはベクトル生成に要する時間を大幅に短縮した。サブテーブルサイズ $\log p = 10$ において、VecGen時間はGloVe.6B.50d上で約424 ms（Kim et al.）から約3.15 ms（IVE-PEL）へと低下し、この特定の段階において134.6倍の高速化を実現した。
トータル・パイプラインの高速化： データセットと埋め込み次元に応じて、平均化されたルックアップ時間は18.5倍から78.4倍向上した。最大の利得は、ベクトル生成が支配的なコストとなっているシナリオで観察された。
乗算深さ： IVE-PELは、ワンホット生成法が必要とする乗算深さの約1/3しか消費しない。これにより、CKKSのノイズ予算を使い果たすことなく、より大きなサブテーブルサイズや高い圧縮品質を実現できる。
エンドツーエンドへの影響： Enron-Spam分類タスクにおいて、ワンホット法をIVEに置き換えることで、全暗号化推論時間に占めるベクトル生成の割合が99.6%から66.3%へと減少し、全体のレイテンシが大幅に改善された。

意義と主張

本論文は、IVE-PELが「プライベート埋め込みルックアップにおける欠落していた設計点」に対処したと主張している。すなわち、コンパクトなクライアント通信（スカラー・インデックス）を維持しながら、サーバー側の過大なコスト（同型ワンホット生成）を回避することである。

ワンホット基底の必要性を検索プロセスから切り離すことで、著者らはプライベートな埋め込みルックアップが軽量なクライアントにとって実用的なものになり得ることを示した。結果は、IVE-PELが、ユーザーの入力インデックスの機密性を損なうことなく、NLPや推薦モデルのための効率的なプライバシー保護推論を可能にすることを示唆している。本手法は、モデルの精度（IMDB感情分析やスパム検出の結果による）を維持しつつ、計算効率を劇的に向上させている。