PaperlayerView exact revision on arXiv

Source-linked AI summary

F1: A Fast and Programmable Accelerator for Fully Homomorphic Encryption (Extended Version)

Axel Feldmann, Nikola Samardzic, Aleksandar Krastev, Srini Devadas, Ron Dreslinski, Karim Eldefrawy, Nicholas Genise, Chris Peikert, Daniel Sanchez

arXiv:2109.05371v2cs.CRcs.AR

TL;DR

FHE enables secure computation on encrypted data, but software overheads and prior accelerators' limited programmability constrain its broader use. F1 combines programmable acceleration of FHE primitives with hardware–compiler co-design to minimize data movement, achieving large speedups and enabling secure real-time deep learning inference.

  • Problem

    FHE can secure computation on encrypted data, but current encryption requires decryption before processing, while prior accelerators do not execute arbitrary FHE programs efficiently.

  • Method

    F1 is a programmable accelerator that combines specialized high-throughput functional units, an explicitly managed memory hierarchy, decoupled data movement, and compiler scheduling to maximize reuse.

  • Results

    F1 accelerates complete FHE programs, delivering 1,200×–17,000× speedups over state-of-the-art software implementations and reducing one deep-learning inference from 20 minutes to 240 milliseconds.

  • Takeaways & Limitations

    F1's programmability preserves ASIC-level performance while supporting arbitrary FHE programs and multiple FHE schemes, enabling secure real-time deep-learning inference.

  • Takeaways & Limitations

    F1's design remains constrained by memory bandwidth, making data reuse crucial despite 1 TB/s of external bandwidth.

Abstract

from arXiv · show

Fully Homomorphic Encryption (FHE) allows computing on encrypted data, enabling secure offloading of computation to untrusted serves. Though it provides ideal security, FHE is expensive when executed in software, 4 to 5 orders of magnitude slower than computing on unencrypted data. These overheads are a major barrier to FHE's widespread adoption. We present F1, the first FHE accelerator that is programmable, i.e., capable of executing full FHE programs. F1 builds on an in-depth architectural analysis of the characteristics of FHE computations that reveals acceleration opportunities. F1 is a wide-vector processor with novel functional units deeply specialized to FHE primitives, such as modular arithmetic, number-theoretic transforms, and structured permutations. This organization provides so much compute throughput that data movement becomes the bottleneck. Thus, F1 is primarily designed to minimize data movement. The F1 hardware provides an explicitly managed memory hierarchy and mechanisms to decouple data movement from execution. A novel compiler leverages these mechanisms to maximize reuse and schedule off-chip and on-chip data movement. We evaluate F1 using cycle-accurate simulations and RTL synthesis. F1 is the first system to accelerate complete FHE programs and outperforms state-of-the-art software implementations by gmean 5400x and by up to 17000x. These speedups counter most of FHE's overheads and enable new applications, like real-time private deep learning in the cloud.

1 INTRODUCTION

FHE protects data during computation but remains far slower than unencrypted execution. F1 addresses this gap with a programmable accelerator designed around FHE computation and data-movement characteristics.

  • Motivation: 10,000× to 100,000× slower than unencrypted computation, even in carefully optimized software, motivates hardware acceleration for FHE.The paper identifies this slowdown as the central performance barrier.
  • Gap: Prior accelerators target individual operations, omit important functionality, and are often restricted to specific schemes or parameters.These limitations prevent them from efficiently executing arbitrary FHE programs.
  • F1 design: F1 is the first programmable FHE accelerator, combining specialized functional units with compiler and hardware mechanisms designed to minimize data movement.Its design targets modular arithmetic, NTTs, automorphisms, static scheduling, reuse, and latency hiding.
  • Evaluation: 1,200×–17,000× speedups over state-of-the-art software implementations are demonstrated using complete FHE applications.The implementation includes 36 tera-ops/second of 32-bit modular arithmetic, 64 MB of on-chip storage, and 1 TB/s memory bandwidth.
  • Evaluation: 240 milliseconds reduces a deep learning inference previously taking 20 minutes, enabling secure real-time deep learning in the cloud.The reported inference time is comparable to server-client roundtrip latency when computation is offloaded.

2 BACKGROUND

FHE evaluates arithmetic on encrypted polynomial data, preserving correctness after decryption while imposing restricted operations, noise growth, and costly ciphertext transformations.

  • FHE model: FHE lets a server compute on ciphertexts so decrypting the result matches computation on plaintext values.This supports computation outsourcing without exposing the underlying data.
  • FHE model: FHE programs are dataflow graphs with statically known operations and dependences, and they cannot use data-dependent branching.This programming model enables static scheduling but restricts algorithm structure.
  • FHE model: BGV ciphertexts encode plaintext vectors as polynomials, while supported vector operations include addition, multiplication, and selected permutations.Ciphertext polynomials use coefficients modulo Q, whereas plaintext coefficients are modulo t.
  • Homomorphic operations: Homomorphic multiplication and permutation require key switching, which is expensive and can dominate multiplication cost.Multiplication first assembles an intermediate ciphertext, while permutation applies an automorphism before key switching.
  • Noise: Multiplicative depth primarily determines noise growth because multiplication increases noise much more than addition or permutation.Noise limits how many operations can be performed before decryption fails unless noise-management strategies are used.

2.3 Algorithmic insights and optimizations

FHE acceleration relies on algorithmic transformations that reduce polynomial-arithmetic cost and represent wide coefficients using narrower residues suitable for efficient hardware.

  • NTT optimization: NTT(a b) = NTT(a) ⊙ NTT(b), so multiplication becomes component-wise in the NTT domain.The relation requires a negacyclic NTT for N-point transforms.
  • NTT optimization: O(N log N) modular operations let NTT-based polynomial multiplication replace naive O(N^2) coefficient convolution.The method uses two forward NTTs, component-wise multiplication, and an inverse NTT.
  • Key switching: Key switching combines inverse and forward NTTs with modular products across residue-polynomial indices to produce two output vectors.The implementation accumulates u0 and u1 across i and j before returning them.
  • RNS optimization: RNS represents a polynomial modulo Q as L residue polynomials modulo smaller primes, avoiding expensive wide arithmetic.For 32-bit words and a 512-bit modulus, the representation uses L = 16 residue polynomials.

2.4 Architectural analysis of FHE

Key-switching analysis shows that FHE acceleration is dominated by data movement, not arithmetic, because operands and reusable hints are too large for on-chip storage. F1 therefore combines decoupled movement, substantial on-chip capacity, high-throughput primitives, and flexibility across algorithms.

  • Key-switching dominates the work in the evaluated FHE benchmarks.
  • At L=16 and N=16K, key-switch hints occupy 32 MB, while fetching each key-switch’s inputs would require about 10 TB/s of memory bandwidth.
  • Key-switch hints are reusable across homomorphic multiplications, but their size means that few values fit on-chip.
  • Tiling key-switching does not effectively reduce storage needs while preserving reuse because it creates long-lived intermediates or conflicts with NTT data dependencies.
  • FHE accelerators therefore need decoupled data movement and more than 32 MB of on-chip storage in the example to sustain reuse across operations.
  • F1 uses relatively few high-throughput primitive units and avoids fixed-function key-switching to preserve reuse and algorithmic diversity.

2.5 FHE schemes other than BGV

BGV is not the only relevant FHE scheme: CKKS, B/FV, and GSW make different tradeoffs in plaintext representation, modulus switching, noise growth, and information capacity. F1 supports BGV, CKKS, and GSW on shared primitive hardware, but its current implementation does not target B/FV.

  • CKKS supports approximate computation on fixed-point values, unlike BGV’s integer plaintexts.
  • B/FV avoids modulus switching before homomorphic multiplication, simplifying programming while foregoing modulo-switching efficiency gains.
  • GSW offers reduced, asymmetric noise growth under homomorphic multiplication but encrypts less information per ciphertext than a full N/2-element vector.
  • F1 supports BGV, CKKS, and GSW with the same hardware because they use the same primitive operations, but current F1 does not target B/FV.

3 F1 ARCHITECTURE

F1 is a wide-vector architecture specialized for FHE primitives, with explicitly managed storage, decoupled memory orchestration, and statically scheduled components. Its design prioritizes feeding high-throughput compute while simplifying control logic.

  • F1 provides vector functional units for modular addition, modular multiplication, forward and inverse NTTs, and automorphisms.
  • F1 uses 128 vector lanes and supports power-of-two vector lengths from 1,024 to 16,384 elements.
  • Fully pipelined functional units sustain 128 elements per cycle, including specialized implementations for NTTs and automorphisms.
  • The memory system combines a 64 MB, 16-bank scratchpad with HBM2 and an on-chip network connecting memory banks to compute clusters.
  • Scratchpad banks fetch data from main memory ahead of use, decoupling off-chip movement from computation while preventing clusters from accessing main memory directly.
  • Static scheduling removes functional-unit stalls, dynamic memory arbitration, and buffered packet-switching control from the hardware.

4 SCHEDULING DATA AND COMPUTATION

F1’s compiler uses multiple scheduling passes to maximize reuse and decouple off-chip movement before assigning exact cycles and on-chip resources. This organization targets data movement as the primary performance constraint.

  • Compiler pipeline: The compiler transforms a high-level FHE DSL through homomorphic-operation ordering, off-chip movement scheduling, and cycle-level scheduling.
  • Compiling homomorphic operations: The first phase clusters operations sharing key-switch hints and orders them to improve reuse before translating them into instruction-level dataflow.
  • Compiling homomorphic operations: Reordering four multiplies and then corresponding rotations reuses each key-switch hint four times instead of cycling through all hints repeatedly.
  • Compiling homomorphic operations: The compiler chooses among key-switch implementations using noise level L, expected hint reuse, and functional-unit load.
  • Scheduling data movement: The second phase greedily schedules computation and loads while selecting evictions by estimated reuse time, approximating Belady’s optimal replacement policy.
  • Cycle-level scheduling: The final phase distributes operations across clusters and schedules on-chip resources at exact cycles without adding off-chip loads or stores.
  • Cycle-level scheduling: Static schedules also serve as a performance measurement tool, enabling rapid design-space exploration for different architecture configurations.

5 FUNCTIONAL UNITS

F1’s functional units target the difficult vector operations central to FHE, especially automorphisms and NTTs, using specialized, pipelined designs that support varied parameters. These units deliver high throughput while reducing the need for large crossbars and many parallel units.

  • Overview: F1 introduces a vectorized automorphism unit, a fully pipelined flexible NTT unit, and a simplified modular multiplier adapted to FHE.These are the paper’s three novel functional-unit contributions.
  • 5.1 Automorphism unit: Automorphisms decompose into independent column and row permutations when a residue polynomial is viewed as a G×E matrix.After transposition, both permutations can be applied in E-element chunks local to each vector.
  • 5.1 Automorphism unit: The automorphism unit applies chunk-local permutations, transposes the G×E matrix, applies row permutations, and reverses the transpose at E=128 elements/cycle.Fixed sub-permutations are selectively applied or bypassed, avoiding crossbars for the row and column operations.
  • 5.1 Automorphism unit: The transpose unit recursively uses quadrant swaps to transpose E×E matrices and remains usable for power-of-two dimensions with G<E.Its quadrant-swap building block swaps quadrants B and C in three K/2-cycle steps.
  • 5.2 Four-step NTT unit: F1 implements N-element NTTs from 1K to 16K by composing E=128-element NTTs in a fully pipelined four-step datapath.The pipeline performs smaller NTTs, twiddle multiplication, transposition, and another NTT, with layers conditionally bypassed to support all N.
  • 5.2 Four-step NTT unit: 1,600×: the fully pipelined four-step NTT unit improves NTT performance over the state of the art.The unit uses 896 multipliers, trading substantial area for high throughput.
  • 5.3 Modular multiplier: 19% area and 30% power reductions result from restricting moduli to q_i = −1 mod 2^16, while still allowing 6,186 prime moduli.The restriction is described as acceptable because FHE requires at most tens of moduli.

6 F1 IMPLEMENTATION

F1 is implemented in a commercial 14/12nm process with high-throughput compute, substantial on-chip storage, and high-bandwidth memory. Despite these resources, off-chip memory bandwidth remains the principal system constraint.

  • Physical implementation: A dual-frequency design runs most components at 1 GHz and memories at 2 GHz, enabling two accesses per cycle with single-ported SRAMs.Keeping most logic at 1 GHz is intended to improve energy efficiency.
  • Physical implementation: F1’s synthesized configuration occupies 151.4 mm2 and uses 1 TB/s of HBM2 bandwidth.The implementation uses commercial SRAM for scratchpad and register-file banks.
  • Area breakdown: Functional units occupy 42% of area, memory 31.7%, the on-chip network 6.6%, and the two HBM2 PHYs 19.7%.The reported breakdown is for the 151.4 mm2 F1 configuration.
  • Memory system: 1 TB/s off-chip bandwidth constrains F1, compared with 24 TB/s in the on-chip network and 128 TB/s between register files and functional units.The mismatch makes maximizing data reuse crucial.

7 EXPERIMENTAL METHODOLOGY

The evaluation uses cycle-accurate simulation of F1 programs ported from state-of-the-art FHE software, supplemented by RTL-derived energy estimates and hardware comparisons. Benchmarks cover logistic regression, neural networks, database lookup, and bootstrapping across CKKS and BGV settings.

  • Modeled system: F1 is evaluated with a cycle-accurate simulator that executes its instruction streams and checks component latencies, dependences, and structural hazards.RTL-synthesis activity levels provide the energy breakdowns.
  • Benchmarks: Benchmarks include HELR logistic-regression training, LoLa-MNIST and LoLa-CIFAR neural networks, DB Lookup, and CKKS and BGV bootstrapping.The workloads exercise different multiplicative depths, automorphism frequencies, and data-movement demands.
  • Benchmarks: LoLa-MNIST has encrypted- and unencrypted-weight variants, whereas LoLa-CIFAR is evaluated only with unencrypted weights.The neural-network benchmarks use CKKS in this evaluation because the original LoLa implementation uses unsupported B/FV for those cases.
  • Bootstrapping workloads: BGV and CKKS bootstrapping use L_max=24, with BGV using Sheriff and Peikert’s non-packed algorithm and CKKS using HEA-AN’s non-packed algorithm.The BGV benchmark stresses scheduler choices at large L; CKKS offers fewer ciphertext multiplications and fewer key-switch-hint reuse opportunities.
  • Baselines: F1 is compared with a 4-core, 8-thread, 3.5 GHz Xeon E3-1240v5 running baseline programs, while prior accelerators are compared through single-operation microbenchmarks.Prior accelerators do not support complete FHE programs in the comparison.

8 EVALUATION

F1 delivers dramatic speedups on complete FHE benchmarks, while evaluation shows that memory traffic, specialized functional units, scheduling, and scaling strongly shape performance.

  • 8.1 Performance: 1,195× to 17,412× speedups, with 5,432× gmean, are achieved by F1 over the CPU on full benchmarks.CKKS bootstrapping has the lowest speedup because it is highly memory-bound.
  • 8.1 Performance: 241 milliseconds reduces LoLa-CIFAR inference from 20 minutes, making real-time deep learning inference practical.The reported latency is comparable to server-client roundtrip latency when inference is offloaded.
  • 8.1 Performance: 172× to 1,866× speedups over HEAXσ demonstrate large gains on microbenchmarks, while pure compute omits FHE program data-movement bottlenecks.The microbenchmarks cover NTT, automorphism, homomorphic multiplication, and permutation operations.
  • 8.2 Architectural analysis: Key-switch hints account for up to 94% of traffic in high-depth workloads, while non-compulsory accesses add only 5–18% for most benchmarks.LoLa-CIFAR is an exception: intermediates consume 75% of traffic because exploiting key-switch-hint reuse requires spilling intermediate ciphertexts.
  • 8.2 Architectural analysis: Data movement dominates power, while computation consumes 20–30% overall; average functional-unit utilization is about 30%.Memory-bound phases lower average utilization, whereas decoupled execution helps sustain compute intensity during bandwidth peaks.
  • 8.3 Design-space analysis: 2.6× and 3.3× gmean slowdowns from low-throughput functional units show that high-throughput units improve performance by avoiding data-movement disruption.A register-pressure-aware scheduler also causes large slowdowns, indicating that prior capacity-aware scheduling is ineffective for F1.
  • 8.4 Scalability: Performance grows about linearly across a large area range as F1 scales its compute clusters, scratchpad banks, HBM controllers, and network topology.The evaluated designs form a performance-versus-area Pareto frontier.

9 RELATED WORK

Related accelerators generally target individual operations, fixed pipelines, or hybrid HE-MPC settings, whereas F1 supports complete and flexible FHE programs by treating data movement as central.

  • FHE accelerators: Prior FHE accelerators target individual operations rather than full FHE computations, often relying on host processors and FPGA-based designs.These designs can be dominated by host-FPGA communication and may be specialized to particular schemes or parameters.
  • FHE accelerators: F1 addresses full-program flexibility because fixed pipelines cannot support the operations of even a single benchmark, while data movement requires reuse across homomorphic operations.Its wide-vector execution and high-throughput functional units support full applications and different FHE schemes.
  • Hybrid HE-MPC accelerators: Hybrid HE-MPC accelerators execute one network layer at a time and send intermediates to the client for final activations, unlike F1’s full-inference offloading.These approaches combine homomorphic encryption with multi-party computation.
  • Hybrid HE-MPC accelerators: Cheetah and Gazelle use ciphertexts up to ∼40× smaller than F1’s but require client re-encryption after each server multiplication to prevent noise blowup.Their direct comparison with F1 is not possible because they use different execution models and communication patterns.
  • Hardware organization: Cheetah and Gazelle use fixed-function pipelines, whereas F1 is programmable and uses fewer high-throughput units instead of many low-throughput units.The paper gives F1’s NTT units as 40× faster than the relevant low-throughput design style.
  • GPU acceleration: GPU acceleration of B/FV multiplication achieves around 10× to 100× over single-thread CPU execution, with lower gains expected against multicore CPUs.FHE operations parallelize well across multicore CPUs.

10 CONCLUSION

F1 addresses FHE’s large computation overheads with a programmable accelerator for complete computations. Its reported acceleration expands FHE toward applications such as secure real-time deep learning inference.

  • 10 CONCLUSION: F1 accelerates full FHE computations by over 3–4 orders of magnitude, addressing overheads that limit FHE to narrow privacy-critical cases.The conclusion identifies high computation overheads as the current applicability constraint.
  • 10 CONCLUSION: Secure real-time deep learning inference is identified as a new use case enabled by F1’s acceleration.This consequence is stated within the paper’s supported application scope.
  • 10 CONCLUSION: F1 combines programmable execution with high-throughput primitive functional units and hardware-compiler co-design that minimizes data movement.The same hardware can support all operations within a program, arbitrary FHE programs, and multiple FHE schemes.
Loading 2109.05371v2…