Memory-Efficient Designs for Word-Wise Universal Fully Homomorphic Encryption Ardhi Wiratama Baskara Yudha† , Erwin Eko Wahyudi‡ , Rian Adam Rajagede‡ , Qian Lou‡ , Yan Solihin‡ †
Advanced Micro Devices, Inc., USA University of Central Florida, USA Email: [email protected], {wahyudierwin, rian, qian.lou, yan.solihin}@ucf.edu
arXiv:2609.04769v1 [cs.CR] 4 Sep 2026
‡
Abstract—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× speedup over the 100x GPU baseline with less than 1% accuracy loss at 50% comparison precision. Index Terms—Universal FHE, Ciphertext Compression, Ciphertext Serialization, Ciphertext Pruning
I. I NTRODUCTION Fully Homomorphic Encryption (FHE) [1] is a cryptographic technique that permits computation directly on encrypted data. It enables collaboration among non-trusting parties. A client keeps its data private by sending encrypted data to the server, the server computes on the encrypted data while keeping its own computation secret, and the client receives the computation result in encrypted form, which can only be decrypted by the client itself. Hence, FHE allows private machine learning as a service (MLaaS), making FHE a key primitive for privacy-preserving cloud computing [2]–[4]. FHE schemes differ in the native data and operations they support: word-wise schemes such as BGV [5] and CKKS [6] support integers or floating-point numbers and arithmetic operations, while bit-wise schemes such as TFHE [7] support logic operations. They are efficient for their native operations but inefficient for non-native ones; for example, wordwise schemes are inefficient for comparisons, while bit-wise schemes are inefficient for arithmetic. Recently, a BGV-based universal FHE (uFHE) scheme [8] enabled word-wise exact comparisons alongside arithmetic, making uFHE the state of the art for mixed operations with SIMD batching support, which TFHE lacks.
Regardless of the scheme, in general FHE incurs enormous ciphertext expansion rate (CER), i.e., the ciphertext is magnitudes larger than the original data. Hence, they typically show a low arithmetic intensity, i.e., few operations per byte accessed in memory (typically less than one [9]– [11]). Many techniques have been proposed to accelerate FHE computation, but their success has made the memory bottleneck (hence arithmetic intensity) even worse in relative terms. Recognizing the arithmetic intensity problem, an option to consider is to increase the GPU memory capacity or bandwidth. However, while this may accommodate FHE better, it is a costly approach. Recently, some have proposed packing multiple messages into a single ciphertext to improve slot utilization [10], [11]. None of these approaches changes the underlying inefficiency of the FHE ciphertext representations. In contrast, we propose mechanisms that directly reduce the ciphertext expansion and improve the arithmetic intensity. To this end, we propose BXT, a novel multi-level optimization framework that targets the memory bottlenecks of FHE on GPUs. BXT introduces four techniques with complementary benefits: • Ciphertext compression. BXT-C uses pseudo-random number generator (PRNG)-based ciphertext compression to regenerate ciphertext components from compact seeds during execution. BXT regenerates ciphertext matrices dynamically in the GPU memory hierarchy, reducing CER and memory traffic. • Ciphertext serialization. BXT-CS additionally serializes ciphertexts by packing coefficients as bit arrays and unpacking them during L2-to-L1 cache transfer. This layout improves cache efficiency and reduces memory bandwidth demand without redesigning arithmetic units. • Delayed seed generation. BXT-CSO further applies delayed seed generation by deferring PRNG-heavy offline work and aggregating it across multiple operations. This strategy reduces intermediate matrix loads and stores, thereby reducing memory accesses. • Ciphertext digit pruning with fault-aware training. For the uFHE scheme [8], we discover an applicationlevel opportunity. We create BXT-CSO75, BXT-CSO50, and BXT-CSO25 variants for pruning low-significance digits in comparisons, guided by fault-aware training, to reduce comparison precision while maintaining accuracy.
This approach is tailored to digit-wise encrypted operations and provides tunable accuracy-performance tradeoffs. We model and evaluate BXT using Accel-Sim [12] and compare it against several state-of-the-art FHE systems on GPUs: 100x [10], TensorFHE [3], and GME [13]. BXT increases arithmetic intensity by 1.5× and achieves up to 3.8× speedup over the 100x baseline [10], with less than 1% accuracy loss at 50% comparison precision. When integrated with GME [13], BXT speeds it up by 2.3×. II. R ELATED W ORK GPU-based Acceleration of Operations. The studies in [3], [10], [13]–[17] introduce solutions for accelerating FHE using GPUs (GPGPU). 100x [10] is the first high-performance FHE implementation on GPGPU, which supports bootstrapping for CKKS but is constrained by inadequate hardware support for modulo calculations. TensorFHE [3] enhances FHE arithmetic operations through algorithmic, Number Theoretic Transform (NTT), and data layout optimizations, and additionally leverages tensor cores to expedite NTT operations. GME [13] presents a novel network-on-chip (NoC) that connects all scratchpad memory within the GPU, minimizing main memory accesses during NTT operations. HE-Booster [14] refines these FHE operations by optimizing the GPU’s NTT computation, building on [18] with fine-grained synchronization at each NTT iteration. Recent works [16], [17] present effective schemes switching between TFHE and CKKS on GPUs. All these accelerators focus on arithmetic kernels, NTT optimization, data locality, or scheme switching. None of them reduces ciphertext size at runtime in memory, in contrast to BXT, which compresses ciphertexts and rebalances computation and memory traffic. Because BXT is orthogonal to these GPU accelerators, our techniques can be applied on top of existing GPU-based FHE implementations. ASIC/FPGA-based Acceleration of Operations. Research such as [19]–[24] focuses on integrating an NTT unit optimized for radix-2 operations into FHE accelerators. CraterLake [23] stands out as the first FHE accelerator designed for high performance across a broad range of unbounded FHE programs, surpassing earlier designs that targeted a limited range of FHE computations [22]. It features a uniprocessor setup with specialized units covering extensive vector spaces, employing static scheduling to leverage the regular patterns in FHE computations. SHARP [19] aims to cut FHE operation latency by restricting the prime modulus to just 36 bits, which reduces the memory bandwidth demands and consequently boosts performance. While ASIC/FPGA platforms offer significant acceleration and power-efficiency advantages over GPUs, they typically require longer development time and more effort to adapt to new schemes, algorithms, and implementations. In this sense, GPUs provide greater flexibility for rapid deployment and iteration. Ciphertext Compression. Ciphertext compression utilizing PRNG was proposed for reducing network communication costs [25] and for offline key-switching matrix generation
(CraterLake [23], ARK [20]). We adopt this approach as one of the four techniques of BXT, but with a major difference in that BXT utilizes this for computation, i.e., ciphertext compression is performed at runtime for computation, and components are regenerated on-the-fly in the memory hierarchy from seeds to directly reduce the memory bandwidth consumption on GPUs. III. BACKGROUND A. Universal FHE and BGV Scheme Traditional arithmetic FHE schemes such as BGV [5] primarily support arithmetic operations. Recent enhancements [8], [26] enable BGV to perform efficient word-wise comparisons while preserving its arithmetic capabilities, establishing it as a universal FHE (uFHE) solution. Alternative approaches such as TFHE-BGV [27] and TFHE-CKKS [28] require scheme-switching with over 70× latency overhead [8], making the enhanced BGV the state-of-the-art uFHE. BGV uses lattice-based encryption founded on the Ring Learning with Errors (RLWE) problem [5]. Key parameters include: N (polynomial degree, typically 216 ), Q (ciphertext modulus as a product of primes qi ), p (plaintext modulus), and L (multiplicative depth). Polynomials operate in the ring RQ = ZQ [x]/(Φm (x)), where Φm (x) is the m-th cyclotomic polynomial. Encryption. The secret key S ∈ RQ is a small polynomial with coefficients in {−1, 0, 1}. To encrypt a plaintext µ ∈ Rp , the scheme samples a random polynomial A from RQ using a seed, and computes B = −A · S + p · E + µ, where E is sampled from a Gaussian distribution. The ciphertext is C = (A, B). Crucially, A can be regenerated from its seed, enabling compression. Decryption computes µ = ((B + A · S) mod Q) mod p. Polynomial Representation & NTT. Ciphertexts consist of polynomial pairs with a degree of N and coefficients of size log(Q). To manage large Q, BGV uses the Residue Number System (RNS) via the Chinese Remainder Theorem, dividing polynomials into L + 1 residue polynomials with coefficients under moduli qi , forming a matrix of size (L+ 1)×m. The Number Theoretic Transform (NTT) enables efficient polynomial multiplication in O(N log N ) time [29]. FHE libraries [30], [31] use NTT with RNS, known as the DoubleCRT format [30], to represent polynomial coefficients as word-sized integers. BGV supports five key homomorphic operations: PADD (plaintext addition), PMULT (plaintext multiplication), HADD (ciphertext addition), HMULT (ciphertext multiplication), and HROTATE (ciphertext rotation). HADD and PADD use element-wise addition, PMULT uses Hadamard multiplication, while HMULT and HROTATE require NTT, basis conversion, and key switching [1], making them computationally intensive. B. Integer-wise Comparison To compare two encrypted integers x and y, each integer is first decomposed into l digits over Fp . Comparison is then performed digit-wise using polynomial interpolation [8] to evaluate the equality (EQ) and less-than
(LT ) functions on each pair of corresponding digits independently. Specifically, EQ(x, y) equals 1 if x = y, and 0 otherwise, while LT (x, y) equals 1 if x < y, and 0 otherwise. In the final step, the digit-level Ql−1results are aggregated lexicographically: EQ(x, y) = i=0 EQ(xi , yi ) and Ql−1 Pl−1 LT (x, y) = i=0 LT (xi , yi ) j=i+1 EQ(xj , yj ). This digitwise comparison method substantially increases the number of ciphertexts and the overall memory footprint compared to arithmetic-only FHE.
𝐆𝐏𝐔 SRAM
SRAM: 19TB/s (20 MB)
𝐆𝐏𝐔 HBM
Main Memory CPU DRAM
HBM: 1.5TB/s (40 GB) DRAM: 12.8 GB/s (>1 TB)
(a) Memory Hierarchy with Bandwidth & Memory Size
Normalized runtime
IV. M OTIVATION 100% 75%
(ciphertext compression via seed regeneration), data layout (bit-array storage), operation (delayed seed generation), and application (digit reduction in comparisons). A. Ciphertext Compression and Serialization A ciphertext comprises two matrices stored in memory. Operating on two ciphertexts requires fetching all four matrices from memory to the L2 cache and then transferring portions of them to the L1 cache for processing (Figure 2, left). With matrix sizes being large (e.g., ranging from 213 to 216 for security strength), fetching them demands significant memory bandwidth and reduces arithmetic intensity.
load
compute
compute
50% store
25%
compute
load store compute
Ours 100x (b) Runtime breakdown comparison
Fig. 1. (a) GPU memory hierarchy and (b) access inefficiencies in the GPUbased FHE accelerator (100×) highlight the need for memory-efficient uFHE designs.
L1 cache/shared mem. bits to int
Seed of Seeds
Memory
Seed of Seeds
Ctxt A
The GPU memory hierarchy in Figure 1(a) consists of multiple memory types with varying sizes and speeds. NVIDIA’s A100 GPU features 40–80 GB of HBM (1.5–2.0 TB/s bandwidth) and 192 KB of on-chip SRAM per SM (aggregate ∼19 TB/s). While SRAM is significantly faster than HBM, it is orders of magnitude smaller. As compute performance has outpaced memory speed improvements, memory has become a major bottleneck, making efficient use of on-chip SRAM critical. As shown in Figure 1(b), when the prior GPU-based FHE accelerator (100×) is adapted for uFHE comparison operations, memory operations account for over 80% of runtime. In uFHE, each digit is encrypted into a separate ciphertext, significantly increasing CER. This overhead is pronounced in DNN workloads with hundreds of non-linear comparisons (e.g., ReLU layers). The high CER leads to low ArI [9]–[11], with fewer than one arithmetic operation per byte, causing frequent memory accesses and limited data reuse. We address this through four techniques: (1) compressing ciphertexts, (2) serializing coefficients to remove redundant bits, (3) delayed seed generation, and (4) pruning less significant digits. FHE inherently expands data size, requiring large parameters for bootstrapping and security. Encrypted data can grow by hundreds of times, depending on parameters and batching utilization. Even with full batching, ciphertexts often exceed cache capacity. Limited cache space hampers locality, leading to frequent memory accesses. Memory access time dominates over cache and ALU execution combined, making memory load latency reduction essential. V. BXT D ESIGN To effectively address the issue of high CER and enhance computation efficiency, we introduce BXT, a novel multilevel optimization strategy spanning four levels: algorithm
PRNG
L2 Cache
Ctxt B
Ctxt A
Ctxt B
Fig. 2. Data flow for processing ciphertext. (Left) Data is fetched from memory through the L2 cache to the L1 cache. (Right) The ciphertext is compressed and serialized into a bit array, which is then converted to integers. A PRNG generates the read-only ciphertext portion from a seed.
To address bandwidth issues, we leverage the fact that one ciphertext matrix is randomly generated. We store only the computed matrix and a seed, regenerating the other matrix on-the-fly using a hardware-supported pseudo-random number generator (PRNG). Similar techniques were utilized for reducing the message size of ciphertext communication [25] or for offline key-switching matrix generation (CraterLake [23], ARK [20]). We adopt this approach for storing the ciphertext in memory and fetching it from memory, resulting in halving the storage requirements and reducing the memory bandwidth. Security Considerations. We assume the same threat model as the underlying BGV-based uFHE scheme: the adversary may observe public parameters, public keys, and ciphertexts stored in memory, but does not know the secret key. As with [25], we assume a PRNG producing uniformly distributed random numbers from a seed that is independent from the secret key. In BXT, the seed is used only to regenerate the random ciphertext component, rather than storing it explicitly, in order to save space. If an adversary learns the seed, they can reconstruct this regenerated random component, but this alone does not reveal the plaintext or the secret key under the standard RLWE-based security assumption. Thus, BXT does not alter the underlying cryptographic security model; it only changes how part of the ciphertext is stored and reconstructed during execution. Ciphertext serialization. We further optimize memory through data layout reorganization. Matrix elements use moduli typically up to 36 bits [19], smaller than 64 bits. By storing elements as bit arrays instead of full integers, we
eliminate unused bits, reduce the matrix sizes, and hence the memory bandwidth. One key design question is when to unpack the bits. One option is to unpack them at the load/store unit of the processor. This saves the storage in the entire cache hierarchy, but complicates the pipeline design due to the unpredictable load/store unit timing. The opposite option is to unpack them as soon as they enter the chip, before storing them in the L2 cache. This reduces the opportunity to also save space in the L2 cache. Thus, instead, we unpack during the L2-to-L1 transfer, avoiding massive compute-unit redesign while improving cache efficiency. Figure 2 (right) illustrates the optimized data flow: compressed data is fetched to L2 cache, converted from bit arrays to integers, and stored in L1 cache for GPU computation. For read-only ciphertexts, one matrix is stored while the other is generated on-the-fly via PRNG (preferably hardware-backed for lower latency). We then introduce new instructions for loading and storing ciphertexts at matrix-fragment granularity, similar to Tensor Cores [32], enabling efficient bit-to-integer conversion. 1) Load/Store Interface for Read-Only Ciphertext: For read-only ciphertexts, we optimize storage by generating one matrix dynamically from a seed while storing only the other in memory. We introduce new load/store instructions inspired by Tensor Core matrix fragments [32] that enable on-the-fly generation at warp-level granularity, allowing 32 elements to be fetched and generated simultaneously, as outlined in Table I. TABLE I P ROPOSED P SEUDO -R ANDOM N UMBER G ENERATOR I NSTRUCTIONS . Variable declaration and interfaces for load/store PRNG-generated matrix wmma::fragment<unused, num_of_element, unused, unused, unused, unused> A_frag wmma::load_limb_fragment_prng(A_frag, seed+index, modulus); wmma::store_limb_fragment_prng(mem_destination, A_frag, modulus);
The num_of_element parameter in the variable declaration specifies the number of elements in the fragment limb to be generated, allowing operations to be executed with warplevel granularity. Given that the current FHE implementation fetches one element of a ciphertext matrix per thread, setting num_of_element to 32 allows for fetching and generating 32 elements simultaneously, thereby enhancing efficiency. 2) Load/Store Interface for Data Layout Modification: The matrix stored in memory is represented as an array of bits, requiring conversion to recover integers for computation. To facilitate this conversion, we introduce specific variable declarations and load/store instructions, as detailed in Table II. As depicted in the table, we begin by declaring a variable to hold the fetched matrix elements, specifying the exact number of elements to be retrieved. This initial declaration sets up the framework for efficient data handling and ensures that the matrix elements are fetched in the required format. Subsequently,
TABLE II P ROPOSED DATA L AYOUT C ONVERTER I NSTRUCTIONS . Variable declaration and interface for load/store compressed ciphertext wmma::fragment<unused, num_of_element, unused, unused, unused, unused> A_frag wmma::load_limb_fragment(A_frag, mem_source, log2(modulus)); wmma::store_limb_fragment(mem_destination, A_frag, log2(modulus));
the load/store instructions are employed to retrieve the array of bits and transform the layout into 64-bit integers. This layout transformation is facilitated by dedicated hardware positioned between the L1 and L2 caches. Notably, the number of bits to be converted into a single 64-bit integer is specified as the final argument in the new load/store instructions. B. Ciphertext Operation Optimization For operations such as PMULT, PADD, and HADD, performance is primarily limited by matrix loads and stores rather than computation. For example, in HADD, 67% of the execution time is spent on matrix loads and 29% on matrix stores, while only about 4% is used for computation, kernel launch, and modulus data fetching. This breakdown shows that reducing matrix load and store overhead is critical to lowering latency and improving overall performance. PMULT
HADD
PADD
Remove unnecessary load/store
Generate
*W
+
*W
+
+ C
+ C
Memory
Load
Time
Store
Fig. 3. Timeline diagram depicting the matrix loads and stores for the sequential operations of PMULT, HADD, and PADD. Combining these operations will reduce the number of loads/stores for the matrix, as highlighted by the red oval lines.
We propose aggregating common operation sequences such as PMULT, HADD, and PADD to reduce data movement overhead. This optimization is motivated by their frequent use in convolutional and fully connected layers in neural networks. For example, to compute x · w + b, where x is ciphertext and w and b are plaintext, PMULT and HADD are first used to compute x · w, followed by PADD to add b. As shown in Figure 3, aggregation removes the intermediate memory transfers highlighted by the red dashed ovals, reducing matrix loads and stores and thus improving efficiency and latency. We also propose another operation-level optimization, which we term delayed seed generation. As shown in Figure 4, the stages of the PMULT, HADD, and PADD operations can be divided into online and offline stages. The online stage involves loading matrices from memory, while the offline stage bypasses matrix loads by generating data through a PRNG
PMULT HADD *W +
PADD + C
ONLINE Generate
*W +
+C
OFFLINE
Memory Load
Store
Time
Fig. 4. Timeline diagram illustrating the online and offline stages of the PMULT, HADD, and PADD operations, with the offline parts delayed to conserve matrix loads.
engine. Additionally, the offline parts of the operations can be postponed until needed, allowing them to be combined with the online parts in operations that require both matrices, such as HMULT or HROTATE operations. Delaying the offline stage in this way helps conserve matrix loads, thus reducing the execution times of the operations. After each operation, the output ciphertext is stored in an uncompressed form because the seed representation cannot be directly propagated through these operations. C. Ciphertext Pruning Our last optimization is specific to a BGV-based universal FHE (uFHE) scheme [8] that enables fast word-wise exact comparisons by operating digit-wise. Without uFHE, comparison operations are very slow compared to arithmetic operations, and therefore various scheme switching techniques have been proposed. uFHE enables fast comparisons by operating on encrypted digits, but it requires each digit to be stored in a separate ciphertext. As described in Section III-B, uFHE performs comparisons in a digit-wise manner and then combines the digit-level results to produce the final comparison result. To speed up comparisons, we propose reducing the number of digits used. As shown in Figure 5, the digit decomposer outputs five digits, yet only three are used in the comparison. The number of digits to retain is determined beforehand by the decomposer. By intentionally discarding low-significance digits, we reduce the effective comparison precision: fewer ciphertexts are stored and compared, resulting in a lower computational load and faster processing. Pruning and precision reduction are widely used in machine learning [33], but applying reduced-precision pruning directly at the ciphertext-digit level for encrypted comparisons is, to our knowledge, novel.
Input 1
Digit decomposer
Digit 0
Digit 0
Digit 1
Digit 1
Digit 2
Digit 2
Digit 3
Digit 3
Digit 4
Digit 4
However, it is important to acknowledge that disregarding certain digits can lead to errors in comparisons. In machine learning workloads, minor errors are typically acceptable if the resulting drop in inference accuracy is minimal and remains within acceptable limits. Identifying the optimal level of precision reduction that still yields reliable outcomes is essential. Furthermore, we mitigate the decreases in inference accuracy by training the network differently. In particular, we can regard ciphertext pruning as logically equivalent to the network operating in a faulty environment [34]. After all, disregarding several least significant digits may result in an incorrect comparison outcome, similar to when those same digits are affected by faults. Therefore, we can utilize faultaware training to add robustness to the network. This approach involves training the model with a custom ReLU function designed to produce the same erroneous outputs as those which may have been caused by digit reduction. This method allows the model to anticipate and correct these specific types of errors during its operation. To perform this training, we set a parameter x that limits the faults to (100 − x)% of the least significant digits. For example, x = 75 means only 25% of the least significant digits are injected with faults. We note that, as shown in many prior studies, there may be a trade-off between robustness and accuracy, that is, the more robust a network is against faults, the lower its accuracy. Hence, we need to find this sweet spot between accuracy preservation and robustness against ciphertext pruning. VI. M ETHODOLOGY A. Evaluation Environment We extend BXT starting with 100x [10] as a base. Then, we model it on Accel-sim [12] configured with Nvidia RTX A6000 architecture (Ampere architecture, Table III). Each streaming multiprocessor (SM) has a 40-cycle PRNG [35] and a 2-cycle bit-to-int converter. TABLE III GPU C ONFIGURATION Aspect SM Configuration Register File Process Size L1D and Shared Mem. L2 cache DRAM
Digit decomposer
Input 2
Fig. 5. Comparing two numbers begins with decomposing each number into digits. The digits colored black show the digits used in comparison, while the digits in gray are unused.
Configuration 84 SMs, 1410 MHz 256 KB/SM, 20.5 MB in total 8 nm 128 KB 2 banks per memory partition, each L2 cache bank is 128 KB, 6 MB in total. 48 GB at 1219 MHz, 24 partitions, 936.2 GB/s
We employ FHE parameters from [13] that are conducive to bootstrapping and provide 128-bit security (λ = 128): the polynomial degree N = 216 , ciphertext modulus bit-length log(Q) = 1728, with L = 23 levels for computation and Lboot = 17 for bootstrapping, and a decomposition number dnum = 3.
Table IV lists our BXT variants arranged based on increasing number of optimizations (BXT-C, BXT-CS, and BXTCSO) and whether ciphertext pruning at various levels is applied (BXT-CSO75, BXT-CSO50, and BXT-CSO25). TABLE IV BXT VARIANTS Scheme BXT-C BXT-CS BXT-CSO BXT-CSO75 BXT-CSO50 BXT-CSO25
Brief Description our scheme with PRNG optimization BXT-C plus bit-serialization layout optimization BXT-CS plus operation optimization (delayed seed generation) BXT-CSO with (100-75)% ciphertext digits pruned BXT-CSO with (100-50)% ciphertext digits pruned BXT-CSO with (100-25)% ciphertext digits pruned
In addition to evaluating BXT variants’ performance, we will put BXT’s performance in the context of several state-ofthe-art FHE systems on GPUs: 100x [10], TensorFHE [3], and GME [13] (Section VII-C). We note that these systems do not perform ciphertext compression; therefore, BXT is orthogonal to them and can be integrated with them. To demonstrate this, we combine BXT with GME and show that their combined speedups greatly outweigh each one on its own. Finally, fault-aware training (Section V-C) is performed in plaintext. We inject errors into ReLU during training by inverting outputs at a specified rate (e.g., outputting x when x < 0 should output 0), enabling the network to develop robustness for reduced-precision encrypted inference. VII. E VALUATION R ESULTS A. Homomorphic Operation Performance We evaluate the speedup of each homomorphic operation in BXT relative to the 100x baseline [10], as shown in Figure 6. BXT-C adds PRNG-based ciphertext compression that generates ciphertext matrices on-the-fly from a seed, BXT-CS additionally serializes ciphertexts into bit arrays, and BXT-CSO further applies ciphertext operation optimizations (delayed seed generation). We report results for PADD, PMULT, HADD, HMULT, and HROTATE. Across all operations, BXT achieves consistent speedups over the baseline: 1.3× for BXT-C, 2.5× for BXT-CS, and
PADD
100x
BXT-C
BXT-CS
PMULT
HADD
HMULT
BXT-CSO
HROTATE
HE Operation
GMEAN
Fig. 6. Execution time speedup over the 100x baseline [10] for each homomorphic operation.
2.9× for BXT-CSO on average, with BXT-C alone ranging from 1.2× to 1.7×. These gains mainly come from reducing matrix loads and stores via the PRNG engine, which is especially beneficial for memory-bound operations such as HADD, where PRNG avoids loading two matrices. The layout modification in BXT-CS, which restructures ciphertext storage and access, nearly doubles the speedup over BXT-C by improving data layout and retrieval. Ciphertext operation optimizations in BXT-CSO further remove unnecessary loads and stores during the offline stage, but only for PADD, PMULT, and HADD, so HMULT and HROTATE do not benefit from BXT-CSO. To understand the source of these gains, we also measured the number of instructions and cache accesses. Figure 7 (top) shows that each optimization reduces total L1 accesses, and Figure 7 (bottom) shows a similar decrease in GPU instructions; L2 accesses and misses follow the same trend, while L1/L2 miss rates remain roughly unchanged. Thus, the speedups primarily stem from fewer instructions and memory accesses without degrading cache locality. Furthermore, across all homomorphic operations with all BXT optimizations enabled (BXT-CSO), we achieve a geometric-mean arithmetic intensity increase of 1.5× over the baseline, indicating better utilization of memory bandwidth in these memory-bound uFHE workloads. 100x
Normalized L1 Total Accesses
C. Schemes Evaluated
5 4 3 2 1 0
1.00 0.75 0.50 0.25 0.00
PADD
PMULT 100x
Normalized Total GPU Instructions
We evaluate five homomorphic operations (PADD, PMULT, HADD, HMULT, HROTATE) using BGV kernels [10], and two ML workloads on encrypted MNIST data [36]: Logistic Regression classifies digits 3 vs. 8. Each 28 × 28 image is encrypted into P 784 ciphertexts (one per pixel). Inference computes S = wi xi with plaintext weights, outputting 1 if S ≥ 0, and 0 otherwise. CNN uses five layers from CryptoDL [37]: Conv (5 × 5 kernels, stride 2), ReLU (ReLU (x) = x · (1 − LT (x, 0))), FC (100 nodes), ReLU, and Output (10 nodes). Unlike prior work using polynomial approximations [14], we employ exact ReLU via encrypted comparison.
Speedup
B. Workloads Evaluated
1.00 0.75 0.50 0.25 0.00
PADD
PMULT
BXT-C
BXT-CS
BXT-CSO
HADD HMULT HROTATE HE Operation BXT-C BXT-CS BXT-CSO
HADD
HE Operation
HMULT
HROTATE
Fig. 7. Total L1 accesses (top) and number of GPU instructions (bottom), normalized to the baseline 100x for each homomorphic operation.
B. Machine Learning Application Results 1) Performance Speedup: Figure 8 shows speedups for Logistic Regression and CNN. BXT-CSO achieves 2.8× (LR) and 2.4× (CNN) at full precision. With digit pruning, BXTCSO50 (50% precision) reaches 3.8× (LR/CNN), while BXTCSO25 (25% precision) achieves 4.4× (LR) and 5.8× (CNN).
Accuracy (%)
BXT
x
100
O O75 CSO50 CSO25 -CS -CS BXT BXT BXT BXT
x
100
Logistic Regression
Arithmetic vs. ReLU Breakdown (CNN): ReLU operations dominate CNN latency due to costly ciphertext comparisons that require many ciphertext multiplications. All BXT variants improve both arithmetic and ReLU performance, and with aggressive pruning (BXT-CSO50), ReLU speedup climbs to 4.2× while still accounting for most of the latency, confirming that optimizing ReLU is critical for uFHE performance. 2) Precision Reduction Impact on Accuracy: Table V presents the accuracy results for logistic regression and CNN workloads at various levels of precision reduction. For logistic regression, reducing precision to 75% and 50% has little impact on accuracy, while 25% precision causes a drop of more than 3%. Thus, maintaining at least 50% precision is advantageous, providing up to 3.8× speedup without sacrificing accuracy. For CNN, fault-aware training mitigates the impact of reduced precision, limiting the accuracy drop to less than 1% at 50% precision and less than 2% at 25% precision. TABLE V ACCURACY RESULTS FOR L OGISTIC R EGRESSION AND CNN MODELS AT VARYING LEVELS OF PRECISION . Logistic Regression Accuracy (%) 95.81 95.81 95.87 92.49
CNN Accuracy (%) 98.56 98.32 97.83 96.62
Figure 9 shows the impact of different training strategies on CNN accuracy at reduced precision. Without fault-aware training, reducing precision to 25% causes an accuracy drop of over 15%. Conversely, the FA-25 model, trained with faultaware training at 25% precision, experiences a less significant accuracy drop of under 2%. This reduction could be tolerable, considering that with 25% comparison precision, the model achieves a speedup of more than 5×. This demonstrates that fault-aware training is effective in enabling a larger degree of ciphertext digit reduction without sacrificing much accuracy. C. Comparison with Other Methods Figure 10 shows the speedup of our schemes, TensorFHE [3], and GME [13] relative to the 100x baseline [10] for CNN applications. BXT-CSO, which uses all optimizations except comparison-precision reduction, outperforms TensorFHE but not GME. Because our optimizations are orthogonal to those of GME, combining BXT-CSO with GME yields a 5.7× speedup over the baseline, corresponding to a 1.5× speedup over GME.
1% drop 2% drop 82.6%
100
75 50 Comparison Precision (%) Original FA-75 FA-50
CNN
Fig. 8. Speedup for Logistic Regression (left) and CNN (right) with varying precision.
Comparison Precision 100% 75% 50% 25%
100 98 96 94 92
O O75 CSO50 CSO25 -CS -CS BXT BXT BXT BXT
25 FA-25
Fig. 9. CNN accuracy with fault-aware training. FA-XX: trained at XX% precision.
Speedup
Speedup
100x 6 5 4 3 2 1 0
10 8 6 4 2 0
100x
TensorFHE BXT-CSO
GME
BXT-CSO BXT-CSO50 + GME + GME
Fig. 10. Comparison of the speedup achieved by TensorFHE, BXT-CSO, GME, BXT-CSO + GME, and BXT-CSO50 + GME relative to the baseline (100x) for CNN applications.
With a 50% comparison-precision reduction, BXT-CSO50 combined with GME achieves a 9.2× speedup with less than 1% accuracy loss, corresponding to a 2.3× speedup over GME. This result shows that BXT integrates easily with complementary GPU acceleration techniques while maintaining high efficiency and minimal accuracy impact. VIII. D ISCUSSION Generalizability. Compression and serialization apply broadly to FHE schemes but are most effective for memory-bound uFHE. Delayed seed generation is workload-dependent, determined by data formats and operation patterns. Ciphertext pruning is particularly effective for ReLU and other activation functions where LSB accuracy is less critical, and it also extends to non-linear operations like division and sorting. Microarchitecture Integration & Overhead. BXT’s serialization requires a bit-to-integer converter between L2 and L1 cache (2-cycle latency assumed). Sensitivity analysis (2— 32 cycles) shows negligible performance impact due to the memory-bound nature of uFHE. PRNG hardware (40-cycle latency per SM) is available in modern GPUs [35]. The additional hardware support is limited in scope: the converter uses simple bit-packing logic, and PRNG units are already present in GPUs. Our techniques integrate into existing GPU architectures without invasive changes, unlike custom NoCs (GME [13]) or specialized functional units (CraterLake [23]). Compression vs. Generic Methods. Generic compression (e.g., gzip, LZ4) fails on ciphertexts due to high entropy from encryption’s diffusion property. BXT exploits FHEspecific structure: (1) seeded PRNG regeneration leverages BGV’s deterministic polynomial generation, and (2) serialization removes unused bits based on known modulus sizes. Domain-specific knowledge is essential for effective ciphertext compression.
IX. C ONCLUSION In this study, we addressed the substantial computational demands of FHE by introducing a novel multi-level strategy for reducing memory usage in FHE computation, derived from algorithmic insights, application-specific considerations, and data access patterns. Through evaluation on CNN workloads, we achieved a notable speedup of 3.8× compared to the 100x baseline with less than 1% accuracy reduction. This highlights the effectiveness of reducing memory accesses in highly memory-constrained workloads, leading to a significant acceleration in execution time. ACKNOWLEDGMENT We thank the reviewers for their valuable comments. This work was supported in part by the National Science Foundation under Grant No. 2413232. The views expressed are those of the authors and do not necessarily reflect those of the NSF. R EFERENCES [1] C. Gentry, S. Halevi, and N. Smart, “Fully homomorphic encryption with polylog overhead,” in Advances in Cryptology - EUROCRYPT 2012, vol. 7237, pp. 465–482, 2012. [2] Amazon Science, “Machine learning models that act on encrypted data.” https://www.amazon.science/blog/ machine-learning-models-that-act-on-encrypted-data, Nov 2020. Accessed: 2025-09-07. [3] S. Fan, Z. Wang, W. Xu, R. Hou, D. Meng, and M. Zhang, “Tensorfhe: Achieving practical computation on encrypted data using gpgpu,” in Proc. 29th HPCA, pp. 922–934, 2023. [4] B. Reagen, W.-S. Choi, Y. Ko, V. T. Lee, H.-H. S. Lee, G.-Y. Wei, and D. Brooks, “Cheetah: Optimizing and accelerating homomorphic encryption for private inference,” in Proc. 27th HPCA, pp. 26–39, IEEE, 2021. [5] Z. Brakerski, C. Gentry, and V. Vaikuntanathan, “(leveled) fully homomorphic encryption without bootstrapping,” ACM Transactions on Computation Theory, vol. 6, no. 3, pp. 1–36, 2014. [6] J. H. Cheon, A. Kim, M. Kim, and Y. Song, “Homomorphic encryption for arithmetic of approximate numbers,” in Advances in Cryptology – ASIACRYPT 2017, pp. 409–437, 2017. [7] I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène, “Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds,” in Advances in Cryptology – ASIACRYPT 2016, pp. 3–33, 2016. [8] I. Iliashenko and V. Zucca, “Faster homomorphic comparison operations for bgv and bfv,” Proc. on Privacy Enhancing Technologies, vol. 2021, no. 3, pp. 246–264, 2021. [9] L. de Castro, R. Agrawal, R. Yazicigil, A. Chandrakasan, V. Vaikuntanathan, C. Juvekar, and A. Joshi, “Does fully homomorphic encryption need compute acceleration?,” arXiv preprint arXiv:2112.06396, 2021. [10] W. Jung, S. Kim, J. H. Ahn, J. H. Cheon, and Y. Lee, “Over 100x faster bootstrapping in fully homomorphic encryption through memory-centric optimization with gpus,” IACR TCHES, vol. 2021, no. 4, p. 114–148, 2021. [11] R. Agrawal, L. De Castro, C. Juvekar, A. Chandrakasan, V. Vaikuntanathan, and A. Joshi, “Mad: Memory-aware design techniques for accelerating fully homomorphic encryption,” in Proc. 56th MICRO, p. 685–697, 2023. [12] M. Khairy, Z. Shen, T. M. Aamodt, and T. G. Rogers, “Accel-sim: An extensible simulation framework for validated gpu modeling,” in Proc. 47th ISCA, pp. 473–486, 2020. [13] K. Shivdikar, Y. Bao, R. Agrawal, M. Shen, G. Jonatan, E. Mora, A. Ingare, N. Livesay, J. L. AbellÁN, J. Kim, A. Joshi, and D. Kaeli, “Gme: Gpu-based microarchitectural extensions to accelerate homomorphic encryption,” in Proc. 56th MICRO, p. 670–684, 2023. [14] Z. Wang, P. Li, R. Hou, Z. Li, J. Cao, X. Wang, and D. Meng, “Hebooster: An efficient polynomial arithmetic acceleration on gpus for fully homomorphic encryption,” IEEE Trans. on Parallel and Distributed Systems, vol. 34, no. 4, pp. 1067–1081, 2023.
[15] W. Choi, J. Kim, and J. H. Ahn, “Cheddar: A swift fully homomorphic encryption library designed for gpu architectures,” in Proc. 31st ASPLOS, Volume 1, p. 35–49, 2025. [16] X. Deng, S. Fan, Z. Hu, Z. Tian, Z. Yang, J. Yu, D. Cao, D. Meng, R. Hou, M. Li, Q. Lou, and M. Zhang, “Trinity: A general purpose fhe accelerator,” in Proc. 57th MICRO, pp. 338–351, 2024. [17] Z. Wang, H. He, L. Zhao, P. Li, Z. Li, D. Meng, and R. Hou, “Chameleon: An efficient fhe scheme switching acceleration on gpus,” IEEE Trans. on Parallel and Distributed Systems, vol. 36, no. 11, pp. 2264–2280, 2025. [18] O. Özerk, C. Elgezen, A. C. Mert, E. Öztürk, and E. Savaş, “Efficient number theoretic transform implementation on gpu for homomorphic encryption,” J. Supercomput., vol. 78, p. 2840–2872, Feb. 2022. [19] J. Kim, S. Kim, J. Choi, J. Park, D. Kim, and J. H. Ahn, “Sharp: A shortword hierarchical accelerator for robust and practical fully homomorphic encryption,” in Proc. 50th ISCA, 2023. [20] J. Kim, G. Lee, S. Kim, G. Sohn, M. Rhu, J. Kim, and J. H. Ahn, “Ark: Fully homomorphic encryption accelerator with runtime data generation and inter-operation key reuse,” in Proc. 55th MICRO, pp. 1237–1254, 2022. [21] S. Kim, J. Kim, M. J. Kim, W. Jung, J. Kim, M. Rhu, and J. H. Ahn, “Bts: An accelerator for bootstrappable fully homomorphic encryption,” in Proc. 49th ISCA, p. 711–725, 2022. [22] N. Samardzic, A. Feldmann, A. Krastev, S. Devadas, R. Dreslinski, C. Peikert, and D. Sanchez, “F1: A fast and programmable accelerator for fully homomorphic encryption,” in Proc. 54th MICRO, p. 238–252, 2021. [23] N. Samardzic, A. Feldmann, A. Krastev, N. Manohar, N. Genise, S. Devadas, K. Eldefrawy, C. Peikert, and D. Sanchez, “Craterlake: A hardware accelerator for efficient unbounded computation on encrypted data,” in Proc. 49th ISCA, p. 173–187, 2022. [24] Y. Zhu, X. Wang, L. Ju, and S. Guo, “Fxhenn: Fpga-based acceleration framework for homomorphic encrypted cnn inference,” in Proc. 29th HPCA, pp. 896–907, 2023. [25] R. A. Mahdavi, A. Diaa, and F. Kerschbaum, “He is all you need: Compressing fhe ciphertexts using additive he,” arXiv preprint arXiv:2303.09043, 2023. [26] A. W. B. Yudha, J. Xue, Q. Lou, H. Zhou, and Y. Solihin, “Boostcom: Towards efficient universal fully homomorphic encryption by boosting the word-wise comparisons,” in Proc. PACT 2024, p. 121–132, 2024. [27] C. Boura, N. Gama, M. Georgieva, and D. Jetchev, “Chimera: Combining ring-lwe-based fully homomorphic encryption schemes,” Journal of Mathematical Cryptology, vol. 14, no. 1, pp. 316–338, 2020. [28] W.-j. Lu, Z. Huang, C. Hong, Y. Ma, and H. Qu, “Pegasus: bridging polynomial and non-polynomial evaluations in homomorphic encryption,” in Proc. 42nd S&P, pp. 1057–1073, IEEE, 2021. [29] J. W. Cooley and J. W. Tukey, “An algorithm for the machine calculation of complex fourier series,” Mathematics of Computation, vol. 19, no. 90, pp. 297–301, 1965. [30] S. Halevi and V. Shoup, “Design and implementation of helib: a homomorphic encryption library.” Cryptology ePrint Archive, Paper 2020/1481, 2020. [31] A. Al Badawi, J. Bates, F. Bergamaschi, D. B. Cousins, S. Erabelli, N. Genise, S. Halevi, H. Hunt, A. Kim, Y. Lee, Z. Liu, D. Micciancio, I. Quah, Y. Polyakov, S. R.V., K. Rohloff, J. Saylor, D. Suponitsky, M. Triplett, V. Vaikuntanathan, and V. Zucca, “Openfhe: Open-source fully homomorphic encryption library,” in Proc. 10th WAHC, p. 53–63, 2022. [32] S. Markidis, S. W. D. Chien, E. Laure, I. B. Peng, and J. S. Vetter, “NVIDIA Tensor Core Programmability, Performance & Precision,” in Proc. IPDPSW 2018, pp. 522–531, May 2018. [33] E. J. Michaud, Z. Liu, and M. Tegmark, “Precision machine learning,” Entropy, vol. 25, no. 1, 2023. [34] U. Zahid, G. Gambardella, N. J. Fraser, M. Blott, and K. Vissers, “Fat: Training neural networks for reliable inference under hardware faults,” in 2020 IEEE International Test Conference, pp. 1–10, IEEE, 2020. [35] S. Yuan, A. W. Baskara Yudha, Y. Solihin, and H. Zhou, “Analyzing secure memory architecture for gpus,” in Proc. ISPASS 2021, pp. 59– 69, 2021. [36] Y. LeCun, “The mnist database of handwritten digits,” http://yann.lecun.com/exdb/mnist/, 1998. [37] E. Hesamifard, H. Takabi, and M. Ghasemi, “Cryptodl: Deep neural networks over encrypted data,” arXiv preprint arXiv:1711.05189, 2017.