💻 computer science

A Unified Benchmark for Privacy-preserving Vector Search

This paper introduces a unified benchmark that provides the first fair, side-by-side comparison of privacy-preserving vector search schemes (SAP, EMVP, BNTM, and Tiptoe) against a plaintext baseline, revealing their distinct trade-offs in privacy, performance, and recall to guide practitioners in selecting the most suitable deployment option.

Original authors: Anne-Marie Kermarrec, Rafael Pires, Mathis Randl, Martijn de Vos

Published 2026-08-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Anne-Marie Kermarrec, Rafael Pires, Mathis Randl, Martijn de Vos

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find a specific song in a massive library of billions of tracks. You hum a few notes, and a super-smart librarian instantly knows exactly which song you mean and hands it to you. This is how modern "vector search" works for computers: it turns your questions and documents into mathematical points (vectors) and finds the closest matches. It powers everything from movie recommendations to chatbots that answer questions using real documents. But here's the catch: for the librarian to do their job, they have to see both your humming and the entire library. This means the librarian could potentially figure out what you are looking for, or even reconstruct the library's secrets just by watching how you search.

To stop this, scientists have invented "privacy-preserving" tricks. Some are like putting your song request in a scrambled envelope that the librarian can still sort through without opening. Others are like putting the whole library in an unbreakable vault where the librarian can only perform math on the locked boxes without ever seeing the contents. The problem is, every scientist who invents a new trick tests it in their own lab, with their own rules, their own library size, and their own stopwatch. It's like comparing a Formula 1 car's speed to a bicycle's speed, but one test was done on a downhill track and the other on a muddy field. You can't tell which vehicle is actually better.

This paper acts as the ultimate referee. The researchers built a single, fair testing ground where they pitted four different privacy tricks against each other and a standard, unencrypted search. They used the exact same library, the exact same questions, and the exact same computer hardware for every single test. Their goal was to answer a simple question: "If I want to keep my data private, how much slower will my search become, and is it worth it?"

The results were a mix of "surprisingly cheap" and "expensive but necessary." The researchers found that the idea that "privacy is too slow to use" is mostly a myth, but it depends entirely on how much privacy you need.

First, there is the "lightweight" trick called SAP. Imagine you put a tiny bit of static noise on your song request so the librarian can't hear the exact notes, but they can still tell if two songs sound similar. This method is incredibly fast; it runs at almost the exact same speed as the unencrypted search. The catch? The librarian can still see the general shape of your library. They can tell which songs are similar to each other, even if they can't hear your specific request perfectly. It's a great deal if you just want to hide your specific query, but not if you want to hide the library's layout.

Then, there are the "heavy armor" methods like EMVP and BNTM. These are like putting the entire library in a magical vault where the librarian can only do math on the locked boxes. The librarian learns absolutely nothing about the songs or your request. This is much stronger privacy, but it comes with a price tag. On a standard computer, these methods are about 4 times slower than the unencrypted search. If you add a feature to verify the librarian's operations (BNTM), it gets even slower, about 22 times slower.

Finally, there is the "ultimate privacy" method called Tiptoe. This one hides not just the songs and the request, but even which section of the library you are looking at. The librarian has to check the entire library for every single question to make sure they don't reveal your target. This is the strongest protection, but it is also the most expensive. It is roughly 190 times slower than the unencrypted search.

The paper also tested these methods on powerful graphics cards (GPUs), which are usually great at speeding things up. Surprisingly, the GPUs only helped the fast methods (the unencrypted one and the lightweight SAP). For the heavy armor methods, the GPUs actually made things slower or didn't help at all. This is because these methods are limited by how fast they can read data from memory, not by how fast they can do math.

In short, the paper proves that you don't have to choose between privacy and speed, but you do have to choose your level of privacy. If you need to hide just your query, a fast, lightweight trick works almost as well as no privacy at all. If you need to hide the entire library's structure, you have to pay a significant speed penalty, but it is still possible to run the system. The old belief that "encrypted search is too slow to be useful" is debunked; it's just a matter of picking the right tool for the job and understanding the trade-off.

Technical Summary: A Unified Benchmark for Privacy-preserving Vector Search

1. Problem Statement

Vector search is a foundational infrastructure for semantic search, recommendation systems, and Retrieval-Augmented Generation (RAG). However, standard implementations lack privacy: the service provider observes both the query embeddings and the corpus embeddings. This exposure creates significant privacy risks, including the potential for "embedding inversion" attacks where an attacker can reconstruct original text or sensitive data (e.g., medical records) from dense embeddings, even without access to the model's internal weights.

While cryptographic schemes exist to mitigate this leakage (e.g., SAP, EMVP, BNTM, Tiptoe), they have historically been evaluated in isolation. Each study utilizes different corpora, embedding models, hardware configurations, threat models, and metric definitions. Consequently, practitioners lack a defensible basis for choosing a scheme, as performance numbers are not directly comparable. The core problem addressed is the absence of a unified benchmark to evaluate the trade-offs between privacy guarantees, performance (throughput/latency), and retrieval accuracy across these schemes.

2. Methodology

The authors constructed a single, uniform experimental harness to compare five schemes: a Plaintext baseline and four privacy-preserving mechanisms (SAP, EMVP, BNTM, and Tiptoe).

Experimental Setup

Corpus & Workload: The benchmark uses the MS MARCO passage collection (8.8M passages) and a 100k subset. Queries are generated from the MS MARCO dataset using the E5-base-v2 embedding model (768 dimensions).
Indexing: To ensure comparability, all schemes utilize a shared Inverted File (IVF) index with $k$ -means clustering. This avoids the incompatibility of graph-based indexes (like HNSW) with end-to-end encryption schemes.
Hardware: Experiments run on a dual-socket Intel Xeon Gold 6426Y (64 logical cores) with 128 GB RAM and an NVIDIA RTX 5000 Ada GPU (32 GB VRAM).
Metrics: Performance is measured via throughput (queries/sec), end-to-end latency, recall@10, communication cost (setup, online, offline), and memory bandwidth usage.
Security Parameters: All cryptographic schemes are configured for 128-bit security. SAP uses a perturbation parameter $\beta$ to tune privacy vs. recall.

The Schemes Compared

Plaintext: Unencrypted baseline.
SAP (Symmetric Additive Perturbation): Uses distance-comparison-preserving encryption. The client perturbs vectors before upload. The server compares distances directly on ciphertexts. It hides the exact vector values but reveals the corpus geometry (relative distances).
EMVP: Encrypts vectors into a matrix. The server computes encrypted matrix-vector products (matvec) for the routed clusters. It provides computational indistinguishability (hides query and corpus) but reveals the accessed cluster.
BNTM: Similar to EMVP but relies on the Learning Parity with Noise (LPN) assumption. It adds malicious-server verifiability, allowing the client to verify the correctness of the server's response using Freivalds' algorithm.
Tiptoe: Uses Private Information Retrieval (PIR) over the entire corpus. The server performs a matvec over the whole database, hiding the specific cluster accessed by the query. It offers the strongest privacy (hiding access patterns) but incurs the highest computational cost.

3. Key Contributions

Unified Evaluation Harness: The authors built a single software framework that isolates the cryptographic primitive from the rest of the pipeline, ensuring that performance differences stem solely from the scheme's specifications rather than implementation artifacts.
Comprehensive Benchmarking: The study evaluates schemes across multiple dimensions: recall-throughput trade-offs, CPU vs. GPU performance, communication costs (setup, online, offline), memory bandwidth requirements, and index build times.
Reproducibility: All experimental artifacts, raw measurements, and code are publicly released to ensure transparency.

4. Key Results

Performance vs. Privacy Trade-offs

SAP: Achieves performance nearly identical to the Plaintext baseline (negligible overhead) but only provides "snapshot" privacy; the server can still infer the relative geometry of the corpus.
EMVP: Provides strong cryptographic indistinguishability (hiding both query and corpus) but incurs a 4× throughput penalty compared to Plaintext on CPU.
BNTM: Adds malicious-server verifiability to EMVP's guarantees. This introduces a further 22× median latency cost compared to Plaintext (or roughly 22× slower than EMVP in some contexts, though the abstract notes a 22× cost over Plaintext).
Tiptoe: Hides the cluster access pattern entirely. However, it is prohibitively slow, incurring a 190× per-query cost compared to Plaintext on a 100k subset. Its recall is also significantly lower due to quantization and the constraint of searching only one cluster per query.

Hardware Acceleration (GPU)

Plaintext and SAP: Benefit significantly from GPU acceleration (1.8–1.9× speedup) because their scoring operations are compute-bound and parallelizable.
EMVP and BNTM: Do not benefit from GPUs; in fact, EMVP performs worse on GPU. These schemes are memory-bandwidth bound. The encrypted matrices are too large to fit in GPU memory (e.g., 91 GB for EMVP on 8.8M corpus), forcing data to stream over the PCIe bus, which negates GPU compute advantages.
Tiptoe: Not evaluated on GPU in this benchmark due to architectural constraints.

Communication and Memory

Network vs. Memory: Schemes rank differently depending on the metric. BNTM has the lowest network traffic (small response size) but requires reading massive amounts of data from server memory (comparable to EMVP).
Latency Breakdown:
- Plaintext/SAP are server-compute bound.
- EMVP and BNTM are client-side decode bound (decoding encrypted responses).
- Tiptoe is response decompression bound (decrypting PIR results).

Index Build Time

Index construction times are relatively comparable (within a 2.5× band), dominated by the $k$ -means clustering step (10.5s for 100k). Encryption overheads for EMVP and Tiptoe add roughly 10–15 seconds to the build time.

5. Significance and Claims

The paper challenges the prevailing belief that cryptographic privacy for vector search is "unaffordable." The authors demonstrate that:

Privacy is not a flat penalty: Schemes exist on a Pareto frontier. Practitioners can choose a level of privacy (e.g., hiding only the query vs. hiding access patterns) with a corresponding, quantifiable cost.
Implementation matters: The performance of a scheme is heavily dependent on implementation details, particularly memory access patterns. A scheme with low network traffic (like BNTM) may still be slow due to high memory bandwidth requirements, which also dictates GPU suitability.
Actionable Guidance: The results provide concrete "action points" for practitioners:
- Use SAP if hiding the corpus geometry is not required but vector values must be protected (near-zero cost).
- Use EMVP if full encryption of query and corpus is needed (4× cost).
- Use BNTM if server honesty cannot be assumed (adds verification cost).
- Use Tiptoe only if hiding the access pattern (which cluster is queried) is critical, accepting massive latency penalties.

The work concludes that while privacy comes at a cost, it is not an insurmountable barrier, and the choice of scheme should be driven by specific threat models and hardware constraints rather than a blanket assumption of infeasibility.