💻 computer science

Billion-Scale Nearest-Neighbor Search under Fully Homomorphic Encryption on a Single GPU, Balancing Leakage and Cost

This paper presents a GPU-accelerated system for billion-scale nearest-neighbor search under fully homomorphic encryption that achieves practical latency by combining rank reduction and hierarchical routing, while quantifying and mitigating the associated geometric leakage through seeded padding.

Original authors: Isamu Isozaki, Madison Bratina, Edward Kim

Published 2026-08-24

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Isamu Isozaki, Madison Bratina, Edward Kim

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 have a library containing billions of photos, and you want to find the one that looks most like a picture in your pocket. Normally, a computer would scan every single photo to find the match, but what if you cannot show the computer your picture because it is private? What if the library is owned by a stranger you do not trust? This is the problem researchers set out to solve. They wanted a way for a computer to search through a massive, secret database without ever seeing the actual question being asked. To do this, they use a method called fully homomorphic encryption, which is like putting your question inside a locked, transparent box. The computer can perform calculations on the box without opening it, returning a result that is still locked. Only you, holding the key, can open the final box to see the answer. For years, this idea was too slow to be useful for huge collections of data, as the math required to keep the box locked was incredibly heavy.

A team of researchers has now built a system that makes this possible for a billion items, running on a single graphics card. They managed to find the most similar images in a database of 1.39 billion entries without the server ever seeing the query. The system works by using two main tricks to speed things up. First, it simplifies the images. Instead of comparing every tiny detail of a photo, the system reduces the description of each image to a shorter, simpler version before the search begins. This makes the math much lighter. Second, it does not look at every single photo. Instead, it uses a hierarchy, like a map that first points to a general neighborhood, then a specific street, and finally a few houses. The computer only checks the photos in those selected areas, skipping the rest. This allows the system to find the right answer quickly, even though the data is locked in a box.

The results show that this approach works remarkably well. On a dataset of 1.39 billion images, the system found the correct match in the top ten results 90 percent of the time. When the researchers allowed for near-duplicates—since the internet is full of slightly different copies of the same photo—the success rate jumped to 95 percent. The entire process took about six seconds per search on a single graphics card. This is a warm, deployable speed, meaning it is fast enough for real-world use once the database is prepared in advance. The researchers also tested the system on a different billion-item collection of 96-dimensional vectors, achieving a 90 percent success rate in just 2.3 seconds. These numbers prove that searching billions of encrypted items on a single machine is no longer just a theoretical dream.

However, the researchers were careful to measure what this speed costs in terms of privacy. While the server never sees the question or the answer, it does see which groups of data the computer asks to look at. This pattern of access can reveal clues about the database itself. By watching which groups are requested together, an observer could reconstruct about 72 percent of the map showing how the data is organized. They could also guess that two different searches were looking for similar things if they requested the same groups. To fix this, the researchers tried a method where the computer asks for extra, fake groups of data along with the real ones to hide the true pattern. If the fake groups change every time, a clever attacker can still figure out the truth by comparing many searches. But if the fake groups are fixed and always the same, the attacker cannot strip them away. This "seeded" padding reduces the information leak by about 35 times, dropping the recovery of the database map from 72 percent down to just 2 percent.

The team also explored other ways to make the search faster, such as a technique called product quantization, which breaks data into small codes. They found that under encryption, this method did not work well. It either failed to beat the standard encrypted search or leaked too much information about the data structure. They decided not to use it, sticking instead to the simpler method of reducing the size of the data descriptions and using the hierarchical map. This choice highlights a key finding: sometimes, a straightforward approach is better than a complex one when privacy is the priority.

The system operates by having the user send an encrypted question to the server. The server, which holds the encrypted database, performs the math on the locked data. It first checks a few thousand broad categories, then narrows down to a few thousand more specific groups, and finally scores the actual images in those groups. At every step, the server returns encrypted scores. The user decrypts the scores, decides which groups to look at next, and sends a new request. The server never sees the user's decision or the final answer. This back-and-forth continues until the top ten matches are found. The researchers measured the time it takes to load the data and perform the scoring, excluding the time it takes for the user to decrypt the final result or for the data to travel over the network. They found that the time is dominated by loading the encrypted data into the computer's memory, not by the math itself.

In their analysis of the privacy risks, the researchers showed that the leak is a property of how the search is routed, not the specific data being searched. Whether the database contained faces or general images, the pattern of access revealed the same amount of structural information. They demonstrated that without protection, an observer could recover the grouping of the data almost perfectly. With the fixed-group padding, this recovery dropped significantly, though it did not disappear entirely. The trade-off is clear: to hide the access pattern, the system must fetch more data than strictly necessary, which increases the time it takes to complete a search. The researchers showed that this cost can be managed, but it requires a balance between how much privacy is needed and how fast the system must run.

This work represents a significant step forward in making private search practical at a massive scale. It proves that you can search a billion items without revealing your intent, provided you are willing to accept a few seconds of delay and a carefully managed privacy cost. The system does not rely on magic or unproven theories; it uses established math and clever engineering to solve a real problem. The researchers have provided a complete guide on how to build and run this system, including the exact settings for speed and accuracy. They have also shown where the limits lie, particularly regarding the information that leaks through the search pattern. By being transparent about what is hidden and what is revealed, they offer a realistic path forward for secure data search in an era where privacy is increasingly valuable.

Technical Summary: Billion-Scale Nearest-Neighbor Search under FHE on a Single GPU

Problem Statement

The paper addresses the challenge of performing approximate nearest-neighbor (ANN) search on a database of billions of vectors (e.g., image embeddings) where the query must remain private from an untrusted server. While Fully Homomorphic Encryption (FHE) allows a server to compute on encrypted data without decryption, the computational cost of scanning billions of encrypted vectors is prohibitive. Prior brute-force approaches on GPUs (e.g., searching 10M vectors on 8 GPUs) would extrapolate to requiring over 1,000 GPUs for billion-scale datasets like DataComp-1B. The core problem is how to score only a small, well-chosen candidate set under encryption on a single GPU while maintaining high retrieval accuracy.

Methodology

The system combines three primary techniques to achieve billion-scale search on a single NVIDIA L40S GPU:

1. Rank Reduction (Projection)

To reduce the computational cost of encrypted matrix-vector multiplications, the system projects high-dimensional query vectors (e.g., 512-dim) to a lower rank $R$ (128 or 256) under encryption.

Mechanism: The server holds the projection matrix $W$ as encrypted "diagonals." It computes $Enc(q_R) = W^\top Enc(q)$ using a diagonal matrix-vector method involving rotations and multiplications.
Optimization: The projection basis is derived via Fisher discriminant analysis (LDA) over clusters. A packing optimization allows multiple chunks of $W$ to be processed in a single ciphertext using non-overlapping windows, reducing storage and computation.
Norm Handling: Projection distorts vector norms. For ranked retrieval (the hierarchy path), the server returns raw scores, and the client normalizes them post-decryption (exact and free). For membership search (face templates), the server must return a binary match; this requires an encrypted threshold comparison using a low-degree Chebyshev polynomial approximation of the square root, increasing the multiplicative depth to 11.

2. Hierarchical Routing

Instead of scanning the entire database, the system employs a two-level hierarchy (Coarse $\to$ Fine $\to$ Rerank) to narrow the search space.

Structure: The database is clustered into $\sim10^6$ leaf clusters, which are further grouped into $\sim1,000$ coarse cells.
Process:
1. Coarse Level: The server scores the encrypted query against $\sim1,000$ coarse centroids. The client decrypts these scores and selects the top $n_{probe}$ (e.g., 16) coarse cells.
2. Fine Level: The server scores the query against the leaf centroids belonging to the selected coarse cells (approx. 18k candidates). The client selects the top $n_{probe}$ leaves.
3. Rerank: The server scores the actual database rows within the selected leaves.
Result: A query touches only $\sim65,000$ to $110,000$ candidates instead of the full billion.

3. GPU Optimizations

The system implements specific GPU kernel and memory management strategies to minimize latency:

Parallel Loading: Encrypted database rows are loaded from disk using 16 threads to saturate I/O.
Projection Caching: The query is projected once and reused across batches.
Memory Management: Encrypted rows are held in CPU memory and uploaded directly to the GPU, avoiding round-trips to disk during the scoring phase.
Key Caching: Small-step (baby-step) rotation keys are kept resident in VRAM, reducing warm-query latency by $\sim96\%$ for the baby-step path.
Allocation: A unified memory allocation strategy (single_alloc) prevents GPU memory fragmentation.

4. Access Pattern Leakage Analysis

The paper acknowledges that while data is encrypted, the access pattern (which cells the client requests) leaks information about the database geometry and query stream.

Threat Model: A strong attacker can link repeated queries from the same client.
Vulnerability: Simple random padding (adding decoy cells) is defeated by an intersection attack; if a client repeats a query, the attacker intersects the observed sets, stripping away the random decoys and revealing the true target set.
Mitigation: The paper proposes seeded (fixed-group) padding, where each cell belongs to a fixed anonymity group. The client always fetches the entire group. This prevents the intersection attack from isolating the true target, though it quantizes the leak to the group granularity. This trades increased fetch cost (latency) for reduced leakage.

Key Results

Performance and Accuracy

Evaluated on three corpora using a single GPU:

DataComp-1B (1.39B vectors, 512-dim CLIP):
- Configuration: Rank 256, Leaf beam 64.
- Accuracy: Recall@10 of 0.90 (exact) and 0.95 (duplicate-tolerant).
- Latency: 6.1 seconds per warm query (server-side load + score).
- Lighter Config: Rank 128, Leaf beam 32 achieves 0.79/0.83 recall at 1.8 seconds.
Deep1B (1B vectors, 96-dim):
- Configuration: Native 96-dim (zero-padded to 128), Rank 128.
- Accuracy: Recall@10 of 0.9045 (matching plaintext routing).
- Latency: 2.3 seconds per warm query.
Face Corpus (222k centroids, 512-dim):
- Evaluated without hierarchy (flat scan).
- Rank 256 maintains F1 of 0.974 (vs. 0.993 full rank) with a latency of 7.0 seconds.

Leakage vs. Cost Trade-off

Baseline Leakage: Without defense, an attacker recovers 72% of coarse-neighbor relationships and 99% of parent-grouping (leaf-to-coarse) structure from access patterns alone.
Seeded Padding: Increasing the padding budget (e.g., to 512) reduces Coarse Neighbor Recovery to 0.02 and Parent Recovery to 0.28–0.30.
Cost: This privacy improvement comes at a linear cost in latency. For DataComp-1B, increasing the padding budget from 64 to 512 increases warm latency from 2.6s to 25.4s.

Negative Findings

Product Quantization (PQ): The paper explicitly reports that PQ does not pay off under FHE. Fully encrypted PQ requires expensive ciphertext-ciphertext multiplications for the gather step. Client-side gather (offloading lookup to the client) is fast but leaks the entire neighbor graph, which is worse than the access-pattern leak of the hierarchical approach.

Significance and Claims

The paper claims to demonstrate the first system capable of performing billion-scale encrypted ANN search on a single GPU with warm latencies in the range of 1.8 to 6.1 seconds.

Scalability: It proves that combining rank reduction and hierarchical routing makes FHE practical for billion-scale datasets, reducing the hardware requirement from thousands of GPUs (for brute force) to one.
Reproducibility: The authors provide a full client-server protocol, detailing every step from encryption to decryption, and report accuracy/latency for every configuration.
Privacy/Cost Transparency: The paper explicitly quantifies the "cost" of privacy in terms of access-pattern leakage. It argues that while FHE hides the data values, the routing logic inherently leaks geometry. The proposed seeded padding offers a tunable mechanism to suppress this leak, but the authors note that closing the gap to fully oblivious traversal remains an open challenge.
System Design: The work highlights that for FHE on GPUs, memory management and I/O (loading ciphertexts) are often more critical bottlenecks than the arithmetic operations themselves.

The authors conclude that while the system achieves high recall and deployable latencies, the remaining work involves further reducing the multiplicative depth to shrink ciphertext sizes and exploring orthogonal cryptographic tools (like transciphering) to reduce storage and transmission footprints.