Optimizing HQC using Frobenius Additive FFT on a RISC-V-based System-on-Chip

HQC is a quantum-resistant cryptographic key encapsulation mechanism, recently selected by NIST as a future standard. Polynomial multiplication is one of the most critical operations in HQC. Due to side-channel security concerns, the previously-used sparse-dense method was recently replaced by classical dense-dense multiplication implemented using Karatsuba's algorithm. This change has made polynomial multiplication the primary performance bottleneck, accounting for approximately 95% of the total execution time. This paper presents an alternative polynomial multiplication technique for HQC: the Frobenius Additive Fast Fourier Transform (FAFFT), which provides significant algorithmic-level performance improvements. We also present ANDROMEDA, the first state-of-the-art hardware implementation of FAFFT, and evaluate its performance impact by integrating our solution in a resourceconstrained RISC-V-based System-on-Chip scenario. Experimental results show that our solution improves HQC performance by approximately 9.64 × and 19.22 × across its security levels, making HQC more practical for real-world deployment.