🤖 AI

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

The paper proposes P $^2$ RAG, an efficient privacy-preserving Retrieval-Augmented Generation service that utilizes an interactive bisection method and secret sharing to support arbitrary top- $k$ retrieval without secure sorting, achieving significant speedups over existing systems while protecting data and user prompts.

Original authors: Yulong Ming, Mingyue Wang, Jijia Yang, Jie Xu, Zihan Wu, Cong Wang, Xiaohua Jia

Published 2026-05-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yulong Ming, Mingyue Wang, Jijia Yang, Jie Xu, Zihan Wu, Cong Wang, Xiaohua Jia

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive, secret library of documents (like medical records, legal contracts, or financial reports) that you want to use to answer questions. You don't want to give the whole library to a search engine company because it's too sensitive. At the same time, you don't want the search engine to know exactly what you are asking, because that reveals your private thoughts or business strategies.

This is the problem P2RAG solves. It's a new way to run a "Retrieval-Augmented Generation" (RAG) service—a fancy term for "an AI that answers questions using your private documents"—without anyone peeking at the secrets.

Here is how it works, broken down into simple concepts:

1. The Old Way: Sorting the Whole Deck

Imagine you have a deck of 1,000 cards, each with a score. You want to find the top 10 highest-scoring cards.

The Problem: In previous secure systems, to find the top 10, the computer had to secretly compare every single card against every other card to sort them from highest to lowest. It's like trying to find the tallest person in a crowd by lining everyone up and measuring them one by one, but doing it in a way where no one can see the measurements.
The Bottleneck: If you want the top 100 cards instead of 10, this "sorting" process gets incredibly slow and expensive. It's like trying to sort a library of books just to find the 5 best ones; the more books you have, the longer it takes.

2. The P2RAG Solution: The "Guess the Threshold" Game

P2RAG changes the game. Instead of sorting the whole deck, it plays a game of "Hot and Cold" (specifically, a binary search or "bisection") to find a cutoff line.

The Setup: Imagine two servers (let's call them Server A and Server B) hold the secret library. They split every document in half so that neither server knows the full story. You (the user) also split your question in half and send a piece to each server.
The Game:
1. You ask the servers: "How many documents are similar enough to my question if we set the bar at this specific level?"
2. The servers count the matches without telling you which documents they are, and without you seeing the scores. They just say, "There are 50 matches."
3. You think: "I only wanted 10. That's too many. Let's raise the bar."
4. You ask again with a higher bar. They say, "Now there are 5 matches."
5. You think: "Too few. Let's lower the bar a little."
6. You keep adjusting the bar back and forth until the count is exactly what you need (e.g., 10 documents).

The Magic: Because you are just adjusting a "bar" and counting, you don't need to sort the entire library. You just need to find the right height for the bar. This makes the process incredibly fast, even if you want a huge number of results (like 1,000 documents).

3. Keeping Secrets Safe (The "No-Trust" Rule)

The paper claims this system is safe even if the servers are "honest but curious" (they follow the rules but try to snoop) or if the user is "malicious" (trying to trick the system).

Against Curious Servers: Because the data is split (secret-shared), Server A only sees a random jumble of numbers, and Server B sees a different random jumble. Neither can reconstruct the document or your question unless they team up. The paper assumes they won't team up (like two different companies in different countries).
Against Sneaky Users: A tricky user might try to ask the servers to lower the bar so low that all documents match, effectively stealing the whole library. P2RAG puts a "speed limit" on how many times you can ask and checks the math to ensure you only get the documents you are allowed to see. It tightly limits how much information a bad user can steal.

4. Why This Matters (The Results)

The authors tested this system and found:

Speed: It is 3 to 300 times faster than the current best secure systems when you want to retrieve a large number of documents (from 16 up to 1,024).
Flexibility: You can ask for any number of results (arbitrary k), which is crucial for fields like finance or law where you might need to see a lot of context to get the right answer.
Accuracy: The system is so precise that it finds the exact same documents as a non-secure system would, with almost no mathematical errors.

The Bottom Line

P2RAG is like a secure, high-speed librarian who can find your specific documents in a massive, locked vault without ever opening the vault to show you the books, and without you ever seeing the other books in the vault. It does this by playing a smart guessing game to find the "cutoff point" rather than sorting the entire collection, making it fast enough to be useful in the real world.

Technical Summary of P2RAG: Efficient Privacy-Preserving RAG Service Supporting Arbitrary Top-k Retrieval

Problem Statement
Retrieval-Augmented Generation (RAG) allows Large Language Models (LLMs) to utilize external knowledge, but outsourcing RAG services introduces significant privacy risks for both data owners (whose proprietary databases are exposed) and users (whose prompts are visible). Existing privacy-preserving RAG (PP-RAG) systems typically frame the problem as a secure top-k retrieval task, relying on secure sorting or secure k-Approximate Nearest Neighbor (k-ANN) techniques. However, these systems face critical limitations:

Inflexibility: They often cannot support arbitrary or dynamic adjustments to the retrieval parameter $k$ .
Efficiency Degradation: Their performance degrades significantly as $k$ increases. This is a major bottleneck because modern applications in finance, law, and healthcare, as well as long-context LLMs, often require large $k$ values (e.g., 100–150 or higher) to achieve optimal accuracy.
Security Gaps: Some existing approaches raise new security issues or fail to tightly bound information leakage against malicious users.

Methodology
The authors propose P2RAG, a privacy-preserving RAG service designed to support arbitrary top-k retrieval efficiently. The system operates on a two-server model where the servers are semi-honest (honest-but-curious) and non-colluding.

System Architecture:
- Data Owner: Outsources an encrypted database to two servers. The database consists of $N$ document embeddings, which are secret-shared between the two servers using Shamir's secret sharing over a prime field.
- User: Submits a prompt embedding, also secret-shared between the two servers.
- Threat Model: The servers follow the protocol but may attempt to infer data. Users are modeled as malicious and may deviate from the protocol to extract information. Data owners are assumed honest.
Core Innovation: Interactive Bisection vs. Sorting
Unlike existing systems that sort all candidate documents (a computationally expensive operation in secure protocols), P2RAG avoids sorting entirely. Instead, it employs an interactive bisection method to determine a distance threshold ( $d_k$ ) that defines the top- $k$ set.
1. Distance Calculation: The servers compute secret-shared cosine distances (approximated via dot products) between the user's prompt and all document embeddings using Beaver triples.
2. Bisection Iteration: The user and servers interact to narrow down a distance threshold. In each iteration, the user specifies a threshold $d_k$ . The servers use Distributed Comparison Functions (DCFs) to count how many documents have distances less than $d_k$ .
3. Threshold Selection: The user updates $d_k$ based on the returned count until the number of documents within the threshold is close to the target $k$ .
4. Result Retrieval: Once the threshold is determined, the servers generate a secret-shared binary vector indicating which documents fall within the threshold. The user retrieves the indices of these documents using Single-Server Private Information Retrieval (PIR).
Security Mechanisms:
- Privacy: Secret sharing ensures neither server learns the database or the prompt.
- Defense Against Malicious Users: To prevent users from extracting excessive information, P2RAG enforces strict restrictions:
  - The number of bisection iterations is capped (limiting the total count leakage to $O(\log^2 N)$ ).
  - The final result set size is bounded.
  - Verification mechanisms ensure the user only retrieves indices corresponding to the agreed-upon binary vector, preventing manipulation of the retrieval process.

Key Contributions

Arbitrary Top-k Support: P2RAG is the first system to efficiently support arbitrary $k$ values without the efficiency degradation seen in sorting-based approaches, making it suitable for large $k$ scenarios required by modern long-context models.
Efficient Protocol Design: By replacing secure sorting with an interactive bisection method using DCFs, P2RAG significantly reduces the number of comparisons, which are the primary bottleneck in secure protocols.
Robust Security: The system protects both the data owner's database and the user's prompt against semi-honest servers. It also introduces specific restrictions and verification steps to tightly bound information leakage against malicious users.
Implementation and Evaluation: The authors implemented P2RAG and released the code under the Apache License 2.0.

Experimental Results
The authors evaluated P2RAG using BEIR datasets (e.g., trec-covid with ~171k documents) and synthetic datasets.

Accuracy: P2RAG achieves high computational accuracy. Recall remains at 1.0 for $k'$ ranging from 16 to 1024, and relevance scores indicate that retrieved documents are generally relevant to the prompt.
Performance: P2RAG demonstrates significant speedups over the state-of-the-art system, PRAG.
- For $k = 16$ , P2RAG is 3.78× faster.
- For larger $k$ (e.g., $k=1024$ ), the speedup increases to 322×.
- The system scales linearly with the number of documents ( $N$ ) but becomes relatively faster as $k$ increases, unlike PRAG which suffers from efficiency degradation.
Communication: While intra-server communication can reach hundreds of megabytes, this is manageable via high-bandwidth data center links. User-server communication remains low (comparable to a few standard images).

Significance and Claims
The paper claims that P2RAG addresses a critical gap in privacy-preserving RAG: the inability to efficiently handle large $k$ values. The authors emphasize that while standard non-secure RAG is simpler and faster, P2RAG is essential for high-stakes domains like healthcare, finance, and legal services where data privacy is a strict requirement. The system enables these sectors to leverage large retrieval sets (which improve LLM accuracy) without compromising the confidentiality of proprietary databases or user queries. The authors modestly note that the system relies on the semi-honest non-colluding server assumption and that standard non-secure RAG remains the choice when privacy is not critical.

1. The Old Way: Sorting the Whole Deck

2. The P2RAG Solution: The "Guess the Threshold" Game

3. Keeping Secrets Safe (The "No-Trust" Rule)

4. Why This Matters (The Results)

The Bottom Line

More like this