Paper 2026/1170

A Fast, Configurable and DSP-Free Hardware Implementation of FrodoKEM

Abstract

FrodoKEM is an unstructured LWE-based key encapsulation mechanism (KEM), widely recognized for its conservativeness and robustness. However, there remains a performance gap of approximately one order of magnitude between FrodoKEM and structured LWE-based KEMs, which severely limits its competitiveness during the standardization process. This work proposes the fastest hardware implementation of FrodoKEM to date, which is also configurable, achieving up to 2.5× speedup over prior hardware designs. Specifically, for the most time-consuming module, modular matrix multiplication, a block matrix processing approach is adopted, where the computation is reformulated into block-level operations and further mapped to vector inner-product computations. Based on this formulation, two optimized architectures are proposed for vector inner-product computation using a carry-save-adder (CSA)-based Wallace tree structure, achieving improvements in resource efficiency while eliminating the use of DSP resources. By fixing the block size to 4×4, the data generation rate using parallel SHAKE-based random number generators is precisely matched with the data consumption rate of matrix multiplication, thereby improving hardware utilization efficiency. The proposed design is implemented in Verilog and verified on both Xilinx Virtex-7 and Artix-7 FPGA platforms, as well as ASIC implementation.