Improved Frobenius FFT for Code-Based Cryptography on Cortex-M4

Abstract

Polynomial multiplication over finite fields is one of the most significant operations in code-based cryptography, including HQC, which has been selected as a standardized algorithm in the NIST PQC round 4 process. In the standardization process, the performance of an algorithm is important not only in general-purpose systems but also in embedded systems. In particular, NIST has recommended the ARM Cortex-M4 as the benchmark platform for embedded systems. In CHES2021, Chen et al. optimized BIKE on the ARM Cortex-M4, using the Frobenius Additive FFT as the polynomial multiplication algorithm. However, although HQC was finally selected as a standard algorithm in March 2025, an efficient implementation for the ARM Cortex-M4 platform, which NIST recommends as the benchmark for embedded systems, has not yet been reported. In this paper, we propose an optimized implementation of the Frobenius Additive FFT to accelerate polynomial multiplication in BIKE and HQC on the ARM Cortex-M4 platform. Our approach exploits the fact that one operand of field multiplications in the Frobenius Additive FFT is fixed, allowing the transformation of these operations into binary matrix-vector products. We then apply XOR-efficient linear layer techniques combined with a register scheduling strategy specifically designed for the constrain