PaperlayerView exact revision on arXiv

Source-linked AI summary

ARK: Fully Homomorphic Encryption Accelerator with Runtime Data Generation and Inter-Operation Key Reuse

Jongmin Kim, Gwangho Lee, Sangpyo Kim, Gina Sohn, John Kim, Minsoo Rhu, Jung Ho Ahn

arXiv:2205.00922v3cs.CRcs.AR

TL;DR

Practical FHE acceleration is limited by the large off-chip memory traffic required by bootstrapping and other expensive encrypted operations. ARK combines runtime data generation, inter-operation key reuse, and a data-movement-conscious accelerator architecture; it reports large gains over prior acceleration and enables practical encrypted inference, while prior designs remain limited by small parameters and simple workloads.

  • Problem

    FHE bootstrapping uses large working sets and costly operations, making acceleration fundamentally constrained by off-chip memory bandwidth.

  • Method

    ARK combines minimum key-switching and on-the-fly limb extension with specialized functional units and access-pattern-aware data distribution to reduce memory traffic and on-chip movement.

  • Results

    ARK improves multiplicative throughput by 2,353× and logistic regression training by 18× over the state-of-the-art HE accelerator, and runs ResNet-20 inference in 0.125 seconds.

  • Takeaways & Limitations

    ARK supports practical FHE workloads by reducing the working set enough to exploit on-chip memory and by addressing computation and data-movement constraints together.

  • Takeaways & Limitations

    Prior accelerator F1 uses small parameters and supports only single-slot bootstrapping, limiting its applicability to practical FHE parameters and complex workloads.

Abstract

from arXiv · show

Homomorphic Encryption (HE) is one of the most promising post-quantum cryptographic schemes that enable privacy-preserving computation on servers. However, noise accumulates as we perform operations on HE-encrypted data, restricting the number of possible operations. Fully HE (FHE) removes this restriction by introducing the bootstrapping operation, which refreshes the data; however, FHE schemes are highly memory-bound. Bootstrapping, in particular, requires loading GBs of evaluation keys and plaintexts from off-chip memory, which makes FHE acceleration fundamentally bottlenecked by the off-chip memory bandwidth. In this paper, we propose ARK, an Accelerator for FHE with Runtime data generation and inter-operation Key reuse. ARK enables practical FHE workloads with a novel algorithm-architecture co-design to accelerate bootstrapping. We first eliminate the off-chip memory bandwidth bottleneck through runtime data generation and inter-operation key reuse. This approach enables ARK to fully exploit on-chip memory by substantially reducing the size of the working set. On top of such algorithmic enhancements, we build ARK microarchitecture that minimizes on-chip data movement through an efficient, alternating data distribution policy based on the data access patterns and a streamlined dataflow organization of the tailored functional units -- including base conversion, number-theoretic transform, and automorphism units. Overall, our co-design effectively handles the heavy computation and data movement overheads of FHE, drastically reducing the cost of HE operations, including bootstrapping.

I. INTRODUCTION

ARK addresses the memory bottleneck that limits practical FHE acceleration, especially during bootstrapping, through algorithm-architecture co-design. Its proposed algorithms reduce single-use data and off-chip traffic, while the accelerator architecture minimizes on-chip movement and supports substantial performance gains.

  • Motivation: FHE bootstrapping enables unbounded encrypted computation but requires large parameters and several-GB working sets, creating severe off-chip memory-bandwidth bottlenecks.Noise limits leveled HE, while bootstrapping refreshes ciphertexts and dominates complex FHE workloads.
  • Algorithmic approach: ARK introduces minimum key-switching and on-the-fly limb extension to reduce single-use bootstrapping data and off-chip memory access.The algorithms target the memory bottleneck identified in CKKS bootstrapping.
  • Algorithmic approach: The proposed algorithms eliminate 88% of off-chip memory access in a major bootstrapping operation and enable a reduced working set to fit on-chip.This allows deployment of substantial computational logic and on-chip memory that conventional systems lack.
  • Architecture: ARK uses specialized base-conversion, NTT, and automorphism units together with access-pattern-aware data distribution to minimize register-file pressure and on-chip data movement.Its dataflow organization splits the chip into logical regions for streamlined execution.
  • Evaluation: ARK improves multiplicative throughput by 2,353× and logistic regression training by 18× over the state-of-the-art HE accelerator, while running ResNet-20 inference in 0.125 seconds.The reported design is sized 418.3mm2 and consumes up to 281.3W.

B. Computational optimizations for HE ops

CKKS reduces expensive polynomial arithmetic through NTT and residue-number representations, while base conversion changes the prime-limb set needed by later operations. These representations trade arithmetic complexity against transformation overhead.

  • Number-theoretic transform: NTT converts polynomial convolution into element-wise multiplication, reducing multiplication complexity from O(N^2) to O(N).FFT algorithms compute NTT in O(N log N), and polynomials are often retained in evaluation representation to avoid unnecessary transforms.
  • Trade-offs: NTT lowers multiplication complexity but introduces additional transform cost, motivating reuse of evaluation representations where possible.The optimization therefore balances cheaper multiplication against the cost of NTT and INTT operations.
  • Residue number system: Residue Number System decomposes large coefficients into word-sized prime limbs, representing a polynomial as an (L + 1) × N matrix.This representation enables word-sized arithmetic across limbs.
  • Base conversion: Base conversion changes a polynomial from one prime-limb set to another and requires coefficient representation.CKKS commonly performs the sequence INTT → BConv → NTT as a BConvRoutine.

C. Primitive HE ops in CKKS

CKKS primitive operations manipulate scaled ciphertexts, polynomial representations, and evaluation keys to preserve levels and decryptability. Key-switching is especially costly because it combines repeated transforms, base conversions, and evaluation-key multiplication.

  • Rescaling: HRescale restores ciphertext scale after multiplication by removing the highest prime limb and multiplying the remaining limbs by q_L^-1 modulo each q_i.Repeated rescaling consumes multiplicative levels until only the q_0-limb remains.
  • Automorphism: Automorphism circularly shifts message slots by mapping each polynomial coefficient according to the rotation amount r.The mapping is applied independently to each limb.
  • Key-switching: Key-switching converts results decryptable under S^2 or ψ_r(S) back to the secret key S using evaluation keys.HMult uses evk_mult, while HRot requires a separate evk_rot(r) for each rotation amount.
  • Key-switching: Key-switching is expensive because it involves multiple NTTs, base conversions, modulus extension, evaluation-key multiplications, and accumulation.Its computational complexity and evaluation-key size increase with the decomposition number d_num.

D. CKKS bootstrapping

CKKS bootstrapping restores multiplicative levels after repeated rescaling, enabling further homomorphic operations. It requires sufficiently large parameters to preserve levels while maintaining 128-bit security.

  • Bootstrapping recovers the multiplicative level after repeated HRescales, enabling further operations on encrypted data.FHE schemes support bootstrapping to continue computation after the ciphertext reaches level zero.
  • Bootstrapping comprises LevelRecover, H-IDFT, EvalMod, and H-DFT.EvalMod approximates the modulo operation with a high-degree polynomial and consumes multiple multiplicative levels.
  • The resulting ciphertext retains L−Lboot multiplicative levels after bootstrapping consumes Lboot levels.The parameter L must therefore be high enough to support bootstrapping and subsequent operations.
  • N must be at least 2^15 for CKKS bootstrapping, with prior work typically using N=2^15 to 2^17.The paper uses a modified Lattigo parameter set that guarantees 128-bit security.

III. FHE MEMORY BOTTLENECKS

FHE operations expose substantial parallelism but remain constrained by memory capacity and bandwidth. Prior accelerator designs therefore struggle with practical bootstrapping parameters and complex workloads.

  • HE primitives such as (I)NTT, BConv, and automorphism can execute in parallel, motivating architectures with many functional units.The memory system must feed these units on-chip, making data delivery a primary design objective.
  • HE operations have low arithmetic intensity and are bounded by off-chip memory bandwidth.Even HMult can require several ciphertexts and an evaluation key totaling several hundred megabytes.
  • F1 evaluates single-slot CKKS bootstrapping with small parameters and massive computational parallelism.Its design uses a dedicated pipelined 2D-FFT-based NTT unit.
  • F1's applicability is limited to small problem sizes and simple workloads requiring little or no practical bootstrapping support.Its performance can degrade significantly for practical FHE parameters and complex workloads with frequent bootstrapping.

B. State-of-the-art bootstrapping algorithm

The state-of-the-art bootstrapping algorithm uses FFT-like homomorphic DFTs with radix-2^k and BSGS to reduce rotations. Its baseline still requires large quantities of distinct evaluation keys and plaintexts.

  • H-(I)DFT occupies most bootstrapping execution time and follows an FFT-like pattern with BSGS.BSGS reduces the number of homomorphic rotations from O(2^k) to a smaller quantity determined by k1 and k2.
  • Each DFT iteration performs homomorphic rotations, plaintext multiplications, and a rescale, consuming one multiplicative level.The process uses precomputed plaintext polynomials as DFT constants.
  • The radix parameter k trades computational work against multiplicative-level consumption.The full process consumes log_2^k n multiplicative levels.
  • The baseline can further improve line 4 by first performing a pre-rotation.The pre-rotation is specified by Eq. 7 before the main DFT computation.
  • For n=2^15 and k=5, each H-(I)DFT performs 40 rotations and 158 plaintext multiplications.The baseline prepares 40 distinct evaluation keys and 158 plaintexts, totaling 6.4GB for H-IDFT or 0.6GB for H-DFT.

C. Memory bottleneck in bootstrapping

Bootstrapping's H-(I)DFT stages are memory-bound because single-use evaluation keys and plaintexts impose a hard off-chip latency bound. Minimum key-switching reduces this burden by reusing evaluation keys across rotations and iterations.

  • Single-use evaluation keys and plaintexts must be fetched from off-chip memory because their aggregate size exceeds practical on-chip capacity.Their loading time becomes the hard latency bound for H-(I)DFT.
  • At 3TB/s off-chip bandwidth, loading the single-use data takes 2.1ms for H-IDFT and 0.2ms for H-DFT.
  • A scaled F1 reaches only 8.61% utilization for H-IDFT and 13.32% for H-DFT under the bootstrapping memory bottleneck.The analysis concludes that resolving off-chip bandwidth should precede adding computational capability.
  • The baseline BSGS patterns require m different evaluation keys for rotations whose amounts form an arithmetic progression.This creates off-chip bandwidth pressure because the keys are loaded for H-(I)DFT computation.
  • The prior minimal key-switching strategy reuses iterative rotation results so all rotations use the same evaluation key.It reduces BSGS requirements to three evaluation keys: pre-rotation, baby-step, and giant-step.
  • Min-KS eliminates pre-rotation and modifies BSGS so each H-(I)DFT iteration requires only two evaluation keys.It also generalizes to arithmetic-progression rotations in homomorphic convolution and slot accumulation.

B. On-the-fly limb extension (OF-Limb)

OF-Limb generates plaintext limbs at runtime instead of loading all precomputed limbs, reducing off-chip traffic while adding NTT computation.

  • B. On-the-fly limb extension (OF-Limb): OF-Limb generates plaintext limbs used in PMult and PAdd on the fly, storing only the precomputed q0-limb.The extended plaintext has ℓ+1 limbs and is produced at runtime.
  • B. On-the-fly limb extension (OF-Limb): OF-Limb reduces PMult and PAdd off-chip memory access to 1/(ℓ + 1) of the original method.
  • B. On-the-fly limb extension (OF-Limb): Plaintexts account for 27.5% of H-IDFT and 40.9% of H-DFT off-chip memory access under the stated memory assumptions.
  • B. On-the-fly limb extension (OF-Limb): OF-Limb adds NTT computation for extended plaintext limbs, accounting for 22.9% of H-IDFT and 24.1% of H-DFT computation.The authors report that reduced off-chip access outweighs this computational overhead.

C. Impact of the optimizations on the arithmetic intensity of homomorphic (I)DFT

Min-KS and OF-Limb raise arithmetic intensity by reducing off-chip access, motivating ARK’s large on-chip memory and specialized datapaths for the resulting computation and access patterns.

  • C. Impact of the optimizations on the arithmetic intensity of homomorphic (I)DFT: Min-KS increases H-IDFT and H-DFT arithmetic intensity by 2.6× and 2.0×, while OF-Limb adds 4.0× and 2.9×, reaching 11.1 and 9.6 ops/byte.Together, the algorithms remove 88% and 78% of off-chip memory access for H-IDFT and H-DFT.
  • C. Impact of the optimizations on the arithmetic intensity of homomorphic (I)DFT: The optimizations target single-use data that other compute optimizations do not reduce.
  • C. Impact of the optimizations on the arithmetic intensity of homomorphic (I)DFT: Min-KS and OF-Limb do not improve conventional CPUs or GPUs because evaluation keys remain off-chip and those systems lack cost-effective capacity for the added computation.
  • C. Impact of the optimizations on the arithmetic intensity of homomorphic (I)DFT: ARK uses 512MB of on-chip scratchpad memory to hold a reduced working set, including reused evaluation keys and temporary HE-operation data.
  • C. Impact of the optimizations on the arithmetic intensity of homomorphic (I)DFT: Practical bootstrappable parameters introduce new access and computation requirements because an evaluation key can reach 600MB at max dnum=24.
  • C. Impact of the optimizations on the arithmetic intensity of homomorphic (I)DFT: For practical large-N, small-dnum parameters, the fraction of computation spent on (I)NTT drops from 73.3% to 54.8%.

B. Access-pattern-oriented data distribution

ARK switches data distribution and dataflow according to access patterns, combining coefficient-wise BConv processing with limb-wise NTT processing while minimizing movement inside each cluster.

  • B. Access-pattern-oriented data distribution: Coefficient-wise distribution splits the α × N polynomial matrix across four clusters, matching BConv’s coefficient-parallel access pattern.
  • B. Access-pattern-oriented data distribution: ARK switches between limb-wise and coefficient-wise distribution, using an all-to-all NoC exchange before BConv processing.
  • B. Access-pattern-oriented data distribution: Each BConvRoutine transfers (α+L+1)·N words, while one key-switching transfers (dnum+2)·(α+L+1)·N words.
  • B. Access-pattern-oriented data distribution: NTTU places coefficient and evaluation register files at opposite ends and uses opposite dataflows for INTT and NTT.
  • B. Access-pattern-oriented data distribution: The BConvRoutine dataflow moves data through RF (Eval) → NTTU → RF (Coeff) → NoC → RF (NoC) → BConvU.
  • B. Access-pattern-oriented data distribution: OF-Twist nearly eliminates memory traffic for loading twisting factors in the NTTU.

D. Automorphism unit (AutoU)

ARK’s AutoU implements automorphism through pipelined internal permutations, while the evaluation uses modeled hardware and FHE workloads including bootstrapping, HELR, ResNet-20, and sorting.

  • Automorphism mapping: Automorphism is implemented as internal permutations between 28-coefficient vector lanes rather than an irregular permutation across all N coefficients.Each lane consumes 28 coefficients per cycle with stride 28.
  • AutoU implementation: The AutoU uses eight pipelined stages that recursively swap data chunks according to ψr index calculations.Index calculation uses a 16-bit multiplier and precomputed 5r mod N.
  • Hardware modeling: ARK’s hardware model uses ASAP7 for functional units and FinCACTI-based SRAM models for scratchpad and register files.The models are adjusted using ASAP7, IRDS, and published 7nm technology data.
  • Hardware costs: ARK is modeled with 418.3mm2 area and up to 281.3W power, including substantial wiring overhead from NTTUs and AutoUs.NTTUs and AutoUs alone account for 10% of area and 21% of peak power.
  • Evaluation setup: The evaluation measures amortized multiplication time, HELR, ResNet-20 inference, and sorting against CPU, GPU, and ASIC baselines.HELR uses 30 training iterations, while ResNet-20 targets CIFAR-10 inference.

B. Performance of ARK

ARK’s algorithmic optimizations and architecture substantially improve FHE performance, with gains depending on workload structure, scratchpad capacity, computational parallelism, and memory bandwidth.

  • Overall performance: ARK achieves 563× lower TA.S. than 100x, 6,142× lower than Lattigo, and 2,353× lower than F1+.ARK outperforms all prior works on the amortized multiplication-time metric.
  • Overall performance: ARK improves HELR performance by 3,139×, 104×, and 18× over Lattigo, 100x, and F1+, respectively.The gap is smaller than for TA.S. because HELR uses only 256 slots during bootstrapping.
  • Algorithmic optimizations: Applying Min-KS and OF-Limb yields 1.72×, 2.20×, and 2.08× speedups for HELR, ResNet-20, and sorting, respectively.HELR benefits less because bootstrapping is only 39.3% of execution and its reduced slot usage limits Min-KS reuse.
  • Memory and architecture sensitivity: Increasing scratchpad capacity from 256MB to 512MB gives higher speedups with the algorithms than without them across bootstrapping, HELR, ResNet-20, and sorting.With the algorithms, the speedups are 1.83×, 1.18×, 1.45×, and 1.50×, respectively.
  • Alternative designs: Alternative designs show that limb-wise-only distribution reduces performance, doubling clusters improves bootstrapping, and doubling HBM bandwidth improves bootstrapping by only 1.07×.HELR is an exception, improving 1.47× with doubled HBM bandwidth because some memory-bound rotations are not covered by Min-KS.
  • Sensitivity analysis: Increasing MAC units per BConv lane from one to six improves HELR and ResNet-20 performance by 1.37× and 1.72×, while non-bootstrapping operations need little extra scratchpad.Bootstrapping remains highly sensitive to scratchpad size.

VIII. RECENT FHE ACCELERATORS AND PRACTICALITY

ARK is positioned against recent FHE accelerators and related CPU, GPU, FPGA, and ASIC designs, achieving higher reported performance while retaining a large chip footprint.

  • Recent FHE accelerators: ARK is 1.23× to 2.58× faster than CraterLake across TA.S., HELR, and ResNet-20.The comparison uses 128-bit secure settings and accounts for CraterLake’s reported configurations.
  • Recent FHE accelerators: BTS addresses evaluation-key loading through parameter search and dataflow optimization, whereas ARK uses algorithmic reductions and data-access-aware architecture.BTS uses 512MB of on-chip memory and coefficient-wise data distribution.
  • Practicality: ARK, CraterLake, and BTS require much larger chip areas than F1 because they employ massive on-chip memories.ARK occupies 418.3mm2 compared with F1’s 151.4mm2.
  • Related work: Prior CPU, GPU, and FPGA approaches often accelerate only subsets of HE operations or target non-bootstrappable and limited-parameter workloads.F1 improves primitive operations but does not target parameters suitable for practical bootstrapping, while BTS and CraterLake do.
  • Conclusion: ARK combines minimum key-switching, on-the-fly limb extension, and data-movement-aware functional-unit design to deliver two to four orders of magnitude higher performance than prior works.The paper reports 0.125-second real-time encrypted ResNet-20 inference.
Loading 2205.00922v3…