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. In this paper, we explore hardware-level parallelization of FrodoKEM's matrix multiplication, which dominates its execution time. Earlier high-throughput work by Howe et al. identified SHAKE as a performance bottleneck and replaced it with the Trivium stream cipher, which renders the implementation incompatible with the FrodoKEM specification. In contrast, our work adheres strictly to the specification, including its use of SHAKE as the PRNG, and introduces a parameterized architecture whose degree of parallelism is set by design-time parameters. We present operation-specific datapaths for FrodoKEM-640 on Artix-7 with 24 parallel multipliers for key generation and 32 for encapsulation and decapsulation, achieving 976-1077 operations per second, i.e., latencies of 0.93-1.02 ms. Among the earlier specification-compliant designs, this is the lowest latency and the lowest area-time product. The design shows that SHAKE is not a barrier to parallel matrix multiplication and that efficient, standard-compliant FrodoKEM implementations are practical for high-speed cryptographic applications.