Paper 2025/1312

Can FrodoKEM Run in a Millisecond? FPGA Says Yes!

Abstract

FrodoKEM is a post-quantum key encapsulation mechanism based on plain Learning With Errors (LWE). In contrast to module-lattice-based schemes, it relies on an unstructured variant of the LWE problem, providing more conservative and better-understood security guarantees. As a result, FrodoKEM has been recommended by European cybersecurity agencies such as BSI and ANSSI, and has also been proposed in international standardization efforts, including ISO and the IETF Internet-Draft process. In this paper, we explore hardware-level parallelization techniques for FrodoKEM. To date, the only notable attempt to parallelize FrodoKEM in hardware was made by Howe et al. in 2021. In their work, the SHAKE function was identified as a performance bottleneck and replaced by the Trivium stream cipher. However, this replacement renders the implementation incompatible with standardized recommendations. In contrast, our work adheres strictly to the original FrodoKEM specification, including its use of SHAKE as the PRNG, and introduces a scalable architecture enabling high-throughput parallel execution. For FrodoKEM-640, we present parallel architectures for key generation, encapsulation, and decapsulation. Our implementation achieves between 976 and 1077 operations per second, making it the fastest FrodoKEM hardware implementation reported to date. Furthermore, we propose a general architecture that offers a scalable area-throughput trade-off: by increasing the number of DSPs and proportionally scaling BRAM usage, our design can be scaled to achieve significantly higher performance beyond the reported implementation. This demonstrates that SHAKE is not inherently a barrier to parallel matrix multiplication, and that efficient, standard-compliant FrodoKEM implementations are achievable for high-speed cryptographic applications.