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

cs.CRAug 26, 2026

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

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

Organizations: The Chinese University of Hong Kong, Shenzhen · State Key Laboratory of Internet Architecture, Tsinghua University · Beijing University of Posts and Telecommunications · The Chinese University of Hong Kong ·

Abstract

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.

Figures & tables

Figure 1: Cross-dataset quality of our pipeline. Each panel reports absolute Stage 2 NDCG@10 at

K\in\{200,500\}

alongside full-corpus pretrained retrieval. The five BEIR corpora span 25K–5.4M documents and four retrieval domains.

Scheme	Search	Infra.	Query privacy	Content privacy	Pattern privacy	Near- lossless	Fast online	Index / auxiliary state
Client-owned outsourcing—corpus owner is querier; cloud is adversary
CGKO06 [ 20 ]	Keyword	1S	✓	–	✗	–	–	Inverted index
CLRZ18 [ 9 ] , SOPK21 [ 74 ]	Keyword	1S	✓	–	dp	–	–	DP index
LZXL25 [ 56 ]	Graph	1S	$\triangle$	–	✗	$\triangle$	✓	Graph + 2 CT
Compass [ 98 ]	Graph	1S	✓	–	✓	✓	$\triangle$	3.2–6.8 $\times$ server
MESS [ 19 ]	Multi-graph	1S	dp	–	dp	$\triangle$	$\triangle$	16 $\times$ HNSW index

Table 1: Private retrieval systems grouped by corpus ownership, querier role, and trusted infrastructure.

Figure 2: Online retrieval pipeline. Metric-DP Hamming shortlisting overlaps the pretrained scoring forward and query encryption. Once $C_{K}$ is fixed, its AEAD ciphertexts stream during exact BFV scoring.

View	Rank / $d_{H}$	Text excerpt
Target	–	Who made the poppies at Tower of London?
DP-Ham.	1 / 65	10 Downing Street: “The terrace and garden were constructed in 1736 …”
DP-Ham.	2 / 69	Anzac Day: “Paper poppies are widely distributed …”
DP-Ham.	3 / 70	Eiffel Tower: “26 December 1888: Construction of the upper stage.”
Stage 2	1439 $\rightarrow$ 5 / 88	Blood Swept Lands and Seas of Red: “The artist was Paul Cummins, with setting by stage designer Tom Piper.”

Table 2: One NQ query ( test1054 ) under the E5 pure-vMF operating point (

\varepsilon=64

K=3000

k=10

, 256 bits). The DP-Hamming neighbors expose a broad mixture of query cues; Stage 2 recovers the answer-bearing passage.

Model	Dataset	Docs	$K$ =200	$K$ =500	S2@200	S2@500	Pretr. Fl.	$\boldsymbol{\Delta@200}$	$\boldsymbol{\Delta@500}$
			Stage 1: Bin. Recall@ $K$		Stage 2: NDCG@10
E5-base-v2	SciDocs	25K	.4331	.5469	.1875	.1874	.1870	$+.0005$	$+.0004$
(256-bit)	NQ	2.7M	.8884	.9271	.5723	.5787	.5854	$-.0132$	$-.0068$
	DBpedia-Entity	4.6M	.4549	.5474	.4144	.4224	.4271	$-.0127$	$-.0047$
	Climate-FEVER	5.4M	.5300	.6154	.2818	.2785	.2627	$+.0192$	$+.0158$
	FEVER	5.4M	.9368	.9484	.8417	.8451	.8501	$-.0084$	$-.0050$

Table 3: Two-forward retrieval on five BEIR corpora spanning 25K–5.4M documents. Stage 1 uses the learned hash model; Stage 2 reranks its candidates with the original pretrained encoder. Pretr. Fl. is matched full-corpus retrieval, and each

\Delta@K

is Stage 2@

K

minus Pretr. Fl.

	Recall@ $K$		NDCG@10
Method	$K=200$	$K=500$	$K=200$	$K=500$
Direct sign (768b)	.5046	.5669	.4183	.4338
Random-hyperplane LSH [ 7 ]	.3068	.3743	.2893	.3283
Super-Bit LSH [ 41 ]	.3257	.3916	.3008	.3366
PCA-sign	.5802	.6398	.4469	.4534
ITQ [ 28 ]	.6080	.6789	.4494	.4562

Table 4: E5 candidate-filter baselines averaged over the five corpora in Table 3 . Every method uses exact Hamming Stage 1 and the same pretrained E5 Stage 2 scorer. Direct sign uses 768 embedding coordinates; remaining methods use 256 bits.

Release	Guarantee	$(\varepsilon,K)$	NDCG@10	Ret.	RAG s	$\Delta$ s
Full-corpus float	Reference	$(\infty,N)$	.5394	100.0%	7.302	—
Plaintext filter	None	$(\infty,500)$	.5363	99.4%	7.305	0
Randomized response	$(\varepsilon,\delta)$ -DP	$(16,3000)$	.0306	5.7%	8.403	+1.098
Gaussian	$(\varepsilon,\delta)$ -DP	$(8,3000)$	.5084	94.3%	8.403	+1.098
Gaussian	$(\varepsilon,\delta)$ -DP	$(16,2000)$	.5350	99.2%	8.033	+0.728
RDP-vMF	$(\varepsilon,\delta)$ -DP	$(8,3000)$	.5187	96.2%	8.403	+1.098

Table 5: Representative two-forward DP operating points. NDCG@10 averages E5 and BGE on SciDocs, NQ, and FEVER. RAG latency uses Qwen3-32B with 128 output tokens on NQ;

\Delta

is the absolute protection cost over the plaintext two-forward pipeline.

Retrieval	$(\varepsilon,K)$	Hit	EM	F1
Full-corpus float	$(\infty,N)$	88.4	50.0	63.09
No-DP hash	$(\infty,500)$	87.8	50.2	63.12
Gaussian	$(16,3000)$	88.2	50.2	63.06
RDP-vMF	$(16,3000)$	87.8	50.2	63.00
Pure-vMF	$(64,3000)$	87.8	50.0	62.89

Table 6: End-to-end RAG quality on 500 NQ queries. Hit is answer-alias coverage in 5 passages supplied to Qwen3-32B.

Figure 3: Protected critical-path latency at

K=500

. After Step 1, Owner-side Step 2 and User-side Step 3 overlap, hiding 5.40 of 7.77 ms for E5 and all 7.83 ms for BGE before Step 4. Times are milliseconds; § 5.2 defines the steps.

			Protected latency (ms)
$K$	Compute	Traffic (MB)	100 Mbps	1 Gbps	10 Gbps
200	104.1	1.64	235.6	117.3	105.4
500	196.6	2.93	430.9	220.0	198.9
1000	376.1	5.07	781.7	416.6	380.1
2000	729.8	9.35	1478.2	804.7	737.3
3000	1096.2	13.64	2187.3	1205.3	1107.1

Table 7: Protected retrieval before generation versus candidate budget on SciDocs. Compute includes query DP and the complete randomized-evaluation protocol except transfer; bandwidth columns add the exact serialized traffic.

Figure 4: Incremental latency over plaintext 128-token RAG. Qwen3-32B generation takes 7.296 seconds on one A100 (7.305 seconds total); labels report added latency, percentage overhead, and protected total.

Figure 5: Matched online protocol latency on three corpus scales using E5-base-v2, top-10 output, and a 100-Mbps link. Our protocol uses pure-vMF at

\varepsilon=64

and the smallest dataset-specific

K

that retains at least 99% of float NDCG@10. PANTHER exhausts 256 GB of memory in NQ-1M.

Metric	Float	No-DP hash	Pure-vMF ( $\varepsilon=64$ )
Search cosine	.824	.638	.423
Search success	.920	.590	.325
Gen. token F1	.545	.368	.205
Gen. cosine	.784	.584	.328

Table 8: Embedding-inversion measurements for E5-base-v2; lower is better. Hash and pure-vMF releases use 256-bit codes, and pure-vMF provides metric DP. Search success uses a verifier-cosine threshold of 0.8.

Figure 6: Search-based embedding inversion under Gaussian and RDP-vMF randomization at

\rho_{h}=2

. The left panel reports mean verifier cosine similarity and the right panel reports attack success at a threshold of 0.8. Horizontal lines show the float and no-DP learned-code references.

Figure 7: Generation-based embedding inversion under Gaussian and RDP-vMF randomization.

Release	$\varepsilon$	Topic	Sentiment	Authorship	Mean
Gaussian	8	.6001	.4763	.0862	.3875
Gaussian	16	.6303	.5402	.1002	.4235
Gaussian	32	.7024	.5849	.1303	.4725
Gaussian	64	.8221	.6575	.1875	.5557
RDP-vMF	8	.5980	.5021	.0727	.3909
RDP-vMF	16	.6251	.5528	.0924	.4234

Table 10: E5 property-inference macro F1 for the validation-selected best attacker; lower is better. Entries average five stratified splits.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

$\varepsilon$	8	16	32	64
$\sigma$	1.3059	0.7372	0.4324	0.2638

Appendix

Table 11: Analytic Gaussian scales for bounded pre-sign representations at Euclidean radius

\rho_{h}=2

and

\delta_{0}=10^{-6}

Case	View	Rank / $d_{H}$	Target or passage excerpt
A	Target	–	How many amendments to the Constitution have there been?
	DP-Ham.	1 / 60	First Amendment to the United States Constitution: “The civil rights of none shall be abridged …”
	DP-Ham.	2 / 60	Limited government: “The Ninth and Tenth Amendments …”
	DP-Ham.	3 / 60	Article Three of the United States Constitution: “Hamilton continues …”
	Stage 2	1742 $\rightarrow$ 1 / 82	List of amendments to the United States Constitution: “Thirty-three amendments … have been proposed … Twenty-seven … are part of the Constitution.”
B	Target	–	Where is the world’s highest battlefield located?

Appendix

Table 12: Three additional NQ candidate-set cases under E5 pure-vMF (

\varepsilon=64

K=3000

k=10

, 256 bits). Stage 2 entries show coarse Hamming rank

\rightarrow

clean-float rank.

Case	Release	Complete target or reconstruction	Cosine
A	Target	Welcome to the U.S. High School Bowling Foundation. The U.S. High School Bowling Foundation (USHSBF) is an IRS 501 (c)(3) non-profit organization that actively promotes the growth of high school bowling throughout the country.	–
	Float	US Bowling Foundation. The nonprofit organization. USABF or HS, is an (non profit.)501, 501(C). US bowling ( foundation) or the bowling ( foundation) (U.s)	.903
	Learned hash	US Bank is affiliated by National Bank Union(UFBG,NFUB or more informlly refererd UBFGU) through UBFBU-UnitedStatebannkinngunitiationthough there name oficialally stands out too - unitesstatebunkfinfinitation. However alot offpeople recognizeit with thershorthandletternamr ofunsttobbankor	.464
	Gaussian, $\varepsilon=8$	The country Australia encompasses expansive territories spanning over seven major regions with diverse geology, resulting form varied processes across historical timescale having several distinct natural environments within different territoories - Northern Territories comprising land that shares the Timoresse Sea and extends from southern coast to Indonesian borders as well northern territory known as Western Artesia, along the Great Victoria river system in addition the southeastern coastline forms extensive shoreline along	$-.060$
B	Target	What does FGA stand for? What does FGA mean? This page is about the various possible meanings of the acronym, abbreviation, shorthand or slang term: FGA.	–
	Float	FAA acronym definition abbreviation. What meaning? short name F.A. Association meaning? What stands: stands for.	.697

Appendix

Table 13: Complete search-based inversion outputs for four MS MARCO targets. Case A is the example summarized in Table 9 ; Cases B–D are additional examples. Cosine is measured by the independent verifier.

Figure 8: E5 two-forward retrieval versus candidate budget. Gaussian and formal pure-vMF use

\varepsilon=32

; the full-corpus float reference is independent of

K

Retrieval	$(\varepsilon,K)$	Hit	EM	F1
Full-corpus float	$(\infty,N)$	89.2	53.2	65.36
No-DP hash	$(\infty,500)$	88.6	53.6	65.68
Gaussian	$(16,3000)$	89.0	53.6	65.71
RDP-vMF	$(16,3000)$	89.2	53.2	65.35
Pure-vMF	$(64,3000)$	89.0	53.2	65.34

Appendix

Table 14: End-to-end RAG with client-side cross-encoder reranking on 500 NQ queries. The opened top ten are reranked to the five passages supplied to Qwen.

Dataset	Mechanism	$\varepsilon$	$K=200$	$K=500$	$K=1000$	$K=2000$	$K=3000$	Float
SciDocs	No DP	$\infty$	.1884	.1881	.1877	.1872	.1870	.1870
	Randomized response	8	.0102	.0203	.0308	.0474	.0596	.1870
	Randomized response	16	.0111	.0235	.0380	.0536	.0700	.1870
	Randomized response	32	.0250	.0458	.0632	.0870	.1057	.1870
	Randomized response	64	.0566	.0766	.0992	.1262	.1407	.1870
	Gaussian	8	.1558	.1685	.1784	.1829	.1844	.1870

Appendix

Table 15: Complete E5 two-forward NDCG@10 under query-side DP. Randomized response, Gaussian, and RDP-vMF use

\delta=10^{-6}

; pure-vMF gives the formal pure metric-DP guarantee.

Dataset	Mechanism	$\varepsilon$	$K=200$	$K=500$	$K=1000$	$K=2000$	$K=3000$	Float
SciDocs	No DP	$\infty$	.2233	.2225	.2227	.2229	.2228	.2228
	Randomized response	8	.0098	.0222	.0344	.0552	.0752	.2228
	Randomized response	16	.0169	.0335	.0486	.0672	.0861	.2228
	Randomized response	32	.0266	.0473	.0671	.0953	.1111	.2228
	Randomized response	64	.0635	.0984	.1295	.1534	.1731	.2228
	Gaussian	8	.2073	.2180	.2202	.2228	.2230	.2228

Appendix

Table 16: Complete BGE two-forward NDCG@10 under query-side DP. Randomized response, Gaussian, and RDP-vMF use

\delta=10^{-6}

; Pure-vMF gives the formal pure metric-DP guarantee.

Figure 9: Two-party message sequence for one authenticated query round. The coarse frame starts Owner-side Hamming search while the User runs the pretrained forward and BFV encryption. Payload streaming begins when

C_{K}

is ready, the scoring query is sent when

ct_{q}

is ready, and either message may arrive first; active-secure OT later hides the selected positions and releases only their content keys.

Tokens	Generation	Plaintext	Protected	Overhead
1	.298	.307	.497	61.9%
32	2.024	2.033	2.223	9.3%
128	7.296	7.305	7.495	2.6%
256	14.438	14.447	14.637	1.3%

Appendix

Table 17: Qwen3-32B generation length and the

K=500

protection overhead. Times are seconds per query.

Method	SciDocs	Touché	NQ-1M
Ours	.152	.071	.796
P 2 RAG	.155	2.254	5.012
RemoteRAG	3.001	5.256	7.167
PANTHER	8.126	20.389	OOM

Appendix

Table 18: Matched online latency at 1 Gbps in seconds per query. Ours uses the smallest

K

retaining at least 99% of float NDCG@10: 292, 104, and 1956, respectively. P 2 RAG includes both client–server and inter-server transfer.

Privacy-Preserving RAG

See all 13 papers

Quantization Enables Private Dense Retrieval against Malicious Service Providers
Sep 28, 2026Louis Tremblay Thibault, Sofiane Azogagh, Marc-Olivier Killijian +1RAG Security Dense Retrieval
École de technologie supérieure and Mila · Eurecom · Université du Québec à Montréal
Spruce: Scalable Private Outsourced Retrieval Using Compact Embeddings
Sep 3, 2026Peichun Hua, Yunming XiaoSecure Multi-Party Computation Embedding Compression
The Chinese University of Hong Kong, Shenzhen · State Key Laboratory of Internet Architecture, Tsinghua University
PILLAR: Private Inverted-Index Lexical Lookup for Augmented Retrieval
Sep 28, 2026Truong Son Nguyen, Daniel Blackley, Ni Trieu +1Retrieval-Augmented Generation Privacy-Preserving RAG
Arizona State University · Department of Computer Science Arizona State University Tempe, AZ 85281, USA · George Mason University +1

Sep 28, 2026J/K move · Enter open · S save

Quantization Enables Private Dense Retrieval against Malicious Service Providers

Louis Tremblay Thibault, Sofiane Azogagh, Marc-Olivier Killijian, Ulrich Aïvodji

École de technologie supérieure and Mila · Eurecom · Université du Québec à Montréal

RAG Security Dense Retrieval

Open paper AskPDF arXiv

Dense retrieval, the key component of Retrieval Augmented Generation (RAG), retrieves the most relevant documents by comparing dense vector representations of queries and passages from a large corpus. In privacy-sensitive applications, the server observes the query and controls which evidence is returned, creating both confidentiality and integrity risks. We formulate private dense retrieval as providing query privacy and retrieval integrity against a malicious server, and develop a two-round cryptographic protocol that provides both guarantees. Our protocol reduces private and verifiable retrieval to multiplication of a committed matrix by an encrypted vector and uses low-bit quantization to make this computation practical. We evaluate the resulting trade-off between cryptographic cost, retrieval quality, and downstream RAG accuracy across six embedding models, four language models, and corpora of up to 2.68 million passages. Our results show that, with a clipped quantizer, three-bit quantization largely preserves retrieval quality and downstream accuracy, while a private query over a corpus the size of a clinical reference requires one to three minutes of server time. These results suggest that private dense retrieval is already practical for moderately sized, privacy-sensitive corpora when minute-scale latency is acceptable.

Abstract

Privacy-Preserving RAG

Explore similar work

Quantization Enables Private Dense Retrieval against Malicious Service Providers

Spruce: Scalable Private Outsourced Retrieval Using Compact Embeddings

PILLAR: Private Inverted-Index Lexical Lookup for Augmented Retrieval