CS Paper Radar

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

Chao Wang, Shubing Yang, Xiaoyan Sun, Yan Bai, Jun Dai, Dongfang Zhao

cs.CR ·submitted 2026-09-12 20:37 UTC · v1
published

Abstract

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.

Comment
20 pages, 4 figures. Accepted at ICICS 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Rosemary: Efficient and Adaptable In-Storage Acceleration for Fully Homomorphic Encryption

cs.CR cs.AR ·2026-10-28 ·Xuan Wang, Tianqi Zhang, Gabrielle De Micheli, Yujin Nam, Keming Fan +3 more
similarity 0.79
Abstract

Fully Homomorphic Encryption (FHE) enables computation on encrypted data and is promising for privacy-preserving computing. However, FHE deployment remains constrained due to massive computational, memory, and data-movement overheads. Existing acceleration strategies often overlook the storage I/O bottleneck caused by the enormous size of FHE data in large-scale applications, as most prior works focus on small benchmarks that fit in main memory. Our studies show that state-of-the-art FHE systems spend 71\% to 85\% of their execution time moving data between storage and compute units rather than performing useful computation. To address the I/O bottleneck, we present Rosemary, a heterogeneous FHE acceleration system that incorporates a novel in-storage processing (ISP) architecture with compiler-level and algorithmic optimizations. Our key innovations include 1) an adaptable hardware-aware FHE engine inside a NAND flash-based solid-state drive (SSD) for efficient and cost-effective in-storage FHE processing, 2) a Throughput-Data-Aware Program Allocator (TDAP) that partitions FHE workloads into heterogeneous programs, and 3) a Compiler-Level Ciphertext-Aware Optimizer (CLCAO) that exploits ISP-friendly FHE kernels for low-cost ISP execution. Across a diverse set of FHE workloads, including encrypted deep learning inference and cloud database queries, Rosemary achieves geometric-mean speedups of $185.7\times$ over state-of-the-art CPU/GPU implementations and $3.7\times$ over prior FHE accelerators, while improving energy efficiency by up to $3.9\times$ and Energy-Delay-Area-Product (EDAP) by up to $16.5\times$.

0.04

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

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

FPGA Acceleration of Fully Homomorphic Encryption with Adaptive Key Switching

cs.CR cs.AR ·2026-09-08 ·Zhihan Xu, Jayashree Adivarahan, Rajgopal Kannan, Viktor K. Prasanna
published similarity 0.74
Abstract

Fully Homomorphic Encryption (FHE) enables privacy-preserving cloud services but incurs substantial computation overhead, making hardware acceleration essential. Among FHE operations, key-switching is a major performance bottleneck. Recent cryptographic advances introduce a novel key-switching method (i.e., KLSS) that reduces certain operational complexity but demands higher computational precision than the traditional Hybrid Key Switching (HKS) method. This trade-off leads to distinct computation and memory requirements, making the relative latency of KLSS and HKS highly dependent on hardware parallelism, FHE security parameters, and available on-chip memory capacity, particularly on FPGA platforms, where memory resources and parallelism must be carefully balanced. In this work, we first propose a memory-efficient KLSS datapath that eliminates off-chip ciphertext transfers. We then develop a performance model to analyze and compare the overheads of both KLSS and HKS. Our analysis reveals that an adaptive solution supporting both methods can achieve lower overall latency than a static method during FHE computation. Guided by the performance model, we design an adaptive FPGA-based FHE accelerator that dynamically selects between HKS and KLSS during computation. We implement the accelerator on an Alveo U280 and evaluate it across multiple FHE benchmarks. Experimental results demonstrate that our adaptive solution achieves a 1.84-3.31$\times$ speedup in bootstrapping latency and a 1.66-2.52$\times$ speedup in secure image classification compared to state-of-the-art FPGA accelerators.

0.35

Hidden in Plain Sight: Privacy-Enhanced Computing Through Register Renaming

cs.AR cs.CR ·2026-11-09 ·Ahmed Nematallah, Stefanos Kaxiras
similarity 0.73
Abstract

Privacy-Enhanced Computing (PEC) is a mechanism to hide program secrets from the outside world without paying the cost of fully-homomorphic encryption. Previous work has developed hardware mechanisms to achieve this goal but they require a dedicated processor enclave where all computations are done, requiring duplicate ALU resources and limiting the performance of PEC-utilizing applications due to not being able to access the full compute resources of the processor (e.g., multiple execution units and vector units), or not being able to execute PEC instructions in parallel and out-of-order. In this work, we introduce HPS-PEC (Hidden in Plain Sight PEC), a novel method of utilizing existing infrastructure in the CPU to achieve PEC with minor modifications to the architecture. We show that, across 25 VIP-Bench benchmarks and with a 7-cycle QARMA-64 cipher, HPS-PEC runs encrypted code at 3.41x the execution time of unprotected native code (geometric mean), of which 1.03x is the cost of data-oblivious code itself, and is 1.26x faster than a Sequestered Encryption (SE) unit while utilizing under a third of its dedicated area. Our method keeps plaintext out of reach of every instruction, as an enclave does given a correctly functioning renamer and register file, which every program already depends on.

0.18

Batched Paillier-Based Hamming-Distance Computation over Binary Embeddings

cs.CR ·2026-09-18 ·Yavor Litchev, Liwen Ouyang
similarity 0.71
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.44

HEAT: Faster Fully Homomorphic Inference via Approximations-Weights Co-Adaptation

cs.CR cs.AI ·2026-09-01 ·Alessandro Zirilli, Davide Marincione, Evgenios M. Kornaropoulos, Giuseppe Ateniese, Emanuele Rodolà
similarity 0.70
Abstract · 9 pages, original extended abstract (v1, 4 pages) accepted at "Beyond Private Training: The New Landscape of AI Privacy" and "Privacy in the…

Fully homomorphic encryption (FHE) allows a server to run a language model directly on encrypted user prompts, but current approaches remain prohibitively slow. Ciphertexts natively support only addition, multiplication, and rotation, and multiplications may be composed only to a bounded depth before a costly bootstrapping operation is required to continue. Every nonlinearity must therefore be approximated by an iterative method; each iteration increasing the number of multiplications. A higher iteration count buys precision but exhausts the available depth more frequently and thus triggers more bootstraps, which dominate latency. We introduce Homomorphic Encryption-Aware Training (HEAT), a fine-tuning method that makes the per-nonlinearity iteration counts learnable, enabling them and the model weights to co-adapt during training. HEAT optimizes iterations with respect to the task objective, allowing the model to adapt to approximation errors encountered during inference without architectural changes or retraining from scratch. We further relate iteration count to quantization bit width and bound, at fixed weights, the gap between our objective and quantization-aware training. On encrypted GPT-2 decoding, HEAT reduces iterations by $3.1\times$, bootstraps by $1.6\times$, and end-to-end latency by $1.4\times$, while improving decode agreement over the calibrated encrypted baseline.

0.60

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

cs.CR ·2026-08-21 ·Isamu Isozaki, Madison Bratina, Edward Kim
similarity 0.70
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.

0.13