Optimized implementation of HQC on Cortex-M4

In March 2025, NIST selected HQC as a standardized PQC algorithm. Since HQC relies on binary polynomial operations, optimizations for prime-field schemes like Kyber are not directly applicable. Furthermore, optimizing HQC on Cortex-M4 involves constraints that complicate objective performance evaluation, which has hindered active research in this area. We address these issues and optimize dense-dense polynomial multiplication, HQC’s main computational bottleneck. Using the PQM4 benchmark framework, our implementation achieves speedups of 1139.53–1347.69% in key generation, 1139.53–1253.73% in encapsulation, and 1042.09–1198.78% in decapsulation over PQClean, and 38.78–45.81%, 38.18–45.58%, and 34.76–43.56% improvements over the NTL-based reference, depending on the security level.