PaperlayerView exact revision on arXiv

Source-linked AI summary

Pointing the Way, Hiding the Destination: Practical Private Dense Retrieval at Scale

Peichun Hua, Danyang Chen, Junan Zhang, Haifeng Sun, Jingyu Wang, Diwen Xue, Mingyu Li, Yunming Xiao

arXiv:2608.25735v1cs.CRcs.AIcs.IRcs.LG

TL;DR

Private dense retrieval must hide queries and selections while returning only authorized documents without repeatedly processing the full corpus cryptographically. The paper uses a directionally private learned shortlist, encrypted reranking, and oblivious transfer. Across five zero-shot corpora, K = 500 retains 98.84%–100% of full-corpus NDCG@10, while the protocol's guarantees exclude several leakage and endpoint assumptions.

  • Problem

    Private RAG over provider-held corpora must protect queries and chosen results while limiting users to authorized documents, but existing approaches either process the full corpus cryptographically or sacrifice retrieval quality for efficiency.

  • Method

    The protocol uses a directionally metric-DP randomized binary code for candidate generation, encrypted BFV scoring for K candidates, and active-secure k-out-of-K OT for selected payloads.

  • Results

    K = 500 retains 98.84%–100% of full-corpus NDCG@10 across five zero-shot BEIR corpora and both evaluated encoders.

  • Takeaways & Limitations

    A learned private shortlist can reduce cryptographic search from the full corpus to high-recall candidates while maintaining near-lossless retrieval across corpus scales and domains.

  • Takeaways & Limitations

    The guarantees assume uncompromised endpoints, authenticated identities and confidential transport, while message metadata, exact-score inference, Sybil resistance, availability, and malformed-ciphertext privacy remain outside the model.

Abstract

from arXiv · show

Hosted retrieval-augmented generation (RAG) and semantic search allow users to query valuable provider-held corpora, raising two competing demands: to hide each query and chosen result, yet reveal only the documents that the user is authorized to receive. Existing cryptographic approaches either make this costly by processing the entire corpus for every query, or sacrifice quality for efficiency by scanning a few clusters. We repurpose learned deep hashing as a private filter: a randomized binary code points the provider to a short candidate list, while encrypted reranking and oblivious key transfer protect the precise query and final selection. This shortlist short-circuits full-corpus cryptographic search without sacrificing retrieval quality: with 200-500 candidates, it closely matches full-corpus retrieval across five zero-shot corpora spanning 25K to 5.4M documents. On the full 2.68M-passage NQ corpus over a 10-Gbps link, our protocol only adds 0.73 seconds, or 10 percent, to a 128-token Qwen3-32B RAG pipeline. The released code satisfies directional metric differential privacy (DP) and substantially reduces embedding-inversion and property-inference leakage, demonstrating that a carefully learned shortlist can make private dense retrieval both accurate and practical.

1 Introduction

The paper addresses private dense retrieval over sensitive provider-held corpora by combining a private learned shortlist with cryptographic reranking and oblivious transfer. This design targets the tension between protecting queries and selections, enforcing authorization, and avoiding full-corpus cryptographic search.

  • Sensitive RAG corpora make both document collections and user queries privacy-sensitive.
  • Existing HE, MPC, and ORAM approaches impose substantial computational, interaction, or client-resource costs at dense-retrieval scale.
  • The protocol exposes only a directionally private coarse candidate pattern, then applies encrypted scoring to K candidates and oblivious transfer to reveal at most k payloads.
  • K = 500 retains 98.84%–100% of full-corpus NDCG@10 across five zero-shot BEIR corpora and both evaluated encoders.
  • The work combines metric-DP shortlist protection, encrypted exact scoring, active-secure k-out-of-K OT, and a practical million-scale realization.

2 Background and Related Work

The paper positions learned hashing as a high-recall private filter rather than a replacement for continuous retrieval geometry. It combines directional metric privacy with shortlist reranking to reduce cryptographic work while preserving retrieval quality across deployment settings.

  • 2.1 Dense Retrieval and Learned Hashing: Dense retrieval independently encodes queries and documents, while cross-encoders are typically reserved for reranking because pairwise scoring is more expensive.
  • 2.1 Dense Retrieval and Learned Hashing: The learned binary code serves as a high-recall first-stage filter, while continuous representations remain for exact reranking over K candidates.
  • 2.2 Representation Privacy: Directional metric privacy randomizes normalized pre-binarization representations, and deterministic binarization preserves the same privacy bound by post-processing.
  • 2.2 Representation Privacy: At L = 256 and (ε = 16,δ = 10−6), randomized response flips 46.1% of bits and yields 0.0306 mean NDCG@10 at K = 3000, versus 0.5360 for Gaussian and 0.5367 for RDP-vMF.
  • 2.3 Private Retrieval across Deployments: The target deployment is a provider-held proprietary corpus serving an external querier, distinct from client-owned, public/shared-corpus, and secret-shared outsourcing models.
  • 2.3 Private Retrieval across Deployments: The protocol keeps the corpus at one provider, gives formal DP guarantees for the search pattern, protects unselected content, and limits homomorphic scoring to filtered candidates.

3 Deployment and Threat Model

The deployment model uses an honest-but-curious corpus owner and an authorized user with explicit visibility boundaries. The threat model covers query, scoring, pattern, and payload protections while measuring representation leakage through inversion and property-inference attacks.

  • 3.1 Parties and Assets: The owner stores the corpus, binary index, plaintext normalized embeddings, encrypted payloads, and per-document content keys, while remaining honest-but-curious.
  • 3.1 Parties and Assets: The user holds the query, shared encoder and hash model, HE keys, and differential-privacy parameters.
  • 3.2 Views, Leakage, and Assumptions: The four security goals protect the coarse code with metric DP, the clean query with BFV, the scoring view with ciphertext simulation, and selected positions with active-secure OT.
  • 3.2 Views, Leakage, and Assumptions: The owner sees the candidate set, randomized code, ciphertexts, transcripts, and metadata, but not the plaintext query, decrypted scores, or selected indices.
  • 3.2 Views, Leakage, and Assumptions: The user receives K scalar scores and candidate ciphertexts, but at most k content keys and corresponding plaintext payloads.
  • 3.3 Empirical Privacy Attacks: The evaluation measures search-based inversion, generation-based inversion, and property inference over topic, sentiment, and authorship attributes.

4 Deep Hash Learning

The paper adapts pretrained dense retrievers into high-recall binary candidate filters while preserving the original continuous encoder for final ranking. Training combines retrieval, ranking-transfer, and geometry-preserving objectives, with hard negatives mined only from MS MARCO.

  • Architecture: The learned hash encoder produces coarse candidate codes, while the unchanged pretrained encoder remains the Stage 2 scorer.This separation reshapes Hamming-search geometry without shifting the final dense ranking.
  • Architecture: A linear head over a LoRA-adapted encoder emits binary codes for Hamming candidate recall.The code length is 256 for E5-base-v2 and 512 for BGE-base-en-v1.5.
  • Training objectives: Training combines retrieval supervision, ranking transfer, and regularization that anchors adapted representations to frozen pretrained geometry.E5 also applies retrieval supervision directly in Hamming space.
  • Hard-negative training: Hard negatives are mined only from MS MARCO using lexical retrieval, reranking, and suppression of likely unlabeled positives.This source-only procedure preserves fine distinctions without adapting to evaluation corpora.
  • Training procedure: E5 and BGE train for 16 epochs while progressively moving from smooth representations to deployment-time binary codes.The schedule includes discretization during training rather than training directly on final codes.

5 DP-Filtered Private Dense Retrieval

The protocol exposes only a differentially private coarse Hamming pattern, then protects exact scoring and final document selection cryptographically. It overlaps hashing, pretrained encoding, ciphertext streaming, and BFV scoring to make private retrieval practical.

  • Protocol roles: K denotes the candidate budget receiving homomorphic scoring, while k denotes the final number of documents returned to the User.The protocol separates broad encrypted scoring from the smaller billable result set.
  • Setup: The Owner stores binary candidate codes and encrypted quantized scoring payloads generated from separate hash and pretrained document encoders.Ciphertexts are padded and encrypted under per-document keys, so length reveals only padded block counts.
  • Online protocol: The User releases a randomized binary query code under metric DP, while the clean query representation is encrypted for exact candidate scoring.The Owner uses the released code for Hamming search and never receives the clean scoring query.
  • Online protocol: Once CK is fixed, AEAD candidate ciphertexts stream while the unchanged pretrained forward and BFV query encryption proceed concurrently.This overlap shortens the serial prefix before packed homomorphic scoring begins.
  • Encrypted scoring: Packed BFV computes exact integer dot products over K candidates without ciphertext–ciphertext multiplication or bootstrapping.The compact layout uses randomized evaluation and clears non-score slots while preserving exact outputs.
  • Design rationale: At ε = 64, K = 3000, and k = 10, Stage 2 recovers an answer-bearing passage ranked 1,439 by coarse Hamming proximity into the User’s hidden top ten.The example demonstrates that coarse cue matching and precise semantic selection are handled by different stages.
  • Final selection: Key-only oblivious transfer sends k content keys through k 1-out-of-K choices, hiding selected positions while keeping OT payloads small.AEAD ciphertexts remain on the ordinary channel, and quotas limit repeated extraction.
  • Deployment: The binary index remains Owner-local and occupies NL/8 bytes, including 283 MB for N = 8.84M and L = 256.This avoids requiring a query-processing intermediary for Hamming search and encrypted scoring.

6 Security Contract and Protocol Guarantees

The protocol separates privacy guarantees across candidate generation, encrypted scoring, and payload access. Its formal scope includes directional metric privacy, computational protection of query and scoring views, and bounded payload-key recovery, while some leakage and exposure remain explicit.

  • Security contract: Four guarantees cover candidate-pattern privacy, Owner-view query privacy, scoring privacy, and a k-payload bound.The contract defines separate guarantees for metric privacy, computational privacy of the Owner’s view, exact BFV scoring, and payload access.
  • Candidate privacy: The vMF mechanism releases a sign-binarized code whose directional metric privacy follows from the continuous mechanism and post-processing.The mechanism samples around the normalized query direction and releases sign(Y); binarization preserves the privacy bound.
  • Query privacy: The Owner’s computational view is protected under BFV IND-CPA, receiver-private OT, and identical auxiliary leakage across adjacent executions.The residual view includes the randomized coarse code and post-processed protocol fields, with the privacy factor supplied by Theorem 1.
  • Scoring privacy: Ciphertext-simulatable BFV restricts a conforming User’s scoring view to the prescribed K exact scores, while evaluated ciphertext coefficients reveal no further candidate-embedding information.This result assumes fresh symmetric, canonically packed bounded queries and the stated correctness and smoothing conditions.
  • Payload access: An accepted malicious receiver recovers at most k distinct candidate content keys and payloads per round, independently of K.The bound relies on active-secure 1-out-of-K OT, pseudorandom masking, independent content keys, and authenticated encryption.
  • Scope and leakage: Across T accepted rounds, payload recovery composes to Tk, while scores, padded lengths, stable-ciphertext linkage, and cross-round inference remain explicit leakage.Corpus enumeration remains possible if accepted selections eventually cover the corpus, and increasing K does not change the per-round payload cap.

7 Evaluation

The evaluation tests whether learned binary filtering preserves retrieval and RAG quality while reducing private-retrieval cost and leakage. Across corpora, privacy mechanisms, budgets, and attacks, shortlists remain effective, though randomized response has poor utility.

  • Evaluation Setup: The evaluation spans five zero-shot BEIR corpora, two encoders, candidate budgets, end-to-end RAG quality, latency, and representation leakage.The corpora range from 25,657 to 5.4M documents, using 256-bit E5 and 512-bit BGE codes.
  • Retrieval Quality: 98.84–100.21% of full-corpus NDCG@10 is retained at K = 500 across SciDocs, NQ, DBpedia-Entity, and FEVER.On Climate-FEVER, NDCG@10 increases by 0.0158 for E5 and 0.0012 for BGE.
  • Retrieval Quality: 0.0357 higher mean Recall@500 and 0.0084 higher mean Stage 2 NDCG@10 than BPR demonstrate the learned filter’s candidate-quality advantage.It also improves mean Stage 2 NDCG@10 by 0.0051 over the strongest unsupervised baseline.
  • Differential Privacy: 99.2% retention requires K = 1000 for RDP-vMF and K = 2000 for Gaussian, while formal pure-vMF reaches 99.4% at K = 2000.Their absolute protection costs are 0.37, 0.73, and 0.73 seconds respectively; K = 3000 adds at most 1.10 seconds.
  • End-to-End RAG: Every two-forward operating point stays within 0.2 EM and 0.20 F1 of full-corpus float retrieval on 500 NQ queries.Pure-vMF at (ε = 64,K = 3000) reaches 50.0 EM and 62.89 F1 versus 50.0 and 63.09 for the float reference.
  • Efficiency: At 10 Gbps, total latency rises from 198.9 ms at K = 500 to 1.107 seconds at K = 3000, while compute rises from 104.1 ms to 1096.2 ms.On the full NQ RAG pipeline, K = 2000 adds 0.728 seconds, or 10.0%.
  • Privacy Leakage: Learned hashing and metric-DP randomization provide layered protection: hashing reduces inversion and attribute signal, while tighter randomization further suppresses reconstruction and property inference.Gaussian and RDP-vMF show similar attack-leakage and utility trade-offs; better trade-offs under the same ε guarantee remain future work.

8 Concluding Remarks

The paper presents a two-party private dense-retrieval design for provider-held corpora and external users. It concentrates private computation on a high-recall shortlist, preserving practical retrieval while limiting query, selection, and representation leakage.

  • Conclusion: The two-party design serves external users over provider-held corpora while concentrating private computation on a high-recall shortlist.This preserves retrieval quality and practical latency at million-document scale.
  • Conclusion: Evaluations show reduced reconstruction fidelity and attribute leakage against embedding-inversion and property-inference attacks.The design aligns disclosure with authorized results and the service’s billing model.

Ethical Considerations

The work evaluates a privacy defense for dense retrieval against documented attacks without introducing new attack algorithms. Its ethical scope relies on public benchmarks, reproduced attacks, and explicit security boundaries rather than proprietary data or product-specific vulnerabilities.

  • The proposed defense targets privacy exposure in dense retrieval within a privacy-sensitive two-party setting, using reproduced and adapted attacks rather than introducing new attack algorithms.The motivation is grounded in attacks documented in prior literature.
  • The study re-implements published embedding-inversion attacks to measure unprotected representation leakage and reproduce existing capabilities on public benchmarks and pretrained encoders.These experiments use no proprietary corpus or production system.
  • All datasets are publicly available academic research benchmarks; the study collects no new data and involves no human-subject interaction.
  • The formal query guarantee covers an honest-but-curious Owner observing the randomized code, candidate set, and protocol metadata, while cryptographic protections constrain scoring and payload-key recovery for Users.The stated boundary distinguishes the Owner's observations from protections against conforming secret-key Users and malicious receivers.
  • The evaluation addresses a general bi-encoder retrieval pipeline and reproduces public attacks, so coordinated vendor disclosure is not applicable.

A Proof Details and Auxiliary Calibration

The appendix calibrates privacy mechanisms in their respective protected spaces and details the cryptographic scoring, simulation, and key-transfer guarantees. It also documents BFV layouts and the assumptions checked for correctness and confidentiality.

  • Analytic Gaussian Baseline: Gaussian perturbation protects bounded pre-sign vectors h under Euclidean adjacency, with calibration at radius ρh solving δG(ε,ρh,σ) ≤ δ0.The implementation uses numerically solved scales for ρh = 2 and δ0 = 10−6.
  • Privacy-Space Comparisons: Gaussian and vMF mechanisms use different protected spaces and radii, so their privacy budgets cannot be ranked under unspecified common adjacency.Gaussian acts on h, whereas vMF acts on normalized direction u under angular or chord adjacency.
  • Approximate-vMF Calibration: The approximate-vMF guarantee requires taking the supremum of the hockey-stick divergence over all angles θ ∈ [0,ρ], while the protocol uses exact pure-vMF calibration.Boundary quadrature alone requires establishing which angle maximizes the divergence.
  • BFV Scoring: BFV batching groups eight candidates per score group and uses rotations and additions to place each dot product at a designated anchor.The multi layout returns ⌈K/8⌉ ciphertexts, while the compact layout masks non-anchor slots and packs groups into output ciphertexts.
  • Security and Correctness: Circuit correctness assumes sufficient BFV noise budget, verified through successful decryption and equality with an int32 oracle; circuit privacy and malicious-input validity are separate properties.The security proof combines active-secure OT receiver privacy, BFV IND-CPA security, and authenticated payload protection.

B.1 Experimental Setup Details

The experiments train and evaluate learned binary filters as high-recall first-stage retrieval systems, while retaining pretrained float representations for candidate reranking. Setup spans five BEIR corpora, two encoders, multiple privacy mechanisms, and representation-leakage attacks.

  • Evaluation Corpora: The evaluation uses SciDocs, Natural Questions, DBpedia-Entity, FEVER, and Climate-FEVER, whose query distributions differ despite largely overlapping corpora.Climate-FEVER adapts claim–evidence retrieval to real-world climate claims and disputed evidence.
  • Metrics: NDCG@k rewards relevant documents ranked higher, whereas Recall@k measures only whether relevant documents appear in the top-k.NDCG is therefore sensitive to top-k ordering while Recall is not.
  • Models and Hard Negatives: Training mines BM25 and cross-encoder hard negatives, removes near-ties from the binary loss, and found that stronger mining settings did not improve results.More hard negatives even harmed evaluated quality.
  • Training Objective: The objective combines continuous ranking, binary ranking, RankKD, FloatKD, and GOR to preserve ranking information and stabilize geometry before binarization.FloatKD retains pretrained geometry during LoRA adaptation, while GOR discourages directional collapse.
  • Two-Forward Evaluation: Stage 1 retrieves exact Hamming top-K candidates with the trained hash encoder, and Stage 2 independently reranks them using the original pretrained encoder’s float similarity.The hash model’s continuous representation is not reused for Stage 2 scoring.
  • Privacy and Hash Baselines: The DP sweeps evaluate E5 and BGE across K ∈ {200,500,1000,2000,3000}, privacy mechanisms, and ε values, followed by exact Hamming search and unchanged pretrained reranking.Gaussian and RDP-vMF use δ = 10−6, while pure-vMF uses the formal calibration.
  • Leakage Evaluation: Additional attack experiments test search-based inversion and property inference using topic, sentiment, and authorship attributes.The property-inference setup trains supervised probes on released representations and evaluates held-out victim releases.
  • Inversion Results: Float releases reconstruct specific entities and relations, whereas learned hashes usually retain only broad cues and Gaussian randomization removes even those associations.Across four inversion cases, Gaussian outputs become unrelated to the target and match near-zero verifier cosine.

C Additional Retrieval Results

Additional results show how candidate budgets and clean-query reranking recover retrieval quality while preserving the intended resolution split between coarse filtering and exact selection. The end-to-end stack remains compatible with client-side reranking and protected payload access.

  • Candidate-Budget Effects: At ε = 32, Gaussian approaches the no-DP curve by K = 1000, while pure-vMF continues benefiting from larger pools on NQ and FEVER.The float references expose remaining candidate loss and the saturation point as K increases.
  • Privacy–Utility Trade-offs: Approximate mechanisms saturate at smaller K, whereas formal pure-vMF needs larger pools at tighter budgets and converges toward the float reference as ε increases.Both encoders exhibit this operating pattern across the reported retrieval sweeps.
  • End-to-End RAG: The protocol opens ten passages through OT, locally reranks them with the MS MARCO cross-encoder, and supplies the top five to Qwen3-32B.The cross-encoder uses the clean query and authorized plaintext payloads entirely on the User side.
  • End-to-End RAG: Client-side reranking raises answer-bearing context coverage by 0.6–1.4 points and improves EM by at least 3.0 points.Protected variants remain within 0.4 EM and 0.35 F1 of the cross-encoder float reference.
  • Protocol Realization: The cryptographic implementation combines compact BFV scoring, active-secure OT, authenticated payload encryption, and long-lived daemon roles for User and Owner.The authenticated round includes session setup, quota reservation, payload delivery, and commit.

D.3 Latency Measurement Methodology

The latency methodology measures complete online protocol paths, including cryptography, transfer, OT, and payload handling, while separating reusable preprocessing from per-query work. Matched comparisons use common embeddings and corpus contracts across several private-retrieval systems.

  • Measurement Design: The corpus comparison evaluates four protocols on common E5-base-v2 embeddings across SciDocs, Webis-Touché, and NQ-1M.A separate two-process harness checks the complete Owner/User message path against retrieval and byte-for-byte payload oracles.
  • Latency Accounting: The pipelined critical path overlaps payload transfer with scoring and includes hashing, DP, Hamming search, encryption, scoring, post-processing, and final opening.Figure 3 reports this path, while Figure 4 adds Qwen3-32B generation.
  • Measurement Scope: The experiments measure protocol stages on 25,657 synthetic rows and RAG performance using full-corpus float queries, 2.68M-code NQ searches, and generation runs.Long-lived BFV and OT state is reused across rounds.
  • Common Benchmark Contract: The benchmark fixes normalized 768-dimensional E5 vectors and top-10 output while including online setup, search, secure scoring, selection, and serialized traffic.Query encoding and one-time key or session setup are excluded because they are shared or reusable.
  • Matched Comparison: The protocol retains at least 99% of float NDCG@10 at K = 292 on SciDocs, K = 104 on Touché, and K = 1956 on NQ-1M.These operating points use pure-vMF at ε = 64 and active-secure 10-out-of-K key transfer.
  • Matched Comparison: RemoteRAG uses spherical-cap shortlists and Paillier encrypted cosine, while P2RAG and PANTHER are measured with their respective official or reproduced implementations.RemoteRAG’s mean shortlist sizes are 627.3 on SciDocs, 1,581.4 on Touché, and 2,178 on measured NQ-1M queries.
  • Message Sequence: Figure 9 expands the authenticated message sequence with session binding, quota reservation, OT extension, payload delivery, and commit.The flow permits coarse search, payload streaming, and scoring-query transmission to proceed in overlapping order.
Loading 2608.25735v1…