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

FHE’s large ciphertext expansion creates a memory bottleneck that limits arithmetic intensity. BXT addresses this with compression, serialization, delayed seed generation, and fault-aware digit pruning, achieving up to 3.8× speedup over the 100x baseline with less than 1% accuracy loss at 50% precision.

  • Problem

    FHE ciphertext expansion creates low arithmetic intensity and makes memory a major bottleneck for computation.

  • Method

    BXT combines seed-based ciphertext compression, bit-array serialization, delayed seed generation, and fault-aware ciphertext-digit pruning for uFHE.

  • Results

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

  • Takeaways & Limitations

    BXT reduces memory accesses in memory-constrained FHE workloads while providing tunable accuracy-performance tradeoffs.

  • Takeaways & Limitations

    Compression and serialization apply broadly to FHE schemes but are most effective for memory-bound uFHE, while delayed seed generation is workload-dependent.

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

FHE’s ciphertext expansion makes memory movement a central bottleneck, motivating BXT’s multi-level framework for reducing representation size and memory traffic. BXT combines compression, serialization, delayed seed generation, and precision-aware digit pruning, achieving substantial speedups with limited accuracy loss.

  • Motivation: FHE ciphertext expansion produces low arithmetic intensity, making memory a worsening bottleneck as compute accelerates.Ciphertexts can be magnitudes larger than original data, typically yielding fewer than one operation per accessed byte.
  • Motivation: BXT directly reduces ciphertext expansion and improves arithmetic intensity instead of relying on costly increases in GPU memory capacity or bandwidth.The framework targets the underlying inefficiency of ciphertext representations.
  • BXT techniques: Ciphertext compression regenerates ciphertext components from compact seeds during execution, reducing ciphertext representation size and memory traffic.BXT dynamically regenerates ciphertext matrices in the GPU memory hierarchy.
  • BXT techniques: Ciphertext serialization packs coefficients as bit arrays and unpacks them during L2-to-L1 transfer, improving cache efficiency without redesigning arithmetic units.The layout reduces memory bandwidth demand.
  • BXT techniques: Delayed seed generation defers PRNG-heavy offline work and aggregates it across operations, reducing intermediate matrix loads and stores.This technique reduces memory accesses across aggregated operation sequences.
  • Results: 3.8× speedup over the 100x baseline is achieved with less than 1% accuracy loss at 50% comparison precision.BXT increases arithmetic intensity by 1.5× and provides tunable accuracy-performance tradeoffs.

II. RELATED WORK

Prior GPU FHE accelerators optimize arithmetic kernels, NTT computation, data locality, or scheme switching, but do not reduce ciphertext size at runtime. BXT instead targets memory traffic while operating within a BGV-based universal FHE context.

  • GPU acceleration: Existing GPU FHE accelerators focus on arithmetic kernels, NTT optimization, data locality, or switching between schemes.Examples include 100x, TensorFHE, GME, HE-Booster, and recent TFHE/CKKS switching approaches.
  • BXT distinction: BXT differs by compressing ciphertexts at runtime and rebalancing computation against memory traffic.Its components are regenerated on-the-fly from seeds in the GPU memory hierarchy.
  • Universal FHE: BGV-based universal FHE extends word-wise arithmetic with exact comparisons, avoiding the over 70× scheme-switching latency reported for TFHE-BGV and TFHE-CKKS alternatives.The enhanced BGV approach is described as the state-of-the-art uFHE solution.
  • BGV representation: BGV represents ciphertext polynomials using RNS and DoubleCRT formats, with NTT enabling polynomial multiplication in O(N log N) time.Residue polynomials form a matrix with L + 1 rows and word-sized coefficients.

B. Integer-wise Comparison

Integer-wise uFHE comparison decomposes encrypted integers into digits, evaluates digit-level equality and less-than functions, and aggregates their results lexicographically. This process increases ciphertext count and memory pressure, while GPU memory operations can dominate runtime.

  • Digit-wise comparison: Encrypted integers are decomposed into l digits, and equality and less-than are evaluated independently for corresponding digit pairs.The digit-level functions are computed using polynomial interpolation.
  • Result aggregation: Digit-level comparison results are aggregated lexicographically to produce the final encrypted comparison result.The aggregation combines equality results across successive digit positions.
  • Memory impact: The digit-wise method substantially increases ciphertext count and overall memory footprint compared with arithmetic-only FHE.Each additional encrypted digit contributes to the comparison representation.
  • GPU bottleneck: Over 80% of runtime is spent on memory operations when 100x is adapted for uFHE comparisons.Large ciphertext expansion and fewer than one arithmetic operation per byte cause frequent memory accesses and limited data reuse.

V. BXT DESIGN

BXT reduces memory pressure across algorithm, data-layout, operation, and application levels. It compresses and serializes ciphertext data, regenerates random components from seeds, and restructures transfers to reduce bandwidth and data movement.

  • Framework: BXT spans four optimization levels: seed-based ciphertext compression, bit-array data layout, delayed seed generation, and digit reduction in comparisons.These levels address algorithmic representation, storage layout, operation scheduling, and application precision.
  • Memory bottleneck: Operating on two ciphertexts requires fetching four large matrices through L2 and L1 caches, consuming bandwidth and reducing arithmetic intensity.Matrix dimensions can range from 2^13 to 2^16 for security strength.
  • Data flow: Figure 2’s data flow fetches ciphertext through L2 to L1, converts serialized bit arrays to integers, and regenerates read-only ciphertext data from a seed.The flow combines serialization with seed-based reconstruction during processing.
  • Ciphertext compression: BXT stores one computed ciphertext matrix and a seed, then regenerates the randomly generated matrix on-the-fly with a hardware-supported PRNG.This replaces explicit storage of the random component during memory access.
  • Ciphertext serialization: Packing coefficients as bit arrays removes unused bits, reduces matrix size, and lowers memory bandwidth.The packed representation is unpacked during L2-to-L1 transfer rather than requiring a broader compute-unit redesign.

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

BXT introduces load/store interfaces that generate ciphertext data from seeds and convert serialized bit layouts during memory transfers. These interfaces support warp-level fetching and on-the-fly data reconstruction.

  • BXT generates one ciphertext matrix dynamically from a seed while storing the other matrix in memory.The proposed instructions support on-the-fly generation for read-only ciphertexts.
  • 32 elements can be fetched and generated simultaneously at warp-level granularity.The num_of_element parameter controls the fragment size, with 32 enabling simultaneous processing of 32 elements.
  • The matrix is stored as an array of bits and converted back into integers for computation.Dedicated declarations and load/store instructions specify how many elements are fetched.
  • Dedicated hardware between the L1 and L2 caches transforms fetched bit arrays into 64-bit integers.The final instruction argument specifies how many bits are converted into each 64-bit integer.

B. Ciphertext Operation Optimization

Ciphertext operation optimization targets matrix movement, which dominates the cost of PMULT, HADD, and PADD. BXT aggregates operations and delays offline seed generation to reduce repeated loads and stores.

  • 67% of HADD execution time is spent on matrix loads and 29% on matrix stores.Only about 4% is used for computation, kernel launch, and modulus data fetching.
  • Aggregating PMULT, HADD, and PADD removes intermediate matrix transfers and reduces loads and stores.The sequence computes x · w + b by combining multiplication, homomorphic addition, and plaintext addition.
  • Delayed seed generation postpones offline PRNG work and combines it with online stages when both matrices are needed.The online stage loads matrices, while the offline stage generates data through a PRNG and can be deferred until needed.
  • Combining operation stages conserves matrix loads and reduces execution time.The delayed offline parts are aggregated across operations rather than performed immediately.

C. Ciphertext Pruning

Ciphertext pruning reduces Universal FHE comparison precision by discarding low-significance digits, while fault-aware training seeks to preserve inference accuracy. The approach trades comparison cost against robustness and accuracy.

  • uFHE encrypts each digit separately and combines digit-level comparison results into a final result.This digit-wise representation increases ciphertext count and memory footprint.
  • Pruning low-significance digits reduces the ciphertexts stored and compared, lowering computational load and speeding comparisons.A decomposer can output five digits while retaining only three for comparison.
  • Discarding digits can cause comparison errors, so the precision level must remain within an acceptable accuracy range.The paper frames the choice of retained digits as a reliability-versus-precision decision.
  • Fault-aware training models ciphertext pruning as a faulty environment and trains the network for robustness.The training procedure injects erroneous ReLU outputs corresponding to pruning-related faults.

B. Workloads Evaluated

The evaluation covers homomorphic kernels, encrypted MNIST workloads, multiple BXT optimization variants, and comparisons with GPU FHE systems. Fault-aware training is performed in plaintext for reduced-precision encrypted inference.

  • The evaluation measures five homomorphic operations: PADD, PMULT, HADD, HMULT, and HROTATE.The kernels are based on BGV and are evaluated alongside encrypted MNIST workloads.
  • The workloads are logistic regression for classifying digits 3 versus 8 and a five-layer CNN.The CNN uses convolution, exact encrypted ReLU, fully connected, and output layers.
  • BXT variants are organized by cumulative optimizations and ciphertext-pruning levels.The variants include BXT-C, BXT-CS, BXT-CSO, BXT-CSO75, BXT-CSO50, and BXT-CSO25.
  • BXT is compared with 100x, TensorFHE, and GME, and can be integrated with systems that do not perform ciphertext compression.The evaluation also combines BXT with GME.
  • Fault-aware training is performed in plaintext by injecting ReLU errors at a specified rate.This trains robustness for reduced-precision encrypted inference.

VII. EVALUATION RESULTS

BXT progressively improves homomorphic-operation performance by reducing ciphertext memory traffic, accesses, and instructions. The strongest average gains come from combining compression, serialization, and delayed seed generation, although the delayed optimization benefits only selected operations.

  • Operation-level speedup: 2.9× average speedup over the 100x baseline is achieved by BXT-CSO, compared with 1.3× for BXT-C and 2.5× for BXT-CS.BXT-C alone ranges from 1.2× to 1.7× across operations.
  • Operation-level speedup: BXT-C reduces matrix loads and stores by generating ciphertext matrices on-the-fly from PRNG seeds, benefiting memory-bound operations such as HADD.For HADD, PRNG generation avoids loading two matrices.
  • Optimization effects: BXT-CS nearly doubles BXT-C’s speedup through serialized ciphertext layouts, while BXT-CSO removes additional offline loads and stores for PADD, PMULT, and HADD.HMULT and HROTATE do not benefit from the delayed seed-generation optimization.
  • Hardware activity: Each optimization reduces total L1 accesses and GPU instructions without substantially changing L1/L2 miss rates, indicating lower traffic rather than degraded cache locality.L2 accesses and misses follow the same decreasing trend.

B. Machine Learning Application Results

BXT’s machine-learning evaluations show that comparison-precision reduction increases speedup, while fault-aware training limits the associated CNN accuracy loss. The largest reported gains occur at 25% precision, but 50% precision offers a stronger accuracy-performance balance.

  • Performance speedup: 3.8× speedup is achieved by BXT-CSO50 at 50% precision for both Logistic Regression and CNN, while BXT-CSO25 reaches 4.4× and 5.8×, respectively.At full precision, BXT-CSO achieves 2.8× for Logistic Regression and 2.4× for CNN.
  • CNN operation breakdown: 4.2× ReLU speedup is achieved with BXT-CSO50, although ReLU still dominates CNN latency because encrypted comparisons require many ciphertext multiplications.All BXT variants improve both arithmetic and ReLU performance.
  • Precision reduction and accuracy: Less than 1% CNN accuracy loss is observed at 50% precision with fault-aware training, while 25% precision remains below 2% accuracy loss.For Logistic Regression, 25% precision causes a drop of more than 3%, whereas 50% precision has little impact.
  • Fault-aware training: Over 15% accuracy loss occurs at 25% precision without fault-aware training, compared with under 2% for the FA-25 model.The FA-25 result accompanies a speedup of more than 5× at 25% comparison precision.

C. Comparison with Other Methods

BXT-CSO outperforms TensorFHE but remains below GME on CNN applications, while combining BXT with GME produces larger gains. BXT-CSO50 plus GME reaches high speedup with limited accuracy loss, and the framework is designed for integration with existing GPU techniques.

  • Comparison with GPU methods: 5.7× speedup over the 100x baseline is achieved by BXT-CSO combined with GME, corresponding to 1.5× speedup over GME.BXT-CSO outperforms TensorFHE but not GME when used alone.
  • Comparison with GPU methods: 9.2× speedup over the 100x baseline is achieved by BXT-CSO50 combined with GME at 50% comparison-precision reduction, with less than 1% accuracy loss.This corresponds to a 2.3× speedup over GME.
  • Generalizability: Compression and serialization apply broadly to FHE schemes but are most effective for memory-bound uFHE, while delayed seed generation depends on data formats and operation patterns.Ciphertext pruning is particularly effective for ReLU and other activation functions where LSB accuracy is less critical.
  • Conclusion: 3.8× speedup with less than 1% accuracy reduction is reported for CNN workloads, supporting memory-access reduction as the central acceleration strategy.The conclusion frames BXT as a multi-level strategy combining algorithmic, application-specific, and data-access insights.
Loading 2609.04769v1…