P$^2$RAG: Efficient Privacy-Preserving RAG Service Supporting Arbitrary Top-$k$ Retrieval

Cong Wang; Jie Xu; Jijia Yang; Mingyue Wang; Xiaohua Jia; Yulong Ming; Zihan Wu

REVIEW 2 major objections 5 minor 1 cited by

P²RAG finds the top-k documents for private RAG by interactive bisection instead of secure sorting, and is 3–300× faster than prior work for large k.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-14 20:57 UTC pith:LQIP6QM6

load-bearing objection Clean systems paper: interactive bisection replaces secure sort for arbitrary top-k under two-party secret sharing, with real measured speed-ups and shipped code. the 2 major comments →

arxiv 2603.14778 v2 pith:LQIP6QM6 submitted 2026-03-16 cs.CR cs.AI

P²RAG: Efficient Privacy-Preserving RAG Service Supporting Arbitrary Top-k Retrieval

Yulong Ming , Mingyue Wang , Jijia Yang , Jie Xu , Zihan Wu , Cong Wang , Xiaohua Jia This is my paper

classification cs.CR cs.AI

keywords privacy-preserving RAGsecure top-k retrievalsecret sharingfunction secret sharingdistributed comparison functionsinteractive bisectiontwo-server model

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Outsourcing retrieval-augmented generation (RAG) to a cloud service exposes both a data owner's proprietary database and a user's prompt. Prior privacy-preserving systems treat the problem as secure top-k retrieval and rely on expensive secure sorting; they either cannot change k freely or become impractically slow once k reaches the hundreds that finance, law, healthcare and long-context models actually need. P²RAG replaces sorting with an interactive bisection protocol run between the user and two non-colluding servers that hold secret shares of the database and the prompt. The user repeatedly proposes a distance threshold; the servers return only the secret-shared count of documents closer than that threshold; after a fixed number of rounds the user obtains a 0/1 mask of the top-k set without ever learning the full ranked list or the embeddings. Restrictions on iteration count and result size, together with a final verification step, keep the leakage a malicious user can extract from the database small and measurable. End-to-end measurements show the approach is already several times faster at modest k and hundreds of times faster at k=1024, while remaining accurate enough for real retrieval tasks.

Core claim

By determining a distance threshold via interactive bisection rather than sorting all candidate distances under cryptography, one can obtain an exact top-k set for RAG under two-server secret sharing, support any k the user chooses, and reduce the number of secure comparisons enough to make large-k private retrieval practical.

What carries the argument

Interactive distance bisection with Distributed Comparison Functions (DCFs): the user and two servers jointly compare every secret-shared document distance against a secret-shared threshold, return only the count of documents below it, and iterate until the count matches the desired k (or a server-enforced budget).

Load-bearing premise

The two servers that hold the secret shares must remain semi-honest and never collude; if either is malicious or they collude, both database and prompt privacy collapse.

What would settle it

Re-run the end-to-end timing experiments of Section 6.2 (N=2^14 or 2^17, k from 16 to 1024) under the same multi-threaded secret-sharing stack; if the measured speed-up versus the sorting-based baseline falls well below the claimed 3–300 imes range, or if the bisection fails to recover the true top-k set on the BEIR embeddings, the central performance claim is false.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

Private RAG can now be deployed with the large retrieval sets (k~100–100+) that domain applications and long-context models already prefer.
Server cost grows more slowly with k than sorting-based secure k-ANN protocols, so larger knowledge bases become economically feasible under the same security model.
Users can trade a few extra bisection rounds for higher recall without redesigning the cryptographic protocol.
Database leakage per query is bounded by O(log² N) bits plus the unavoidable top-k results themselves, enabling explicit per-user leakage budgets.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same threshold-bisection idea could be applied to other secure selection problems (e.g., private top-k recommendation or private quantile queries) where only the set, not the full order, is required.
Once long-context models routinely accept thousands of retrieved tokens, the relative advantage of bisection over sorting should continue to grow.
A practical deployment would still need a metadata-private front-end if query timing or frequency itself is sensitive; the paper leaves that layer outside its threat model.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

Clean systems paper: interactive bisection replaces secure sort for arbitrary top-k under two-party secret sharing, with real measured speed-ups and shipped code.

read the letter

The useful takeaway is simple: they stop sorting secret-shared distances and instead run a fixed-iteration interactive bisection that only returns a count (via DCFs). That is enough to pick a threshold for the top-k set, and it is why the system stays fast as k grows to 1024 while PRAG does not.

What is new is the protocol shape, not a new primitive. Distance calculation is ordinary Beaver triples; comparison is standard FSS/DCF. The design choice is to keep the documents unsorted, let the user drive the threshold, fix the iteration count to S = ceil(log2(N/k)) so timing does not leak the prompt, and then verify the final 0/1 mask before text retrieval. They also give an explicit physical-leakage bound of O(log^2 N) bits of counts and compare it numerically to the unavoidable baseline of returning the documents themselves. That comparison is honest and useful.

The paper does the systems work carefully. Algorithms are fully specified, code is public, accuracy on BEIR embeddings is recall = 1 after fixed-point conversion, and the end-to-end numbers (3–300× vs PRAG, communication volumes, SimplePIR text-retrieval cost) are measured under the same multi-threading regime they claim. Appendix F shows the iteration bound is enough on real BEIR sets. The security model is the usual semi-honest non-colluding pair plus trusted dealer; they do not pretend otherwise, and they add concrete restrictions (step_max, k' = k + ξ, mask verification) against a malicious user.

Soft spots are real but proportional. The model collapses if the servers collude or the dealer is dishonest—standard for this literature, not a hidden gap. Multi-query leakage accumulates additively and they only sketch a budget; that is fine for a systems paper but would need more if someone deploys it. Fixed-point precision and the public-norm assumption are minor and checked. Nothing load-bearing is broken under their own threat model.

This is for people building or reviewing privacy-preserving RAG / secure ANN under secret sharing. It deserves a serious referee. I would engage with it and cite the protocol when the large-k case matters.

Referee Report

2 major / 5 minor

Summary. The paper proposes P²RAG, a privacy-preserving RAG-as-a-service system that supports arbitrary top-k retrieval while protecting both the data owner's database and the user's prompt. It secret-shares embeddings and texts across two semi-honest non-colluding servers, computes secret-shared cosine (dot-product) distances, and replaces secure sorting with an interactive bisection protocol: the user and servers iteratively refine a distance threshold via Distributed Comparison Functions, returning only a secret-shared count c of documents below the threshold (and finally a 0/1 indicator vector). Server-enforced limits on iterations (S = ⌈log₂(N/k)⌉) and result cardinality, plus verification that retrieved indices match the indicator, bound leakage against malicious users. Offline Beaver triples and DCF keys are supplied by a trusted dealer. Experiments on BEIR embeddings and synthetic data report perfect recall of integer distances, relevance scores >1 for k′ ≤ 300, and 3–300× server-time speedups versus PRAG for k = 16–1024, with communication volumes and real-network timings also measured.

Significance. If the claims hold under the stated two-server semi-honest model, the work is a clear practical advance for privacy-preserving RAG. Large-k regimes (k ≈ 100–150 or higher) are required by finance/law/healthcare deployments and by long-context models; existing secure-sorting approaches degrade sharply, while P²RAG's cost improves or stays favorable with larger k. The explicit physical-leakage bound of O(log² N) bits per query (versus the unavoidable baseline of the returned documents themselves), the open-source Apache-2.0 implementation, the multi-threaded DCF evaluation, the SimplePIR text-retrieval micro-benchmark, and the non-secure parallel-sort baseline together make the contribution concrete and reproducible. The design is a useful addition to the cryptographic RAG literature that already contains PRAG and related FSS/HE/TEE systems.

major comments (2)

Section 4.2 and Appendix F: the fixed iteration count S = ⌈log₂(N/k)⌉ is shown empirically sufficient on five BEIR sets (max iterations ≤ S), yet the text acknowledges that exact top-k is not always obtained after S steps. The practical allowance k′ = k + ξ and the option to continue bisection on a subsequent query are reasonable, but a short worst-case or high-probability bound on the excess |c − k| (or on the number of extra iterations needed) would make the “supports arbitrary top-k” claim fully rigorous rather than largely empirical.
Section 6.2 / Table 1: P²RAG is multi-threaded (96 threads) while PRAG is evaluated by amortizing a batch of 96 sequential instances. The resulting speed-ups are large and directionally convincing, yet a single-query latency comparison (or an explicit statement that the numbers are throughput-oriented) would remove any residual doubt that the 3–300× figures partly reflect implementation parallelism rather than the bisection algorithm alone.

minor comments (5)

Figure 1 and the surrounding text contain several garbled or placeholder tokens (e.g., “��”); these should be cleaned for camera-ready readability.
Algorithm 1’s bit-representation extension for signed integers is stated but not formally proved correct; a one-sentence invariant would help.
Table 2’s communication volumes are useful; adding the corresponding byte counts for the offline phase (or noting that they are amortized) would complete the cost picture.
The claim that ℓ₂-norms are public “because they do not leak any information” (Section 4.1) is true for a single query under the paper’s model, but a brief remark on multi-query norm leakage would be prudent.
Appendix D’s discussion of membership-inference and distance-inversion attacks correctly notes that they rely only on baseline leakage; cross-referencing the concrete numerical comparison already given in the main text would tighten the argument.

Circularity Check

0 steps flagged

No significant circularity: design, leakage bounds, and speedups are self-contained and externally benchmarked.

full rationale

P²RAG is a systems/crypto paper whose central claims (arbitrary top-k via interactive distance bisection under two-party secret sharing, O(log² N) physical leakage bound, and measured 3–300× speedups vs PRAG) do not reduce to fitted parameters, self-definitional identities, or load-bearing self-citations. The bisection threshold search is an algorithmic design choice that correctly identifies an unsorted top-k set by construction of binary search on the secret-shared distances; S = ⌈log₂(N/k)⌉ follows from the information-theoretic depth of that search and is only empirically validated (Appendix F), not fitted to produce the claimed speedups. Leakage analysis compares the explicit O(S log(N+1)) bits of returned counts against the unavoidable baseline of returning k documents, using concrete parameters rather than a uniqueness theorem or ansatz imported from the authors. Performance numbers are obtained by direct wall-clock comparison against an external baseline (PRAG) and a non-secure sort, with no intermediate parameters that are later re-labeled as predictions. No circular steps of any of the six enumerated kinds appear.

Axiom & Free-Parameter Ledger

3 free parameters · 4 axioms · 1 invented entities

The central efficiency and privacy claims rest on standard cryptographic assumptions (secret sharing, DCF security, non-collusion) plus a small number of engineering parameters chosen for the experiments; no free parameters are fitted to produce the claimed speed-ups.

free parameters (3)

iteration bound S = ⌈log₂(N/k)⌉ and server-side step_max
Chosen by the authors to limit leakage; empirically verified on five BEIR sets but not proved sufficient for every possible embedding distribution.
extra-result allowance ξ (k′ = k + ξ)
Engineering slack that lets the protocol terminate early; affects both accuracy and communication.
fixed-point precision f = 32 and field prime p = 2⁶⁴−59
Implementation choices that keep truncation error negligible but are not forced by theory.

axioms (4)

domain assumption Two servers are semi-honest and non-colluding; a trusted dealer correctly distributes offline randomness.
Stated in Section 2.1; standard for two-party secret-sharing systems but load-bearing for all privacy claims.
standard math Distributed Comparison Functions (DCFs) and Beaver triples are secure under the usual cryptographic assumptions.
Invoked for every comparison and multiplication (Algorithms 1 and 3).
domain assumption Embeddings are ℓ₂-normalized and cosine/dot-product ranking is the correct relevance metric.
Assumed throughout Section 4.1; matches common RAG practice but is not proved optimal.
domain assumption The user obtains the prompt embedding offline with a public embedding model.
Stated in Section 2.1; inherited from prior privacy-preserving RAG papers.

invented entities (1)

Interactive distance-bisection protocol returning only a secret-shared count no independent evidence
purpose: Replace full secure sort with a logarithmic number of threshold comparisons so that arbitrary large k remains efficient.
Core algorithmic contribution of the paper; security and complexity are argued from standard DCF properties rather than from a new physical entity.

pith-pipeline@v1.1.0-grok45 · 15519 in / 2357 out tokens · 40252 ms · 2026-07-14T20:57:55.075115+00:00 · methodology

0 comments

read the original abstract

Retrieval-Augmented Generation (RAG) enables large language models to use external knowledge, but outsourcing the RAG service raises privacy concerns for both data owners and users. Privacy-preserving RAG systems address these concerns by performing secure top-$k$ retrieval, which is typically implemented using secure sorting to identify relevant documents. However, existing systems face challenges supporting arbitrary $k$ due to their inability to change $k$, new security issues, and in particular, efficiency degradation with large $k$. This is a significant limitation because applications such as finance, law, and healthcare require a $k$ that is large enough to cause huge overhead for existing systems. Also, modern long-context models generally achieve higher accuracy with larger retrieval sets. We propose P$^2$RAG, an efficient privacy-preserving RAG service that supports arbitrary top-$k$ retrieval. Unlike existing systems, P$^2$RAG avoids sorting candidate documents. Instead, it uses an interactive bisection method to determine the set of top-$k$ documents. For security, P$^2$RAG uses secret sharing on two semi-honest non-colluding servers to protect the data owner's database and the user's prompt. It enforces restrictions and verification to defend against malicious users and tightly bounds the information leakage of the database. The experiments show that P$^2$RAG is 3--300$\times$ faster than the state-of-the-art PRAG for $k = 16$--$1024$.

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

GoldenRetriever: Non-Interactive Homomorphic Encrypted Retrieval for Privacy-Preserving RAG
cs.CR 2026-07 reject novelty 4.0

GoldenRetriever performs non-interactive encrypted document retrieval for RAG by thresholding cosine similarity under CKKS homomorphic encryption, with a degree-7 mask-polarization polynomial for token recovery.