Abstract

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 encryption (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 vectors dimension) 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 __ 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 image 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 latenciesclient 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 routingthe 96 __ 128 zero-pad is exact, correlation 1 _._ 0) at 2 _._ 3 s warm per query. We describe the full clientserver protocol in enough detail to reproduce it, and report accuracy and latency for every configuration. We also measure what this speed costs: the hierarchys 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 __ 35 __ (to __ 2%), where naive padding is defeated by a repeated-query attack.