PaperlayerView exact revision on arXiv

Source-linked AI summary

HEAX: An Architecture for Computing on Encrypted Data

M. Sadegh Riazi, Kim Laine, Blake Pelton, Wei Dai

arXiv:1909.09731v2cs.CRcs.AIcs.ARcs.PF

TL;DR

FHE preserves data confidentiality during cloud computation, but its enormous overhead limits large-scale use. HEAX introduces a flexible, highly parallel FPGA architecture centered on NTT and optimized FHE operations, with implementations demonstrating broad performance gains while focusing on CKKS and retaining the scheme’s security properties.

  • Problem

    FHE enables encrypted computation without cloud trust, but enormous computation overhead remains the critical obstacle to large-scale deployment.

  • Method

    HEAX combines high-throughput NTT, optimized modular arithmetic, multi-level parallelism, and pipelined FPGA modules for CKKS and other FHE operations.

  • Results

    HEAX implementations on reconfigurable hardware demonstrate 164–268× performance improvement across a wide range of FHE parameters.

  • Takeaways & Limitations

    HEAX provides a flexible FPGA architecture for CKKS that can be adjusted across FPGA resource configurations and is not tied to one FHE parameter set.

  • Takeaways & Limitations

    The paper focuses on CKKS, although its core modules are described as applicable to most FHE schemes.

Abstract

from arXiv · show

With the rapid increase in cloud computing, concerns surrounding data privacy, security, and confidentiality also have been increased significantly. Not only cloud providers are susceptible to internal and external hacks, but also in some scenarios, data owners cannot outsource the computation due to privacy laws such as GDPR, HIPAA, or CCPA. Fully Homomorphic Encryption (FHE) is a groundbreaking invention in cryptography that, unlike traditional cryptosystems, enables computation on encrypted data without ever decrypting it. However, the most critical obstacle in deploying FHE at large-scale is the enormous computation overhead. In this paper, we present HEAX, a novel hardware architecture for FHE that achieves unprecedented performance improvement. HEAX leverages multiple levels of parallelism, ranging from ciphertext-level to fine-grained modular arithmetic level. Our first contribution is a new highly-parallelizable architecture for number-theoretic transform (NTT) which can be of independent interest as NTT is frequently used in many lattice-based cryptography systems. Building on top of NTT engine, we design a novel architecture for computation on homomorphically encrypted data. We also introduce several techniques to enable an end-to-end, fully pipelined design as well as reducing on-chip memory consumption. Our implementation on reconfigurable hardware demonstrates 164-268x performance improvement for a wide range of FHE parameters.

1 INTRODUCTION

FHE enables computation on encrypted data while preserving end-to-end confidentiality, but its substantial computational overhead remains the main barrier to large-scale deployment. HEAX addresses this challenge with a flexible hardware architecture built around high-throughput NTT and parallel FHE operations.

  • Motivation: FHE lets cloud servers evaluate functions on ciphertexts while only the data owner can decrypt intermediate and final results.This supports privacy-preserving cloud applications without requiring the cloud provider to access plaintext data.
  • Motivation: The main obstacle to deploying FHE at scale is enormous computation overhead compared with plaintext execution.
  • Motivation: CKKS performs approximate real-number computation and supports efficient truncation, motivating its use for applications such as encrypted machine learning.The paper focuses on CKKS while noting that its core modules apply to most FHE schemes.
  • Contributions: HEAX combines optimized modular-arithmetic blocks, a high-throughput NTT architecture, and higher-level FHE modules for encrypted-data computation.The design targets multiple levels of parallelism and is intended to accelerate FHE-based privacy-preserving systems.
  • Challenges: FHE hardware must handle intensive big-integer modular arithmetic, complex data dependencies, large polynomial degrees, and prohibitive intermediate-data storage demands.These constraints make high-throughput architecture design difficult and limit practical accelerator designs.

2 PRELIMINARIES

The preliminaries define the CKKS algebraic setting and the arithmetic primitives used by HEAX. They cover polynomial rings, RNS representations, modular reduction and multiplication, gadget decomposition, and core CKKS subroutines.

  • Algebraic setting: The paper works over the polynomial ring R = Z[X]/(X^n + 1), with residue ring R_q = R/qR and coefficients represented modulo q.The parameter n is assumed to be a power of two.
  • Residue Number System: RNS decomposes q into pairwise-coprime moduli, enabling polynomial arithmetic over R_q to be performed across separate residue bases.The representation supports parallel modular operations on corresponding residues.
  • CKKS operations: Gadget decomposition maps an element of R_q to a vector of small polynomials whose gadget inner product reconstructs the original element modulo q.
  • CKKS operations: CKKS subroutines include setup, symmetric encryption, key generation, and addition over ciphertexts represented in the defined polynomial rings.The preliminaries introduce these operations before presenting hardware architectures for homomorphic computation.
  • Modular arithmetic: Mod(x, p) reduces integer values modulo p, while MulRed(x, y, y′, p) computes x · y (mod p) using a precomputed quotient approximation.MulRed is specified for w-bit words and moduli p < 2^w−2.

3 MULT MODULE

The MULT module accelerates homomorphic multiplication by exploiting NTT form, RNS-level independence, and parallel dyadic cores. Its architecture supports flexible ciphertext sizes while reducing on-chip memory demands and adapting FPGA word operations.

  • Word size and native operations: Using 54-bit words instead of 64-bit native operations reduces required DSP units by 1.4–2.25× across HE parameters.The FPGA implementations use 27-bit DSP units, making 27-bit or 54-bit words efficient choices.
  • Homomorphic multiplication: Because ciphertexts are normally in NTT form, multiplication becomes a sequence of dyadic products across ciphertext components.The architecture for ciphertext-plaintext multiplication is treated as a special case of ciphertext-ciphertext multiplication.
  • MULT architecture: The MULT module instantiates ncDYD Dyadic Cores and computes ncDYD dyadic multiplications per clock cycle.Each core consumes two polynomial coefficients, two precomputed constants, and a prime modulus, then outputs the result.
  • Homomorphic multiplication: CKKS homomorphic multiplication produces a ciphertext with α + β − 1 components from ciphertexts containing α and β components.The multiplication is performed in RNS and NTT form and produces a ciphertext encrypting the product of the plaintexts.
  • Memory organization: RNS independence lets the design store only one residue of one ciphertext component on the FPGA, reducing BRAM utilization.The computation can proceed independently for each RNS basis.

4 NTT MODULE

The NTT module accelerates polynomial transforms through parallel, pipelined modular arithmetic and adaptable core-level throughput. Its memory and coefficient-reordering architecture addresses changing access patterns, pipeline bubbles, and FPGA resource limits.

  • 4.1 Algorithms: NTT and inverse NTT are computationally intensive operations, while NTT-based polynomial multiplication reduces the need for repeated transform conversions.The paper uses NTT over a finite field to support efficient negacyclic convolution and keeps polynomials in NTT form when possible.
  • 4.2 NTT Architecture: A fully pipelined FHE design allocates one NTT module per algorithmic NTT operation and adjusts each module's throughput through its number of NTT cores.The required relative throughput depends on the selected FHE parameters.
  • 4.2 NTT Architecture: The NTT module computes a polynomial transform in log n stages, processing 2ncNTT coefficients per step and using parallel data, twiddle-factor, and output memories.Each NTT core accepts two coefficients, one twiddle factor, precomputed data, and a prime, then produces two transformed coefficients through pipelined modular arithmetic.
  • 4.3 Access Patterns: Changing coefficient access patterns divide NTT execution into Type 1 and Type 2 stages, with Type 2 stages selecting coefficient pairs independently within each memory element.Type 1 stages read paired coefficients from different memory elements; after inter-memory dependency ends, Type 2 stages require local selection and reordering.
  • 4.4 Reordering Coefficients and Optimal MUXs: Optimal multiplexers reduce the eight-core NTT register count from 224,000 to 97,000 and avoid inefficient scaling caused by super-linear resource consumption.The design replaces larger multiplexers with multiplexers whose size is bounded by the logarithm of the number of NTT cores.
  • 4.4 Reordering Coefficients and Optimal MUXs: Without addressing cross-memory coefficient access, two memory elements must be read before computation, creating a 50% pipeline bubble and reducing throughput to (log n − log ncNTT − 1)/log n.This issue affects the first log n − log ncNTT − 1 NTT stages.
  • 4.5 Memory Organization: Parallel storage across FPGA memory blocks can underutilize memory capacity in both depth and width when multiple polynomial coefficients are stored concurrently.The paper identifies this as a memory-consumption challenge for the architecture.

5 KEYSWITCH MODULE

The KeySwitch module implements CKKS key switching as a balanced, end-to-end pipeline of inverse and forward NTTs, dyadic multiplication, accumulation, and modulus switching. Its architecture matches component throughputs while using buffering to handle data dependencies and reduce on-chip memory use.

  • 5.2 KeySwitch Architecture: KeySwitch transforms one RNS-component polynomial at a time, applying INTT, NTTs across other primes, dyadic multiplication, accumulation, and modulus switching.The design outputs two polynomials and performs the final Floor-based modulus-switching stage before producing the new ciphertext.
  • 5.3 Balancing Throughput: KeySwitch uses multiple NTT modules because each initial INTT requires k NTTs, with throughput choices determined by the number of RNS components.The architecture can use one larger NTT module or multiple smaller modules; Figure 5 selects the latter for its stated parameter setting.
  • 5.3 Balancing Throughput: The design targets a fully end-to-end pipeline that processes multiple key-switching operations simultaneously without excessive FIFOs.Component core counts are tuned so NTT, dyadic multiplication, and related stages have compatible throughputs.
  • 5.4 KeySwitch Ops. and Synchronization: All KeySwitch modules and internal components are pipelined, allowing different key-switching operations to occupy different stages concurrently.The high-level pipeline balances throughput across stages, including synchronized dyadic modules and modulus switching.
  • 5.4 KeySwitch Ops. and Synchronization: Data dependencies require additional BRAM buffers because delayed dyadic computation can encounter overwritten input polynomials and modulus switching depends on prior outputs.The design allocates buffers for input polynomials and DyadMult outputs to prevent these dependencies from corrupting pipeline execution.

6 SYSTEM-VIEW and DATA FLOW

HEAX connects a host CPU and FPGA board over PCIe, with the FPGA using on-chip BRAM and off-chip DRAM for computation and storage. The system avoids off-chip intermediate-result traffic where possible, but larger parameter sets require DRAM for key-switching keys and use pipelined transfers to mitigate bandwidth effects.

  • System View: The HEAX system view comprises a host CPU, an FPGA board connected through PCIe, an FPGA chip, and off-chip DRAM connected through DDR.The FPGA board contains both the computation device and external memory used by the design.
  • Memory Organization: On-chip BRAM provides fast, high-throughput storage but limited capacity, whereas off-chip DRAM offers several Gigabytes with higher response delay.The architecture therefore aims to avoid off-chip accesses for intermediate results because their read/write delays reduce performance.
  • Memory Organization: For n = 2^14, insufficient BRAM forces part of the design into off-chip memory, while n = 2^13 has sufficient on-chip memory on Stratix 10.The design places key-switching keys in DRAM because their size grows rapidly with HE parameters.
  • Data Transfer: HEAX distributes key-switching keys across four DRAM banks and pipelines burst reads to use available off-chip bandwidth and reduce throughput loss.The reported DRAM bandwidth is sufficient to match KeySwitch throughput; for n = 2^14 and k = 8, two key sets require approximately 151 megabits.
  • Data Transfer: The system can retain computation results in DRAM and reference them through a CPU-held memory map, avoiding PCIe transfers when results will be reused soon.This storage path is intended for applications where returning results to the CPU immediately is inefficient.
  • Data Transfer: CPU-side batching and multithreaded PCIe transfers are paired with FPGA-side buffers to interleave computation and data movement.DMA reduces copying overhead, while double buffering suffices for MULT and quadruple buffering is required for KeySwitch dependencies.

7 IMPLEMENTATION and EXPERIMENTS

HEAX is implemented on two FPGAs and evaluated across multiple CKKS parameter sets, with pipelined architectures designed around resource and memory constraints. It substantially outperforms CPU, GPU, and prior baselines while scaling with available hardware resources.

  • Experimental Setup: HEAX is implemented on Arria 10 and Stratix 10 FPGAs and evaluated across parameter sets spanning n = 2^12 to n = 2^14 and 109- to 438-bit ciphertext moduli.The evaluation uses Set-A, Set-B, and Set-C parameter sets.
  • Experimental Setup: HEAX reaches maximum clock frequencies of 275 MHz on Arria 10 and 300 MHz on Stratix 10.The design eliminates critical paths through repeated design iterations.
  • Scalability: The Stratix 10 instantiation consumes close to twice the resources and provides twice the throughput of the Arria 10 instantiation for Set-A.This demonstrates scaling across different FPGA resource levels without manual tuning.
  • Performance: HEAX’s NTT architecture is 36–81× faster than data-center GPUs and consumes significantly less power.The comparison uses a Stratix 10 implementation with ten 16-core NTT modules.
  • Architecture: The implementation uses end-to-end pipelining because modulus switching and other computation stages have non-parallelizable dependencies.Separate modules and pipeline stages are used rather than time-sharing one NTT/INTT module across different steps.
  • Performance: 164–268× performance improvements are achieved over CPU execution for high-level CKKS operations across multiple HE parameter sets on Stratix 10.The comparison covers Rotation, Relinearization, and complete ciphertext multiplication.

8 RELATED WORK

Prior hardware work has accelerated selected operations, relied on off-chip memory, or targeted narrow parameter sets, while CKKS lacked comparable FPGA or GPU architectures. HEAX addresses this gap with a CKKS-focused FPGA design.

  • CKKS Acceleration: Before HEAX, hardware acceleration for CKKS was not available in the cited FPGA and GPU literature.The paper identifies HEAX as the first architecture proposed and implemented for CKKS.
  • Prior Hardware: A prior BFV FPGA system for n = 2^15 suffered massive off-chip data transfer and did not outperform CPU execution.The cited work illustrates the performance cost of relying on off-chip memory.
  • Prior Hardware: Roy et al. reported 13× speed-up over FV-NFLlib for n = 2^12 using two processors, but comparison with Microsoft SEAL was less favorable.Their architecture targeted BFV and avoided off-chip memory by focusing on a modest parameter size.
  • Platform Choice: FPGAs are presented as more suitable than GPUs for high-performance, low-power secure computation because GPUs generally provide less performance per watt.The cited comparison motivates FPGA-based acceleration for encrypted computation.
  • Security and Assumptions: Some YASHE and LTV architectures rely on constructions subject to a subfield lattice attack and no longer considered secure.Another cited YASHE design assumes unlimited memory bandwidth, limiting the realism of its off-chip-memory model.

9 CONCLUSION

HEAX introduces flexible, fully implemented FPGA architectures for CKKS and evaluates them across two FPGA platforms and a wide range of FHE parameters. The authors report more than two orders of magnitude of performance improvement and identify applicability beyond CKKS.

  • Contributions: HEAX is presented as the first fully implemented hardware acceleration architecture for the CKKS FHE scheme.The design targets encrypted computation with CKKS, which supports floating-point operations and is described as a candidate for machine learning on encrypted data.
  • Flexibility: The architecture is flexible across FPGA chips and is not tied to a specific FHE parameter set.The proof-of-concept implementation uses two FPGAs with contrasting hardware resources.
  • Results: More than two orders of magnitude of performance improvement are demonstrated across a wide range of FHE parameters.The evaluation supports the paper’s claim of broad performance gains rather than a result for only one parameter configuration.
  • Scope: HEAX components can also be used for other lattice-based cryptosystems and other FHE or HE schemes.This extends the stated scope beyond the CKKS architecture evaluated in the paper.
Loading 1909.09731v2…