Source-linked AI summary
Billion-Scale Nearest-Neighbor Search under Fully Homomorphic Encryption on a Single GPU, Balancing Leakage and Cost
Isamu Isozaki, Madison Bratina, Edward Kim
TL;DR
The paper addresses how to perform approximate nearest-neighbor search over billion-scale vector databases when queries must remain private. It combines encrypted rank reduction with client-steered hierarchical routing and evaluates the resulting GPU system, including its performance and leakage. The system achieves high recall with warm server-side query times of roughly seconds while exposing database geometry through access patterns, which seeded padding substantially reduces.
Problem
Billion-entry encrypted vector databases are too costly to scan exhaustively, motivating accurate encrypted candidate selection at practical scale.
Method
The system combines rank reduction under FHE with an all-levels-FHE coarse-to-fine hierarchy and client-steered routing.
Results
The paper demonstrates encrypted ANN at billion scale on a GPU and reports accuracy and latency for every configuration across three corpora.
Takeaways & Limitations
The hierarchy makes encrypted billion-scale search practical in warm server-side latency, but observable access patterns reveal database geometry.
Takeaways & Limitations
The measured prototype encrypts database rows on demand rather than storing the full database pre-encrypted, while fully hidden product quantization did not outperform plain encrypted vector search.
Abstract
from arXiv · showhide
We build a system that answers "which database vectors are most similar to my query?" without the server ever seeing the query. The query is encrypted with fully homomorphic en- cryption (FHE); the server does all its scoring on ciphertexts and returns encrypted results that only the client can read. The challenge is speed: at a billion vectors, scoring every row under encryption is far too slow, so we combine two ideas - rank reduction (shrink each vector's dimen- sion) and a hierarchy (route to a small candidate set instead of scanning everything) - executed under encryption on a single GPU. We evaluate on three corpora at very different scales: a face corpus of 222 049 centroids clustered from ~10 M face images (512-dim), DataComp-1B (1.39 x 10^9 vectors, 512-dim CLIP), and Deep1B (10^9 vectors, 96-dim). On DataComp-1B we reach a recall@10 of 0.90 against the single labeled answer, or 0.95 when a near-duplicate im- age in the top-10 also counts as correct (the data is web-scraped and full of duplicates), at ~6 s per encrypted query on a GPU; a lighter configuration reaches 0.78/0.83 at ~1.8 s. These are warm (deployable) server-side latencies - client decryption and network transfer are excluded. On Deep1B we reach recall@10 0.90 under all-levels FHE (0.9045 measured over 2000 FHE queries, matching the 0.906 plaintext routing - the 96 -> 128 zero-pad is exact, correlation 1.0) at 2.3 s warm per query. We describe the full client-server protocol in enough detail to repro- duce it, and report accuracy and latency for every configuration. We also measure what this speed costs: the hierarchy's access pattern leaks the database geometry (an observer recovers 72% of the coarse-cell neighbor graph from access patterns alone), and we show that seeded (fixed-group) padding cuts this leak by ~35x (to ~2%), where naive padding is defeated by a repeated-query attack.
1 Introduction
The paper makes encrypted approximate nearest-neighbor search feasible at billion scale by combining rank reduction, hierarchical routing, and GPU optimization, while measuring both performance and access-pattern leakage.
- Motivation and contributions: Billion-scale encrypted ANN search is presented as a GPU systems problem requiring accuracy, latency, and leakage evaluation.The work reports a reproducible protocol, full configuration measurements, and an access-pattern analysis.
- Core techniques: Rank reduction projects encrypted queries to a smaller dimension while correcting projection-induced norm distortion for true cosine similarity.The projection matrix remains hidden from the server, and the paper addresses both norm recovery and a packing optimization.
- Core techniques: The all-levels-FHE hierarchy routes from coarse to fine cells and reranks only ∼65–110k candidates instead of 1.39 B vectors.The client steers routing after decrypting intermediate scores.
- Core techniques: ∼5.4× lower warm per-query cost comes from GPU optimizations applied to the encrypted search pipeline.The reported optimization targets the per-query server-side cost.
- Security trade-offs: Access-pattern leakage exposes database geometry, while padding trades reduced leakage for additional fetch cost and naive padding remains vulnerable to repeated-query intersection.The analysis treats the group ids requested at each hierarchy level as observable metadata.
2 System Overview: one query, start to finish
The protocol keeps the query and scores encrypted on the server while letting the client decrypt intermediate scores and steer hierarchical routing; deployment requires pre-encrypted database data and substantial ciphertext storage.
- System setting: The billion-scale path uses a hierarchy, whereas the smaller face corpus is scored flat without hierarchical routing.The overview covers DataComp and Deep1B; the face corpus follows a separate flat path.
- Deployment boundary: The measured prototype encrypts touched database rows on demand, but the deployable warm configuration assumes ciphertexts are pre-encrypted and stored.Cold latency includes per-query enrollment encryption; warm latency loads serialized ciphertexts and scores them.
- Deployment boundary: At R=128, ciphertext storage is approximately 51 KB per vector, about 51 GB for the routing index and 71 TB for 1.39 B rows.These figures describe one-time encrypted-at-rest storage in a deployment.
- Cryptographic setting: The system uses 128-bit classic security parameters and a shallow multiplicative depth of 4 for the ranked DataComp path.CKKS supports packed approximate arithmetic, but the pipeline must conserve multiplicative depth.
- Query protocol: The client encrypts the query, the server scores ciphertexts through coarse, fine, and reranking stages, and the client selects the next groups and final top-10.Routing decisions occur after client decryption, while the server remains a stateless encrypted scorer.
- Query protocol: The server performs only encrypted arithmetic, with all “which cells next” decisions made by the client after decrypting scores.This separates routing logic from server-side ciphertext scoring.
3 Method
The method combines encrypted rank reduction with hierarchical routing to make billion-scale approximate nearest-neighbor search feasible, while analyzing product quantization and GPU optimizations as cost and leakage trade-offs.
- Rank reduction: Projecting encrypted queries to R=256 or 128 dimensions reduces scoring cost while preserving accuracy when R is not too small.The server evaluates the projection without learning its matrix, using encrypted diagonals and a Fisher-discriminant basis.
- Rank reduction: Ranked retrieval returns raw projected scores, allowing the client to divide by |qR| after decryption instead of performing homomorphic normalization.This keeps the ranked hierarchical path at multiplicative depth 4, unlike the face membership path’s encrypted threshold computation.
- Hierarchy: The hierarchy routes encrypted queries from coarse cells to fine cells and then reranks rows in selected leaves, touching ∼65–110k candidates instead of 1.39 B.The deployed DataComp index uses a fixed coarse beam of 16 and a leaf beam of 32 or 64.
- Product quantization: Product quantization was not used because fully encrypted codebook gathers added ciphertext–ciphertext multiplications and never beat plain encrypted vector search.A client-side residual-PQ gather was faster but exposed neighbor-graph information through published codes.
4 Evaluation
The evaluation measures accuracy, latency, and operating assumptions across face, DataComp-1B, and Deep1B datasets, showing few-second encrypted search at billion scale while highlighting tuning and measurement boundaries.
- Evaluation setup: The evaluation uses 2000 held-out queries across three corpora and runs on one NVIDIA L40S GPU with pre-encrypted database storage.The datasets include 222,049 face centroids, billion-scale DataComp vectors, and Deep1B descriptors.
- Evaluation caveats: The reported operating points are best-case because rank, beam widths, and the face threshold were selected on the same queries rather than a separate tuning set.The authors state that the single reported points should be read with this qualification.
- Face corpus: Recall quality on the face corpus is limited by very low rank: R=32 caps quality regardless of K, while PQ recall@10 saturates near K ≈2000.Figure 5 compares quality with rank and PQ recall with codebook size.
- Face corpus: The face experiment scans all 222,049 encrypted centroids without hierarchy, judging retrieval by identity and stressing rank reduction on 512-dimensional vectors.There is no reranking or hierarchy in this corpus, so hierarchical access-pattern leakage does not apply to the face setting.
- DataComp-1B: DataComp-1B reports recall@10 and warm latency per configuration, with warm timing loading and scoring pre-encrypted candidates while excluding on-the-fly enrollment.The plaintext no-rank-reduction row provides the accuracy ceiling, and duplicate-tolerant recall accounts for near-duplicate images.
- Deep1B: Deep1B reaches FHE recall@10 0.9045 at 2.30 s warm per query, matching plaintext routing because zero-padding 96-dimensional vectors to 128 is exact.The operating point uses coarse beam 16 and leaf beam 64; the full pipeline runs under all-levels FHE.
- Latency: Encrypted-scan latency grows super-linearly with scored rows and increases with rank, defining the few-seconds-per-query operating point.Figure 7 also shows a jump when the working set exceeds a GPU threshold.
5 Access-Pattern Leakage
The hierarchy hides encrypted values but exposes access patterns: linked observations reveal database geometry and relationships among private queries. Seeded padding reduces this leakage durably, while random padding is defeated by repeated-query intersection at added fetch cost.
- What the server observes: The server sees two nested leaf-id selections per query, but not the query, scores, answer, coarse ids, or coarse-to-leaf map.The client reveals a coarse neighborhood first and a finer leaf set second; flat, tree-free storage makes parent structure recoverable rather than directly exposed.
- Defenses: Fresh random padding is undone by intersection over repeated linked queries, whereas seeded padding survives by reducing observations to fixed anonymity groups.When queries cannot be repeated or linked, both schemes are indistinguishable because the intersection has only one observation.
- Measured leakage: 72% coarse-neighbor recovery, 0.99 parent-grouping recovery, and 0.22 leaf-neighbor recovery are obtained from co-access alone on DataComp-1B.Deep1B shows the same routing structure: 0.75 coarse recovery, 0.98 parent recovery, and 0.14 leaf recovery.
- Measured leakage: A shared coarse cell raises mean cosine from 0.44 to 0.54, while a shared leaf raises it to 0.68 on DataComp-1B.The shared-leaf signal is rarer but sharper; its relative lift depends on the corpus’s query distribution.
- Privacy-cost trade-off: Under equal budget, Coarse Neighbor Recovery falls to approximately 0.02 by B=128, while Parent Recovery falls from 0.80 to 0.28 and Leaf Neighbor Recovery from 0.22 to 0.001.Because the coarse fanout is smaller, the same budget buys larger coarse groups, making coarse leakage cheaper to suppress.
6 Related Work
The paper combines rank reduction with a hierarchical encrypted search design, extending GPU-accelerated FHE approaches toward billion-scale ANN. Its defense analysis frames seeded padding as a privacy-cost dial whose cost is reported for the full encrypted pipeline.
- Position and contribution: The work builds on CKKS and FIDESlib’s GPU-accelerated BSGS-Diagonal transforms, extending projection and scoring to rank-reduced hierarchical search.Earlier encrypted-matching systems and GPU face-similarity search are identified as related approaches.
- Privacy-cost trade-off: Equal-budget seeded padding makes coarse leakage cheaper to hide because Gc = 4Gℓ, while query-similarity lifts collapse toward 1 as the budget grows.The corresponding warm latency is measured for the full padded pipeline under all-levels FHE.
- Position and contribution: The system combines rank reduction and a hierarchy to enable encrypted ANN at billion scale on a GPU.The hierarchy is the paper’s central scale-oriented design contribution.
7 Conclusion and Future Work
The paper demonstrates billion-scale encrypted ANN on a single GPU by combining rank reduction with hierarchical routing, while documenting both performance and access-pattern leakage. It identifies privacy-cost tuning, hot-cluster loading, and shallower circuits as future directions.
- Conclusion: Recall@10 reaches 0.90/0.95 on DataComp-1B at approximately 6 s warm per encrypted query and 0.90 on Deep1B at 2.3 s.The DataComp values are exact-answer and duplicate-tolerant recall; the reported latency is server-side warm cost.
- Conclusion: The hierarchy recovers 0.72 coarse-neighbor structure on DataComp-1B and 0.75 on Deep1B, while parent-grouping recovery reaches 0.98–0.99.The paper characterizes parent recovery as a routing property rather than a corpus-specific effect.
- Future work: Seeded padding suppresses leakage durably, whereas fresh-decoy padding is undone by repeated-query intersection, at a fetch cost cheapest on the coarse reveal.The paper leaves tightening this privacy/cost trade-off and closing the gap to fully oblivious traversal open.
- Future work: Warm cost is dominated by loading candidate ciphertexts, motivating permanently resident hot clusters and fetch-frequency sharding across GPUs.This proposed optimization targets common queries by avoiding repeated loads of frequently fetched encrypted clusters.
- Future work: A shallower scoring circuit could reduce every ciphertext’s limb count, storage, and dominant database-wide load cost.This is presented as a separate performance direction from hot-cluster residency.