Accelerating HQC with Additive FFT

This paper presents an accelerated implementation of the Hamming Quasi-Cyclic (HQC) key encapsulation mechanism by leveraging additive Fast Fourier Transform (FFT) for polynomial multiplication (polymuls). A common challenge when applying FFT-based polymuls to HQC are the polynomial degrees fractionally greater than powers of two, making standard FFT polymuls inefficient for those parameters. We introduce a novel combination of additive FFT with the Chinese Remainder Theorem (CRT) to multiply such just-above-power-of-two degree polynomials.Further optimizations are achieved by caching the FFT transforms of the public and secret keys during or after key generation and reusing the transform of the shared random polynomial during the encapsulation and decapsulation processes. This approach significantly reduces redundant computations.The effectiveness of these optimizations is evaluated across various hardware platforms, including x86-64 with AVX2 and Galois Field New Instructions (GFNI), as well as ARM NEON on Apple M1 and Cortex-A72 processors. Benchmarks show that on platforms with long carry-less multiplication instructions like PCLMULQDQ, the proposed caching and reuse strategies allow FFT-based implementations to outpace traditional Toom-Karatsuba methods in the Encap and Decap operations of the HQC scheme, even with comparable raw multiplication speeds. On platforms lacking long carry-less multiplication instructions, the additive FFT approach already gives the superior performance.