PaperlayerView exact revision on arXiv

Source-linked AI summary

FPGA Acceleration of Fully Homomorphic Encryption with Adaptive Key Switching

Zhihan Xu, Jayashree Adivarahan, Rajgopal Kannan, Viktor K. Prasanna

arXiv:2609.09423v1cs.CRcs.AR

TL;DR

Key-switching is a major FHE bottleneck, and KLSS’s reduced computational complexity comes with memory and precision demands that make its FPGA performance dependent on the hardware setting. The paper combines a memory-efficient KLSS datapath and a model-guided accelerator that switches between KLSS and HKS at runtime. On an Alveo U280, the adaptive design outperformed state-of-the-art FPGA accelerators on bootstrapping and secure image classification.

  • Problem

    Key-switching is a major FHE bottleneck, and it is unclear whether KLSS’s computational savings outweigh its higher memory and precision demands on FPGA systems.

    Source: §I · p. 1

  • Method

    The paper proposes a memory-efficient KLSS datapath and a performance-model-guided accelerator that switches between KLSS and HKS at runtime.

    Source: §I · pp. 1–2

  • Results

    1.84–3.31× speedup on bootstrapping and 1.66–2.52× on secure image classification over state-of-the-art FPGA accelerators.

    Source: §I · p. 2

  • Takeaways & Limitations

    The adaptive design demonstrated high performance on both shallow benchmarks with small parameter sets and deep workloads with large parameter sets.

    Source: §VIII · p. 9

Abstract

from arXiv · show

Fully Homomorphic Encryption (FHE) enables privacy-preserving cloud services but incurs substantial computation overhead, making hardware acceleration essential. Among FHE operations, key-switching is a major performance bottleneck. Recent cryptographic advances introduce a novel key-switching method (i.e., KLSS) that reduces certain operational complexity but demands higher computational precision than the traditional Hybrid Key Switching (HKS) method. This trade-off leads to distinct computation and memory requirements, making the relative latency of KLSS and HKS highly dependent on hardware parallelism, FHE security parameters, and available on-chip memory capacity, particularly on FPGA platforms, where memory resources and parallelism must be carefully balanced. In this work, we first propose a memory-efficient KLSS datapath that eliminates off-chip ciphertext transfers. We then develop a performance model to analyze and compare the overheads of both KLSS and HKS. Our analysis reveals that an adaptive solution supporting both methods can achieve lower overall latency than a static method during FHE computation. Guided by the performance model, we design an adaptive FPGA-based FHE accelerator that dynamically selects between HKS and KLSS during computation. We implement the accelerator on an Alveo U280 and evaluate it across multiple FHE benchmarks. Experimental results demonstrate that our adaptive solution achieves a 1.84-3.31$\times$ speedup in bootstrapping latency and a 1.66-2.52$\times$ speedup in secure image classification compared to state-of-the-art FPGA accelerators.

I. INTRODUCTION

Key-switching is a major FHE bottleneck, while KLSS’s lower computational complexity comes with greater memory and precision demands that make its FPGA performance uncertain. The paper addresses this trade-off with a memory-efficient KLSS datapath, a performance model, and runtime selection between KLSS and HKS.

I. INTRODUCTION

  • Key-switching can account for 80% of runtime, and KLSS’s reduced NTT count comes with higher evaluation-key memory and precision demands.The paper therefore asks whether KLSS is beneficial on FPGA systems with varying hardware architectures and memory capacity.Source: §I · p. 1
  • The proposed KLSS datapath avoids intermediate ciphertext transfers to off-chip memory, improving data reuse and arithmetic intensity.It is designed for FPGA devices with limited on-chip memory.Source: §I · p. 1
  • A model of computation and memory footprint shows that neither HKS nor KLSS is universally optimal, motivating runtime switching based on computation depth and parameter configuration.The accelerator supports both methods and dynamically switches between them during computation.Source: §I · pp. 1–2
  • 1.84–3.31× speedup on bootstrapping and 1.66–2.52× on secure image classification over state-of-the-art FPGA accelerators.The accelerator was implemented on an Alveo U280 and evaluated across multiple parameter sets and FHE benchmarks.Source: §I · p. 2

II. BACKGROUND

  • The paper focuses on CKKS, which supports approximate arithmetic over fixed-point real or complex numbers for applications such as machine learning.Source: §II · p. 2

A. RNS-CKKS FHE scheme

  • RNS-CKKS represents ciphertext polynomials using limbs over machine-word-sized primes, with a freshly encrypted ciphertext containing 2(L + 1) limbs.The full modulus is decomposed into coprime moduli.Source: A. RNS-CKKS FHE scheme · p. 2

1) CKKS Operations:

CKKS operations include addition, multiplication, and rotation, while ciphertext maintenance includes key-switching, rescaling, and bootstrapping. These maintenance operations support continued computation as ciphertexts change and levels are consumed.

1) CKKS Operations:

  • CKKS addition adds ciphertext components, multiplication applies polynomial products plus key-switching, and rotation permutes coefficients before key-switching.Source: 1) CKKS Operations · p. 2

2) Ct Maintenance Operations:

  • Key-switching is required after each multiplication and rotation and primarily performs an inner product between the input polynomial and evaluation key.Source: 2) Ct Maintenance Operations · p. 2
  • Rescaling removes the last modulus and consumes one multiplicative level, restoring the message scale after multiplication.Source: 2) Ct Maintenance Operations · p. 2
  • When a ciphertext reaches level 0, bootstrapping refreshes its levels and enables deep circuits without returning ciphertexts to the client.Bootstrapping involves many multiplications and rotations, making key-switching its dominant cost.Source: 2) Ct Maintenance Operations · p. 2

B. Key-switching

Key-switching uses NTT, inverse NTT, basis conversion, and key inner products. HKS and KLSS differ in how they decompose and convert data, with KLSS reducing required NTT operations while adding limb recovery.

B. Key-switching

  • Basis conversion cannot be performed in the evaluation domain, so inverse NTT precedes it and NTT converts the result back afterward.Basis conversion computes inner products across limbs; ModUp increases the modulus and ModDown decreases it.Source: B. Key-switching · p. 2
  • HKS decomposes the input ciphertext into β digits, extends each digit with ModUp, multiplies by the evaluation key, then applies ModDown.Source: B. Key-switching · pp. 2–3
  • KLSS decomposes the evaluation key into a tensor, reducing ModUp’s basis-conversion work and the required NTT operations, then performs limb recovery before ModDown.Limb recovery uses basis conversion to restore the number of limbs before aggregation.Source: B. Key-switching · p. 3

III. MEMORY-EFFICIENT KLSS DATAPATH ON FPGA

The proposed KLSS datapath uses memory-aware buffering and scheduling to execute entirely on-chip, avoiding intermediate ciphertext transfers to off-chip memory.

III. MEMORY-EFFICIENT KLSS DATAPATH ON FPGA

  • During ModUp, the α and α′ limbs require a 13 MB buffer; the original α limbs can then be discarded to free memory.The α′ limbs in RT use a 62-bit coefficient modulus.Source: §III · pp. 3–4
  • The 35 MB KLSS evaluation key exceeds remaining on-chip memory, so row-wise chunking and double buffering stream key data during KeyInnerProd.Two evaluation-key chunks are buffered simultaneously; together with input and output buffers, the memory requirement fits on-chip SRAM.Source: §III · p. 4
  • Fusing limb recovery with ModDown reduces required buffering from about 38 MB to about 19 MB.The design recovers the α limbs needed for each ModDown and generates the remaining limbs one-by-one for immediate subtraction.Source: §III · p. 4
  • Evk chunking, double buffering, and fusion of limb recovery with ModDown let KLSS execute entirely on-chip without intermediate ciphertext transfers.The design targets an FPGA with 43 MB SRAM.Source: §III · pp. 3–4

IV. ANALYTICAL MODEL FOR HKS-KLSS SELECTION

The section develops a performance model that maps algorithmic complexity to execution cycles using hardware and device characteristics, then applies it to choose between HKS and KLSS.

IV. ANALYTICAL MODEL FOR HKS-KLSS SELECTION

  • The model maps algorithmic complexity to execution cycles while incorporating accelerator architecture and device characteristics.It follows a summary of computational complexity for FHE primitives under HKS and KLSS.Source: §IV · p. 4
  • The model is used to determine whether HKS or KLSS should be applied for different benchmarks and FHE parameter sets.Source: §IV · p. 4
  • The analysis covers both HKS and KLSS primitive-operation complexity before modeling their execution on the accelerator.Source: §IV · p. 4

A. Computational Complexity Analysis

HKS and KLSS have different primitive-operation costs: KLSS reduces NTT count, but its complexity for other operations can depend on the parameter set.

A. Computational Complexity Analysis

B. Performance Modeling

The performance model accounts for compute and memory time, including the differing coefficient sizes and parallelism of HKS and KLSS.

B. Performance Modeling

  • The accelerator is modeled as processing dp coefficients per cycle, with conflict-free on-chip memory supply after off-chip data is loaded.dp denotes SIMD parallelism, or the number of compute lanes.Source: B. Performance Modeling · pp. 4–5
  • HKS uses smaller coefficients than KLSS and can therefore achieve higher SIMD parallelism under the same resource budget.The model represents the difference as dpHKS = δ · dpKLSS.Source: B. Performance Modeling · p. 5
  • Primitive-operation compute time is derived from algorithmic complexity, while operation latency is modeled using computation and memory time.The primitive set is iNTT, NTT, BConv, and KeyInnerProd.Source: B. Performance Modeling · p. 5
  • Memory time is modeled using peak off-chip bandwidth, total read and write transfer volumes, and clock frequency.Source: B. Performance Modeling · p. 5

C. Motivating Example

HKS and KLSS trade places in efficiency as ciphertext levels change, motivating runtime selection between them. The accelerator combines configurable compute and permutation resources to support both modes.

C. Motivating Example

  • KLSS is faster at high Ct levels, while HKS becomes more efficient as Ct falls, motivating runtime switching.The crossover reflects KLSS's reduced limb count at high levels and HKS's greater parallelism as KLSS's algorithmic advantage narrows.Source: C. Motivating Example · p. 5, Figure 2 · p. 5

V. THE PROPOSED ACCELERATOR

  • The accelerator combines a compute array, scratchpad, permute unit, and scheduler, which switches methods using Ct metadata.The array and permutation unit support two parallelism modes; the scheduler also coordinates their tasks.Source: §V · p. 5, Figure 3 · p. 5

A. Adaptive Compute Array

  • Each compute unit has two regular cores and one KLSS core, enabling 512-lane regular execution or 256-lane KLSS execution.Regular cores use 32-bit coefficients; KLSS cores use 62-bit coefficients, matching parallelism to arithmetic precision.Source: A. Adaptive Compute Array · pp. 5–6
  • The 62-bit modular multiplier uses Solinas primes to reduce DSP use, an optimization not applicable to RQ's many distinct moduli.The reduction uses shifts and additions instead of multipliers.Source: A. Adaptive Compute Array · p. 6

B. Adaptive Permute Unit

The accelerator adapts permutation throughput and scratchpad access to its two execution modes. Its scheduler overlaps permutation and computation in both modes using limb packing where needed.

B. Adaptive Permute Unit

  • The permutation unit combines butterfly-based spatial networks with temporal reorder buffers to support arbitrary coefficient permutations.Its physical width is 256 coefficients per cycle; packing two 32-bit coefficients from different limbs provides 512 logical coefficients per cycle for regular execution.Source: B. Adaptive Permute Unit · p. 6, Figure 4 · p. 6

C. Multi-bank Scratchpad

  • Eight dual-port scratchpad banks serve 256 62-bit or 512 32-bit coefficients per access and store limbs for the memory-efficient KLSS datapath.The scratchpad also serves HBM and compute-array requests, and its capacity avoids intermediate ciphertext transfers off-chip.Source: C. Multi-bank Scratchpad · p. 6

D. Datapath Scheduler

  • The scheduler uses Ct metadata and model-derived switching points to select HKS or KLSS, while overlapping permutation and computation in both modes.For regular execution, it packs coefficients from two limbs to match the 256-lane permute unit to the compute array's 512-lane throughput.Source: D. Datapath Scheduler · pp. 6–7

E. Resource Utilization

The accelerator's key-switching advantage depends on parameter scale: HKS leads on the small set, while KLSS leads on the large set. On the large set, it also outperforms prior FPGA accelerators for Mult and Rotate.

E. Resource Utilization

  • DSP resources are used only by the compute array; BRAM also supports temporal-permutation buffers and HBM AXI interfaces.Table III summarizes accelerator resource consumption.Source: E. Resource Utilization · p. 7

A. Experimental Setup

  • Evaluation uses two 128-bit-security parameter sets, only the larger of which supports bootstrapping, and excludes PCIe transfer time from latency.Set-2 matches parameter configurations in prior FPGA work for comparison.Source: A. Experimental Setup · p. 7

C. Performance on FHE Operations

B. Key-switching Performance

  • On Set-1, HKS is approximately 3× faster than KLSS; on Set-2, KLSS achieves about 1.3× speedup over HKS.HKS performs better at small Ct levels and KLSS at large levels; the reported explanation cites HKS's higher parallelism and KLSS's reduced limb count in dominant operations.Source: B. Key-switching Performance · p. 7, Figure 5 · p. 7

D. Performance on Benchmarks

Across application-level benchmarks, adaptive key switching improves performance on deep workloads while HKS remains preferable across the small benchmark’s ciphertext levels. The work situates this FPGA design against prior accelerators and concludes that a performance model and memory-efficient KLSS datapath support runtime choice between HKS and KLSS.

D. Performance on Benchmarks

  • The evaluation covers LoLA-MNIST on Set-1, bootstrapping on Set-2, and secure CIFAR-10 ResNet-20, which traverses the ciphertext-level span over multiple bootstrap rounds.The benchmarks compare HKS-only, KLSS-only, and Adaptive configurations; the application-level evaluation accounts for ciphertext levels decreasing during execution.Source: D. Performance on Benchmarks · p. 8
  • For LoLA-MNIST, HKS-only and Adaptive perform equally because HKS is selected from ciphertext levels 8 through 3; both achieve 1.14×–58.5× speedup over prior FPGA works.The reported gains reflect higher compute parallelism than FxHENN and Yang and better compute-unit utilization than DAHE and OLA.Source: D. Performance on Benchmarks · p. 8
  • 1.84×–3.31× bootstrapping speedup and 1.66×–2.52× RN-20 inference speedup over prior FPGA accelerators demonstrate the adaptive design’s deep-benchmark performance.On RN-20, Adaptive is 2.08× faster than HKS-only and 1.27× faster than KLSS-only.Source: Table VII · p. 8, D. Performance on Benchmarks · p. 8

VII. RELATED WORK

  • Prior FPGA accelerators mainly use HKS, while FAST and HAWK introduce adaptive HKS/KLSS on ASICs but rely on large on-chip SRAM; this work targets memory-constrained FPGAs.The paper identifies its design as the first FPGA accelerator to implement KLSS and evaluate adaptive key switching on full FHE benchmarks.Source: §VII · p. 8

VIII. CONCLUSION

  • The performance model captures computation and memory footprint, finding that neither HKS nor KLSS is universally optimal and supporting runtime selection between them.The conclusion ties their efficiency to ciphertext level and a trade-off between parallelism and algorithmic complexity.Source: §VIII · p. 8
  • The memory-efficient KLSS datapath avoids intermediate ciphertext transfers to off-chip memory, and the Alveo U280 implementation performs across shallow and deep workloads.The conclusion attributes improved FPGA FHE performance to supporting adaptive key-switching methods and hardware parallelism.Source: §VIII · p. 9
Loading 2609.09423v1…