Paper 2025/1939

Efficient Polynomial Multiplication for HQC on ARM Cortex-M4

Abstract

In this paper, we propose the Hybrid FAFFT-CRT method for accelerating HQC polynomial multiplication on the ARM Cortex-M4. The method uses the Chinese Remainder Theorem to map the polynomial ring to a product of an FAFFT-friendly ring of size $2^{d+1}$ and a small-degree residual ring, reducing the FAFFT transform length by half compared to the state-of-the-art. We also present the Hybrid Karatsuba-FAFFT method as an alternative hybrid based on a 2-way Karatsuba split, and apply radix-16 multiplication to HQC for the first time, with an operation-count cost model for selecting Karatsuba and Toom-Cook combinations. Additionally, we improve the core FAFFT butterfly through shortened XOR sequences, register scheduling, and SWAPMOVE-based bit swaps. On a NUCLEO-L4R5ZI board with a Cortex-M4 microcontroller, the Hybrid FAFFT-CRT method reduces polynomial multiplication cycles by 36.0% and 29.3% for HQC-1 and HQC-3, leading to cycle reductions for key generation, encapsulation, and decapsulation by 25.5%, 26.1%, and 23.5% for HQC-1, and 19.3%, 20.0%, and 19.1% for HQC-3. For HQC-5, our optimized butterfly FAFFT provides a consistent speedup of 1.4-1.6% across all KEM operations.