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 \times$ and $19.22 \times$ across its security levels, making HQC more practical for real-world deployment.

Abstract An important open problem in supersingular isogeny-based cryptography is to produce, without a trusted authority, concrete examples of ‘hard supersingular curves’ that is equations for supersingular curves for which computing the endomorphism ring is as difficult as it is for random supersingular curves. A related open problem is to produce a hash function to the vertices of the supersingular $\ell $-isogeny graph, which does not reveal the endomorphism ring, or a path to a curve of known endomorphism ring. Such a hash function would open up interesting cryptographic applications. In this paper, we document a number of (thus far) failed attempts to solve this problem, in the hope that we may spur further research, and shed light on the challenges and obstacles to this endeavour. The mathematical approaches contained in this article include: (i) iterative root-finding for the supersingular polynomial; (ii) gcd’s of specialized modular polynomials; (iii) using division polynomials to create small systems of equations; (iv) taking random walks in the isogeny graph of abelian surfaces, and applying Kummer surfaces and (v) using quantum random walks.