CS Paper Radar

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

Isamu Isozaki, Madison Bratina, Edward Kim

cs.CR ·submitted 2026-08-21 14:08 UTC · v1

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 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.

Closest papers

Nearest neighbours by meaning across the whole index.

CAROUSEL: GPU-Accelerated Private Vector Search via Homomorphic Sketching

cs.CR ·2026-11-07 ·Sohaib, Divyakant Agrawal, Amr El Abbadi, Soamar Homsi
similarity 0.79
Abstract

Vector search on untrusted infrastructure exposes the \emph{query embedding}, a faithful summary of the user's intent. Fully homomorphic encryption can hide the query, but existing approaches still require a full scan followed by ranking of encrypted scores. Scalable private systems avoid encrypted ranking by either sending scores from a single cluster to the client or moving the search to the client, which must first stream the entire vector index for preprocessing. We present \textsc{Carousel}, which instead scores the full corpus under encryption and compresses the results for client-side ranking. The server scores every vector under encryption, raises the scores to a power that preserves their order by magnitude while suppressing all but a handful, and compresses the resulting sparse vector into a logarithmic number of ciphertexts using homomorphic additions alone. Because every vector is scored, \textsc{Carousel} incurs no recall loss from discarding candidates. Since clients hold no database-dependent state, insertions and deletions take effect immediately at the cost of a single vector write. \textsc{Carousel} searches $1$ billion vectors of BIGANN SIFT1B across multiple GPUs and achieves recall@100 of $0.9715$. At $100$ million SIFT vectors, it achieves recall@100 of $0.9845$ with a query latency of $3.735$ seconds on a single GPU.

0.20

Memory-Efficient Designs for Word-Wise Universal Fully Homomorphic Encryption

cs.CR ·2026-09-04 ·Ardhi Wiratama Baskara Yudha, Erwin Eko Wahyudi, Rian Adam Rajagede, Qian Lou, Yan Solihin
published similarity 0.71
Abstract · Accepted at ICCD 2026

Fully Homomorphic Encryption (FHE) enables computation on encrypted data, preserving privacy throughout analysis. While its privacy is very strong, FHE is much slower to execute than the original computation. In particular, due to the recent success in accelerating its compute, the performance bottleneck shifts to the memory, especially considering that FHE magnifies the data size by orders of magnitude, resulting in a low arithmetic intensity. We propose BXT, an FHE optimization framework that mitigates the memory bottleneck through four techniques: (1) ciphertext compression, which regenerates ciphertext components from seeds during execution; (2) ciphertext serialization, which packs coefficients as bit arrays and unpacks them during L2-to-L1 transfer; (3) delayed seed generation, which defers PRNG-heavy offline work across aggregated operations; and (4) ciphertext digit pruning guided by fault-aware training tailored for Universal FHE. On CNN inference, the BXT-CSO50 configuration effectively achieves up to 3.8$\times$ speedup over the 100x GPU baseline with less than 1% accuracy loss at 50% comparison precision.

0.28

Batched Paillier-Based Hamming-Distance Computation over Binary Embeddings

cs.CR ·2026-09-18 ·Yavor Litchev, Liwen Ouyang
similarity 0.70
Abstract

Additively homomorphic encryption supports outsourced computation on encrypted binary embeddings, but large-integer arithmetic and data movement can limit throughput. We describe a Paillier-based client that combines a carry-separated binary encoding, table-based encryption, reduced-exponent decryption, CUDA/CGBN arithmetic, persistent device state, and batched retrieval integration. We establish the encoding's correctness and characterize four CPU and GPU client configurations. The lookup configuration uses a 280-bit exponent-size parameter. Across 3 warm-state trials on batches of 10,000 random 512-bit embeddings, the lookup GPU configuration achieved median-batch throughputs of 43,091 encryptions/s and 28,983 Hamming- distance decodes/s. Its amortized costs were 0.0232 ms and 0.0345 ms per vector, corresponding to factors of 453.8 and 200.9 relative to the measured CPU baseline. These implementation- specific results demonstrate the throughput benefits of combining cryptographic precomputation, batched accelerator execution, and persistent runtime state. The study distinguishes warm-batch performance from isolated-request latency and identifies the remaining costs of initialization, transport, and retrieval integration.

0.24

PixCrypt: Fast Fine-Grained FHE with Range-Aware Caching

cs.CR ·2026-09-12 ·Chao Wang, Shubing Yang, Xiaoyan Sun, Yan Bai, Jun Dai +1 more
published similarity 0.70
Abstract · 20 pages, 4 figures. Accepted at ICICS 2026

Many analytics tasks require secure computation over encrypted data. In particular, fine-grained data such as pixel-level images require higher precision, as every pixel can directly affect outcomes in tasks like tumor segmentation and anomaly detection. While Multi-Party Computation (MPC) is interactive, Differential Privacy (DP) protects only aggregate values, and Partially Homomorphic Encryption (PHE) lacks multiplicative support, none of them can efficiently handle fine-grained data analytics. Fully Homomorphic Encryption (FHE) uniquely enables arbitrary operations on encrypted pixels but remains computationally expensive, posing significant challenges for both software and hardware accelerators. We present PixCrypt, a caching-based acceleration mechanism for fine-grained fully homomorphic encryption. PixCrypt replaces expensive fresh ciphertext generation with cache retrieval and coefficient-level operations across CKKS, BFV, and BGV, while randomized reconstruction ensures that ciphertexts do not repeat. Its linear noise growth reduces the need for bootstrapping and lowers NTT load, improving hardware accelerator efficiency. This design yields up to 35x faster fine-grained encryption and maintains IND-CPA (Indistinguishability under Chosen Plaintext Attack) security. Experiments on five real-world pixel-level image processing tasks show that PixCrypt significantly improves the practicality of FHE for privacy-preserving analytics.

0.28

Encrypt What Matters: When Selective Homomorphic Inference Is Efficient

cs.CR cs.LG ·2026-09-08 ·Ali Backour, Juan Reyes, Jaime Punyed, Ana Onoprishvili
similarity 0.69
Abstract

Fully homomorphic encryption (FHE) enables inference on private data without revealing it to the server, but evaluating an entire input under FHE is expensive. We study \emph{selective homomorphic inference}, where only a sensitive region of interest (ROI) is encrypted, and computations independent of that region are performed in plaintext. Selective evaluation produces the same output as full FHE on the same model, without retraining. Its efficiency depends on how quickly encrypted dependencies spread through the network. For small encrypted ROIs, locality-preserving architectures can achieve order-of-magnitude homomorphic-evaluation speedups, whereas architectures with early global mixing provide essentially no speedup. These results identify locality as the key architectural property governing the benefit of selective homomorphic inference.

0.27

HULK: An Efficient Algorithm for Enabling Fast Bulk Bitwise Operations on Homomorphically Encrypted Data

cs.CR cs.ARcs.DC ·2026-10-13 ·Mayank Kabra, Phillip Widdowson, Harshita Gupta, Rakesh Nadig, Nisa Bostancı +7 more
code/data similarity 0.69
Abstract · 24 pages, 10 figures, 3 tables. Code: https://github.com/CMU-SAFARI/HULK

A wide range of important cloud applications, e.g., database analytics, graph analytics, and genome analysis, spend a considerable amount of time performing bulk bitwise operations (e.g., AND, OR, XOR). These applications often operate on highly sensitive data, making data privacy a critical concern. Homomorphic encryption (HE) enables secure computation on encrypted data without requiring decryption, ensuring privacy in untrusted and shared environments. We analyze 13 end-to-end applications across three domains (healthcare, graph, and database analytics) and observe that bulk bitwise operations take 62-100% of the execution time of the healthcare and graph workloads. The key problem is that existing HE approaches perform them with high-latency homomorphic operations (e.g., multiplication or lookup tables) and significantly increase the data size. Our goal is to enable fast bulk bitwise operations on homomorphically encrypted data by designing an efficient HE algorithm that reduces the use of these costly operations. To this end, we propose HULK, which performs two key steps: (1) it constructs bulk bitwise operations using low-cost homomorphic additions, which compute the Hamming weight of the encrypted operand bits in every slot of a packed ciphertext without any homomorphic multiplication, and (2) it decodes the result of an AND, OR, or XOR from the Hamming weight with a single indicator polynomial, keeping the result in the standard encoding. Across 13 end-to-end applications in healthcare, graph, and database analytics, HULK improves performance over the arithmetic approach used by prior works by up to 7.26x (CPU) and 6.65x (GPU), and on average by 2.32x/1.78x/1.45x (CPU) and 2.08x/1.70x/1.51x (GPU) for healthcare/graph/database analytics. When we increase the reduction depth in a representative application, HULK's speedup grows to 10.10x over the state-of-the-art GPU baseline.

0.22

Feasibility of Homomorphic Inference for a Genomic Foundation Model

cs.CR ·2026-09-14 ·Christos Galanopoulos, Kimon Antonios Provatas, Ilias Georgakopoulos-Soares
hot direction similarity 0.66
Abstract · 13 pages, 8 figures

Human genomic sequences can identify individuals, cannot be replaced after disclosure, and are the inputs that genomic foundation models are designed to interpret. We assess whether a compute provider can execute a released genomic foundation model without receiving query-derived genomic values in plaintext and whether correctness, memory, or cost prevents complete encrypted inference. We first reproduce the released model on three genomic task families and freeze an independently validated numerical reference. We then implement a client-assisted approximate homomorphic encryption protocol: the provider evaluates linear algebra on ciphertexts, while the key-holding data owner evaluates exact normalization, causal softmax, and activation functions at fixed boundaries. A noninteractive configuration completes one released-weight block but exceeds the tested accelerator-memory envelope when configured for composition. The client-assisted configuration executes all released transformer blocks and the task head for one heldout genomic-signal input at its full prompt length. It matches the frozen final label, peaks at 9,839 mebibytes of accelerator memory, and completes in 6,683 seconds on one accelerator. These results establish arithmetic feasibility for a complete classifier, while repeatability, network transport, and private token-index lookup remain unresolved. The biomedical significance is that, under the stated threat model, a served genomic model can process an encoded sequence without exposing plaintext queryderived activations to the compute provider.

0.53

GPU-Accelerated Non-Interactive Encrypted Neural Network Training with Batched Diagonal Packing

cs.CR cs.LG ·2026-11-09 ·Kentaro Mihara
code/data similarity 0.66
Abstract · 12 pages. Research preprint. Code and evidence: https://github.com/kenmaro3/ckks-train

Training a neural network under homomorphic encryption requires transposes, batch reductions, optimizer updates, and repeated refreshes in addition to forward matrix products. We combine rectangular diagonal packing, feature-major SIMD mini-batch lanes, baby-step giant-step evaluation, and compact optimizer state in an MIT-licensed Rust CKKS implementation. Its CUDA path keeps training and bootstrap ciphertext arithmetic on the GPU, while retaining host key generation and client operations. In a matched 100-update experiment on the main non-interactive MNIST model, device-resident bootstrapping reduces training time from 14,268.295 to 293.075 seconds, a $48.68\times$ ratio against our CPU implementation, with exactly equal decoded parameters and predictions. Including setup and final evaluation gives a $40.67\times$ ratio. A separate GPU run completes ten passes over 4,800 images in 2,967.095 seconds and achieves 90.35% test accuracy versus 90.41% for its plaintext twin. These are single-initialization results; exact CPU/GPU parameter agreement is verified at 100 updates, not for the full 1,000-update run. Earlier completed CPU runs support a larger-batch key-switch advantage and baseline-batch accuracy within the registered tolerance, but the baseline-batch normalized key-switch target is missed. The released ReBoot baseline does not meet the common security-estimator threshold, and its full-setting CPU time is unmeasured. We therefore distinguish measured acceleration of our implementation from conditional layout comparisons and do not claim unconditional superiority over ReBoot.

0.60