Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper presents a comprehensive benchmark for evaluating various cryptographic schemes designed to enable privacy-preserving vector search, addressing a critical gap in the field where existing methods are evaluated in isolation. The authors conduct a uniform experimental comparison across multiple cryptographic backends, revealing a Pareto frontier that illustrates trade-offs between privacy, performance, and recall. Key findings indicate that while SAP achieves performance parity with plaintext searches, other schemes like EMVP and BNTM incur significant costs in throughput and latency, highlighting the nuanced choices practitioners face when selecting privacy solutions.
Privacy-preserving vector search schemes reveal a surprising trade-off landscape, with some methods matching plaintext performance while others impose hefty costs on usability.
Vector search powers semantic search, recommendation systems, and retrieval-augmented generation (RAG). By design, the service answering a query sees both the query embedding and, usually, the corpus against which it is matched. This is a privacy breach for both the user issuing the query and the owner of the corpus. A family of cryptographic schemes (e.g., SAP, EMVP, BNTM, Tip-toe) addresses that leak. However, as each scheme is published and evaluated on its own corpus, threat model, parameter choices, hardware, and metric conventions, the numbers cannot be compared directly. Consequently, a practitioner asking which one to deploy today has no defensible way to choose. We close that gap with a uniform experimental comparison, including a Plaintext baseline and four cryptographic backends running over the same workload, hardware, and metric definitions. Under that ruler, the schemes spread across a Pareto frontier in privacy, performance, and recall rather than imposing a flat penalty on performance. We find 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. GPU acceleration pays off for Plaintext and SAP but not for EMVP or BNTM. All our experiment artifacts are publicly available for reproducibility