Ming-Shing Chen
IIS and CITI, Academia Sinica, Taipei, Taiwan

Tun-You Chien
IIS and CITI, Academia Sinica, Taipei, Taiwan; National Tsing Hua University, Hsinchu, Taiwan

Chun-Ming Chiu
IIS and CITI, Academia Sinica, Taipei, Taiwan

Han-Hsuan Lin
National Tsing Hua University, Hsinchu, Taiwan

Chun-Tao Peng
IIS and CITI, Academia Sinica, Taipei, Taiwan

Bo-Yin Yang
IIS and CITI, Academia Sinica, Taipei, Taiwan

Keywords: HQC, additive FFT, F2 polynomial multiplication, extended CRT

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 F256 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.