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 preprint · 2026

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

Read paper (PDF) arXiv record arXiv PDF

Overview

This paper studies private retrieval over a provider-held corpus: a user should obtain authorized results while protecting the query and final selection. A learned binary filter reduces cryptographic search to a compact candidate set.

Method

The user releases a randomized hash code under directional metric differential privacy. The provider builds a Hamming shortlist, scores candidates with packed BFV homomorphic encryption, and uses oblivious key transfer to release only the selected document payloads. The design explicitly permits a coarse, privacy-controlled candidate pattern.

Protocol diagram connecting a randomized user hash to provider shortlisting, BFV encrypted embedding scores, and k-of-K oblivious key transfer for selected documents. — Private retrieval combines a privacy-controlled hash shortlist, encrypted scoring, and oblivious selection. Figure 2 in the paper

Evaluation

Shortlists of 200–500 candidates closely match full-corpus retrieval across five zero-shot corpora spanning 25K–5.4M documents. On the 2.68M-passage Natural Questions corpus over a 10 Gbps link, the evaluated protocol adds 0.73 seconds, or 10%, to a 128-token Qwen3-32B RAG pipeline. The paper separately evaluates privacy–utility trade-offs under randomized releases.

Shortlist reranking versus full-corpus retrieval
Corpus	Documents	NDCG@10, K = 200	NDCG@10, K = 500	Full-corpus NDCG@10
SciDocs	25K	0.1875	0.1874	0.1870
Natural Questions	2.7M	0.5723	0.5787	0.5854
DBpedia-Entity	4.6M	0.4144	0.4224	0.4271
Climate-FEVER	5.4M	0.2818	0.2785	0.2627
FEVER	5.4M	0.8417	0.8451	0.8501

E5-base-v2 (256-bit) subset of Table 3. A learned binary hash selects K candidates, then the unchanged pretrained encoder reranks them. This table evaluates the base two-forward retrieval pipeline; randomized-release privacy–utility experiments are reported separately in the paper. Corpus sizes are rounded as in the source. Table 3 in the paper

private retrieval
homomorphic encryption
oblivious transfer
differential privacy
deep hashing
RAG

Citation

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