PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Ardhi Wiratama Baskara Yudha, Erwin Eko Wahyudi, Rian Adam Rajagede, Qian Lou, Yan Solihin

arXiv:2609.04769v1cs.CR

TL;DR

GPU-based uFHE comparisons are memory-bound because ciphertext expansion lowers arithmetic intensity. BXT targets that bottleneck with a multilevel memory-optimization framework; on CNN workloads, it reports 3.8× speedup over the 100x baseline with less than 1% accuracy loss at 50% comparison precision.

  • Problem

    GPU-based uFHE comparisons are memory-bound because ciphertext expansion lowers arithmetic intensity, while prior packing approaches do not change ciphertext representation inefficiency.

    Source: §I · p. 1, §IV · p. 3

  • Method

    BXT is a multilevel framework that targets FHE memory bottlenecks through ciphertext compression, serialization, delayed seed generation, and ciphertext digit pruning.

    Source: §I · p. 1, §IV · p. 3

  • Results

    3.8× speedup over the 100x baseline with less than 1% accuracy loss at 50% comparison precision is reported for CNN inference.

    Source: §I · p. 2, 2) Precision Reduction Impact on… · p. 7, §IX · p. 8

  • Takeaways & Limitations

    BXT's memory-focused strategy is effective for highly memory-constrained FHE workloads, including CNN inference.

    Source: §IX · p. 8

    Delayed seed generation is workload-dependent, with its applicability determined by data formats and operation patterns.

    Source: §VIII · p. 7

Abstract

from arXiv · show

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.

I. INTRODUCTION

BXT targets FHE’s memory bottleneck by reducing ciphertext expansion and improving arithmetic intensity through complementary optimizations. For BGV-based universal FHE, the framework also applies fault-aware digit pruning to comparison operations.

I. INTRODUCTION

  • FHE enables computation on encrypted data, while word-wise schemes support arithmetic and BGV-based uFHE adds exact comparisons with SIMD batching for mixed operations.Word-wise schemes are inefficient for comparisons, whereas bit-wise schemes are inefficient for arithmetic.Source: §I · p. 1
  • FHE’s large ciphertext expansion yields low arithmetic intensity, and prior GPU-capacity or slot-packing approaches do not change ciphertext-representation inefficiency.The paper motivates directly reducing ciphertext expansion to improve arithmetic intensity.Source: §I · p. 1
  • BXT-C regenerates ciphertext components from compact seeds in GPU memory, while BXT-CS packs coefficients as bit arrays and unpacks them during L2-to-L1 transfer.These techniques reduce memory traffic and bandwidth demand without redesigning arithmetic units.Source: §I · p. 1
  • BXT-CSO defers PRNG-heavy offline seed generation and aggregates it across operations to reduce intermediate matrix loads, stores, and memory accesses.This optimization builds on BXT-CS.Source: §I · p. 1
  • For uFHE, BXT-CSO75, BXT-CSO50, and BXT-CSO25 prune low-significance comparison digits using fault-aware training to trade comparison precision for accuracy and performance.The approach is tailored to digit-wise encrypted operations and is designed to maintain accuracy.Source: §I · pp. 1–2
  • 1.5× arithmetic intensity increase, up to 3.8× speedup over the 100x baseline, and 2.3× speedup when BXT is integrated with GME.BXT achieves less than 1% accuracy loss at 50% comparison precision.Source: §I · p. 2

II. RELATED WORK · III. BACKGROUND · A. Universal FHE and BGV Scheme

Prior FHE accelerators optimize arithmetic, memory locality, or scheme switching, while BXT uses runtime ciphertext compression to reduce GPU memory traffic. Enhanced BGV provides a universal FHE scheme with efficient word-wise comparisons while retaining arithmetic capabilities.

II. RELATED WORK

  • BXT complements GPU FHE accelerators by compressing ciphertexts at runtime, unlike prior work focused on arithmetic kernels, NTT optimization, data locality, or scheme switching.The paper states that BXT's techniques can be applied on top of existing GPU-based FHE implementations.Source: §II · p. 2
  • ASIC/FPGA FHE accelerators can offer acceleration and power efficiency, while GPUs provide greater flexibility for rapid deployment and iteration.CraterLake targets broad unbounded FHE programs, while SHARP reduces memory-bandwidth demand by restricting the prime modulus to 36 bits.Source: §II · p. 2
  • PRNG-based ciphertext compression previously reduced communication costs and supported offline key-switching matrix generation; BXT instead regenerates components from seeds on-the-fly during computation.This runtime use targets memory-bandwidth consumption on GPUs.Source: §II · p. 2

A. Universal FHE and BGV Scheme

  • Enhanced BGV enables efficient word-wise comparisons while preserving arithmetic, making it the state-of-the-art uFHE; TFHE-BGV and TFHE-CKKS require scheme switching with over 70× latency overhead..Source: A. Universal FHE and BGV Scheme · p. 2
  • BGV is based on RLWE and parameterized by polynomial degree N, ciphertext modulus Q, plaintext modulus p, and multiplicative depth L.Its polynomials operate in RQ = ZQ[x]/(Φm(x)); the passage gives N as typically 216.Source: A. Universal FHE and BGV Scheme · p. 2
  • BGV encrypts µ as ciphertext C = (A, B), where A is sampled using a seed and can be regenerated, enabling compression.B = −A · S + p · E + µ, and decryption computes µ = ((B + A · S) mod Q) mod p.Source: A. Universal FHE and BGV Scheme · p. 2
  • BGV represents polynomials using RNS residues under moduli qi, and NTT enables polynomial multiplication in O(N log N) time.FHE libraries use the RNS-plus-NTT DoubleCRT format to represent coefficients as word-sized integers.Source: A. Universal FHE and BGV Scheme · p. 2
  • BGV supports PADD, PMULT, HADD, HMULT, and HROTATE; HMULT and HROTATE require NTT, basis conversion, and key switching, making them computationally intensive.HADD and PADD use element-wise addition, while PMULT uses Hadamard multiplication.Source: A. Universal FHE and BGV Scheme · p. 2

B. Integer-wise Comparison · IV. MOTIVATION

Integer-wise comparison decomposes encrypted integers into digits and compares corresponding digits, increasing ciphertext count and memory use. In uFHE, memory access dominates comparison workloads, motivating four memory-reduction techniques.

B. Integer-wise Comparison

  • Each encrypted integer is decomposed into l digits over Fp, and corresponding digit pairs are evaluated independently using polynomial interpolation.Source: B. Integer-wise Comparison · p. 2
  • Digit-level EQ and LT outputs are aggregated lexicographically to determine the integer comparison.EQ is 1 when x = y and 0 otherwise; LT is 1 when x < y and 0 otherwise.Source: B. Integer-wise Comparison · p. 3
  • Digit-wise comparison substantially increases ciphertext count and overall memory footprint compared with arithmetic-only FHE.Source: B. Integer-wise Comparison · p. 3

IV. MOTIVATION

  • 40–80 GB of A100 HBM provides 1.5–2.0 TB/s bandwidth, while 192 KB of SRAM per SM reaches ∼19 TB/s aggregate bandwidth.SRAM is much faster but orders of magnitude smaller, and memory has become a bottleneck as compute performance has outpaced memory-speed improvements.Source: §IV · p. 3
  • Over 80% of runtime is spent on memory operations when the prior 100× GPU-based FHE accelerator is adapted for uFHE comparisons.High ciphertext expansion ratio (CER) yields fewer than one arithmetic operation per byte, with hundreds of nonlinear comparisons in DNN workloads such as ReLU layers.Source: §IV · p. 3
  • BXT addresses uFHE comparison memory overhead through ciphertext compression, coefficient serialization, delayed seed generation, and pruning less significant digits.Source: §IV · p. 3
  • Encrypted data can grow by hundreds of times, and ciphertexts often exceed cache capacity even with full batching.Limited cache space reduces locality; memory-access time dominates cache and ALU execution combined, making load-latency reduction essential.Source: §IV · p. 3

V. BXT DESIGN · A. Ciphertext Compression and Serialization

BXT addresses FHE memory bottlenecks with optimizations spanning algorithm, data layout, operation, and application levels. Its ciphertext compression and serialization reduce storage and bandwidth demands while reconstructing data during execution.

V. BXT DESIGN

  • BXT combines four optimization levels: seed-regenerated ciphertext compression, bit-array data layout, delayed seed generation, and comparison digit reduction.These span algorithm, data layout, operation, and application levels.Source: §V · p. 3

A. Ciphertext Compression and Serialization

  • Ciphertexts comprise two matrices, and processing two ciphertexts requires fetching all four; their large sizes (2^13 to 2^16) raise bandwidth demand and reduce arithmetic intensity.The passage gives matrix sizes as ranging from 2^13 to 2^16 for security strength.Source: A. Ciphertext Compression and… · p. 3
  • Storing one computed matrix and a seed lets a hardware-supported PRNG regenerate the other matrix on-the-fly, halving storage requirements and reducing memory bandwidth.The regenerated matrix is the randomly generated ciphertext component.Source: A. Ciphertext Compression and… · p. 3, Figure 2 · p. 3
  • BXT assumes the underlying BGV-based uFHE threat model; learning the seed alone does not reveal plaintext or the secret key under the standard RLWE-based security assumption.The seed is independent of the secret key and regenerates only the random ciphertext component, so this changes storage and reconstruction, not the underlying security model.Source: A. Ciphertext Compression and… · p. 3
  • Storing matrix elements as bit arrays instead of full integers eliminates unused bits, shrinking matrices and reducing memory bandwidth.The passage notes moduli typically use up to 36 bits, less than 64-bit integers.Source: A. Ciphertext Compression and… · pp. 3–4
  • Unpacking during L2-to-L1 transfer preserves L2 cache savings while avoiding unpredictable load/store timing and major compute-unit redesign.Compressed data is converted from bit arrays to integers before entering L1 for GPU computation.Source: Figure 2 · p. 3, A. Ciphertext Compression and… · p. 4
  • New matrix-fragment-granularity load/store instructions enable efficient bit-to-integer conversion; read-only ciphertexts store one matrix and regenerate the other via PRNG.The instructions are similar to Tensor Cores, and hardware-backed PRNG is preferred for lower latency.Source: A. Ciphertext Compression and… · p. 4

1) Load/Store Interface for Read-Only Ciphertext: · 2) Load/Store Interface for Data Layout Modification:

The read-only ciphertext interface stores one matrix and regenerates the other from a seed, while the data-layout interface retrieves bit arrays and converts them into integers for computation. Both use specialized load/store instructions to support efficient data handling.

1) Load/Store Interface for Read-Only Ciphertext:

2) Load/Store Interface for Data Layout Modification:

B. Ciphertext Operation Optimization

The section targets memory-bound ciphertext operations by reducing matrix transfers through operation aggregation and delayed seed generation. Aggregation removes intermediate transfers, while delaying offline work conserves matrix loads.

B. Ciphertext Operation Optimization

  • In HADD, matrix loads consume 67% of execution time and stores 29%, while computation, kernel launch, and modulus data fetching together use about 4%.This breakdown motivates reducing matrix load and store overhead for PMULT, PADD, and HADD.Source: B. Ciphertext Operation Optimization · p. 4
  • Aggregating PMULT, HADD, and PADD removes intermediate matrix transfers in common neural-network computations such as x · w + b.These sequences frequently occur in convolutional and fully connected layers; Figure 3 illustrates the reduced matrix loads and stores.Source: B. Ciphertext Operation Optimization · p. 4, Figure 3 · p. 4
  • Delayed seed generation postpones PRNG-based offline stages until needed, combining them with online work in HMULT or HROTATE to conserve matrix loads.Outputs are stored uncompressed because seed representations cannot be propagated directly through these operations.Source: B. Ciphertext Operation Optimization · pp. 4–5, Figure 4 · p. 5

C. Ciphertext Pruning · VI. METHODOLOGY · A. Evaluation Environment

BXT prunes low-significance ciphertext digits to accelerate uFHE comparisons, then uses fault-aware training to limit accuracy loss. The evaluation models BXT on an RTX A6000 and uses 128-bit-security FHE parameters.

C. Ciphertext Pruning

  • uFHE enables fast word-wise exact comparisons by operating on encrypted digits, but each digit requires a separate ciphertext.Without uFHE, comparisons are very slow relative to arithmetic, motivating scheme-switching techniques.Source: C. Ciphertext Pruning · p. 5
  • Discarding low-significance digits reduces ciphertexts stored and compared, lowering computational load; the decomposer retains three of five output digits, and ciphertext-digit pruning for encrypted comparisons is described as novel.The retained digit count is set beforehand by the decomposer.Source: C. Ciphertext Pruning · p. 5, Figure 5 · p. 5
  • Digit removal can cause comparison errors, so precision reduction must be chosen to keep inference-accuracy loss within acceptable limits.The method seeks a balance between accuracy preservation and robustness because greater fault robustness may lower accuracy.Source: C. Ciphertext Pruning · p. 5
  • Fault-aware training models ciphertext pruning as faults and uses a custom ReLU to reproduce digit-reduction errors, helping the network anticipate and correct them.Parameter x limits faults to (100 − x)% of least-significant digits; x = 75 injects faults into 25%.Source: C. Ciphertext Pruning · p. 5

A. Evaluation Environment

  • BXT extends 100x and is modeled in Accel-sim for an Nvidia RTX A6000 (Ampere), with per-SM costs of 40 cycles for PRNG and 2 cycles for bit-to-int conversion.Source: A. Evaluation Environment · p. 5
  • The evaluation uses FHE parameters from providing 128-bit security: N = 216, log(Q) = 1728, L = 23 computation levels, Lboot = 17 bootstrapping levels, and dnum = 3.Source: A. Evaluation Environment · p. 5

B. Workloads Evaluated · C. Schemes Evaluated

The evaluation covers five homomorphic operations and two encrypted-MNIST workloads, then compares BXT optimization variants with existing GPU FHE systems. It also uses plaintext fault-aware training to build robustness for reduced-precision encrypted inference.

B. Workloads Evaluated

  • The evaluation benchmarks five homomorphic operations—PADD, PMULT, HADD, HMULT, and HROTATE—using BGV kernels.The workloads also include two machine-learning tasks on encrypted MNIST data.Source: B. Workloads Evaluated · p. 6
  • Logistic Regression classifies MNIST digits 3 versus 8 by encrypting each 28 × 28 image into 784 pixel ciphertexts and evaluating a plaintext-weighted sum.It outputs 1 when S ≥ 0 and 0 otherwise.Source: B. Workloads Evaluated · p. 6
  • The CNN uses five CryptoDL layers—convolution, ReLU, fully connected, ReLU, and output—and implements ReLU with encrypted comparison rather than polynomial approximation.The convolution uses 5 × 5 kernels with stride 2; the fully connected layer has 100 nodes and the output layer has 10.Source: B. Workloads Evaluated · p. 6

C. Schemes Evaluated

  • BXT variants add optimizations progressively as BXT-C, BXT-CS, and BXT-CSO, with BXT-CSO75, BXT-CSO50, and BXT-CSO25 applying ciphertext pruning at different levels.Table IV lists the variants.Source: C. Schemes Evaluated · p. 6, Table IV · p. 6
  • The GPU comparison includes 100x, TensorFHE, and GME; because these systems lack ciphertext compression, BXT can be integrated with them.The evaluation combines BXT with GME to demonstrate the integration.Source: C. Schemes Evaluated · p. 6
  • Fault-aware training is performed in plaintext by injecting ReLU output-inversion errors at a specified rate, helping the network tolerate reduced-precision encrypted inference.For example, when x < 0 should produce 0, training may instead output x.Source: C. Schemes Evaluated · p. 6

VII. EVALUATION RESULTS · A. Homomorphic Operation Performance

BXT speeds up homomorphic operations over the 100x baseline through ciphertext compression, serialization, and operation optimizations. The gains reflect fewer memory accesses and instructions, with improved arithmetic intensity in these memory-bound workloads.

A. Homomorphic Operation Performance

  • BXT-C compresses ciphertexts by regenerating matrices from seeds, BXT-CS adds bit-array serialization, and BXT-CSO adds delayed seed generation; the evaluated operations are PADD, PMULT, HADD, HMULT, and HROTATE.The operation speedups are compared with the 100x baseline.Source: A. Homomorphic Operation Performance · p. 6
  • Across all operations, BXT-C, BXT-CS, and BXT-CSO achieve speedups of 1.3×, 2.5×, and 2.9× on average, respectively.Speedups are relative to the 100x baseline.Source: A. Homomorphic Operation Performance · p. 6, Figure 6 · p. 6
  • BXT-C alone ranges from 1.2× to 1.7× speedup, with PRNG-based matrix-load reduction especially benefiting memory-bound HADD.For HADD, PRNG avoids loading two matrices.Source: A. Homomorphic Operation Performance · p. 6
  • BXT-CS nearly doubles BXT-C’s speedup through improved data layout and retrieval, while BXT-CSO’s offline load/store savings apply only to PADD, PMULT, and HADD—not HMULT or HROTATE.The CSO optimizations remove unnecessary loads and stores during the offline stage.Source: A. Homomorphic Operation Performance · p. 6
  • L1 accesses and GPU instructions decrease with each optimization, while L2 accesses and misses follow the same trend and L1/L2 miss rates remain roughly unchanged.The reported speedups primarily stem from fewer instructions and memory accesses without degrading cache locality.Source: A. Homomorphic Operation Performance · p. 6, Figure 7 · p. 6
  • 1.5× is the geometric-mean arithmetic-intensity increase across homomorphic operations with all BXT optimizations enabled, relative to the baseline.The result indicates better memory-bandwidth utilization in these memory-bound uFHE workloads.Source: A. Homomorphic Operation Performance · p. 6

B. Machine Learning Application Results · 1) Performance Speedup: · 2) Precision Reduction Impact on Accuracy:

BXT accelerates logistic regression and CNN inference as ciphertext precision is reduced, while fault-aware training limits the resulting CNN accuracy loss. ReLU remains a major CNN latency contributor, making its optimization important for uFHE performance.

1) Performance Speedup:

  • 2.8× (LR) and 2.4× (CNN) speedups at full precision rise to 3.8× for both workloads with BXT-CSO50 and 4.4× (LR) and 5.8× (CNN) with BXT-CSO25.These are the speedups reported for the varying-precision configurations.Source: 1) Performance Speedup · p. 6, Figure 8 · p. 7
  • 4.2× ReLU speedup with BXT-CSO50 still leaves ReLU accounting for most CNN latency, as ciphertext comparisons require many ciphertext multiplications.All BXT variants improve both arithmetic and ReLU performance.Source: 1) Performance Speedup · p. 7

2) Precision Reduction Impact on Accuracy:

  • Maintaining at least 50% precision is advantageous for logistic regression, providing up to 3.8× speedup without sacrificing accuracy.At 25% precision, logistic-regression accuracy drops by more than 3%.Source: 2) Precision Reduction Impact on… · p. 7
  • More than 3% accuracy loss at 25% precision for logistic regression contrasts with little impact at 75% and 50% precision.The results support maintaining at least 50% precision for logistic regression.Source: Table V · p. 7, 2) Precision Reduction Impact on… · p. 7
  • Less than 1% and less than 2% accuracy drops at 50% and 25% precision, respectively, are reported for CNN with fault-aware training.These results are for the CNN workloads under precision reduction.Source: Table V · p. 7, 2) Precision Reduction Impact on… · p. 7
  • Over 15% CNN accuracy loss without fault-aware training at 25% precision falls to under 2% for FA-25.At 25% comparison precision, the model achieves more than 5× speedup.Source: 2) Precision Reduction Impact on… · p. 7

C. Comparison with Other Methods · VIII. DISCUSSION · IX. CONCLUSION

BXT-CSO50 combined with GME achieves a 9.2× speedup over the 100x baseline with less than 1% accuracy loss, while the conclusion reports BXT’s 3.8× speedup with less than 1% accuracy reduction. The discussion explains where BXT’s techniques apply and how they integrate into existing GPU architectures.

C. Comparison with Other Methods

  • 9.2× speedup with less than 1% accuracy loss is achieved by BXT-CSO50 combined with GME, corresponding to 2.3× over GME.The comparison uses the 100x baseline for CNN applications.Source: Figure 10 · p. 7, C. Comparison with Other Methods · p. 7
  • 5.7× speedup over the 100x baseline, or 1.5× over GME, is achieved by combining BXT-CSO with GME; BXT-CSO outperforms TensorFHE but not GME.BXT-CSO uses all optimizations except comparison-precision reduction; the authors describe its optimizations as orthogonal to GME’s.Source: Figure 10 · p. 7, C. Comparison with Other Methods · p. 7

VIII. DISCUSSION

  • Compression and serialization apply broadly to FHE but are most effective for memory-bound uFHE; delayed seed generation depends on data formats and operation patterns.Ciphertext pruning is particularly effective for ReLU and other activations where LSB accuracy is less critical, and also extends to division and sorting.Source: §VIII · p. 7
  • Serialization uses a bit-to-integer converter between L2 and L1 cache, and sensitivity analysis from 2 to 32 cycles shows negligible performance impact; its assumed latency is 2 cycles.The discussion says PRNG hardware has 40-cycle latency per SM and is available in modern GPUs; the added support is limited and avoids invasive changes such as custom NoCs (GME) or specialized functional units (CraterLake).Source: §VIII · p. 7
  • Generic compression such as gzip and LZ4 fails on ciphertexts because encryption diffusion produces high entropy; BXT instead uses seeded PRNG regeneration and modulus-aware serialization.The discussion identifies BGV’s deterministic polynomial generation and known modulus sizes as FHE-specific structure enabling compression.Source: §VIII · p. 7

IX. CONCLUSION

  • 3.8× speedup over the 100x baseline with less than 1% accuracy reduction is reported for CNN workloads.The conclusion attributes the acceleration to a multi-level strategy for reducing FHE memory usage.Source: §IX · p. 8
Loading 2609.04769v1…