論文の概要: Billion-Scale Nearest-Neighbor Search under Fully Homomorphic Encryption on a Single GPU, Balancing Leakage and Cost

• arxiv url: http://arxiv.org/abs/2608.21131v1
• Date: Fri, 21 Aug 2026 14:08:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-24 14:49:32.564554
• Title: Billion-Scale Nearest-Neighbor Search under Fully Homomorphic Encryption on a Single GPU, Balancing Leakage and Cost
• Title（参考訳）: 単一GPU上での完全同型暗号化による数十億ドル規模のニアニアサーチ
• Abstract要約: どのデータベースベクタが私のクエリに最もよく似ているか?」と答えるシステムを構築します。 クエリは完全に同型 En-cryption (FHE) で暗号化される サーバは暗号文でスコア付けを行い、クライアントのみが読める暗号化された結果を返す。
• 参考スコア（独自算出の注目度）: 1.8050555114021396
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We build a system that answers "which database vectors are most similar to my query?" without the server ever seeing the query. The query is encrypted with fully homomorphic en- cryption (FHE); the server does all its scoring on ciphertexts and returns encrypted results that only the client can read. The challenge is speed: at a billion vectors, scoring every row under encryption is far too slow, so we combine two ideas - rank reduction (shrink each vector's dimen- sion) and a hierarchy (route to a small candidate set instead of scanning everything) - executed under encryption on a single GPU. We evaluate on three corpora at very different scales: a face corpus of 222 049 centroids clustered from ~10 M face images (512-dim), DataComp-1B (1.39 x 10^9 vectors, 512-dim CLIP), and Deep1B (10^9 vectors, 96-dim). On DataComp-1B we reach a recall@10 of 0.90 against the single labeled answer, or 0.95 when a near-duplicate im- age in the top-10 also counts as correct (the data is web-scraped and full of duplicates), at ~6 s per encrypted query on a GPU; a lighter configuration reaches 0.78/0.83 at ~1.8 s. These are warm (deployable) server-side latencies - client decryption and network transfer are excluded. On Deep1B we reach recall@10 0.90 under all-levels FHE (0.9045 measured over 2000 FHE queries, matching the 0.906 plaintext routing - the 96 -> 128 zero-pad is exact, correlation 1.0) at 2.3 s warm per query. We describe the full client-server protocol in enough detail to repro- duce it, and report accuracy and latency for every configuration. We also measure what this speed costs: the hierarchy's access pattern leaks the database geometry (an observer recovers 72% of the coarse-cell neighbor graph from access patterns alone), and we show that seeded (fixed-group) padding cuts this leak by ~35x (to ~2%), where naive padding is defeated by a repeated-query attack.
• Abstract（参考訳）: どのデータベースベクタが私のクエリに最もよく似ているか?」と答えるシステムを構築します。 クエリは、完全に同型なen-cryption (FHE)で暗号化され、サーバは暗号文でスコア付けを行い、クライアントのみが読める暗号化結果を返す。 10億のベクターでは、暗号化下ですべての行をスコアするのは非常に遅いので、ランクの低減(各ベクターのダイメン次元を縮小)と階層(すべてをスキャンする代わりに小さな候補セットに切り替える)という、2つのアイデアを1つのGPU上で暗号化で実行します。 約10Mの顔画像 (512-dim), DataComp-1B (1.39 x 10^9 ベクトル, 512-dim CLIP), Deep1B (10^9 ベクトル, 96-dim) の3つの顔コーパスを, 異なるスケールで評価した。 DataComp-1Bでは、単一のラベル付き回答に対して0.90のリコール@10に達するか、上位10のほぼ重複したIm- Ageも正しい(データはWebスクラッチで重複でいっぱいだ)と0.95に達する。 これらは温かい(デプロイ可能な)サーバ側のレイテンシです。クライアントの復号化とネットワーク転送は除外されます。 Deep1Bでは、すべてのレベルの FHE (0.9045 over 2000 FHE query, 0.906 plaintext routing - 96 -> 128 zero-pad is exact, correlation 1.0) でリコール@10 0.90に到達します。 完全なクライアントサーバプロトコルを詳細に記述し、それを再プロデューサし、設定毎に正確さとレイテンシを報告します。 階層のアクセスパターンはデータベースのジオメトリをリークする(観測者はアクセスパターンのみから粗いセルグラフの72%を復元する)。

関連論文リスト

• What Drives Recovery in Agentic Text-to-Cypher? LAST-CQ: An LLM Agent Self-Refinement Framework [0.0]
  LAST-CQは5エージェント、トレーニング不要、実行ベースとしたText-to-Cypherフレームワークである。 私たちは2,471件のライブデータベースクエリと3つのベンダースケール層にまたがる6つのバックボーンで3つのカウンタファクトを実行しています。
  論文  参考訳（メタデータ） (2026-09-11T11:47:42Z)
• Codebook Agent: Amortized Topology Design for LLM Multi-Agent Systems [67.04448659688579]
  クエリ非依存の16エントリのコードブックを開発し、上位のデコード候補を1回のバッチフォワードパスでランク付けする。 反復検索がなく、テスト時にメッセージパッシングがないため、Codebook Agentは6つのベンチマークでもっとも正確な方法である。
  論文  参考訳（メタデータ） (2026-09-02T08:10:22Z)
• Pointing the Way, Hiding the Destination: Practical Private Dense Retrieval at Scale [19.48684574323907]
  ホストされた検索強化世代(RAG)とセマンティックサーチにより、ユーザは価値あるプロバイダが所有するコーパスをクエリできる。 既存の暗号化アプローチでは、クエリ毎にコーパス全体を処理することでコストがかかります。 このショートリストは、検索品質を犠牲にすることなく全コーパス暗号検索を行う。
  論文  参考訳（メタデータ） (2026-08-26T12:46:36Z)
• The Recall Trap: A Recall-Maximizing Retriever Configuration Reduces Issue Resolution in Fixed-Budget Code Context [45.88028371034407]
  コード修復における制御ケーススタディを報告し,新しい現象ではない。 私たちは、同じスタック上の1つのフラグ(1チャンク毎の重複)を切り替えます。 BM25(3.2pp、重要なパラダイム間相互作用)を逆転させる。 厳格な固定予算では、ファイルごとのハードダイドプリケートや、タスクに対するA/Bパッケージングポリシは、メトリックフラグを調整しないことが示されます。
  論文  参考訳（メタデータ） (2026-08-14T19:22:50Z)
• MediaWiki Code2Code Search: Neural Retrieval for the Semantic Discovery of Open-Source Software Entities [0.5279475826661643]
  本稿では,意味的コード-コード発見のためのニューラル検索システムであるCode2 InformationCode Searchを紹介する。 2500以上の大規模リポジトリにまたがる構造的(関数,型,テンプレート)のコードにより,本システムは計算意図に基づく検索を可能にする。 我々はスプリットビルドアーキテクチャを採用し、CPUのみのサービス層から集中的なオフラインインデックスを分離しています。
  論文  参考訳（メタデータ） (2026-07-29T11:07:07Z)
• Reliable Homomorphic Matching for Fuzzy Labeled PSI at Scale [0.6430130814523795]
  Fuzzy Labeled Private Set Intersection (FLPSI)は、受信者がそのクエリと同じような登録レコードのラベルを学習する。 我々は、その準同型形式について研究し、レベル付きBFV準同型暗号(HE)、ガーブラード回路、シークレット共有を組み合わせて、暗号の下での一致を判定し、レコードのラベルを解放する。
  論文  参考訳（メタデータ） (2026-06-26T07:40:03Z)
• GPUSparse: GPU-Accelerated Learned Sparse Retrieval with Parallel Inverted Indices [3.3723515662362265]
  本稿では,GPUを高速化した正確なスパース検索システムであるGPUSparseを提案する。 ブロック整列されたワープ対応のポストリストを持つGPU並列逆インデックスを使用する。 Batched scatter-add スコアリングアルゴリズムは数百のクエリを同時に処理する。
  論文  参考訳（メタデータ） (2026-06-24T23:07:57Z)
• MonaVec: A Training-Free Embedded Vector Search Kernel for Edge and Offline AI Systems [0.0]
  MonaVecはエッジとオフラインAIのための決定論的、組み込みベクター検索カーネルである。 デバイス上のRAG,オフラインの組込み検索 -- リレーショナルデータのニッチ – をターゲットとしています。
  論文  参考訳（メタデータ） (2026-06-17T18:00:54Z)
• Claudini: Autoresearch Discovers State-of-the-Art Adversarial Attack Algorithms for LLMs [75.62489398666644]
  我々は,Claude Codeをベースとしたemphautoresearchスタイルのパイプライン citepkarpathy2026autoresearch が,新しいホワイトボックス対逆攻撃を発見できることを示した。 textbfsignantは、jailbreakで既存のすべての(30以上のメソッド)を著しく上回り、インジェクション評価を促します。
  論文  参考訳（メタデータ） (2026-03-25T16:50:56Z)
• FuseSampleAgg: Fused Neighbor Sampling and Aggregation for Mini-batch GNNs [51.56484100374058]
  FuseSampleAggは、隣人の平均アグリゲーションをGraphSAGEの1つのパスにフューズし、サンプリングする。 Operatorは決定論的であり、標準のPyTorchと統合され、CSVログからすべてのテーブルとフィギュアを再現するスクリプトが同梱されている。
  論文  参考訳（メタデータ） (2025-11-17T17:57:18Z)
• Peekaboo, I See Your Queries: Passive Attacks Against DSSE Via Intermittent Observations [43.35160637778568]
  DSSEは動的暗号化されたデータベースのセキュアな検索を可能にするが、固有の情報漏洩に悩まされている。 我々は新しいユニバーサルアタックフレームワークであるPeekabooを提案し、コア設計は検索パターンの推測に依存している。 FMA の 30% に対して,検索パターン回復のための 0.9 調整されたランドインデックス,90% のクエリ精度を実現した。
  論文  参考訳（メタデータ） (2025-09-04T01:47:22Z)
• Infini-gram mini: Exact n-gram Search at the Internet Scale with FM-Index [110.90283601829724]
  ペタバイトレベルのテキストコーパスを検索可能にするシステムであるinfini-gram miniを提案する。 FMインデックスデータ構造に基づいて,本システムはコーパスの44%の大きさのインデックスを生成する。 ベンチマーク汚染の大規模解析において重要なユースケースが1つある。
  論文  参考訳（メタデータ） (2025-06-13T21:13:57Z)
• Encrypted Vector Similarity Computations Using Partially Homomorphic Encryption: Applications and Performance Analysis [0.0]
  部分同型暗号(PHE)を用いて暗号化されたコサイン類似性を計算可能であることを示す。 PHEは計算集約性が少なく、高速で、より小さな暗号文/鍵を生成する。 結果は、PHEがメモリ制限された環境と現実世界のプライバシー保護暗号化類似性検索に適していることを示している。
  論文  参考訳（メタデータ） (2025-03-07T09:52:16Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。