Quantization enables private search with secure verification
Quantization Enables Private Dense Retrieval against Malicious Service Providers
Cryptography and SecurityArtificial Intelligence
Summary
Searching for information while keeping your question secret and ensuring the results are trustworthy is a big challenge. This paper tackles that by creating a way to keep queries private and make sure the server can't cheat. The authors use math tricks and low-bit compression to speed up secure searches and tested their method on large datasets. They found that using just three bits for compression keeps search quality high and is practical for moderately sized datasets if waiting a few minutes is okay.
What this means in practice
- •For healthcare it teams: Provide privacy-preserving search over sensitive clinical documents ensuring query confidentiality and trustworthy results.
- •For legal data engineers: Implement verifiable private document retrieval for secure handling of confidential legal case databases.
Authors
Louis Tremblay Thibault, Sofiane Azogagh, Marc-Olivier Killijian, Ulrich Aïvodji
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.