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

Summary

This paper builds private retrieval for a provider-held corpus: a user queries a valuable document collection, the provider learns little about the query or which documents the user selects, and the user receives only the documents it is authorized to get. A learned binary filter shrinks the cryptographic work to a short candidate list. With 200 to 500 candidates, retrieval quality closely matches a scan of the full corpus on five datasets of 25 thousand to 5.4 million documents, and on a 2.68 million passage corpus the protocol adds 0.73 seconds, 10%, to a retrieval-augmented generation (RAG) pipeline.

Key numbers

• 0.73 s (10%)Added latency over a plaintext 128-token Qwen3-32B RAG pipeline on 2.68M passages at 10 Gbps
• 0.5787 vs 0.5854NDCG@10 on Natural Questions with 500 candidates compared with full-corpus retrieval
• 99.2–99.4%Retrieval quality retained under randomized, differentially private query codes with 1,000 to 2,000 candidates

Method

Dense retrieval maps queries and documents to vectors and returns the nearest ones, and it sits at the core of RAG ^[1]. Embeddings are not opaque: attacks recover source text and private attributes from them ^[2][3]. Cryptographic protocols that scan the whole corpus, using homomorphic encryption (HE, arithmetic on encrypted data) or multi-party computation, cost orders of magnitude more than plaintext search. This design instead reveals a coarse candidate pattern on purpose and spends cryptography only on the resulting shortlist.

The Corpus Owner is honest-but-curious: it follows the protocol and tries to learn from what it sees. It keeps the full-precision embeddings and a binary index. The User maps its query to a binary hash code and randomizes the bits under directional metric differential privacy (mDP), a guarantee that makes queries pointing in similar directions produce similar code distributions, so the Owner cannot tell them apart. The Owner finds a Hamming shortlist of K candidates, scores them against the encrypted query with packed BFV homomorphic encryption ^[4], and returns the encrypted scores. The User decrypts, picks the top k locally, and uses k-out-of-K oblivious transfer (OT, a protocol that lets a receiver open chosen items without revealing the choice and without learning the others) to obtain only those k documents.

Recovering quality under noise may need K between 500 and 3,000, while a RAG request releases and bills only k = 3 to 10 documents. Returning the shortlist would disclose hundreds of times more content than the user paid for, and requesting the final documents directly would reveal the selection. The OT step closes that gap and ties each round to the billable result count.

Evaluation

The retrieval stage uses a learned hash to select K candidates, and the unchanged pretrained encoder reranks them. Across five BEIR ^[5] corpora (SciDocs, Natural Questions, DBpedia-Entity, Climate-FEVER, and FEVER) of 25K to 5.4M documents, K = 200 to 500 closely matches full-corpus retrieval. On Natural Questions, NDCG@10, the ranking quality of the top 10 results, is 0.5723 at K = 200 and 0.5787 at K = 500, against 0.5854 for the full corpus. On Climate-FEVER the shortlist exceeds the full-corpus score (0.2818 against 0.2627).

Randomizing the released code keeps quality. At K = 1,000 to 2,000, three randomization mechanisms retain 99.2 to 99.4% of retrieval quality. Their absolute protection cost on a 128-token Qwen3-32B pipeline is 0.37 to 0.73 seconds, or at most 9.97% of the plaintext pipeline, and the K = 3,000 endpoint adds at most 1.10 seconds. The paper compares online latency with p²RAG ^[6] and RemoteRAG ^[7] on matched corpora.

The released code lowers the success of three published attacks. Search-based inversion, generation-based inversion ^[3], and property inference reconstruct less text and recover fewer attributes from the learned hash than from float embeddings, and metric-DP randomization adds a further drop. In the paper's case study, the float embedding reveals a named organization, the learned hash produces a banking organization, and the randomized code produces an unrelated geographic passage.

Security model and limitations

The Owner is honest-but-curious, and the protocol leaks by design: it reveals a metric-DP coarse candidate pattern, message lengths, timing, and the public result count k. A malicious User is covered only for payload extraction, where the active-secure OT limits it to k keys per round. Authenticated accounts and cumulative quotas govern repeated extraction across rounds.

Privacy and quality trade against each other: tighter privacy budgets need larger candidate sets, and the K = 3,000 endpoint adds up to 1.10 seconds on the generation pipeline. The payload bound composes across accepted rounds, so quotas cap total extraction. The attack evaluation reproduces published attacks and adds no new ones, so protection against an attack not yet published is not measured. Two retrievers (E5 and BGE) and five corpora are evaluated.

Citation

@article{hua2026pointing,
  author       = {Peichun Hua and
                  Danyang Chen and
                  Junan Zhang and
                  Haifeng Sun and
                  Jingyu Wang and
                  Diwen Xue and
                  Mingyu Li and
                  Yunming Xiao},
  title        = {Pointing the Way, Hiding the Destination: Practical Private Dense Retrieval at Scale},
  journal      = {CoRR},
  volume       = {abs/2608.25735},
  year         = {2026},
  url          = {https://arxiv.org/abs/2608.25735},
  doi          = {10.48550/arXiv.2608.25735},
  eprinttype   = {arXiv},
  eprint       = {2608.25735}
}

References

1. Patrick Lewis et al. Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks. NeurIPS, 2020. arxiv.org/abs/2005.11401
2. John X. Morris, Volodymyr Kuleshov, Vitaly Shmatikov, and Alexander M. Rush. Text Embeddings Reveal (Almost) As Much As Text. EMNLP, 2023. arxiv.org/abs/2310.06816
3. Haoran Li, Mingshi Xu, and Yangqiu Song. Sentence Embedding Leaks More Information than You Expect: Generative Embedding Inversion Attack to Recover the Whole Sentence. Findings of ACL, 2023. arxiv.org/abs/2305.03010
4. Junfeng Fan and Frederik Vercauteren. Somewhat Practical Fully Homomorphic Encryption. IACR Cryptology ePrint Archive, 2012. eprint.iacr.org/2012/144
5. Nandan Thakur et al. BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models. NeurIPS Datasets and Benchmarks, 2021. arxiv.org/abs/2104.08663
6. Yulong Ming et al. P²RAG: Efficient Privacy-Preserving RAG Service Supporting Arbitrary Top-k Retrieval. arXiv, 2026. arxiv.org/abs/2603.14778
7. Yihang Cheng et al. RemoteRAG: A Privacy-Preserving LLM Cloud RAG Service. Findings of ACL, 2025. arxiv.org/abs/2412.12775