End-to-End NTT on FPGA for FHE Acceleration

arXiv:2611.03325v1 [cs.CR] 2 Nov 2026

End-to-End NTT on FPGA for FHE Acceleration Mohamed Allam

Thomas Spendlhofer

mohamed.allam@bsc.es Barcelona Supercomputing Center (BSC) Barcelona, Spain Universitat Politècnica de Catalunya (UPC) Barcelona, Spain

thomas.spendlhofer@bsc.es Barcelona Supercomputing Center (BSC) Barcelona, Spain

Hugo Sanz-González

Antonio J. Peña

hsanzgon@bsc.es Barcelona Supercomputing Center (BSC) Barcelona, Spain

antonio.pena@bsc.es Barcelona Supercomputing Center (BSC) Barcelona, Spain

Abstract Fully homomorphic encryption (FHE) enables privacy-preserving computation on encrypted data without decryption. Despite its strong security guarantees, FHE incurs substantial computational and memory overhead. In FHE-based deep learning inference, on average 63% of the CPU time is spent on the number theoretic transform (NTT) and its inverse (INTT), which reduce the complexity of polynomial multiplication from 𝑂 (𝑁 2 ) to 𝑂 (𝑁 log 𝑁 ). Prior FPGA works follow two approaches: accelerating entire FHE schemes, which yields significant speedups but ties them to specific parameters and algorithms, or accelerating only the NTT, which applies across schemes, algorithms, and libraries. Most FPGA NTT designs require interconnects that grow with parallelism and utilize significant resources, which complicates routing on multi-die FPGAs. Additionally, to the best of our knowledge, end-to-end NTT acceleration within an FHE context has so far been left unexplored. We design a fully unrolled, delay-commutator streaming NTT/ INTT kernel, and floorplan it across the three dies of an AMD Alveo V80. At 400 MHz, the kernel transforms a polynomial of 216 coefficients every 5.12 𝜇s, the highest throughput among FPGA designs at this size. Offloaded end to end, it is up to 22× faster than the CPU per transform. We integrate the kernel into the Lattigo FHE library and evaluate it end to end. With 128-bit secure parameters, it accelerates core FHE operations, such as key switching and bootstrapping, by 1.8–2.2×, and neural network inference by 1.8–2.1×.

Keywords Privacy-Preserving Machine Learning, Fully Homomorphic Encryption, FPGA, NTT, CKKS, Private Inference

1

Introduction

Fully homomorphic encryption (FHE) [22] is a lattice-based, quantum-safe cryptographic primitive that enables computation on encrypted data without decryption. It is particularly useful for preserving data privacy in cloud computing, since it enables servers to process sensitive information—such as medical or financial records—while maintaining end-to-end confidentiality. However, FHE incurs significant memory and computational overhead: depending on the cryptographic parameters, it may

require orders of magnitude more memory and computation than the same calculation on unencrypted data. FHE schemes used in machine learning, primarily CKKS [9], encode plaintext data into polynomials over large modular rings, so that encrypted computation reduces to polynomial arithmetic. Polynomial multiplication in particular is a critical performance bottleneck. The number theoretic transform (NTT) reduces the complexity of this multiplication from 𝑂 (𝑁 2 ) to 𝑂 (𝑁 log 𝑁 ). The NTT and its inverse (INTT) dominate the cost of key CKKS operations such as key switching and bootstrapping [27]. In our experiments, they consume on average ∼63% of the CPU time in FHE neural network inference. The NTT is costly because of its large working set, irregular access patterns, and modular arithmetic on large integers. FPGAs are a strong acceleration fit for the NTT, since these enable pipelined architectures tailored to modular arithmetic and memory layouts that match its access patterns. State-of-the-art FPGA works [2, 3, 60, 61, 63] often accelerate an entire FHE scheme; despite significant speedups over CPUs, they are tailored to one implementation of a scheme and hard to adapt to new schemes or algorithms. Dedicated NTT accelerators instead apply across schemes, algorithms, and libraries. Most FPGA accelerators propose iterative or partially unrolled architectures [2, 3, 12, 35–37, 40, 45, 57, 60], which operate at high parallelism and utilize significant resources. Given the access patterns of the NTT, they generate significant routing congestion and are challenging to place and route on multi-die FPGAs, often exhausting the limited inter-die wires at high frequencies. Fully unrolled designs alleviate routing demands by dedicating a pipelined hardware stage to each transform stage. Works that reach high parallelism reorder coefficients among groups of stages through addressed buffers, shufflers or transposes [34, 38, 71], while those built on delay commutators, which reorder with fixed delays and switches only, have been implemented at low parallelism or small polynomial sizes [10, 25, 54, 56, 67, 69]. Across these works, timing closure at high frequency, routing congestion, and multi-die placement are rarely discussed, and, to the best of our knowledge, none evaluates end-to-end NTT offloading within an FHE library or application. In this work, we address these challenges through a fully unrolled, delay-commutator streaming NTT/INTT kernel, floorplanned across the three dies of an AMD Alveo V80 FPGA,

Allam et al.

integrated into the Lattigo [16] FHE library and evaluated on privacy-preserving neural network inference. In summary, our main contributions are: • A placed-and-routed streaming NTT/INTT kernel for 𝑁 =216 and 62-bit primes on a multi-die FPGA, with the highest frequency and throughput among comparable FPGA designs. • Integration of the kernel into the Lattigo FHE library, and evaluation of end-to-end NTT/INTT offloading, up to ∼22× faster than the CPU per transform, and of core CKKS operations, such as key switching and bootstrapping, with up to ∼2× speedup. • End-to-end evaluation on several FHE neural network inference workloads, attaining speedups of up to ∼15× for NTT/INTT and ∼2× for inference. The rest of the paper is structured as follows. Section 2 introduces FHE, the RNS-CKKS scheme and the NTT. Section 3 describes the kernel architecture and our design considerations. Section 4 presents the experimental setup and evaluation. Section 5 discusses related work, and Section 6 concludes the paper.

2

Background

In this section, we provide the necessary theoretical background on FHE, the RNS-CKKS scheme, and NTT.

2.1

FHE and RNS-CKKS

FHE is a cryptographic primitive whose security relies on the hardness of lattice-based assumptions, primarily the learning with errors (LWE) and ring-LWE problems [44, 49], which offer post-quantum security guarantees. CKKS [9] is an approximate FHE scheme that encodes vectors of real or complex numbers and supports efficient SIMD computation. A message is represented as a plaintext polynomial whose coefficients approximate the target values under a fixed scaling factor. This polynomial is then encrypted to produce a ciphertext of two polynomials (𝑎, 𝑏) under secret key 𝑠, which carries a small noise for security that grows with each operation. The ability of CKKS to handle real numbers and perform vectorized linear algebra—such as matrix multiplications, convolutions, dot products, and activation approximations—makes it particularly effective for privacy-preserving deep learning inference [48]. In CKKS, encrypted computation is performed as approximate arithmetic over the cyclotomic ring 𝑅𝑄 = Z𝑄 [𝑋 ]/(𝑋 𝑁 + 1), where 𝑁 is a power of two and 𝑄 is a large integer modulus. Homomorphic multiplication of two ciphertexts results in a ciphertext of three polynomials (𝑎, 𝑏, 𝑐) encrypted under 𝑠 2 and an increased scale. The rescaling operation restores the scale, while relinearization restores the ciphertext to the form (𝑎, 𝑏), encrypted under the original key 𝑠. The latter is attained via key switching, which is also needed after rotations. RNS-CKKS [8] uses the Chinese remainder theorem to store each polynomial as 𝐿+1 residue polynomials, or limbs, one per prime of Î𝐿 the ciphertext modulus 𝑄 = 𝑖=0 𝑞𝑖 . Rescaling divides a ciphertext by its last prime, removing one limb; a ciphertext with ℓ+1 limbs is at level ℓ. RNS-CKKS is often combined with hybrid key switching [24], Î which limits noise growth with an auxiliary modulus 𝑃 = 𝑗 𝑝 𝑗 , extending the ring to 𝑅𝑄𝑃 . Hybrid key switching splits the limbs

into dnum digits, each extended to 𝑄𝑃 and transformed with NTTs, so the NTT/INTT work grows with dnum [31]. Once a ciphertext is left with a single limb, bootstrapping is required to refresh it. This process raises the ciphertext to a higher level, enabling further multiplications. Bootstrapping is the most expensive operation in CKKS, performing many rotations and multiplications, each followed by a key switch [6, 7].

2.2

NTT

NTT is a fundamental algorithm for efficient polynomial multiplication. It reduces the computational complexity from 𝑂 (𝑁 2 ) to 𝑂 (𝑁 log 𝑁 ), where 𝑁 , a power of two, is the polynomial degree, by operating in a polynomial ring Z𝑞 [𝑋 ]/Φ(𝑋 ). If Φ(𝑋 ) = 𝑋 𝑁 − 1, the NTT computes a positively-wrapped convolution (PWC), using an 𝑁 -th primitive root of unity 𝜔 satisfying 𝜔 𝑁 ≡ 1 (mod 𝑞). However, PWC requires explicit zero-padding to emulate linear convolution, which is inefficient. To avoid this, FHE schemes typically work in the negacyclic ring Z𝑞 [𝑋 ]/(𝑋 𝑁 + 1), where polynomial multiplication is a negatively-wrapped convolution (NWC). NWC requires a primitive 2𝑁 -th root of unity 𝜓 , such that 𝜓 𝑁 ≡ −1 (mod 𝑞) and 𝜓 2 ≡ 𝜔 (mod 𝑞). NWC may be implemented by scaling the inputs and outputs of a standard NTT: pre-multiplying polynomial coefficients by 𝜓 𝑖 before the forward transform and post-multiplying by 𝜓 −𝑖 after the inverse transform. The pre-scaling and post-scaling operations may be fused into the transform itself by merging the powers of 𝜓 into the twiddle factors, producing the NTT𝜓 variant. The forward and inverse transforms are provided in equations (1) and (2), respectively.

𝑎b𝑗 =

𝑁 −1 ∑︁

𝑎𝑖 𝜓 𝑖 (2𝑗+1)

(mod 𝑞)

(1)

𝑖=0

𝑎𝑖 = 𝑁 −1

𝑁 −1 ∑︁

𝑎b𝑗 𝜓 −𝑖 (2𝑗+1)

(mod 𝑞)

(2)

𝑗=0

This formulation is algebraically equivalent to NWC but performs no scaling outside the transform. The main difference between the NTT and INTT lies in the type of butterfly operation performed, as well as in the fact that the INTT requires a final scaling by 𝑁 −1 mod 𝑞. Forward NTT uses the

Algorithm 1 Cooley–Tukey NTT𝜓 1: procedure NTT(𝐴, 𝑁 , 𝑞,𝜓 )

⊲ 𝜓 : 2𝑁 -th root of unity for 𝑚 ← 1, 2, 4, . . . , 𝑁 /2 do 3: 𝑡 ← 𝑁 /(2𝑚) 4: for 𝑖 ← 0 . . . 𝑚 − 1 do 5: 𝜁 ← 𝜓 bit_rev(𝑚+𝑖 ) mod 𝑞 6: for 𝑗 ← 2𝑖𝑡 . . . (2𝑖 + 1)𝑡 − 1 do 7: 𝑢 ← 𝐴[ 𝑗], 𝑣 ← 𝐴[ 𝑗 + 𝑡] · 𝜁 mod 𝑞 8: 𝐴[ 𝑗] ← 𝑢 + 𝑣 mod 𝑞, 𝐴[ 𝑗 + 𝑡] ← 𝑢 − 𝑣 mod 𝑞 9: end for 10: end for 11: end for 12: return 𝐴 13: end procedure 2:

End-to-End NTT on FPGA for FHE Acceleration

kernel clock

QDMA H2C stream

512 b

CDC FIFO

reorder buffer (2 limbs)

16 queues

stage

1

2

3

4

5

6

7

8

9 10 11 12 13 14 15

16

8

4

2

1

1

1

1

1

1

16 BUs per stage

0

Host CPU

PCIe 32 × 62 b

C2H stream 512 b

CDC FIFO

FIFO

output serializer

1

1

2

4

8

twiddle generators

commutator

16

𝑐

32 × 62 b

TF roots store

HBM

𝐴𝑖

𝑧 −2

𝐴

MM

TF

68 twiddle generators

scheduler

64 × 2 (NTT/INTT)

FIFO swap NTT/INTT limb (0,1,2)

lane wiring

.. . 𝐵𝑖

control (PCIe BAR)

reg

AXI4-Lite CSRs

(a) Kernel overview. H2C/C2H: host-to-card/card-to-host streams; CDC: clockdomain crossing; TF: twiddle factor; BU: butterfly unit. Numbers below the stages: twiddle generators per stage.

2𝑐 : 1–1,024 words, set per transform type

𝐴′

BU1

operand delay 25 cyc.

𝑐 𝑧 −2

𝐵

BU0

𝐵′

BU15

reg

𝑐

(b) Pipeline stage. 𝐴/𝐵: the two 16-lane paths; 𝑧 −2 : delay of 2𝑐 words; reg: register; BU: butterfly unit; TF: twiddle factor.

Figure 1: The streaming NTT/INTT kernel. Cooley–Tukey (CT) butterfly, whereas INTT uses the Gentleman– Sande (GS) butterfly, as shown in equations (3) and (4), where 𝜁 is a power of 𝜓 (the twiddle factor). 𝑢′ = 𝑢 + 𝑣 · 𝜁

(mod 𝑞),

𝑣′ = 𝑢 − 𝑣 · 𝜁

(mod 𝑞)

𝑢′ = 𝑢 + 𝑣

(3)

(mod 𝑞),

𝑣 ′ = (𝑢 − 𝑣) · 𝜁 −1

Clock

Memory

Size

CDC FIFO (input) Reorder buffer Pipeline FIFO (input) Pipeline FIFO (output) Output serializer CDC FIFO (output)

DMA → kernel kernel kernel kernel kernel kernel → DMA

BRAM URAM (32) URAM (28) URAM (56) LUTRAM BRAM

512 × 512 b 8 × 4,096 × 248 b 4,096 × 1,984 b 8,192 × 1,984 b 32 × 1,984 b 512 × 512 b

(4)

Methodology

In this section, we describe our kernel architecture and its main components: the stream interface, the streaming pipeline, the butterfly unit and on-the-fly twiddle factor generation, and finally how we floorplan it across the FPGA dies.

3.1

Buffer

(mod 𝑞)

Algorithm 1 illustrates a CT forward NTT𝜓 with input in natural order and output in bit-reversed order.

3

Table 1: Buffers in the stream interface.

Overall Architecture

Figure 1a shows the kernel, a fully pipelined streaming NTT/INTT architecture for 𝑁 = 216 and moduli of up to 𝑘 = 62 bits. Limbs are streamed between host and kernel over the streaming queues of the QDMA engine, without staging in HBM. HBM holds only the twiddle roots, which a 256-bit AXI master loads into the roots store once, at setup. The pipeline consists of 16 stages, each computing one stage of the transform. Every stage contains 16 butterfly units (BUs) and between 1 and 16 on-the-fly twiddle generators, 68 in total. A scheduler coordinates the pipeline and keeps up to three limbs in flight at once. The host controls the kernel through an AXI4-Lite slave. It starts a job with a single register write and then polls for completion while results are streamed from the card to the host.

DMA clock: 333 MHz; kernel clock: 400 MHz.

3.2

Stream Interface

The host streams limbs through the QDMA engine in AXI4-Stream mode, with 16 queues per direction that share a 512-bit stream at 333 MHz (21.3 GB/s). A limb is split into 16 slices of 32 KB, one per queue. Two 512-beat clock-domain crossing (CDC) FIFOs, one per direction, pass the streams between the DMA and the kernel clocks. Reorder buffer. The reorder buffer turns 512-bit input beats, eight coefficients in host order, into pipeline words of 32 coefficients from across the limb. It consists of 8 banks, each four coefficients wide, followed by two layers of 2:1 multiplexers that place the coefficients on the pipeline lanes. Each beat is written to two banks in one cycle and each word reads every bank once, so neither writes nor reads conflict. The buffer holds two limbs; hence, one limb is written while the previous feeds the pipeline through a 4,096-word input FIFO. Output serializer. The output serializer turns each pipeline word into four 512-bit beats of eight coefficients, each padded to 64 bits, without reordering; the host places each coefficient at its index. It is fed by an 8,192-word output FIFO and consists of a 32-word LUTRAM FIFO whose head is read four times, once per beat, through a 4:1 multiplexer. Table 1 lists the buffers of the stream interface.

Allam et al.

Table 2: NTT and INTT stages. For each butterfly, the input position (word, path, lane) at which its two operands arrive, in input order (natural for NTT, bit-reversed for INTT). Stage Pairs

Operand 1 Operand 2

Stride

Via

NTT 0 1–11 12 13 14 15

(𝑡, 𝐴, 𝑖 ) (𝑡, 𝑝, 𝑖 ) (𝑡, 𝑝, 𝑖 ) (𝑡, 𝑝, 𝑖 ) (𝑡, 𝑝, 𝑖 ) (𝑡, 𝑝, 𝑖 )

(𝑡, 𝐵, 𝑖 ) (𝑡 +211−𝑠 , 𝑝, 𝑖 ) (𝑡, 𝑝, 𝑖+8) (𝑡, 𝑝, 𝑖+4) (𝑡, 𝑝, 𝑖+2) (𝑡, 𝑝, 𝑖+1)

none 211−𝑠 words 8 lanes 4 lanes 2 lanes 1 lane

– delay wiring wiring wiring wiring

(𝑡, 𝐴, 𝑖 ) (𝑡, 𝑝, 𝑖 ) (𝑡, 𝑝, 𝑖 ) (𝑡, 𝑝, 𝑖 ) (𝑡, 𝑝, 𝑖 ) (𝑡, 𝑝, 𝑖 )

(𝑡, 𝐵, 𝑖 ) (𝑡, 𝑝, 𝑖+1) (𝑡, 𝑝, 𝑖+2) (𝑡, 𝑝, 𝑖+4) (𝑡, 𝑝, 𝑖+8) (𝑡 +2𝑠 −5 , 𝑝, 𝑖 )

none 1 lane 2 lanes 4 lanes 8 lanes 2𝑠 −5 words

– wiring wiring wiring wiring delay

𝑎 𝑗 , 𝑎 𝑗 +215 𝑎 𝑗 , 𝑎 𝑗 +215−𝑠 𝑎 𝑗 , 𝑎 𝑗 +23 𝑎 𝑗 , 𝑎 𝑗 +22 𝑎 𝑗 , 𝑎 𝑗 +21 𝑎 𝑗 , 𝑎 𝑗 +20

INTT 0 𝑎 𝑗 , 𝑎 𝑗 +20 1 𝑎 𝑗 , 𝑎 𝑗 +21 2 𝑎 𝑗 , 𝑎 𝑗 +22 3 𝑎 𝑗 , 𝑎 𝑗 +23 4 𝑎 𝑗 , 𝑎 𝑗 +24 5–15 𝑎 𝑗 , 𝑎 𝑗 +2𝑠

3.3

Streaming Pipeline

The pipeline consumes one word of 32 coefficients per cycle, split into two paths, 𝐴 and 𝐵, of 16 lanes each, so a limb streams as 2,048 words over consecutive cycles. The reorder buffer places the two operands of each stage-0 pair on the same lane of 𝐴 and 𝐵: for the NTT, whose input is in natural order, the first half of the limb on 𝐴 and the second half on 𝐵; for the INTT, whose input is in bit-reversed order, the even positions on 𝐴 and the odd on 𝐵. Each stage (Figure 1b) comprises 16 butterflies and computes stage 𝑠 of the transform, for both transform types. It performs its 𝑁 /2 butterfly operations over 2,048 iterations, one word per iteration: it reorders the incoming 𝐴 and 𝐵, generates the twiddle factors its butterflies need, and passes 𝐴′ and 𝐵 ′ to the next stage. Butterfly 𝑖 is hardwired to lane 𝑖 of the 𝐴 and 𝐵 paths: it always reads 𝐴[𝑖] and 𝐵 [𝑖] and writes its two results back to them. Stage inputs must already be aligned when they arrive at the BUs. Table 2 lists, for every stage of both transform types, where the two operands of a pair arrive and their stride, the distance among the two operands in the stream. Three cases occur: • No stride (stage 0 of both transform types). The operands are placed in the same word and lane, on different paths, and the stage needs no reordering. • Stride of 2𝑐 words (NTT stages 1–11, INTT stages 5–15). The operands are placed on the same path and lane, 2𝑐 words apart. A delay commutator aligns them. • Stride of 2𝑙 lanes (NTT stages 12–15, INTT stages 1–4). The operands are placed in the same word and path, 2𝑙 lanes apart. A fixed lane wiring aligns them. Commutator. The commutator (Figure 1b) is an input register, a delay line on path 𝐵, a 2×2 swap, a delay line on path 𝐴, and an output register. Each delay line delays by 2𝑐 words and is 995 bits wide: 16 coefficients plus control bits, which travel with the data. Since the same physical stage serves both NTT and INTT, each line is built for the larger of its two delays (Table 3) and its depth is selected at run time by the transform type. Depending on depth, a

Table 3: Commutator delay per stage/transform. The larger of the two is built. S: shift registers (SRL), B: BRAM, U: URAM. Stage

0 1

NTT INTT

– 1K 512 256 128 64 32 16 8 4 2 1 – – – – – – – – – 1 2 4 8 16 32 64 128 256 512 1K

2

3

4

5

6

7 8 9 10 11 12

13

14 15

Built – 1K 512 256 128 64 32 16 8 16 32 64 128 256 512 1K Storage – U B B B B S S S S S B B B B U

delay line is implemented as shift registers (SRLs) up to 32 words, BRAM from 64 to 512 words, and URAM for the 1,024-word lines of stages 1 and 15. A RAM delay line is 14 BRAM36 or 14 URAM blocks wide. Together, the lines hold 130,304 coefficients (1.99𝑁 , 8.1 Mbit), the only large memory in the pipeline. The swap is two 2:1 multiplexers per lane, one per output, each selecting between the current 𝐴 and the delayed 𝐵: 32 coefficientwide multiplexers sharing one select. The select is registered and replicated 32 times, one copy per multiplexer. In stages where only one transform type uses the commutator, a further 2:1 multiplexer on each output bypasses it for the other, leaving only the input register. The latency of the commutator is 2𝑐 + 2 cycles. Lane wiring. The lane wiring is a fixed crossing of the lanes and utilizes no memory. For a stride of 2𝑙 lanes, it routes the operand of 𝐴[𝑖+2𝑙 ] onto 𝐵 [𝑖] in the lanes with bit 𝑙 clear, and that of 𝐵 [𝑖−2𝑙 ] onto 𝐴[𝑖] in the lanes with bit 𝑙 set; the other 16 coefficient positions are untouched. Because the other transform type uses a commutator at the same stage, each of the 16 rerouted positions implements a coefficient-wide 2:1 multiplexer selected by the transform type. The multiplexers feed the register that every stage features after its commutator, so the crossing adds no latency. Twiddle factor generators. A stage needs as many generators as the largest number of distinct twiddle factors its 16 butterflies require in one iteration, over both transform types. The twiddle of the pair 𝑎 𝑗 , 𝑎 𝑗+𝑑 , where 𝑑 is the stride of the stage in coefficient indices, depends only on ⌊ 𝑗/2𝑑⌋. When 𝑑 ≥ 16, the 16 pairs of an iteration share this value, hence one generator serves all 16 butterflies; when 𝑑 < 16, these need 16/𝑑 distinct twiddles and as many generators. Table 4 lists these counts; each stage implements the larger of its NTT and INTT counts, 68 generators in total.

3.4

Butterfly Unit

The butterfly unit, in Figure 2, computes CT butterflies for the forward transform and GS butterflies for the inverse. Both modes reuse the same units: a modular multiplier, a modular adder, a Table 4: Distinct twiddle factors per iteration, by stage and transform type. The larger of the two at each stage sets the number of on-the-fly twiddle factor generators implemented. Stage 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Tot. NTT 1 1 1 1 1 1 1 1 1 1 1 1 2 4 8 16 42 INTT 16 8 4 2 1 1 1 1 1 1 1 1 1 1 1 1 42 Built 16 8 4 2 1 1 1 1 1 1 1 1 2 4 8 16 68

End-to-End NTT on FPGA for FHE Acceleration

3.5

×2 −1

𝐴

𝐵

𝑇𝐹

delay

mod add

21 cyc.

4 cyc.

WLM

mod sub

21 cyc.

4 cyc.

out0

out1

0/4 cyc.

CT (NTT): out0 = 𝐴 + 𝐵 𝑇 𝐹 , out1 = 𝐴 − 𝐵 𝑇 𝐹 GS (INTT): out0 = (𝐴+𝐵) 2−1 , out1 = (𝐴−𝐵) 𝑇 𝐹 2−1

Figure 2: Butterfly unit. WLM: word-level Montgomery multiplier; unlabeled bars: 2:1 multiplexers selected by the transform type.

Algorithm 2 Word-Level Montgomery multiplication procedure WLM(𝐵,𝑇 𝐹, 𝑞) ⊲ 𝑊 = 17, 𝜆 = 4, 𝑅 = 2𝑊 𝜆 , 𝑞ℎ = 𝑞 ≫ 𝑊 𝑡 ← 𝐵 ·𝑇𝐹 ⊲ full 2𝑘-bit product for 𝑖 ← 1 . . . 𝜆 do 𝑡𝑙 ← 𝑡 mod 2𝑊 , 𝑡ℎ ← 𝑡 ≫ 𝑊 𝑡 ′ ← (−𝑡𝑙 ) mod 2𝑊 ⊲ 𝑞 ′ = −1: no multiply 𝑐 ← 𝑡 ′ [𝑊 −1] ∨ 𝑡𝑙 [𝑊 −1] ⊲ 𝑐 = 1 iff 𝑡𝑙 ≠ 0 𝑡 ← 𝑡ℎ + 𝑞 ℎ · 𝑡 ′ + 𝑐 end for if 𝑡 ≥ 𝑞 then 𝑡 ← 𝑡 − 𝑞 return 𝑡 ⊲ = 𝐵 · 𝑇 𝐹 · 𝑅 −1 mod 𝑞 end procedure

modular subtractor and a 21-cycle delay line. Multiplexers set by the transform type connect them in the CT or the GS order, and both output at the same latency. Modular multiplication uses word-level Montgomery reduction (WLM, Algorithm 2) with 𝑊 = 17-bit words, so that 2𝑊 = 2𝑁 ; at 𝑘 = 62, this requires 𝜆 = 4 reduction steps. NTT-friendly primes satisfy 𝑞 ≡ 1 mod 2𝑁 = 2𝑊 . Their Montgomery constant 𝑞 ′ = −𝑞 −1 mod 2𝑊 is therefore −1, and each reduction step needs no multiplication by 𝑞 ′ . The Montgomery factor 𝑅 is carried by the twiddle factors, so WLM(𝐵,𝑇 𝐹 ) returns 𝐵 · 𝜓 𝑒 . The inverse transform includes a final scaling by 𝑁 −1 mod 𝑞 (Equation (2)). Instead of a separate 𝑁 −1 multiplication on the output, each of the 16 stages scales both GS outputs by 1/2: together, these scale by 𝑁 −1 . Neither halving costs a multiplier: out0 is halved modulo 𝑞 by one 𝑘-bit carry chain (the ×2−1 block in Figure 2); out1 is halved for free, since 2−1 mod 𝑞 is folded into the twiddle factors. The WLM multiplier utilizes 20 DSP58 blocks: 12 for the full 62×62-bit product and two for each of the four reduction steps. The adder and subtractor are carry chains in LUTs with a conditional correction by 𝑞, and the delay line utilizes shift registers (SRLs). The 256 BUs utilize 5,120 DSPs.

On-the-Fly Twiddle Factor Generation

The NTT𝜓 requires 𝑁 − 1 twiddle factors per prime and transform type (Algorithm 1). Stored twiddle factors must be reloaded for every prime of the modulus chain and, since many butterflies share each of these, require either a distribution network, which adds routing congestion, or replicated storage larger than the polynomial itself. We therefore generate twiddle factors on the fly, trading storage for multipliers. We split each exponent into its low and high byte, 𝑒 = 𝑒𝑙𝑜 +256 𝑒ℎ𝑖 , 𝑖 and keep √ two sets of 256 twiddle roots, 𝑟𝑙𝑜 [𝑖] = 𝜓 and 𝑟ℎ𝑖 [𝑖] = 256𝑖 𝜓 (2 𝑁 in total), so that any twiddle factor is one modular multiplication of two roots [28, 32, 33, 67] (Equation (5)).
𝑒 𝜓 𝑒 = 𝜓 𝑒𝑙𝑜 · 𝜓 256 ℎ𝑖 = 𝑟𝑙𝑜 [𝑒𝑙𝑜 ] · 𝑟ℎ𝑖 [𝑒ℎ𝑖 ] (5) TF roots store. Since prime chains are known in advance, the host computes the twiddle roots of every prime and transform type once, at setup, and the kernel loads them from HBM into the on-chip roots store. The roots store holds up to 64 primes for both transform types, sufficient for a full CKKS modulus chain, and utilizes 16 URAM. The host also folds two constants into 𝑟𝑙𝑜 in advance: the Montgomery factor 𝑅 2 and, for the INTT, the 2−1 of the GS halving ′ [𝑖] = 𝜓 𝑖 𝑅 2 , or (Section 3.4). We denote these precomputed roots 𝑟𝑙𝑜 𝑖 2 −1 𝜓 𝑅 2 for the INTT. Local buffers. The generators read the twiddle roots from local buffers in each stage. Since up to three limbs, each with its own prime, may be in flight, every buffer holds three banks, one per limb; the scheduler fills a bank from the roots store in 512 cycles ahead of its limb, overlapping limb loading. In every iteration, the generators of a stage share 𝑒𝑙𝑜 and differ only in 𝑒ℎ𝑖 , so a stage ′ buffer for all its generators (three banks of 256 words keeps one 𝑟𝑙𝑜 in two BRAM36), while each generator keeps its own 𝑟ℎ𝑖 buffer. On-the-fly twiddle factor generator. The generator (Figure 3) ingests an exponent 𝑒, derived from the iteration and the transform type, and multiplies its two twiddle roots with one WLM multiplier (Equation (6)). The result is 𝜓 𝑒 𝑅, the operand the butterfly expects (Section 3.4). Each generator utilizes a WLM multiplier (20 DSPs) and its 𝑟ℎ𝑖 buffer (two BRAM36); the 68 generators utilize 1,360 DSPs and 136 BRAM36.
′ 𝑇 𝐹 = WLM 𝑟𝑙𝑜 [𝑒𝑙𝑜 ], 𝑟ℎ𝑖 [𝑒ℎ𝑖 ] = 𝜓 𝑒 𝑅 (· 2−1 ) mod 𝑞 (6)

′ buffer 𝑟𝑙𝑜

𝑒𝑙𝑜

′ [𝑒 ] 𝑟𝑙𝑜 𝑙𝑜

shared by stage

TF roots store

iteration 𝑡 , NTT/INTT

exponent 𝑒

𝑒ℎ𝑖

𝑟ℎ𝑖 buffer per generator

𝑟ℎ𝑖 [𝑒ℎ𝑖 ]

WLM

𝜓𝑒𝑅

generator

Figure 3: On-the-fly twiddle factor generator. WLM: wordlevel Montgomery multiplier.

Allam et al.

S0

S1

S2

S3

S4

S5

S6

S7

S8

S9

AMD EPYC 9645 processors (96 cores each) and 1.5 TB of memory. All CPU baselines use Lattigo v6.2.0 [16]. We used an AI assistant to help with analysis and plotting scripts.

AXI master S10

stream interface

HBM

QDMA

TF roots store

4.2 S15

SLR0

S14

2 words + TF

S13

S12

SLR1

S11

2 words + TF

SLR2

Figure 4: Floorplan. S0–S15: pipeline stages; black bars: registered SLR crossings of the stage chain; orange: twiddle-root broadcast from the TF roots store, registered per boundary.

3.6

Floorplan

The V80 features three SLRs, with 18,870 super long lines (SLLs) at each boundary. We manually floorplan all kernel cells (Figure 4). The two external interfaces of the kernel are placed at opposite ends of the device: the QDMA engine in SLR0 and the HBM ports next to SLR2. We therefore place the stream interface in SLR0 and the roots store, with the AXI master that loads it, in SLR2. The AXI master connects to an HBM BLI port, which bypasses the networkon-chip (NoC) of the V80 entirely. Limbs flow through a U-shaped pipeline that starts and ends next to the stream interface: S0–S1 and S14–S15 in SLR0, S2–S6 and S12–S13 in SLR1, and S7–S11 in SLR2. Twiddle roots flow against the forward direction of the limbs: for every limb, the roots store broadcasts the modulus and twiddle roots from SLR2 to all stages through a register tree, with one register pair per SLR boundary and one register in front of each stage. Each boundary is thus traversed only by two stage-to-stage words, one in each direction (S1/S2 and S13/S14, S6/S7 and S11/S12), each 1,984 data bits wide, and by the twiddle-root broadcast. Each of these paths is registered on both sides of the boundary, and together they utilize fewer than 4,200 SLLs. Control signals reach the stages through a register tree that limits their fan-out. Since they change only while the pipeline is idle or once per limb, we also constrain them as two-cycle multicycle paths, which relaxes their routing and eases timing closure: the reset, held for 1,300 cycles; the transform direction, changed only on an empty pipeline; the job configuration registers; and the modulus of each stage, which changes at most once every 2,048 cycles.

4

Evaluation

In this section, we describe the experimental setup, report implementation results, and compare our kernel with state-of-the-art FPGA designs. We then describe the integration into Lattigo, analyze offloading in terms of latency and power, and evaluate it on CKKS operations and FHE neural network inference workloads.

4.1

Experimental Setup

Our kernel is written in SystemVerilog and implemented for 𝑁 = 216 and primes of up to 62 bits on an AMD Alveo V80 card with Vivado 2025.1. Synthesis and implementation use the default strategies, followed by post-route physical optimization with the Explore directive. The card is attached over PCIe Gen5 x8 to a host with two

Implemented Kernel

4.2.1 Post-Place-and-Route Results. The kernel closes timing at 400 MHz, and we report all results at this frequency. It utilizes 60% of the DSPs of the V80 and about a quarter of its LUTs and FFs (Table 5). SLR1, which holds seven of the 16 stages, is the most utilized, with 73.5% of its DSPs. The design is not limited by routing resources: the kernel shows no routing congestion, and each SLR boundary utilizes 22.1% of its SLLs. The frequency is instead bound by wire delay across a clock domain that spans all three SLRs. The critical paths are shallow, 4.65 logic levels on average, but routing accounts for 74% of their delay. 4.2.2 Comparison with State-of-the-Art FPGA Designs. Table 6 compares the resource utilization, frequency, latency, and throughput of our kernel against prior FPGA NTT implementations. To weigh performance against hardware cost, we use the area-time product (ATP), the product of the latency and a normalized area term that aggregates LUTs, FFs, DSPs, BRAMs, and URAMs. Designs with lower parallelism [12, 23, 37, 40, 45, 67] run at 196– 300 MHz and require 54.9–168.8 𝜇s per transform at 𝑁 =216 , 11–33× our latency, mostly at a higher ATP. Zaman et al. [67], the only other delay-commutator pipeline in the table, use one butterfly per stage. Only Kurniawan et al. [40] reach a lower ATP, with 288 DSPs, but at 13× our latency. At 𝑁 =217 , Kim et al. [34] and Dang Truong et al. [11] require 89.5 and 257.7 𝜇s, at a higher ATP. Poseidon [63] reaches 450 MHz with 512 butterflies, but on 32-bit moduli, and requires 16× our latency at a higher ATP; SAM [57] requires 74× our latency, also at a higher ATP. The closest designs to ours are the four fully pipelined kernels with 256 butterflies on the U280: AutoNTT [38], AutoNest [71], Seven-step [35], and TP-NTT [36]. These run at 208–280 MHz and require 8.28–10.01 𝜇s per transform, 1.6–2.0× our latency. AutoNTT, AutoNest and Seven-step experience a higher ATP. TP-NTT attains a lower ATP, 7,692: it restricts the primes to utilize 11 DSPs per butterfly, against 25 for our kernel, and stores all 𝑁 twiddle factors per prime, against 512 twiddle roots for ours.

Table 5: Kernel per-SLR utilization and SLR crossings. Resource LUT FF DSP BRAM tile URAM SLLs

SLR0

SLR1

SLR2

223k (24.8%) 269k (32.8%) 178k (20.8%) 415k (23.0%) 505k (30.8%) 339k (19.8%) 2,240 (56.2%) 2,540 (73.5%) 1,700 (49.9%) 147 (11.0%) 212 (17.7%) 48 (4.0%) 172 (25.4%) 0 16 (2.6%) Used / available

SLR0 ↔ SLR1 4,178 / 18,870 (22.1%): 2,094 up, 2,084 down SLR1 ↔ SLR2 4,178 / 18,870 (22.1%): 2,094 up, 2,084 down

End-to-End NTT on FPGA for FHE Acceleration

Table 6: Comparison with state-of-the-art FPGA NTT implementations.

Implementation

Platform

N

log q

Red.

PEs

OTF TF

Stored TF

LUT/FF/BRAM/URAM/DSP

Freq. (MHz)

Lat. (𝜇s)

Th.put (NTT/s)

ATP

Poseidon [63] Kurniawan [40] Mareta [45] Duong-Ngoc [12] OpenNTT [37] SAM [57]

U280 VU37P U250 ZU9EG ZCU102 U250

216 216 216 216 216 216

32 60 60 60 52 64

Bar – Bar Bar WLM –

512 32 16 32 32 –

× × ✓ ✓ ✓ P

𝑁 𝑁 128 375 𝑂 (log 𝑁 ) 304

358k / 344k / 1,024 / 0 / 4,032 74.5k / 61.4k / 155𝑎 / 0 / 288 274.4k / 83.1k / 241𝑎 / 0 / 630 148.5k / 90.9k / 137𝑎 / 0 / 564 157k / 117k / 98 / 0 / 896 267k / 328k / 2,126𝑏 / – / 2,736

450 250 250 200 210 165

80.17 66.51 66.2 83.8 78.4 380

12,474 15,035 15,106 11,933 – –

92,320 7,702 16,266 15,761 19,882 414,732

Guo et al. [23] Zaman et al. [67] Kim et al. [34]𝑐 Dang Truong et al. [11] AutoNTT [38]𝑑 AutoNest [71] Seven-step [35] TP-NTT [36]

ZU15EG Virtex-7 VU190 VU13P U280 U280 U280 U280

216 216 217 217 216 216 216 216

64 64 62 62 64 64 64 60

Bar WLM Bar – WLM WLM WLM WLM

– 16 68 – 256 256 256 256

– P ✓ – × × P ×

– 6,206 – – – 𝑁 √ 𝑂( 𝑁) 𝑂 (𝑁 )

82.1k / 76.2k / 356.5𝑏 / – / 678 47.3k / 36.3k / 127 / 0 / 399 365k / 335k / 2,258𝑎 / 0 / 1,332 118.3k / 119.2k / 822 / 0 / 840 503k / 840k / 292 / 128 / 5,120 747k / 929k / 176 / 184 / 6,080 460k / 470k / 280 / 0 / 6,320 361k / 340k / 1,128𝑏 / – / 2,816

300 196 200 280 208 280 248 250

54.9 168.8 89.5 257.7 10.01 8.48 8.34 8.28

– – 11,170 – 99,900 117,925 119,904 –

13,097 20,580 76,808 97,900 15,574 15,950 12,560 7,692

V80

216

62

WLM

256

✓

512

670k / 1,259k / 407 / 188 / 6,480

400

5.12

195.3k

10,567

Our Work

Red.: WLM = word-level Montgomery, Bar = Barrett. OTF TF: twiddles generated on the fly (P: partial, only inter-dimension twiddles for SAM and Seven-step, the last five stages for Zaman). Stored TF: twiddles stored per prime. Lat.: average time per transform, over consecutive transforms for Zaman, Kim, Seven-step, and TP-NTT, 𝑁 /( coefficients per cycle · 𝑓 ) for AutoNTT, AutoNest, and ours, 1/throughput for Poseidon and single-transform latency otherwise. ATP = Lat. × (kLUT + kFF + DSP + BRAM + 8× URAM)/5. 𝑎 BRAM36 converted from the reported on-chip RAM in KB. 𝑏 BRAM36 equivalent, including URAM. 𝑐 INTT. 𝑑 HLS; reproduced on the U280 in [71].

Host→card

615 µs

CPU 222 µs (2.8×)

MM, 33 limbs

99 µs (6.2×)

Streaming, 1 limb

89 µs (6.9×)

Streaming, 33 limbs 0

Host→card Kernel Card→host

28 µs (22.0×) 200

400

Time per limb (µs)

600

Lattigo Integration

We integrate the kernel into Lattigo [16], an open-source FHE library, by offloading its Ring transforms, which cover all the limbs of a polynomial, and its SubRing transforms, covering a single limb. We batch the digit decomposition of key switching, which Lattigo transforms one limb at a time, into one call per digit, so that the card amortizes its transfers over multiple limbs. The offloaded transforms call a C library that we have developed, which interfaces with the QDMA driver and streams the limbs through its queues. Limbs are transferred without staging copies. The library also loads the twiddle roots of the prime chain at setup.

80

6.9×

60

10.6× 12.8×

40

14.4×

16.5×

18.5× 18.8× 19.5×

20.4× 21.4× 22.0×

20

Figure 5: CPU vs. kernel offloading in MM mode and streaming mode, 1 and 33 limbs per call, split into host-to-card transfer, kernel, and card-to-host transfer. Labels: end-toend speedup over CPU.

4.3

Card→host

100

Time per limb (µs)

MM, 1 limb

Kernel

0

1

2

3

4

6

8

10

Limbs per call

12

17

25

33

Figure 6: Streaming mode with 1 to 33 limbs per call, time per limb split into host-to-card transfer, kernel, and card-to-host transfer. Labels: end-to-end speedup over CPU.

4.4

Offloading Analysis

We test two offload modes (Figure 5): our streaming mode and memory-mapped (MM) mode, which we implement by instantiating AXI ports on HBM. In MM mode, the DMA engine copies the limbs into HBM, the kernel reads them and writes the result back, and the DMA engine copies the result to the host. In this mode, an NTT call of a single non-pipelined limb requires 222 𝜇s, versus 615 𝜇s on CPU (2.8×), but card-to-host transfers dominate it (103 𝜇s). Since

Allam et al.

Figure 7: Board power of the V80 by rail, 5-sample moving average. Shaded: 60 s of NTT executions.

3

4

dnum

6

11

(a) MulRelin, level 10 (11 limbs).

the DMA engine must read HBM, these peak at 7.0–8.0 GB/s, against 15.3–17.2 GB/s from host to card. With pipelined calls, the average latency drops to 99 𝜇s per limb (6.2× CPU), still dominated by the card-to-host transfer. In streaming mode, a call of a single limb requires 89 𝜇s (6.9× CPU): 43 𝜇s to stream the limb to the card, 11 𝜇s in the kernel, and 31 𝜇s to stream the result back. With 33 pipelined limbs per call, the NTT and the output transfer of each limb overlap the input transfer of the next, and the latency drops to 28 𝜇s per limb (22.0× CPU). Figure 6 shows the per-limb latency of streaming mode with 1 to 33 limbs per call: the speedup over the CPU rises from 6.9× to 22.0×, since the kernel and the card-to-host transfer are hidden behind the input stream. From three limbs on, the host-to-card stream accounts for more than 65% of the time per limb, and at 33 limbs the call transfers at 18.8 GB/s in each direction, close to the 21.3 GB/s peak of the stream interface.

4.5

Power Analysis

We read the power of the V80 from its board sensors every 0.5 s while the host runs batches of 10,000 pipelined NTTs for 60 s (Figure 7). The measurement includes the transfers in both directions, since the kernel ingests its input and returns its output over the PCIe streams. The kernel adds 14.0 W to the 59.1 W the card draws while idle, most of it (11.3 W) in the fabric, while the HBM power stays flat, since no limb passes through HBM. At one NTT every 26.5 𝜇s, the card spends 1.94 mJ per NTT, 0.37 mJ above idle.

4.6

CKKS Operations

We evaluate the offload on two core CKKS operations: key switching, measured through ciphertext-ciphertext multiplication (MulRelin), and bootstrapping. The number of NTT calls depends on dnum, the number of digits in the key-switching decomposition [31]. Each digit is extended to the full basis 𝑄𝑃, which requires transforming its limbs out of and back into the NTT domain, so the number of transforms grows with dnum (Figure 8). For MulRelin at level 10 (Figure 8a), the offload is faster at every dnum, from 2.07× at dnum=1 to 2.17× at dnum=11, where it reduces the MulRelin time from 154.1 ms to 71.1 ms. Within the 128-bit security bound (dnum≥4), the speedup is 1.98–2.19×. For bootstrapping (Figure 8b), the speedup rises from 1.66× at dnum=2 to 2.09× at dnum=25. Within the security bound (dnum≥5), it is 1.76–2.09×; at dnum=5 (log 𝑄𝑃 = 1546), the offload reduces the bootstrapping time from 12.04 s to 6.84 s. From dnum=2 to 13, the

0

2

3

2.09×

2

Latency (s)

1

1.99×

0

10

1.92×

50

1.76×

Other

1.96×

Transceivers

CPU + FPGA

20 1.69×

HBM

2.17×

100

80

2.19×

Time (s)

CPM5 (PCIe, DMA)

60

1.97×

VCCINT (fabric)

40

30

2.06×

20

150

2.07×

0

CPU 40

Latency (ms)

40

CPU + FPGA

1.98×

Power (W)

CPU 200

1.66×

80

5

7

9

13 25

dnum

(b) Bootstrapping (25 limbs).

Figure 8: Latency of MulRelin and bootstrapping, CPU-only vs. CPU with NTT/INTT on FPGA, against dnum. Shaded: log 𝑄𝑃 > 1550, not 128-bit secure [6]. Times are the mean of 10 runs. Labels: end-to-end speedup over CPU. Table 7: Cryptographic parameters of the workloads. Parameter Ring dimension (𝑁 ) Multiplicative depth log 𝑞 0 (first prime) log Δ (scale) log 𝑄 log 𝑃 log 𝑄𝑃 dnum Hamming weight of secret key

MLP

CNNs

216 5 55 40 255 183 (3 × 61) 438 2 192

216 25𝑎 55 40 1276 244 (4 × 61) 1520 7 192

𝑎 Including bootstrapping levels.

speedup follows the share of CPU time spent in NTT and INTT, which rises from 50.0% to 63.8%.

4.7

FHE Neural Network Inference

We evaluate end-to-end inference on six FHE neural networks with Lattigo, following the convolution formulation, polynomial approximation, and bootstrap placement methodology of Orion [14]. The networks fall into three categories: a shallow network that requires no bootstrapping; convolutional neural networks (CNNs) that operate on a single ciphertext (ResNet-20 and ResNet-32 on CIFAR-10); and CNNs whose activations span multiple ciphertexts in some layers (AlexNet and VGG16 on CIFAR-10, ResNet-18 on Tiny-ImageNet). Table 7 lists the cryptographic parameters, all 128-bit secure [6]. We exclude setup, which runs once for many inferences. The CPU-only and the offloaded runs produce identical outputs. Table 8 summarizes the results, and Figure 9 compares the time per inference: the offload speeds up inference by 1.81–2.08×. Per inference, the time Lattigo spends in NTT and INTT falls by 11.4– 15.1× in the shallow and single-ciphertext networks, and by 5.1– 14.0× in the multi-ciphertext networks.

End-to-End NTT on FPGA for FHE Acceleration

Table 8: FHE inference: CPU vs. CPU + NTT/INTT on FPGA, per inference (mean of 5 inferences).

CPU

CPU + FPGA (NTT/INTT)

Dataset MNIST Bootstraps 0 NTT calls 351 Limbs per call 3.81

CPU + FPGA Total (s) NTT/INTT (s) Per limb (𝜇 s) Speedup NTT speedup

CIFAR-10 37 41.5k 9.52

CIFAR-10 61 68.1k 9.54

VGG16

ResNet-18

CIFAR-10 CIFAR-10 15 28 21.1k 37.3k 9.08 9.22

Tiny-IN 128 199k 9.11

1.44 0.81 (56.1%)

393.9 238.4 (60.5%)

649.1 392.8 (60.5%)

171.4 105.4 (61.4%)

319.3 192.4 (60.1%)

560.7 430.3 (76.6%)

0.80 0.071 (8.9%) 52.4

190.8 15.8 (8.3%) 39.4

312.7 26.8 (8.6%) 40.7

89.6 7.5 (8.4%) 38.6

165.8 15.3 (9.2%) 44.1

301.0 84.7 (28.1%) 43.3

1.5

2.07 × 15.1 ×

2.08 × 14.7 ×

1.91 × 14.0 ×

1.93 × 12.5 ×

1.86 × 5.1 ×

4.7.2 Single-Ciphertext Networks. ResNet-20 and ResNet-32 on CIFAR-10 operate on a single ciphertext in every layer. ResNet-32 is the deeper of the two and requires 61 bootstraps per inference, against 37 for ResNet-20. Accordingly, ResNet-32 issues 68.1k NTT calls per inference, against 41.5k for ResNet-20. Their NTT profiles, however, coincide: their calls carry 9.5 limbs on average, and NTT and INTT require 60.5% of their wall-clock time in the CPU-only runs. Since these feature similar profiles, the offload accelerates both networks alike. It reduces the time per inference of ResNet-20 from 393.9 s to 190.8 s (2.07×) and that of ResNet-32 from 649.1 s to 312.7 s (2.08×), close to the Amdahl bound of 2.53× set by their NTT share. 4.7.3 Multi-ciphertext Networks. AlexNet, VGG16, and ResNet-18 require 15, 28, and 128 bootstraps per inference. In some of their layers, the activations span several ciphertexts. Inference then uses multi-threading: each ciphertext is processed by its own thread, and the threads issue their NTT calls concurrently. AlexNet and VGG16 span two ciphertexts in their first two convolutional layers and a single ciphertext afterward. ResNet-18, with 64×64×3 inputs, spans eight, four, two, and one ciphertexts in its four stages. AlexNet and VGG16 issue 21.1k and 37.3k NTT calls per inference, and ResNet-18 199k. The calls of all three networks carry 9.1–9.2 limbs on average. In the CPU-only runs, 1.2, 1.1, and 2.6 threads issue NTT calls at a time on average. We therefore count the NTT and INTT time as the time during which at least one transform is in flight. NTT and INTT then require 61.4% and 60.1% of the wallclock time of AlexNet and VGG16, close to the single-ciphertext networks, and 76.6% in ResNet-18.

0.80

649

600

191

200

0

MLP

400

313

200

100

ResNet-20

1.91×

0

ResNet-32

1.93×

171

300

150 100

2.08×

394

300

0.5

90

200

1.86× 600

319

400 166

AlexNet

0

561

301

200

100

50 0

4.7.1 Shallow Network. Our multi-layer perceptron (MLP) is a three-layer fully connected network composed of a 784×128 layer, a 128×128 layer, and a 128×10 output layer, with square activations. Its multiplicative depth is 5, so bootstrapping is not required. Its short modulus chain limits each call to 3.81 limbs on average, the smallest batches of all workloads; accordingly, the cost per limb is the highest, 52.4 𝜇s. Offloading reduces the time per inference from 1.44 s to 0.80 s, a 1.81× speedup, against an Amdahl bound of 2.28×.

400

1.0

200

1.81 × 11.4 ×

2.06×

1.44

0.0

Time per inference (s)

CPU only Total (s) NTT/INTT (s)

ResNet-20 ResNet-32 AlexNet

Time per inference (s)

1.81× MLP

VGG16

0

ResNet-18

Figure 9: FHE inference time, CPU only vs. CPU + NTT/INTT on the FPGA, mean of 5 inferences. Bar labels: time per inference (s); above each panel: speedup.

AlexNet and VGG16 thus behave like the single-ciphertext networks. The offload accelerates them by 1.91× (171.4 s to 89.6 s) and 1.93× (319.3 s to 165.8 s), against Amdahl bounds of 2.59× and 2.51×. ResNet-18 features a higher bound, 4.27×, but it gains 1.86× (560.7 s to 301.0 s). With the offload, its concurrent calls queue serially on the card, so its NTT and INTT time falls by only 5.1×, against 14.0× and 12.5× for AlexNet and VGG16. Across all workloads, the batch size of the calls and multithreading determine the gain. At 3.81 limbs per call, the MLP gains 1.81×. The single-ciphertext networks, at 9.5 limbs per call, gain 2.07–2.08×. The multi-ciphertext networks issue calls almost as large, 9.1–9.2 limbs, but share the card among concurrent threads and gain 1.86–1.93×. Figure 10 shows the same trend in the cost per limb: larger calls amortize the fixed cost of each transfer.

5

Related Work

Hardware acceleration of the NTT has been explored on GPUs, ASICs, and processing-in-memory systems. GPU implementations map the butterflies onto thousands of threads, generate twiddle factors on the fly to relieve memory bandwidth, and fuse kernels onto tensor cores [13, 17, 18, 26, 29, 32, 47, 53, 68, 72, 73]. ASIC accelerators build vectorized NTT units around large onchip memories, with four-step decompositions, transpose-based or conflict-free memories, and short words that localize communication [20, 30, 31, 33, 51, 52], and processing-in-memory designs execute the NTT inside DRAM [5]. FPGA accelerators implement either the full scheme or only the NTT. Full-scheme designs [2, 3, 50, 60, 61, 63] accelerate bootstrapping, but target fixed parameters and specific algorithms. NTT accelerators apply across schemes and libraries. We classify these

Allam et al.

100

Time per limb (µs)

Table 9: FPGA FHE and NTT accelerator approaches.

NTT Inference workload (average)

MLP

80

VGG16, ResNet-18 AlexNet, ResNet-20, -32

60 40 20 0

0

5

10

15

20

Limbs per call

25

30

Figure 10: Latency per limb of the inference workloads against the NTT on FPGA: line, NTT batches of 1–33 limbs (Figure 6); dots, latency per offloaded limb in each workload.

by how they map the log 𝑁 butterfly stages onto hardware and how they reorder coefficients among stages. Iterative accelerators reuse an array of PEs across stages and reorder the coefficients through banked memory with conflict-free access [11, 12, 23, 37, 40, 41, 45]. These utilize few resources but require 55–84 𝜇s per transform at 𝑁 =216 . Dataflow accelerators unroll the stages but still reorder through networks or memories among them. Ye et al. [64] and NTTGen [62] pair fixed wiring with a permutation network, Kim et al. [34] doublebuffer BRAMs among groups of stages, and AutoNTT [38] implements crossbar shufflers on a constant-geometry formulation [55]. SAM [57], Seven-step [35], TP-NTT [36], and AutoNest [71] decompose the transform into sub-NTTs joined by transposes, and AutoNest splits its transposes into blocks to shorten their critical paths. In both classes, the reordering interconnect grows with parallelism, adding routing congestion and SLR crossings. Delay commutators avoid this interconnect [19, 59]. NTT designs built on these run at low parallelism or small polynomial sizes [10, 21, 25, 39, 42, 43, 56, 65, 69]. Stelzer et al. [54] stream up to 64 coefficients per cycle, but only up to 𝑁 =212 ; Zaman et al. [67] reach 𝑁 =216 with one butterfly per stage, and Wang and Ikeda [58] stream eight lanes at 𝑁 =214 . ASIC accelerators [4, 15, 66] and zeroknowledge accelerators [1, 70] adopt such pipelines at larger scale. To share hardware between the NTT and the INTT, these pipelines reverse the data flow [15, 39, 54], select different folding sets [56], or reformulate the data flow [69]; Proteus [25] notes that delays sized for both orderings would avoid these changes, but discards the option as too complex. Our kernel streams 32 coefficients per cycle at 𝑁 =216 and computes the NTT and the INTT in the same direction through delays sized for both orderings. Most works store the twiddle factors, which requires memory that grows with 𝑁 for every prime [25, 36, 40, 42, 54, 63], and AutoNest fetches those of its last stage from √ HBM for every transform [71]. Generating every twiddle from 2 𝑁 twiddle roots with one modular multiplication was introduced in FFT processors [28] and on GPUs [32], and BTS [33] and Osiris [15] dedicate one such multiplier to each PE or butterfly. Zaman et al. [67] apply it to the last five stages of a delay-commutator pipeline and

Architecture Reorder

OTF E2E Works

PE array PE array PE array Multi-stage Multi-stage Multi-stage Sub-NTT Sub-NTT Unrolled Unrolled Unrolled Unrolled

Memory Memory Network Memory Memory Network Network Transpose Buffers Network Delay Delay

× ✓ × × ✓ × × × ✓ × × ✓

× × × × × × × × × × × ×

[2, 3, 38, 50] [37, 46] [61] [40, 63] [45] [38] [60] [35, 36, 57, 71] [34] [38, 64, 71] [10, 21, 25, 42, 54, 56, 65, 67] [58]

Unrolled

Delay

✓

✓

Our work

PE array: one array iterated over all stages; Multi-stage: a core of several stages iterated over stage groups; Sub-NTT: multi-dimensional decomposition into unrolled sub-NTTs. OTF: all twiddles generated on chip. E2E: placed and routed with per-SLR results, and run end to end under a CPU-hosted FHE library.

store the twiddles of the first eleven. Recurrences need only a few seeds, but one multiplier per PE and a fixed generation order [34, 37, 46, 57, 66]; powers of a few bases need 375 words and 15 multipliers at 𝑁 =216 [12], and power generation needs 254 multipliers [20]. Our kernel generates all twiddles on chip with 68 generators that share one low-digit buffer per stage and place no constraint on the dataflow. Most of these works do not discuss placement or multi-die crossings and none of them evaluates end-to-end offloading within an FHE library. Table 9 summarizes FPGA approaches.

6

Conclusions

In this work, we have designed a fully unrolled, delay-commutator streaming NTT/INTT kernel. Our kernel streams 32 coefficients per cycle through 256 butterfly units in 16 stages and reorders coefficients with delay commutators and fixed lane wiring instead of networks or transposes. A total of 68 generators produce the twiddle factors on the fly from 512 twiddle roots per prime. We have floorplanned the kernel across the three SLRs of an AMD Alveo V80 and closed timing at 400 MHz. Our kernel transforms a polynomial of 𝑁 =216 coefficients every 5.12 𝜇s. Offloaded end to end, including the transfers over PCIe, it is up to 22.0× faster than CPU-only executions. To the best of our knowledge, among FPGA designs at this polynomial size, it is the delay-commutator NTT with the highest parallelism and attains the highest throughput, 1.6–2.0× higher than designs with the same parallelism, with a competitive area-time product. We have integrated the kernel into the Lattigo FHE library and evaluated it on FHE workloads with 128-bit secure parameters. The offload speeds up MulRelin by 1.98–2.19×, bootstrapping by 1.76– 2.09×, and FHE neural network inference by 1.81–2.08×, while the NTT/INTT time per inference falls by up to 15.1×. The host-to-card stream accounts for more than 65% of the time per offloaded limb. Future work may reduce this share with a second stream interface, through the second PCIe controller of the V80, or by integrating the kernel into a larger FHE accelerator to retain limbs on the card.

End-to-End NTT on FPGA for FHE Acceleration

Acknowledgments Funded by the European Union (ERC, HomE, 101043467). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. Antonio J. Peña was partially supported by the Ramón y Cajal fellowship RYC2020-030054-I, funded by MCIN/AEI/10.13039/501100011033 and by “ESF Investing in your future”. Special thanks to the HomE team, to Antonio Filgueras from OmpSs@FPGA and Juan Miguel De Haro Ruiz from Microarchitecture Design and implementation (MAD) at BSC for the valuable support.

References [1] Kaveh Aasaraai, Emanuele Cesena, Rahul Maganti, Nicolas Stalder, Javier Varela, and Kevin Bowers. 2022. CycloneNTT: An NTT/FFT Architecture Using QuasiStreaming of Large Datasets on DDR- and HBM-based FPGA Platforms. Cryptology ePrint Archive, Paper 2022/1657. [2] Rashmi Agrawal, Anantha Chandrakasan, and Ajay Joshi. 2024. HEAP: A Fully Homomorphic Encryption Accelerator with Parallelized Bootstrapping. In Proceedings of the 51st Annual International Symposium on Computer Architecture (Buenos Aires, Argentina) (ISCA ’24). IEEE Press, Buenos Aires, Argentina, 756–769. doi:10.1109/ISCA59077.2024.00060 [3] Rashmi Agrawal, Leo de Castro, Guowei Yang, Chiraag Juvekar, Rabia Yazicigil, Anantha Chandrakasan, Vinod Vaikuntanathan, and Ajay Joshi. 2023. FAB: An FPGA-Based Accelerator for Bootstrappable Fully Homomorphic Encryption. In 2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA). IEEE, Montreal, QC, Canada, 882–895. doi:10.1109/HPCA56546.2023.1 0070953 [4] Aikata Aikata, Ahmet Can Mert, Sunmin Kwon, Maxim Deryabin, and Sujoy Sinha Roy. 2025. REED: Chiplet-based Accelerator for Fully Homomorphic Encryption. IACR Transactions on Cryptographic Hardware and Embedded Systems 2025, 2 (2025), 163–208. doi:10.46586/tches.v2025.i2.163-208 [5] Tathagata Barik, Priyam Mehta, Zaira Pindado, Harshita Gupta, Mayank Kabra, Mohammad Sadrosadati, Onur Mutlu, and Antonio J. Peña. 2026. Long Integer NTT Execution on UPMEM-PIM for 128-bit Secure Fully Homomorphic Encryption. Future Generation Computer Systems (2026), 108386. doi:10.1016/j.future.2 026.108386 [6] Jean-Philippe Bossuat, Christian Mouchet, Juan Troncoso-Pastoriza, and JeanPierre Hubaux. 2021. Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-Sparse Keys. In Advances in Cryptology – EUROCRYPT 2021 (Lecture Notes in Computer Science, Vol. 12696). Springer, Cham, 587–617. doi:10.1007/978-3-030-77870-5_21 [7] Jung Hee Cheon, Kyoohyung Han, Andrey Kim, Miran Kim, and Yongsoo Song. 2018. Bootstrapping for Approximate Homomorphic Encryption. In Advances in Cryptology – EUROCRYPT 2018, Jesper Buus Nielsen and Vincent Rijmen (Eds.). Springer International Publishing, Cham, 360–384. [8] Jung Hee Cheon, Kyoohyung Han, Andrey Kim, Miran Kim, and Yongsoo Song. 2018. A Full RNS Variant of Approximate Homomorphic Encryption. In Selected Areas in Cryptography – SAC 2018: 25th International Conference, Calgary, AB, Canada, August 15–17, 2018, Revised Selected Papers (Calgary, AB, Canada). Springer-Verlag, Berlin, Heidelberg, 347–368. doi:10.1007/978-3-030-10970-7_16 [9] Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. 2017. Homomorphic Encryption for Arithmetic of Approximate Numbers. In Advances in Cryptology – ASIACRYPT 2017, Tsuyoshi Takagi and Thomas Peyrin (Eds.). Springer International Publishing, Cham, 409–437. [10] Sin-Wei Chiu and Keshab K. Parhi. 2025. Architectures for Serial and Parallel Pipelined NTT-Based Polynomial Modular Multiplication. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 33, 9 (2025), 2474–2487. doi:10.1109/ TVLSI.2025.3576782 [11] Quang Dang Truong, Phap Duong-Ngoc, and Hanho Lee. 2025. Hybrid Number Theoretic Transform Architecture for Homomorphic Encryption. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 33, 7 (2025), 2039–2043. doi:10.1109/TVLSI.2025.3552852 [12] Phap Duong-Ngoc, Sunmin Kwon, Donghoon Yoo, and Hanho Lee. 2023. AreaEfficient Number Theoretic Transform Architecture for Homomorphic Encryption. IEEE Transactions on Circuits and Systems I: Regular Papers 70, 3 (2023), 1270–1283. doi:10.1109/TCSI.2022.3225208 [13] Phap Duong-Ngoc, Thang Xuan Pham, Hanho Lee, and Tuy Tan Nguyen. 2022. Flexible GPU-Based Implementation of Number Theoretic Transform for Homomorphic Encryption. In 2022 19th International SoC Design Conference (ISOCC). 259–260.

[14] Austin Ebel, Karthik Garimella, and Brandon Reagen. 2025. Orion: A Fully Homomorphic Encryption Framework for Deep Learning. In Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2. 734–749. [15] Austin Ebel and Brandon Reagen. 2026. Osiris: A Systolic Approach to Accelerating Fully Homomorphic Encryption. ACM Trans. Archit. Code Optim. (Jan. 2026). doi:10.1145/3788287 Just Accepted. [16] EPFL-LDS and Tune Insight SA. 2024. Lattigo v6. Online: https://github.com/t uneinsight/lattigo. [17] G. Fan, M. Zhang, F. Zheng, S. Fan, T. Zhou, X. Deng, W. Tang, L. Kong, Y. Song, and S. Yan. 2025. WarpDrive: GPU-Based Fully Homomorphic Encryption Acceleration Leveraging Tensor and CUDA Cores. In IEEE Int. Symp. on High Performance Computer Architecture (HPCA). 1187–1200. [18] Shengyu Fan, Zhiwei Wang, Weizhi Xu, Rui Hou, Dan Meng, and Mingzhe Zhang. 2023. TensorFHE: Achieving Practical Computation on Encrypted Data Using GPGPU. In IEEE International Symposium on High-Performance Computer Architecture (HPCA). 922–934. [19] Mario Garrido, Jesús Grajal, Miguel A. Sánchez, and Oscar Gustafsson. 2013. Pipelined Radix-2𝑘 Feedforward FFT Architectures. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 21, 1 (2013), 23–32. [20] Robin Geelen, Michiel Van Beirendonck, Hilder V. L. Pereira, Brian Huffman, Tynan McAuley, Ben Selfridge, Daniel Wagner, Georgios Dimou, Ingrid Verbauwhede, Frederik Vercauteren, and David W. Archer. 2022. BASALISC: Programmable Hardware Accelerator for BGV Fully Homomorphic Encryption. Cryptology ePrint Archive, Paper 2022/657. https://eprint.iacr.org/2022/657 [21] Yue Geng, Xiao Hu, and Zhongfeng Wang. 2024. GS-MDC: High-Speed and AreaEfficient Number Theoretic Transform Design. IEEE Transactions on Circuits and Systems II: Express Briefs 71, 12 (2024), 4974–4978. doi:10.1109/TCSII.2024.3430954 [22] Craig Gentry. 2009. A Fully Homomorphic Encryption Scheme. Ph. D. Dissertation. Stanford University, Stanford, CA, USA. [23] Jianbo Guo, Jiaoyang Zhu, and Hao Xiao. 2026. A High-Performance and Configurable NTT Accelerator Based on Scalable 2-D Architecture. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 34, 2 (2026), 506–518. doi:10.1109/TVLSI.2025.3606636 [24] Shai Halevi, Yuriy Polyakov, and Victor Shoup. 2019. An Improved RNS Variant of the BFV Homomorphic Encryption Scheme. In Topics in Cryptology – CT-RSA 2019, Mitsuru Matsui (Ed.). Springer International Publishing, 83–105. [25] Florian Hirner, Ahmet Can Mert, and Sujoy Sinha Roy. 2024. Proteus: A Pipelined NTT Architecture Generator. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 32, 7 (2024), 1228–1238. doi:10.1109/TVLSI.2024.3377366 [26] Dian Jiao, Xianglong Deng, Zhiwei Wang, Shengyu Fan, Yi Chen, Dan Meng, Rui Hou, and Mingzhe Zhang. 2025. Neo: Towards Efficient Fully Homomorphic Encryption Acceleration Using Tensor Core. In 52nd Annual International Symposium on Computer Architecture. 107–121. [27] Wonkyung Jung, Eojin Lee, Sangpyo Kim, Keewoo Lee, Namhoon Kim, Chohong Min, Jung Hee Cheon, and Jung Ho Ahn. 2020. HEAAN Demystified: Accelerating Fully Homomorphic Encryption Through Architecture-centric Analysis and Optimization. arXiv:2003.04510. [28] Hyeong-Ju Kang, Byung-Do Yang, and Jong-Yeol Lee. 2013. Low Complexity Twiddle Factor Multiplication with ROM Partitioning in FFT Processor. Electronics Letters 49, 9 (2013), 589–591. doi:10.1049/el.2013.0689 [29] J. Kim, W. Choi, and J. Ahn. 2024. Cheddar: A Swift Fully Homomorphic Encryption Library for CUDA GPUs. arXiv:2407.13055 (2024). [30] Jongmin Kim, Sangpyo Kim, Jaewan Choi, Jaiyoung Park, Donghwan Kim, and Jung Ho Ahn. 2023. SHARP: A Short-Word Hierarchical Accelerator for Robust and Practical Fully Homomorphic Encryption. In 50th Annual International Symposium on Computer Architecture (ISCA). [31] Jongmin Kim, Gwangho Lee, Sangpyo Kim, Gina Sohn, Minsoo Rhu, John Kim, and Jung Ho Ahn. 2022. ARK: Fully Homomorphic Encryption Accelerator with Runtime Data Generation and Inter-Operation Key Reuse. In IEEE/ACM International Symposium on Microarchitecture (MICRO). [32] Sangpyo Kim, Wonkyung Jung, Jaiyoung Park, and Jung Ho Ahn. 2020. Accelerating Number Theoretic Transformations for Bootstrappable Homomorphic Encryption on GPUs. In 2020 IEEE International Symposium on Workload Characterization (IISWC). 264–275. doi:10.1109/IISWC50251.2020.00033 [33] Sangpyo Kim, Jongmin Kim, Michael Jaemin Kim, Wonkyung Jung, John Kim, Minsoo Rhu, and Jung Ho Ahn. 2022. BTS: An Accelerator for Bootstrappable Fully Homomorphic Encryption. In Proceedings of the 49th Annual International Symposium on Computer Architecture. 711–725. [34] Sunwoong Kim, Keewoo Lee, Wonhee Cho, Yujin Nam, Jung Hee Cheon, and Rob A. Rutenbar. 2020. Hardware Architecture of a Number Theoretic Transform for a Bootstrappable RNS-based Homomorphic Encryption Scheme. In IEEE 28th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM). 56–64. https://ieeexplore.ieee.org/document/9114594 [35] Emre Koçer, Selim Kirbiyik, Tolun Tosun, Ersin Alaybeyoğlu, and Erkay Savaş. 2025. IO-Optimized Design-Time Configurable Negacyclic Seven-Step NTT Architecture for FHE Applications. In Proceedings of the Great Lakes Symposium

Allam et al.

on VLSI (GLSVLSI). doi:10.1145/3716368.3735514 [36] Emre Koçer, Tolun Tosun, Beren Aydoğan, Erkay Savaş, Furkan Turan, and Ingrid Verbauwhede. 2026. TP-NTT: Batch NTT Hardware with Application to Relinearization. IACR Transactions on Cryptographic Hardware and Embedded Systems 2026, 4 (2026), 705–730. doi:10.46586/tches.v2026.i4.705-730 [37] Florian Krieger, Florian Hirner, Ahmet Can Mert, and Sujoy Sinha Roy. 2024. OpenNTT: An Automated Toolchain for Compiling High-Performance NTT Accelerators in FHE. In Proceedings of the 43rd IEEE/ACM International Conference on Computer-Aided Design (ICCAD). 1–9. doi:10.1145/3676536.3697123 [38] Dilshan Kumarathunga, Qilin Hu, and Zhenman Fang. 2025. AutoNTT: Automatic Architecture Design and Exploration for Number Theoretic Transform Acceleration on FPGAs. In 2025 IEEE 33rd Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM). 1–9. doi:10.1109/FC CM62733.2025.00024 [39] Dur E Shahwar Kundi, Jose M. Bermudo Mera, Pierre-Yves Strub, and Michael Hutter. 2024. High-Performance NTT Hardware Accelerator to Support ML-KEM and ML-DSA. In Proceedings of the 2024 Workshop on Attacks and Solutions in Hardware Security (ASHES). 100–105. doi:10.1145/3689939.3695785 [40] Stefanus Kurniawan, Phap Duong-Ngoc, and Hanho Lee. 2023. Configurable Memory-Based NTT Architecture for Homomorphic Encryption. IEEE Transactions on Circuits and Systems II: Express Briefs 70, 10 (2023), 3942–3946. doi:10.1109/TCSII.2023.3289489 [41] Chulwoo Lee, Hanyoung Lee, Ardianto Satriawan, and Hanho Lee. 2024. Configurable Arithmetic Core Architecture for RNS-CKKS Homomorphic Encryption. IEEE Access PP (01 2024), 1–1. doi:10.1109/ACCESS.2024.3473903 [42] Ju-Hyung Lee, Young-Chan Jang, and Kyung-Wook Shin. 2026. A Radix-2/4/8Based Pipelined NTT/INTT Architecture for Homomorphic Encryption. IEEE Access 14 (2026), 87042–87058. doi:10.1109/ACCESS.2026.3699867 [43] Chen Liu et al. 2024. HMNTT: A Highly Efficient MDC-NTT Architecture for Privacy-preserving Applications. In Proceedings of the Great Lakes Symposium on VLSI (GLSVLSI). doi:10.1145/3649476.3658734 [44] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. 2010. On Ideal Lattices and Learning with Errors over Rings. In Advances in Cryptology – EUROCRYPT 2010 (Lecture Notes in Computer Science, Vol. 6110). Springer, 1–23. doi:10.1007/978-3642-13190-5_1 [45] Rella Mareta, Ardianto Satriawan, Phap Ngoc Duong, and Hanho Lee. 2024. A Bootstrapping-Capable Configurable NTT Architecture for Fully Homomorphic Encryption. IEEE Access 12 (2024), 52911–52921. doi:10.1109/ACCESS.2024.3386 977 [46] Ahmet Can Mert, Aikata, Sunmin Kwon, Youngsam Shin, Donghoon Yoo, Yongwoo Lee, and Sujoy Sinha Roy. 2023. Medha: Microcoded Hardware Accelerator for computing on Encrypted Data. IACR Transactions on Cryptographic Hardware and Embedded Systems 2023, 1 (2023), 463–500. doi:10.46586/tches.v2023.i1.463500 [47] Ozgun Ozerk, Can Elgezen, Ahmet Can Mert, Erdinc Ozturk, and Erkay Savas. 2021. Efficient Number Theoretic Transform Implementation on GPU for Homomorphic Encryption. Cryptology ePrint Archive, Paper 2021/124. https: //eprint.iacr.org/2021/124 [48] Zaira Pindado, Thomas Spendlhofer, Mohamed Allam, Priyam Mehta, Lena Martens, and Antonio J. Peña. 2026. SoK of Private Deep Neural Network Inference with Approximate Fully Homomorphic Encryption. Cryptology ePrint Archive, Paper 2026/047. https://eprint.iacr.org/2026/047 [49] Oded Regev. 2009. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. Journal of the ACM (JACM) 56, 6 (2009), 1–40. [50] M. Sadegh Riazi, Kim Laine, Blake Pelton, and Wei Dai. 2020. HEAX: An Architecture for Computing on Encrypted Data. In Proceedings of the 25th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS ’20). Association for Computing Machinery, 1295–1309. doi:10.1145/3373376.3378523 [51] Nikola Samardzic, Axel Feldmann, Aleksandar Krastev, Srinivas Devadas, Ronald Dreslinski, Christopher Peikert, and Daniel Sanchez. 2021. F1: A Fast and Programmable Accelerator for Fully Homomorphic Encryption. In MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture (Virtual Event, Greece) (MICRO ’21). Association for Computing Machinery, New York, NY, USA, 238–252. doi:10.1145/3466752.3480070 [52] Nikola Samardzic, Axel Feldmann, Aleksandar Krastev, Nathan Manohar, Nicholas Genise, Srinivas Devadas, Karim Eldefrawy, Chris Peikert, and Daniel Sanchez. 2022. CraterLake: A Hardware Accelerator for Efficient Unbounded Computation on Encrypted Data. In Int. Symp. Comp. Arch. [53] Kaustubh Shivdikar, Gilbert Jonatan, Evelio Mora, Neal Livesay, Rashmi Agrawal, Ajay Joshi, Jose L. Abellan, John Kim, and David Kaeli. 2022. Accelerating Polynomial Multiplication for Homomorphic Encryption on GPUs . In 2022 IEEE International Symposium on Secure and Private Execution Environment Design (SEED). IEEE Computer Society, Los Alamitos, CA, USA, 61–72. doi:10.1109/SE ED55351.2022.00013 [54] Tobias Stelzer, Patrick Karl, and Andreas Zankl. 2026. Flexible Parallel Radix-4 MDC NTT for FHE. IEEE Transactions on Circuits and Systems II: Express Briefs 73, 8 (2026), 863–867. doi:10.1109/TCSII.2026.3700928

[55] J. Takala, D. Akopian, J. Astola, and J. Saarinen. 2000. Constant Geometry Algorithm for Discrete Cosine Transform. IEEE Transactions on Signal Processing 48, 6 (2000), 1840–1843. doi:10.1109/78.845951 [56] Weihang Tan, Sin-Wei Chiu, Antian Wang, Yingjie Lao, and Keshab K. Parhi. 2024. PaReNTT: Low-Latency Parallel Residue Number System and NTT-Based Long Polynomial Modular Multiplication for Homomorphic Encryption. IEEE Transactions on Information Forensics and Security 19 (2024), 1646–1659. doi:10.1 109/TIFS.2023.3338553 [57] Cheng Wang and Mingyu Gao. 2023. SAM: A Scalable Accelerator for Number Theoretic Transform Using Multi-Dimensional Decomposition. In 2023 IEEE/ACM International Conference on Computer Aided Design (ICCAD). 1–9. doi:10.1109/IC CAD57390.2023.10323744 [58] Zeyu Wang and Makoto Ikeda. 2024. High-Throughput and Fully-Pipelined Ciphertext Multiplier for Homomorphic Encryption. IEICE Electronics Express 21, 6 (2024), 20230628. doi:10.1587/elex.21.20230628 [59] Erling H. Wold and Alvin M. Despain. 1984. Pipeline and Parallel-Pipeline FFT Processors for VLSI Implementations. IEEE Trans. Comput. C-33, 5 (1984), 414–426. [60] Zhihan Xu, Rajgopal Kannan, and Viktor K. Prasanna. 2026. HERA: A Bandwidthefficient Accelerator for Fully Homomorphic Encryption on HBM-enabled FPGA. In Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays (FPGA). 265–276. doi:10.1145/3748173.3779201 [61] Zhihan Xu, Tian Ye, Rajgopal Kannan, and Viktor K. Prasanna. 2025. FAST: FPGA Acceleration of Fully Homomorphic Encryption with Efficient Bootstrapping. In Proceedings of the 2025 ACM/SIGDA International Symposium on Field Programmable Gate Arrays (FPGA ’25). Association for Computing Machinery, New York, NY, USA, 115–126. doi:10.1145/3706628.3708879 [62] Yang Yang, Sanmukh R. Kuppannagari, Rajgopal Kannan, and Viktor K. Prasanna. 2022. NTTGen: A Framework for Generating Low Latency NTT Implementations on FPGA. In Proceedings of the 19th ACM International Conference on Computing Frontiers (Turin, Italy) (CF ’22). Association for Computing Machinery, New York, NY, USA, 30–39. doi:10.1145/3528416.3530225 [63] Yinghao Yang, Huaizhi Zhang, Shengyu Fan, Hang Lu, Mingzhe Zhang, and Xiaowei Li. 2023. Poseidon: Practical Homomorphic Encryption Accelerator. In 2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA). 870–881. doi:10.1109/HPCA56546.2023.10070984 [64] Tian Ye, Yang Yang, Sanmukh R. Kuppannagari, Rajgopal Kannan, and Viktor K. Prasanna. 2021. FPGA Acceleration of Number Theoretic Transform. In High Performance Computing (ISC High Performance) (Lecture Notes in Computer Science). Springer. doi:10.1007/978-3-030-78713-4_6 [65] Zhaoxiang Ye, Ray C. C. Cheung, and Kai Huang. 2022. PipeNTT: A Pipelined Number Theoretic Transform Architecture. IEEE Transactions on Circuits and Systems II: Express Briefs 69, 10 (2022), 4068–4072. [66] Sungwoong Yune, Hyojeong Lee, Adiwena Putra, Hyunjun Cho, Cuong Duong Manh, Jaeho Jeon, and Joo-Young Kim. 2025. ABC-FHE: A ResourceEfficient Accelerator Enabling Bootstrappable Parameters for Client-Side Fully Homomorphic Encryption. In 62nd ACM/IEEE Design Automation Conference (DAC). [67] Moonis Amir Zaman, Muhammad Bilal Khan, Waqar Ahmad, Ayesha Khalid, and Máire O’Neill. 2026. A Lightweight and Hardware-Efficient NTT FPGA Accelerator for FHE Applications. IEEE Transactions on Circuits and Systems II: Express Briefs 73, 1 (2026), 78–82. doi:10.1109/TCSII.2025.3633181 [68] Yujia Zhai, Mohannad Ibrahim, Yiqin Qiu, Fabian Boemer, Zizhong Chen, Alexey Titov, and Alexander Lyashevsky. 2022. Accelerating Encrypted Computing on Intel GPUs. In 2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 705–716. doi:10.1109/IPDPS53621.2022.00074 [69] Bo Zhang, Mingzhe Zhang, and Shoumeng Yan. 2026. Binary Subscript Representation and Efficient Pipelined Number Theoretic Transform. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 45, 9 (2026), 4316–4329. doi:10.1109/TCAD.2025.3648669 [70] Ye Zhang, Shuo Wang, Xian Zhang, Jiangbin Dong, Xingzhong Mao, Fan Long, Cong Wang, Dong Zhou, Mingyu Gao, and Guangyu Sun. 2021. PipeZK: Accelerating Zero-Knowledge Proof with a Pipelined Architecture. In ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA). [71] Yilan Zhu, Geng Yang, Xingyu Tian, Dilshan Kumarathunga, Liang Kong, Xianglong Deng, Shengyu Fan, Guang Fan, Guiming Shi, Lei Chen, Bo Zhang, Yisong Chang, Shoumeng Yan, Zhenman Fang, and Mingzhe Zhang. 2026. An Efficient and Scalable Hardware Architecture for Number Theoretic Transform on FPGA with Design Automation. In 2026 IEEE International Symposium on High Performance Computer Architecture (HPCA). doi:10.1109/HPCA68181.2026.11408615 [72] Ege Özcan and Erkay Savaş. 2023. Two Algorithms for Fast GPU Implementation of the Number Theoretic Transform. Cryptology ePrint Archive, Report 2023/1410. https://eprint.iacr.org/2023/1410 [73] Ege Özcan, Erkay Savaş, et al. 2022. Homomorphic Encryption on GPU: Optimized NTT Kernels for BFV. Cryptology ePrint Archive, Report 2022/1222. https://eprint.iacr.org/2022/1222

Related documents

• Adapting AlphaEvolve to Optimize Fully Homomorphic Encryption on TPUs#187242
• CPUBone: Efficient Vision Backbone Design for Devices with Low Parallelization Capabilities#971779
• Towards Standardized Evaluation of GPU Memory Safety with GMSBench#986496
• Parametrized Exact Hardware-Software Partitioning#1218437
• LibFHE: A Numba-Based CUDA-Python Library for Non-RNS CKKS-BGV Fully Homomorphic Encryption on GPUs#346450