Paper 2021/155

Exploring Parallelism to Improve the Performance of FrodoKEM in Hardware

James Howe, Marco Martinoli, Elisabeth Oswald, and Francesco Regazzoni

Abstract

FrodoKEM is a lattice-based key encapsulation mechanism, currently a semi-finalist in NIST’s post-quantum standardization effort. A condition for these candidates is to use NIST standards for sources of randomness (i.e., seed-expanding), and as such most candidates utilize SHAKE, an XOF defined in the SHA-3 standard. However, for many of the candidates, this module is a significant implementation bottleneck. Trivium is a lightweight, ISO standard stream cipher which performs well in hardware and has been used in previous hardware designs for lattice-based cryptography. This research proposes optimized designs for FrodoKEM, concentrating on high throughput by parallelising the matrix multiplication operations within the cryptographic scheme. This process is eased by the use of Trivium due to its higher throughput and lower area consumption. The parallelisations proposed also complement the addition of first-order masking to the decapsulation module. Overall, we significantly increase the throughput of FrodoKEM; for encapsulation we see a 16x speed-up, achieving 825 operations per second, and for decapsulation we see a 14x speed-up, achieving 763 operations per second, compared to the previous state-of-the-art, whilst also maintaining a similar FPGA area footprint of less than 2000 slices.