PaperlayerView exact revision on arXiv

Source-linked AI summary

BTS: An Accelerator for Bootstrappable Fully Homomorphic Encryption

Sangpyo Kim, Jongmin Kim, Michael Jaemin Kim, Wonkyung Jung, Minsoo Rhu, John Kim, Jung Ho Ahn

arXiv:2112.15479v2cs.CRcs.AR

TL;DR

HE’s accumulated noise limits practical computation depth, while bootstrapping enables unlimited operations but imposes substantial computation and memory demands. BTS analyzes these constraints and designs a bootstrapping-oriented, massively parallel accelerator; it reports large gains over CPU, GPU, and ASIC baselines, subject to off-chip bandwidth constraints.

  • Problem

    Accumulated noise limits HE operation depth, while practical bootstrapping support requires substantial computation and memory bandwidth.

  • Method

    BTS analyzes CKKS parameters, computation, and memory demands, then uses massively parallel processing elements and a tailored network-on-chip for bootstrapping-oriented FHE acceleration.

  • Results

    BTS achieves 5,556× faster CNN inference and 2,237× higher HE multiplication throughput than state-of-the-art CPU implementations, plus 5,714× multiplicative-throughput speedup against F1.

  • Takeaways & Limitations

    BTS demonstrates that balancing off-chip memory accesses, on-chip data reuse, and bootstrapping computation can support high-throughput FHE acceleration.

  • Takeaways & Limitations

    FHE-optimized parameters cause quadratic growth in ciphertext, evaluation-key, and temporal data sizes, making these components impossible to place on-chip.

Abstract

from arXiv · show

Homomorphic encryption (HE) enables the secure offloading of computations to the cloud by providing computation on encrypted data (ciphertexts). HE is based on noisy encryption schemes in which noise accumulates as more computations are applied to the data. The limited number of operations applicable to the data prevents practical applications from exploiting HE. Bootstrapping enables an unlimited number of operations or fully HE (FHE) by refreshing the ciphertext. Unfortunately, bootstrapping requires a significant amount of additional computation and memory bandwidth as well. Prior works have proposed hardware accelerators for computation primitives of FHE. However, to the best of our knowledge, this is the first to propose a hardware FHE accelerator that supports bootstrapping as a first-class citizen. In particular, we propose BTS - Bootstrappable, Technologydriven, Secure accelerator architecture for FHE. We identify the challenges of supporting bootstrapping in the accelerator and analyze the off-chip memory bandwidth and computation required. In particular, given the limitations of modern memory technology, we identify the HE parameter sets that are efficient for FHE acceleration. Based on the insights gained from our analysis, we propose BTS, which effectively exploits the parallelism innate in HE operations by arranging a massive number of processing elements in a grid. We present the design and microarchitecture of BTS, including a network-on-chip design that exploits a deterministic communication pattern. BTS shows 5,556x and 1,306x improved execution time on ResNet-20 and logistic regression over a CPU, with a chip area of 373.6mm^2 and up to 163.2W of power.

1 INTRODUCTION

HE enables computation on encrypted data but accumulated noise limits operation depth and practical use. BTS addresses this bottleneck with bootstrapping-oriented hardware and reports large gains over prior CPU, GPU, and ASIC implementations.

  • Motivation: Noise accumulation limits HE computations, while bootstrapping refreshes ciphertexts to permit unlimited operations.This limitation hinders practical workloads such as accurate deep-learning models.
  • Motivation: Prior accelerators largely target small ciphertext sizes and omit bootstrapping, despite its frequent and high computational cost.A single ResNet-20 inference can require more than 1,000 bootstraps.
  • Evaluation: 5,714× speedup in multiplicative throughput is achieved against F1 when bootstrapping is properly considered.The comparison uses F1, described as the state-of-the-art ASIC implementation.
  • Evaluation: 1,306× faster logistic-regression training than CPU, 27× faster than GPU, and 5,556× faster ResNet-20 inference than prior CPU implementation are reported.These results cover both training and inference workloads.
  • BTS Contributions: BTS analyzes HE parameters and proposes massively parallel compute units with NoCs tailored to FHE operation patterns.The architecture targets bootstrapping as a first-class capability and enables unbounded multiplicative depth.

2 BACKGROUND

CKKS is an FHE scheme for fixed-point complex arithmetic that represents encrypted polynomials using residue moduli and supports ciphertext operations such as addition, multiplication, rotation, rescaling, and bootstrapping. Its performance depends on balancing security, polynomial parameters, key-switching decomposition, evaluation-key storage, and computation.

  • Noise management: Bootstrapping refreshes ciphertexts to reduce accumulated noise and enables unlimited operations, but its parameters and evaluation keys impose substantial storage and performance costs.Generalized key-switching increases the aggregate evaluation-key size and per-operation complexity linearly with dnum, making parameter selection important.
  • CKKS representation: CKKS supports fixed-point complex numbers and packs up to N/2 complex message values into one plaintext.The polynomial degree N is typically a power of two ranging from 2^10 to 2^18.
  • CKKS representation: Full-RNS CKKS decomposes modulus Q into word-sized prime moduli, replacing big-integer polynomial operations with residue-polynomial operations.The paper adopts Full-RNS CKKS, which represents a polynomial as an N × (L+1) residue matrix and a ciphertext as a pair of such matrices.
  • Primitive operations: HMult combines a tensor product with key-switching to recover encrypted message multiplication, while HRot combines automorphism with key-switching to rotate packed slots.Evaluation keys enable the resulting ciphertexts to remain decryptable under the original secret key.
  • Noise management: HRescale controls error growth after multiplication by dividing by the last prime modulus and discarding its residue, progressively reducing ciphertext size.Each rescaling removes another residue modulus while the application continues computing.

3 TECHNOLOGY-DRIVEN PARAMETER SELECTION OF BOOTSTRAPPABLE ACCELERATORS

Bootstrappable accelerator performance is constrained by off-chip bandwidth because evks are too large for on-chip storage. Analysis of CKKS parameters identifies high polynomial degrees and low dnum values as desirable targets for BTS.

  • Technology constraints: Hundreds of MBs of on-chip SRAM are feasible, but evks remain too large to store on-chip, making off-chip bandwidth performance-critical.Ciphertexts can be reused on-chip, whereas evks must be streamed from main memory.
  • Parameter interplay: 128-bit security with bootstrappable CKKS requires log P Q above 500 and N larger than 2^14.Higher Q lowers λ, while higher N raises λ.
  • Parameter interplay: A larger dnum raises L but increases evk size linearly, while the benefit to L saturates quickly.Thus, dnum must balance multiplicative depth against memory and computation costs.
  • Bootstrapping demands: More than 40 evks may be required for bootstrapping, each potentially consuming hundreds of MBs and exhibiting poor locality.Bootstrapping uses many rotations with different r values during its linear transformations.
  • Parameter evaluation: Higher dnum can help smaller N reach 128-bit security but causes a superlinear increase in Tmult,a/slot.The increase follows from larger evks and saturated gains in L.
  • Selected target: BTS targets N=2^17 with (L, dnum) pairs (27, 1), (39, 2), and (44, 3), achieving Tmult,a/slot values of 27.7ns, 19.9ns, and 22.1ns.The accelerator is not optimized for other CKKS instances because they have worse Tmult,a/slot or require substantially more on-chip resources.

4 ARCHITECTING BTS

BTS balances computation, data movement, and storage for bootstrappable CKKS by sizing parallel units to evk-loading time and supporting both NTT and increasingly important BConv operations.

  • HE operation analysis: HMult and HRot dominate bootstrapping, and key-switching within them relies primarily on NTT, iNTT, and BConv.BTS therefore focuses its accelerator organization on these functions.
  • HE operation analysis: FFT-style algorithms reduce (i)NTT complexity from O(N^2) to O(Nlog N) through staged butterfly operations.The transform converts polynomial convolution into element-wise multiplication, followed by iNTT for the final result.
  • HE operation analysis: BConv matches a ciphertext's residue-polynomial base with an evaluation key base, requiring transitions between the RNS and NTT domains.BTS commonly uses the sequence iNTT → BConv → NTT.
  • Technology-aware design: 64× larger ciphertext, evaluation-key, and temporal-data sizes arise when moving from N=2^14 to N=2^17, making on-chip placement impossible for bootstrappable instances.This shifts the performance bottleneck toward off-chip memory bandwidth rather than simply adding NTT units.
  • Processing-unit sizing: 1,328 fully pipelined NTTUs are required for N=2^17 when dnum=1, so BTS uses 2,048 NTTUs to provide margin for other operations.The minimum required count is defined by completing an HE operation within the evaluation-key loading time.
  • Balanced compute design: BConv's relative complexity rises from 12% at dnum=max to 34% at dnum=1, motivating a dedicated BConv unit.Prior work primarily targeted the maximum-dnum case and emphasized (i)NTT acceleration.
  • Dataflow and communication: BTS uses coefficient-level parallelism with fixed coefficient-index placement, avoiding exchanges for coefficient-wise and element-wise functions.Only (i)NTT and automorphism require inter-PE communication, whose pattern is predetermined.
  • Microarchitecture: Each of BTS's 2,048 processing elements includes an NTTU, BConvU, modular adder, modular multiplier, and SRAM scratchpad.The design distributes residue data across PEs and uses 3D-NTT to reduce exchanges.

5 BTS MICROARCHITECTURE

BTS organizes massively parallel processing elements and specialized units to accelerate CKKS operations, while using separate communication networks and scratchpad management to handle data movement and bandwidth demands. Its microarchitecture overlaps NTT, base conversion, and related operations to improve utilization.

  • Architecture: 2,048 processing elements are arranged in a grid, with each PE containing an NTTU, BConvU, modular adder, modular multiplier, and SRAM scratchpad.The grid has 32 vertical and 64 horizontal positions, connected by dimensionwise crossbars.
  • Architecture: BTS maps residue-polynomial coefficients across the PE grid as a three-dimensional cube to support distributed 3D-NTT execution.Residues are assigned to PEs by their two-dimensional coordinates, with the third dimension representing residues handled over time.
  • NTT: Epoch-based pipelining overlaps 3D-NTT data exchanges with computation, allowing one residue polynomial’s (i)NTT to finish every epoch.Separate vertical and horizontal NoCs support concurrent exchanges during the pipeline.
  • NTT: On-the-fly twiddling reduces twiddle-factor storage by 2/m by combining higher- and lower-digit tables distributed between the BrU and PEs.The BrU broadcasts the higher-digit table for each prime modulus at every (i)NTT epoch.
  • BConvU: BConvU combines modular multiplication and multiply-accumulate hardware, while partial overlap with iNTT allows coefficient-wise accumulation to begin after l_sub=4 residue polynomials are ready.The MMAU also supports fused subtraction-scaling-addition operations.
  • Scratchpad: The scratchpad stores temporary data, prefetched evaluation keys, and software-managed ciphertexts, but BConvU bandwidth creates a trade-off between larger l_sub and wider MMAU hardware.Increasing l_sub reduces partial-sum bandwidth pressure while increasing MMAU lanes and RFMMAU size.
  • Communication: Three separate NoCs handle PE-memory traffic, broadcast constants, and inter-PE exchanges, enabling deterministic communication for their distinct traffic patterns.The PE-PE NoC supports (i)NTT and automorphism exchanges, while the BrU NoC distributes precomputed values.

6 EVALUATION

BTS is evaluated through simulation, synthesis, and comparisons with CPU, GPU, and ASIC implementations across CKKS microbenchmarks and applications. Its performance depends on parameter selection, scratchpad capacity, and workload characteristics.

  • Evaluation setup: BTS is evaluated with a cycle-level simulator, synthesized in ASAP7 at 7nm, and compared against Lattigo, 100x, F1, and scaled F1+ implementations.The evaluation covers amortized multiplication throughput, logistic regression training, ResNet-20 inference, and sorting.
  • Amortized multiplication: 45.5ns amortized multiplication time per slot is achieved with INS-2, 2,237× better than Lattigo.F1 is 2.5× slower than Lattigo, while F1+ has 824× lower performance than BTS; 100x reports 743ns for a 97b-secure parameter set and 8μs for a 173b-secure set.
  • Application performance: BTS performs up to 5,556× faster on ResNet-20 and 1,482× faster on sorting than prior works.Channel packing adds a 17.8× gain over the un-packed ResNet-20 configuration, reaching 1.91s latency per encrypted image.
  • Evaluation limits: BTS does not fully utilize all 216 slots on the evaluated complex applications because their problem sizes are small.Amortized multiplication throughput does not always predict application performance: ResNet-20 favors INS-1 when bootstrapping is a smaller fraction, and level imbalance can negate deeper parameter settings.
  • Memory behavior: BTS's scratchpad averages 58.6% bandwidth utilization, peaks at 90% during BConv, and requires 183MB at maximum capacity.Increasing scratchpad size improves performance and energy efficiency until most HE-operation working sets fit on-chip; 192MB causes frequent off-chip ciphertext loads.
  • Memory behavior: With a 512MB scratchpad, ciphertext cache-hit rates are 65.6%, 98.8%, 93.7%, 98.6%, 97.5%, and 47.8% for HMult, HRot, PMult, HAdd, HRescale, and CMult/CAdd.When ciphertexts reside on-chip, non-evk operations can benefit from an on-chip-to-off-chip bandwidth ratio greater than 10; HMult/HRot remain bounded by evk load time.

7 RELATED WORK

Prior HE accelerators span CPU, GPU, FPGA, and ASIC platforms, but most do not support bootstrapping. BTS addresses this gap with on-chip storage and architecture tailored to FHE traffic patterns.

  • Prior accelerators: Most prior FPGA and ASIC accelerators target HE computation without bootstrapping, while GPU work only later supported CKKS bootstrapping.The GPU implementation 100x reduced off-chip accesses through kernel fusion but remained constrained by limited on-chip storage; BTS stores temporary data on-chip.
  • Prior accelerators: CPU, GPU, FPGA, and ASIC approaches use multithreading, SIMD, abundant integer units, memory bandwidth, or dedicated HE hardware to accelerate HE operations.HEAX reports a 200× gain over a CPU implementation but is fixed to limited parameters and does not support bootstrapping.

8 CONCLUSION

The paper designs BTS around CKKS parameter analysis, massively parallel processing, and a traffic-specialized network-on-chip. The resulting architecture balances memory access, on-chip reuse, and bootstrapping computation while delivering large throughput gains.

  • Architecture: BTS distributes massively parallel processing elements through a network-on-chip tailored to number theoretic transform and automorphism traffic.These are identified as critical functions of HE operations.
  • Results: 2,237× higher HE multiplication throughput and 5,556× faster CNN inference are obtained compared with state-of-the-art CPU implementations.The architecture is designed to balance off-chip memory accesses, on-chip data reusability, and bootstrapping computation.
Loading 2112.15479v2…