- 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
-
The problem formulation is clear and well motivated.
-
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.
-
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
-
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.
-
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.
-
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.
-
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
- 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.?
- 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?
- 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?
- 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?
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.