Paper 2026/739

Additive FFTs for HQC on ARM Cortex-M4, Revisited

Tun-You Chien, Academia Sinica, National Tsing Hua University

Chun-Ming Chiu, Academia Sinica

Han-Hsuan Lin, National Tsing Hua University

Chun-Tao Peng, Academia Sinica

Bo-Yin Yang, Academia Sinica

Abstract

This paper presents an optimized implementation of the Hamming Quasi-Cyclic (HQC) key encapsulation mechanism, leveraging the additive fast Fourier transform (FFT) for polynomial multiplication. A primary challenge in applying FFT-based multiplication to HQC is that the polynomial degrees slightly exceed powers of two, making standard FFT approaches inefficient. To address this, we propose a new method combining the Frobenius additive FFT (FAFFT) with the Chinese Remainder Theorem (CRT) to efficiently multiply polynomials of these specific degrees. Such a combination is made possible by our new interpretation of FAFFT's Encode step as ring isomorphisms, from which we derive an exact formula for the modulus of any FAFFT-based polynomial multiplier. In addition to the multiplication algorithm, we replace the Berlekamp-Massey decoder with an Extended Euclidean Algorithm (EEA) based method. The regular data flow of EEA facilitates the use of our highly optimized GF(256) SIMD arithmetic, leading to a faster execution speed. Benchmarks demonstrate that our FFT-based approach significantly outperforms traditional Toom-Karatsuba methods, even at lower degrees, on the Arm Cortex-M4 platform. Our integrated optimizations result in a 19.5% and 20.4% speedups for the encapsulation and the decapsulation processes compared to the current state-of-the-art HQC-1 implementation.

@misc{cryptoeprint:2026/739,
      author = {Ming-Shing Chen and Tun-You Chien and Chun-Ming Chiu and Han-Hsuan Lin and Chun-Tao Peng and Bo-Yin Yang},
      title = {Additive {FFTs} for {HQC} on {ARM} Cortex-M4, Revisited},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/739},
      year = {2026},
      url = {https://eprint.iacr.org/2026/739}
}