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.
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.
Retrieval-Augmented Generation (RAG) has made dense retrieval over large document collections a standard building block. Organizations increasingly outsource vector indexes to untrusted clouds, exposing proprietary corpora and user queries. Cryptographic protection is challenging because each query searches corpus-scale state, causing computation, correlated randomness, and communication to grow with the corpus. At million-document scale, a naive secure implementation takes minutes and about 90 GB of communication per query. Even recent optimized systems require 10--22 seconds. We propose Spruce (Scalable Private Outsourced Retrieval Using Compact Embeddings), which co-designs representations with the cryptographic protocol. Spruce learns compact binary codes that preserve candidates for full-precision reranking, replacing corpus-wide embedding scoring with efficient Hamming-distance computation under two-server multi-party computation (MPC). A corpus-calibrated fixed-radius protocol avoids multi-round candidate selection while preserving retrieval quality. Spruce also provides private cluster pruning, which trades minor quality loss for substantially less computation, and a one-core owner-operated dealer that removes cloud OT preprocessing bottlenecks. Across four corpora containing 383K--5.42M documents, Spruce preserves the original search quality with median candidate sets of only 382--1,952. At 10 Gbps inter-server bandwidth, full scans take 0.21--2.97 seconds, $4.8$--$6.7\times$ faster than the closest measured prior work. Private pruning takes 0.06--1.09 seconds, achieves $13.1$--$22.9\times$ speedups, and retains $93.9\%$--$97.3\%$ of full-float NDCG. On the largest corpus, pruning and the dealer jointly improve sustained throughput by $31.5\times$ at 1 Gbps per link.
A uniform experimental comparison of vector search schemes finds that the performance of SAP matches Plaintext, EMVP delivers cryptographic indistinguishability at a 4x throughput cost on CPU, BNTM adds malicious-server verifiability at a further 22x median-latency cost, and Tiptoe hides the cluster choice itself, but incurs a 190x per-query cost compared to Plaintext.
Anne-Marie Kermarrec, Rafael Pires, Mathis Randl et al.· 1 citation
Retrieval-augmented generation (RAG) depends on dense retrieval: each document is stored as a learned vector, and a query is answered by finding its nearest neighbors in that vector space. Keeping one full-precision vector per document is the dominant index cost at corpus scale, so retrieval systems replace each vector with a short code of a few bytes---a step called quantization. Standard quantizers such as product quantization (PQ) pick the code that reconstructs the original vector most closely. A single code is even more useful if it serves several byte budgets at once: when its short prefixes are each directly searchable, a deployment can set its efficiency--quality operating point without re-encoding the corpus. But training all prefixes under one objective makes the early bits a compromise across budgets---short codes improve while the full-width code degrades. Quantization to low-bit representation, such as binary codes, further sharpens the conflict. We introduce Matryoshka Hash Representations (MHR), a two-stage procedure that separates full-width training from prefix organization. MHR first learns a longer binary code, then freezes the model and trains additional zero-initialized residual code adaptors for directly searchable prefixes. Documents are stored at one bit per coordinate, while queries keep continuous logits like PQ to attain sufficient expressivity. We implement the search process with FAISS FastScan. Trained on MS MARCO and zero-shot transferred to seven BEIR datasets, MHR reaches .5561 NDCG@10 and .6535 Recall@100 at 32 bytes, surpassing the best baseline of the same budget. The advantage is more pronounced in lower budgets. The same code also strengthens two common pipelines: shortlisting candidates for full-precision reranking, and pruning a low-storage graph index such as LEANN.
: We study the problem of enabling users to perform range queries over a cloud-managed database without revealing which records are retrieved, while also allowing users to verify the correctness of the returned results. Existing approaches support either query privacy through Private Information Retrieval (PIR) or query result authentication through Authenticated Data Structures (ADSs), but not both simultaneously for range queries. To address this problem, we present an Authenticated Private Information Retrieval (APIR) protocol for range queries with guarantees of soundness and completeness. We first propose a baseline scheme that combines PIR with Merkle Hash Trees (MH-trees), achieving authenticated query processing but incurring high communication and storage overhead due to redundant verification objects (VOs). To improve efficiency, we further introduce the APIR-tree , a novel authenticated data structure that embeds values at every node, enabling nodes to serve as VOs for their ancestors and eliminating redundancy. Simulation results show that the APIR-tree reduces storage overhead by up to 25 × and communication costs by an order of magnitude while preserving strong privacy and authenticity guarantees.
This paper presents MESS, a system that ensures data, query, and access pattern privacy, and constructs a multi-graph Hierarchical Navigable Small World (HNSW) index over the perturbed codes, and gives formal analysis of the system's privacy and extensive evaluation of its performance.
Haoyu Cui, Zengpeng Li, Tien Tuan Anh Dinh et al.· arXiv.org· 2 citations· ⚡1
Private Information Retrieval (PIR) enables a client to retrieve a target record from a server‐held database without revealing the queried index. Existing single‐server PIR schemes still face difficulty in achieving both query privacy and practical efficiency, due to large query size, large storage overhead, or high server‐side computation. To address these limitations, this article proposes GPIR, an efficient PIR scheme based on Garbled Bloom Filters (GBFs) and BFV homomorphic encryption, together with a query‐compressed row‐revealing variant, wGPIR. In GPIR, the server arranges the database into a square matrix and encodes each row as an additive GBF. The client generates a row‐masked sparse query vector according to the target index and encrypts it before sending. The server then homomorphically evaluates the query over all row‐wise GBFs and returns one encrypted response per row. To further improve efficiency, the variant wGPIR explicitly reveals the target row and compresses the query into three ciphertexts corresponding to the three GBF positions, which are expanded by the server to form the encrypted query vector. Security analysis shows that GPIR protects the queried index, target row, and GBF positions, while wGPIR provides intra‐row query privacy under the IND‐CPA security of BFV. Experiments on a database with 220$$ {2}^{20} $$ records show that GPIR achieves 1.53 ×$$ \times $$ improvement in computation over APIR, and wGPIR further achieves 1180 ×$$ \times $$ , 768.20 ×$$ \times $$ improvements in communication over APIR and GPIR, respectively, along with 4.09 ×$$ \times $$ and 49.5 ×$$ \times $$ improvements in computation over APIR and GPIR, respectively, demonstrating its practicality for efficient private retrieval.
Zixuan Di, Wenqi Zhang, Shuai Shang et al.· Concurrency and Computation· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
