CS Paper Radar

Implementation and Evaluation of NTT Arithmetic for ML-KEM on a CGLA

Takuto Ando, Yasuhiko Nakashima

cs.AR ·submitted 2026-09-24 01:33 UTC · v1
hot direction

Abstract

FIPS 203 standardizes ML-KEM for post-quantum key establishment. Its polynomial multiplication relies on NTT butterflies with exact modular arithmetic over q = 3329. Dedicated NTT accelerators minimize latency with fixed modular arithmetic and stage schedules. A CPU-Grounded Linear Array (CGLA) reuses one programmable linear datapath across several workloads. Mapping the transform to this datapath requires exact FP32 reconstruction and explicit stage transitions across the ARM-to-CGLA interface. We implement an eight-stage cyclic radix-2 driver over the ML-KEM modulus by splitting each twiddle into 8-bit and 4-bit parts before modular reduction. This driver differs from the standardized seven-layer incomplete negacyclic NTT and does not implement the full ML-KEM polynomial multiplication path. The arithmetic sequence keeps every integer below 2^24. One 41-PE call fuses the first two radix-2 stages, and six 47-PE calls execute the remaining stages while scattering outputs into next-stage records. Across four cohorts, 105 FPGA runs match all 817152 output coefficients. At batch size 64, measured FPGA end-to-end latency is 27.5 us per NTT, and the ASIC projection is 6.74 us. With PE gating, projected ASIC system energy is 10.1 uJ per NTT at batch size 8 and 58.9 uJ at batch size 64.

Comment
Accepted as a Regular Paper for the WICS Workshop at CANDAR 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Implementation and Evaluation of BitNet Inference on a CGLA by Signed-Int4 Instructions

cs.AR ·2026-09-23 ·Takuto Ando, Yasuhiko Nakashima
similarity 0.67
Abstract · Accepted as a Regular Paper for the CSA Workshop at CANDAR 2026

Large language model (LLM) inference transfers model weights and activations for every generated token, making memory traffic and its energy cost part of the decode path. BitNet b1.58 represents its low-bit weights by ternary values and uses integer activations. However, this arithmetic does not match conventional int8 or floating-point general matrix multiplication, and existing BitNet accelerators implement it in specialized datapaths. We instead map this operation to a CPU-Grounded Linear Array (CGLA), a programmable ASIC with explicit direct memory access, local memories, and reusable compiler-visible integer lanes. The mapping adds OP_SMA4 as a reusable signed-int4 multiply-accumulate instruction rather than a BitNet-only datapath. Each ternary weight occupies one signed 4-bit lane. Each int8 activation is split into two signed-int4 fragments and reconstructed by shift-and-add. Frequency scaling of the 145 MHz FPGA measurement to an 840 MHz 28 nm CGLA achieved 0.390 ns per signed-int4 product. We showed that CGLA-offloaded BitNet C++ execution measures 2.52 tokens/s.

0.35

End-to-End NTT on FPGA for FHE Acceleration

cs.CR cs.AR ·2026-11-02 ·Mohamed Allam, Thomas Spendlhofer, Hugo Sanz-González, Antonio J. Peña
similarity 0.63
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 $O(N^2)$ to $O(N \log N)$. 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 $2^{16}$ coefficients every 5.12 $μ$s, the highest throughput among FPGA designs at this size. Offloaded end to end, it is up to 22x 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.2x, and neural network inference by 1.8-2.1x.

0.06

Benchmarking StreamNTT with a Verilog-to-Routing Toolchain

cs.AR ·2026-09-19 ·Wei He, Young-kyu Choi, Hyunwoo Park, Sunwoong Kim
code/data similarity 0.63
Abstract · Accepted to the 2nd Workshop on Domain-Specialized FPGAs (WDSFPGA), co-located with ISFPGA 2026

As post-quantum cryptography algorithms move toward large-scale data center deployment, hardware acceleration of their computational bottleneck, which is the number theoretic transform (NTT), has gained increasing attention. StreamNTT, a high-level synthesis- and field-programmable gate array-based accelerator, achieves state-of-the-art throughput through various optimization techniques. However, its reliance on a commercial tool and a device makes direct comparisons difficult for researchers without access. We address this by building StreamNTT on an open-source Verilog-to-Routing toolchain, which achieves similar digital signal processing and multiplier usage. Significant differences in internal memory utilization indicate that further memory-level optimization is needed to approach commercial tool performance.

0.32

FoldNTT: A Multiplier- and Twiddle-Lean NTT Core with Formally Verified Arithmetic for Proth Primes

cs.CR ·2026-09-06 ·Masato Kamba
similarity 0.62
Abstract

Hardware for lattice-based post-quantum cryptography spends a large share of its area on the number-theoretic transform (NTT), dominated by modular multipliers and twiddle storage. FoldNTT is a redesign of the released radix-2 CFNTT accelerator (TCHES 2022) for the Falcon / FN-DSA prime q = 12289 with one hardware multiplier per butterfly instead of three and about half the stored twiddle constants. The Proth shape q = 3*2^12 + 1 turns modular reduction into shift-and-add K-RED folds, and the bit-reversed twiddle table obeys w[N/2+j] = psi*w[j], so half the table is derived without a multiplier. Checking the released RTL against the mathematics also exposed a bug: its inverse transform omits a per-stage halving and returns 2^10*x, which the retrofit corrects. Every arithmetic block is proven by exact-width SMT and compositional SymbiYosys proofs, control-safety invariants by k-induction; the proofs are mutation-tested and the composed transform is validated by simulation, all rerun by CI. On Artix-7 in a fully open flow, the retrofit costs 3->1 DSP48 per butterfly and -50% stored twiddle bits at a whole-core Fmax cost of about 4% (best of three seeds; within the seed-to-seed spread), measured on the released datapath driven by a controller we reconstructed (the reference FSM was never released) and validated by full-core simulation; a sequential core with our own controller builds to a timing-gated Basys-3 bitstream.

0.39

Exhaustive Evaluation of Fixed-Point Reciprocal Architectures for FPGAs

cs.AR ·2026-11-15 ·Navaneeth Kutty, Anish Murali, Iacovos Ioannou, Priyan Mariappan, Prabagarane Nagaradjane
similarity 0.62
Abstract · 27 pages, 11 figures

Fixed-point reciprocals are used in normalization and division on field-programmable gate arrays (FPGAs). Designs that share an output format can differ in worst-case error and in their need for memory and multipliers. The effect of table width, internal precision and refinement was evaluated for reciprocal computation in the Q16.16 and Q8.24 formats. Every representable input in the interval from 0.5 to 2.5 was tested against an exact integer reference. Five arithmetic paths were reconstructed from register-transfer-level source. Guarded interpolation, Newton-Raphson refinement and residual correction were then evaluated alongside polynomial and digit-recurrence baselines. Correct rounding was verified for all 131,073 Q16.16 and 33,554,433 Q8.24 inputs by adding one residual check to a guarded interpolated seed and one refinement step. An implementation with product reuse was verified at one input per cycle with a latency of 10 cycles in both formats. The Q8.24 implementation used nine digital signal processing slices in 7 series synthesis. The exact radix-2 control used no such slices and had a latency of 28 cycles. The reconstructed refined paths reduced the maximum relative error by factors of 205 to 223 when eight fractional bits were added. The evaluated designs provide reproducible choices for fixed accuracy budgets. In particular, correct rounding can be obtained on the tested interval by using a compact seed and checking the integer residual before the result is returned.

0.27

FIGFLEX: A Mixed-Precision FP-INT GEMM Accelerator Co-Designed with Low-Bit LLM Quantization

cs.AR cs.LG ·2026-10-21 ·Faraz Tahmasebi, Haocheng Xu, Andrew Trauger, Yomal Perera, Zhenyu Tang +2 more
similarity 0.61
Abstract · 15 pages, 12 Figures

Weight-only quantization keeps LLM activations in floating point and stores weights as low-bit integers, turning the dominant workload into floating-point-integer (FP-INT) general matrix multiplication. Recent quantizers reach a 2-3-bit average with mixed precision, but hardware has not kept pace: GPUs dequantize weights to FP16 before the tensor-core multiply-accumulate, and bit-parallel FP-INT accelerators run at a single weight precision, so fewer bits save memory but not computation. In this paper, we present FIGFLEX, an algorithm-hardware co-designed mixed-precision accelerator whose bit-parallel datapath scales throughput as precision falls. FIGFLEX contributes (1) a shift-add, radix-4 reformulation of FP-INT multiplication that fuses the multiply-accumulate into a unified, precision-flexible partial-product reduction and roughly halves the partial products, together with a novel INT3 optimization that reclaims the idle datapath radix-4 leaves at that precision; and (2) a mixed-precision quantizer that assigns each channel group its bit-width according to the error GPTQ cannot compensate, with a per-input-channel column scaling whose power-of-two normalization keeps the scaled activations out of the FP16 subnormal range, so that the quantized model maps directly onto FIGFLEX's datapath with the same accuracy as on a GPU. On LLaMA-2-7B, FIGFLEX attains 5.85 and 8.77 WikiText-2 perplexity at 3- and 2-bit average precision, lower than GPTQ, AWQ, SliM-LLM, AMQ, and QuIP# (without fine-tuning), while delivering 1.56x and 1.42x higher whole-chip throughput per area on the linear GEMMs of a 3-bit mixed-precision model than AxCore and FIGLUT, respectively.

0.13

A Combined Streaming FPGA Architecture for Client-Side CKKS Encoding and Encryption

cs.CR cs.AR ·2026-10-19 ·Joseph Kurina, Bogdan Pasca, Suleyman Demirsoy, Sunwoong Kim
published similarity 0.61
Abstract · Accepted to the International Conference on Field Programmable Technology (FPT) 2026

Homomorphic encryption allows a computing service to process encrypted data, but the client must first encode and encrypt its inputs. Sharing hardware between floating-point encoding and modular encryption reduces area but requires those transform roles to execute at different times. We present a streaming FPGA architecture for CKKS encoding and encryption that computes the shared floating-point encoding transform once and performs the integer transforms for six residue moduli in parallel. Dedicated transform pipelines exchange intermediate results on chip rather than through off-chip memory. DSP Builder generates the transform RTL, and Altera HLS IP Gen compiler compiles the surrounding SYCL pipeline into IP integrated with DMA and control logic in an accelerator functional unit. At polynomial degree N = 8192, the Altera Agilex 7 implementation delivers 5,143 complete ciphertexts per second at 471 MHz. One SEAL-Embedded CPU worker on the same workstation delivers 113 ciphertexts per second for real-valued inputs using all 4,096 slots. Measurements cover prepared-input computation through complete ciphertext construction, including FPGA submission and output delivery.

0.24

Peregrino: A Full-Hardware Accelerator for the Complete Falcon Post-Quantum Digital Signature Scheme on Resource-Constrained Edge Devices

cs.CR cs.AR ·2026-09-25 ·Antonio Carreño, Jaime Señor, Jorge Portilla
similarity 0.61
Abstract

The arrival of quantum computers threatens the security guarantees of classical cryptography, since quantum algorithms can break schemes that remain secure against conventional attacks. The National Institute of Standards and Technology (NIST) has therefore standardized a set of post-quantum cryptographic algorithms, among them Falcon, a lattice-based digital signature scheme with the most compact signature and public-key sizes of the standardized candidates. Falcon's reliance on floating-point arithmetic makes it hard to implement in hardware, and prior work offers only partial accelerators for specific operations such as signature generation or verification, or a single full implementation generated through high-level synthesis (HLS). This work presents Peregrino, the first hardware accelerator of the complete Falcon digital signature scheme designed from scratch in HDL, targeting resource-constrained edge devices without a native floating-point unit through an emulated floating-point datapath. Implemented on a single Artix 7 XC7A200T FPGA, Peregrino uses 85261 LUTs, 41382 FFs, 44 BRAMs, and 142 DSPs for the Falcon-1024 variant. Against the only prior full implementation, the HLS-based FalconTakesOff, it uses 1,9$\times$ fewer LUTs, 3,4$\times$ fewer FFs, 2,7$\times$ fewer BRAMs, and 9,9$\times$ fewer DSPs, fitting the entire scheme on one FPGA where the HLS design requires at least two. Operating as a peripheral of an on-chip MicroBlaze soft-core, the accelerator additionally reduces key-pair generation, signature generation, and signature verification clock cycles by 92\%, 96\%, and 85\% over the emulated floating-point reference software.

0.23