acceptodds
Under review as a conference paper at ICLR 2027

Quantization Enables Private Dense Retrieval Against Malicious Service Providers

Abstract

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.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Privacy-preserving protocols, dense retrieval, RAG, quantization

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_ucJbOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies private dense retrieval for RAG when the retrieval server is actively malicious, and requires both query privacy and integrity of the returned scores and documents. The authors build a two-round protocol from an existing verifiable primitive that multiplies a committed plaintext matrix by an encrypted vector. The first round returns encrypted similarity scores for the whole corpus, from which the client selects the best document locally, and the second round fetches that document with an encrypted one-hot query. Because homomorphic encryption operates over integers, embeddings are quantized, and the paper analyzes how the bit-width determines the noise budget and therefore the cryptographic parameters.

Critical strengths
  1. The problem formulation is clear and well motivated.

  2. The coupling between quantization bit-width and cryptographic parameters is derived carefully and transparently, which makes the reported cost–quality trade-off reproducible and easy to reason about.

  3. The empirical study is thorough and statistically sound, covering several encoders, corpus sizes and LLM readers with paired significance and equivalence tests, and the concrete costs and limitations are reported honestly.

Critical weaknesses
  1. Novelty is limited. The protocol composes known building blocks. Scoring with a homomorphic matrix–vector product and then fetching the document via PIR is the structure of Coeus [1], the second round is standard linear PIR with a one-hot query, and malicious security is inherited entirely from the primitive of Tremblay Thibault et al., which the paper uses as a black box. Integrity against a malicious single PIR server, given an out-of-band digest, has also been studied in Authenticated PIR [2]. Neither [1] nor [2] is cited or included in Table 1, so the claim that existing systems provide only one of the two guarantees needs qualification. On the ML side, percentile clipping and low-bit embeddings are standard, and what is new is mainly the bit-width-to-noise-budget accounting and the empirical location of the operating point. For ICLR, this is a thin contribution.

  2. The security guarantees do not match the paper's own motivation. The setting is justified by the corpus being proprietary and licensed per seat. Yet the client receives the score of every document, and the server cannot check the encrypted query. A client can therefore recover the full embedding matrix with roughly as many unit-vector queries as the embedding dimension, and the paper itself cites work showing that such embeddings can be inverted to text. Integrity also holds only relative to the committed index. Nothing binds the committed embeddings to the committed documents, so a malicious server can manipulate rankings simply by committing crafted embeddings. Unless an external party audits the index, this weakens the claims about preventing evidence manipulation and indirect prompt injection.

  3. Practicality is narrow and partly extrapolated. Server and client cost both grow linearly with corpus size. At a million chunks, a query takes several minutes of server time, about a minute of single-core client time and about 16 MB of communication in each direction, and the authors acknowledge that literature-scale corpora are infeasible. The claim that a clinical reference can be served in one to three minutes is extrapolated from topic counts, not measured on such a corpus. The largest downstream experiments also exceed the corpus sizes for which the protocol was run or parameterized, so they evaluate quantized retrieval in plaintext rather than the protocol itself.

  4. There is no measured comparison with prior systems. Tiptoe, Compass, PIR-RAG and PPMI appear only in a qualitative table, so the benefit of exact linear-scan retrieval over clustered or approximate private search is never quantified, in either quality or cost. Practical alternatives such as trusted execution environments are not discussed either. Finally, a five-point equivalence margin for downstream accuracy is fairly loose given the sample sizes.

References

[1] Ishtiyaque Ahmad, Laboni Sarker, Divyakant Agrawal, Amr El Abbadi, and Trinabh Gupta. Coeus: A System for Oblivious Document Ranking and Retrieval. In SOSP, 2021.

[2] Simone Colombo, Kirill Nikitin, Henry Corrigan-Gibbs, David J. Wu, and Bryan Ford. Authenticated Private Information Retrieval. In USENIX Security, 2023.

Questions for authors
  1. How does the protocol differ from Coeus [1] and Authenticated PIR [2], and what does it add beyond combining their ideas with the verifiable primitive of Tremblay Thibault et al.?
  2. Since the setting relies on the corpus not being shared, how do you prevent a client from reconstructing the licensed embedding matrix (and, through embedding inversion, the corpus) with unit-vector queries?
  3. How is consistency between the committed embeddings and the committed documents enforced or audited, so that a malicious server cannot steer rankings by committing crafted embeddings?
  4. Can you report measured quality and cost against at least one prior private retrieval system (e.g., Tiptoe or Compass) to quantify the benefit of exact retrieval?
1 comment
AuthorsOpenReview ↗

Response to Reviewer ucJb

We thank the reviewer for their careful review and shedding light on the fact that our work is thorough and statistically sound and provides high coverage.

Before answering the reviewer’s questions, we would like to address the Reviewer’s concerns. W1. We would like to point the Reviewer to the reply to Reviewer mB4h, which explains that our contribution is the first realization of a maliciously-secure private dense retrieval protocol and expands on novelty with respect to the field of Representation Learning. Q1 discusses references [1, 2].

W3. We would like to clarify that the 1-3 minute headline is correct and measured. Since the time taken to serve a request depends only on the size of the corpus and not its contents, we do not need the actual corpus to measure the practicality of our protocol with respect to it. Topic counts are sufficient and provided by the literature (Wolters Kluwer, 2026b). The measurements are included in the new Table 7. By Theorem 2, the protocol returns exactly the plaintext integer scores, so the plaintext quality measurements are the correct ones.

W4. We answer the four points in order. The measured comparison with prior systems is the new Table 2 (see Q4). It also quantifies the benefit of exact retrieval. TEEs provide confidentiality and integrity under a different trust assumption, namely trust in the hardware vendor and in its attestation, and enclaves have repeatedly been subject to side-channel attacks. Our guarantees rest on cryptographic assumptions only. As such, we consider TEEs complementary to our approach and out of the scope of this work. Regarding the equivalence margin, the paper already reports a tighter 3 points margin, as 21 of 32 combinations are equivalent to floating point at b=4 and 17 of 32 at b=3 (Appendix E). Our samples of 188 to 300 queries cannot resolve a smaller margin, since the 95% intervals are themselves 2 to 3 points wide on each side. Independently of any margin, no combination drops significantly at b=4 and only two do at b=3 (Table 8).

Q1. We thank the reviewer for pointing out those prior works, which we now cite and discuss in our main text. Coeus is a ranking system that does not make use of embeddings, relying on basic TF-IDF instead. It performs worse than exact embedding-based approaches (Henzinger et al., 2023). Authenticated PIR is a PIR system that does not provide search or ranking functionalities. Further, it requires an honestly generated digest for malicious security, i.e. a dishonest digest breaks security against a malicious server. In contrast, we propose a dense retrieval protocol, combining both embedding-based search/ranking and retrieval, that is made private and verifiable (i.e., private even against a malicious adversary).

Q2/W2. As discussed in the answer to Reviewer mB4h (Security-1), the goal of our protocol is not to prevent the client from reconstructing the database. To this day, UpToDate has no way of preventing a client from reconstructing the database, yet their business model holds. Our protocol aims at hiding client queries, which we argue may hold very sensitive information (e.g., clinical patient information).

Q3. We currently propose no method for auditing the correctness of embeddings, however this is straightforward via a trusted third party. Proving, without the help of a trusted third party, the correctness of the embedding calculation is an interesting future direction. We would like to highlight to the reviewer that the commitment being binding means that the server can only steer rankings once, and is stuck with such steered ranking for the lifetime of the commitment. It is likely not in its advantage to commit to an inexact database without having the possibility to mount adaptive attacks subsequently.

Q4. We add a performance study in the Related Works section, which includes Table 2 indicating the accuracy, latency and communication complexity of Tiptoe, PPMI and our work.

Reviewer_VAEqOpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper provides a 2 round protocol to perform dense retrieval while keeping the user query private. In the setup phase, the server commits to the embeddings of the documents (A) and the document matrix (D). In round 1, the user sends encrypted query, which the server homomorphically multiplies to the embedding matrix and provides this result (A.x) along with a proof of execution to the client. The client verifies and then decrypts (A.x) and picks the top relevant document. In round 2, the user sends an encrypted one hot vector of the relevant document index which the server multiples with D and returns with another proof.

Embeddings need to be rounded to b bits and the paper shows that at b=3, the downstream RAG utility is mostly preserved with reasonable encryption efficiency.

Critical strengths
  1. Clear 2 round cryptographic protocol, using a mixture of existing frameworks that addresses both privacy and integrity under malicious security.
  2. Thorough analysis linking bit-width, cryptographic cost and downstream utility.
Critical weaknesses

No major weaknesses. The method is currently limited to moderately sized corpus, as the authors acknowledge.

Questions for authors

No questions, the scope of the paper and threat model are well defined.

2 comments
AuthorsOpenReview ↗

Response to Reviewer VAEq

We thank the reviewer for their positive assessment, and for noting that the scope and the threat model of our work are well defined.

For the reviewer's convenience, we summarize the changes of the revision, which are highlighted in blue:

  1. Table 2 adds a measured comparison with prior private retrieval systems in retrieval quality, latency and communication. The new table 7 gives in-depth performance measures of our prototype;
  2. Table 4 now reports the communication of a query in place of its dollar cost;
  3. Table 5 now evaluates SciFact on chunks, the retrieval unit of the protocol, and Appendix E repeats the evaluation for all four readers. On this endpoint, b=3 holds for the quantization-aware encoder with all four readers. With the conventional encoder, one reader out of four needs b=4;
  4. The related work section now discusses Coeus and Authenticated PIR.

Two concerns are shared by the other reviewers, and we state our position on them here. First, our threat model is that of PIR: the protocol hides the query of the client and does not aim to hide the database from the client, as stated in Section 2. Second, to the best of our knowledge, ours is the first dense retrieval protocol over a server-held corpus that is secure against a malicious server, and the first measurement of how the quantization bit-width sets its cost.

We are happy to give further clarifications if necessary.

Thank you authors for the response and the updates to the paper and comparison to previous work.

Reviewer_mB4hOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper considers a retrieval setting where the server holds (and owns) a database and the client wants to query it without the server learning the query. The proposed scheme builds mostly on previous work on practical SNARGs for plaintext-matrix - ciphertext-vector multiplication. The paper evaluates the scheme on several datasets to demonstrate its cost and accuracy. The main finding is that, for the embedding models evaluated, low-bit quantization of the embeddings preserves retrieval quality while allowing smaller cryptographic parameters and thus lower cost.

Critical strengths

The paper leverages a very recent work on verifiable matrix-vector multiplication to address the problem of private and verifiable semantic search.

Critical weaknesses

Security

  1. There's a clear mismatch between the setting and the security definition. In the motivating example, the paper mention it considers a proprietary database and the provider can only provide query-time access. However, later in the security definition 1, the paper claims it follows the standard PIR setting and does not require database privacy. In fact, according to the proposed protocol, round 1 results include the exact inner products between the query and every single document in the database. And therefore the client can easily recover the entire database with n queries, where n is the dimension of the embeddings.

  2. Beside this mismatch, it's not clear the motivation of integrity under the indirect prompt injection example. During the preprocessing the server commit to the corpus. However, nothing prevents the server from committing an injected database. In this case, even with the proof in each round of the query, the client could still receive an altered version of the database. The paper briefly mentions the database is audited while no concrete discussion is included.

  3. The paper proposes verify-before-decrypt to block reaction attacks. However, both verification and decryption are local computations that the server cannot observe, so their order does not matter in itself.

Novelty

The technical contribution of this paper is limited. The main component of the protocol: verifiable matrix vector multiplication is directly from a prior work. The proposed 2 round protocol (search and retrieval) is a standard practice in the field and quantization for efficient semantic search has been proposed and explored in many previous work in both plaintext (diskann) and encrypted setting (tiptoe, compass).

Evaluation

  1. A major issue of the evaluation is that while encrypted search is an active research area, no baseline is included in the paper for comparison. The only comparison to prior work is done conceptually in Table 1 and there's no concrete comparison during evaluation.
  2. The paper claims batching queries barely increase the latencies. This is not true as the communication cost grows linearly with the batch size and given a fixed network bandwidth eventually the network will become the bottleneck and the the latency will grow linearly with the batch size. The result in Table 3 only measures single query while the paper mentions top-k retrieval in the realistic RAG setting.
  3. Configuration mismatch between the latency and accuracy experiments: section 4.4 measures the accuracy with whole abstract retrieved while not every abstract fit into the chunk. The results in Table 7 (left in appendix) should be more useful for downstream accuracy analaysis.
Questions for authors

See the weaknesses above.

3 comments
AuthorsOpenReview ↗

Response to Reviewer mB4h

We thank the reviewer for their careful review.

Security

  1. As stated in our manuscript, we consider the threat model protecting client confidentiality, not database privacy. Indeed, in PIR as in plain database access, a client can reconstruct the database. Private dense retrieval, just like PIR, does not aim to protect against this type of attack. We add a sentence in "Limitations" to emphasize this. Modern tools such as UpToDate and OpenEvidence are also vulnerable to such reconstruction attacks, yet their business model of monetizing access to their proprietary database per-seat remains sound.
  2. We agree that the protocol binds the service provider to some database without giving guarantees about this database or its embeddings. We clearly state in the manuscript that a database audit with respect to the commitment is necessary for security against prompt injection attacks.
  3. We would like to remind the reviewer that the verify-before-decrypt paradigm is widely discussed in the literature and known to thwart reaction attacks. The fact that the proof system is publicly verifiable and does not require a designated verifier is precisely what makes the protocol composable and maliciously secure, because the client's reaction with respect to verification is observable by the server. We have updated the manuscript to state this more clearly in the “Verification before decryption” paragraph.

Novelty. We argue that our main contribution is highlighting that representation learning techniques such as robustness under quantization directly impacts the cost of state-of-the-art privacy-preserving AI systems. To support this claim, we build, for the first time, a maliciously-secure dense retrieval protocol, and show that its performance is dictated by robustness to quantization. To the best of our knowledge, this has not been achieved before. Indeed, prior works lack the verifiability layer and have to assume a semi-honest/honest-but-curious setting where the server is trusted not to deviate from the protocol to avoid reaction attacks, wherein a malicious server manipulates encrypted results and exploits the client's reactions to infer private information. We argue that this setting is not realistic as the entire point of a privacy-preserving protocol is to protect a client from a potentially malicious server. As such, ours is the first and only work to achieve security in the stronger, realistic security model for a server-held corpus.

Evaluation

  1. We agree with the reviewer that more baselines should be included. As such, we add a performance study in the Related Works section, which includes a table indicating the accuracy, latency and communication complexity of the cited encrypted search works that have an open-source implementation.
  2. We agree that for large batches of queries, the bandwidth will become the latency bottleneck. However, for common use cases (k=1-10) and reasonable bandwidth speeds, the prover time remains the wall-clock bottleneck (see answer to reviewer Hz8U/Q1 above).
  3. We thank the reviewer for this correct observation. In the revision, we add experiments with all LLM readers in the chunked setting. Those experiments show that the operating point for RAG on all corpus sizes moves from b=3 to b>=3, putting emphasis on the role of representation learning in building efficient privacy-preserving protocols. Prose and tables throughout Section 4 are updated accordingly, and the updates are highlighted in blue. Table 5 now carries the relevant measurements.

We are happy to give further clarifications if necessary.

Thanks to the authors for their rebuttal response and for providing an updated manuscript. However, I’m still not convinced by the comparison results with the other baselines. First the comparison table only considers the cost of Round 1 rather than the cost of the end-to-end. If the authors only consider Round 1, then the baseline should be other work on verifiable matrix–vector multiplications. Second, the comparison results are based on 5000 passages, which is a fairly small scale of database. I understand that the security assumptions are different, but both baseline papers evaluate databases with over a million entries (and report a few seconds of latency), and therefore I think a more detail comparison would help to understand the performance and tradeoff of the proposed system. If the target database size is around 5,000 passages, then under the PIR assumption, I think another good baseline to include is client downloading the entire database and search locally. With this, I would like to maintain my current score.

We thank the reviewer for their response. We would like to clarify that the new Table 2 aims to give a small quantitative analysis of the cost (in latency and communication) and benefit (in accuracy) of using a private and exact search algorithm instead of a non-exact one (e.g., Tiptoe), with and without integrity. As such, Round 1 of our protocol (the ranking round) is the only relevant part of our protocol to compare against, and 5000 is sufficient to expose the difference between the approaches.

The target is not databases of 5000 elements. Million-scale experiments are discussed in the "Experimental Analysis" section, although we do not include latency and communication comparison with systems providing weaker security guarantees, as we believe those could be misleading.

Reviewer_Hz8UOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies dense retrieval when the server can try to learn a query or alter the evidence returned to the client. The client first verifies and decrypts scores against a committed embedding matrix, then privately fetches the selected documents against a second commitment. The experiments examine how embedding precision affects retrieval quality, downstream question answering, and the cost of verifying the computation.

Critical strengths
  1. The two-round design gives retrieval integrity a precise meaning. A server that changes a score or substitutes a passage must still produce a proof consistent with the committed database. Section 2 explains why the client verifies each response before decrypting it.
  2. The paired equivalence tests help identify how much precision the reader actually needs. Across two encoders and four readers, 3-bit retrieval met the ±5 percentage-point accuracy margin in 30 of 32 settings, compared with 9 of 32 at 2 bits (Table 6). This is stronger evidence for choosing a bit width than a comparison of retrieval scores alone.
Critical weaknesses
  1. The deployment claim combines costs from two different response formats. At one million chunks, Table 3 reports 5.4 minutes of server time for 3-bit retrieval, and Section 5 reports roughly 16 MB of downloads. The public cost script derives the bandwidth figure assuming packed outputs and describes the timed implementation as sending one ring element per output row. How long a client waits to receive the selected passages therefore remains open.
  2. The public artifact also differs from Table 5 on a parameter that affects the security estimate. The table uses a second-round noise standard deviation of about 3.2, whereas the estimator script uses log₂ σ = 5.3. The paper should identify the configuration behind the reported 223-bit estimate.
Questions for authors
  1. On a corpus of 200,000–500,000 chunks, how many bytes does the timed implementation actually send and receive for k=1 and k=5? At a stated bandwidth and round-trip time, what is the elapsed time until the client has verified and decrypted the requested passages?
  2. Which code revision and estimator inputs reproduce the second round of Table 5? Were those same parameters used for the cost measurements in Table 3?
3 comments
AuthorsOpenReview ↗

Response to Reviewer Hz8U

We thank the reviewer for highlighting that our work gives retrieval integrity a precise meaning, and correctly identifying that measuring downstream accuracy gives stronger evidence for choosing an operating bit. We extend our thanks to the reviewer for pointing out calculation mistakes, which are now fixed and pushed to the anonymized repositories.

W1/Q1. Using very recent results from Tremblay Thibault (2026) which strictly improves upon the communication metrics of Tremblay Thibault et al. (2026), we have updated Table 4 and accompanying text to include communication size instead of cost in dollars. Further, we have added Table 7 in Appendix D, which shows an elapsed time of 103 to 228s for 200,000-500,000 chunks, taking into account the few MiBs of communication. The code is updated and reproduces the Table 7 measures.

W2/Q2. We fixed the outdated script in the latest revision and pushed the changes to the anonymized repository. It now reproduces the round 2 row of Table 6 exactly. Those are the security parameters used in Table 4. The estimator inputs are n = 2^12, q = 2^64 − 2^32 + 1, ternary secret, Gaussian error of width 3.2, giving 223.1 bits (dual-hybrid attack).

Thank you for the clarifications and revisions. While the corrected security parameters and additional timing results address several important concerns raised in my review, the reported latency of 103-228 seconds for the specified chunks continues to raise significant doubts about the practicality of real-world deployment. Therefore, although I acknowledge the improvements made in the revision, they do not sufficiently alleviate my concerns to warrant a change in my overall assessment. I thus maintain my original score.

We thank the reviewer for their response. We would like to bring the reviewer's attention to the "Setting" paragraph in the introduction, which states that we target the deferred-response setting. Indeed, curbside consults, requests to a medical librarian, tumour-board preparation and pharmacovigilance review are all workflows in which a question is posed and a researched answer expected in minutes to hours. Against that budget, our protocol is deployable today. Privacy based on advanced cryptography is usually dismissed as too slow. That judgment assumes a web-search latency budget, but clinical use cases (where security is critical) have a relaxed budget, which is why we believe our protocol is a good fit.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Discussion summary

We thank the reviewers for their careful reviews. We have addressed every weakness and question raised, and the uploaded revision highlights all changes in blue. We summarize the discussion herein for the convenience of the Area Chair.

The changes to the manuscript are as follows:

  1. Measured comparison with prior systems (mB4h, ucJb). The new Table 2 compares our protocol against Tiptoe and PPMI in retrieval quality, latency and communication, while stating threat model discrepancies;
  2. Communication and elapsed time (Hz8U, mB4h). Table 4 now reports the communication of a query. The new Table 7 reports an elapsed time of 103 to 228 s for 200,000 to 500,000 chunks, communication included, which satisfies the targeted deferred-response setting;
  3. Security parameters (Hz8U). The estimator script is fixed and reproduces the Round 2 row of Table 6 exactly, i.e. 223.1 bits of security. These are the parameters used in Table 4;
  4. Downstream accuracy on chunks (mB4h). Table 5 now evaluates SciFact on chunks, and Appendix E repeats the experiments for all four readers.
  5. Related work (ucJb). We now cite and discuss Coeus and Authenticated PIR;
  6. Clarifications (mB4h, ucJb). "Limitations" now states that database privacy is not a goal. "Verification before decryption" states more clearly how it thwarts reaction attacks.

Two raised concerns relate to scope rather than correctness. First, our threat model is that of PIR: the protocol hides the query from the server and does not aim to hide the database from the client. Second, integrity holds with respect to the committed database, and auditing the committed embeddings currently requires a trusted third party.

Regarding latency, Reviewer Hz8U wrote that the revision addresses several important concerns of their review, and kept one reservation on the practicality of a 103 to 228 s response. We answered it in our follow-up. We target the deferred-response setting stated in the introduction. Curbside consults, requests to a medical librarian and tumour-board preparation are workflows in which an answer is expected in minutes to hours. In this setting, our protocol is deployable today.

To the best of our knowledge, ours is the first dense retrieval protocol over a server-held corpus that is secure against a malicious server, and the first measurement of how the quantization bit-width sets crytpographic costs. Our findings highlight that the field of quantization (and more generally representation learning) have tremendous leverage over the cost of privacy in AI systems.

We are happy to answer any further questions from the reviewers or the Area Chair.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.