Cryptology ePrint Archive: Report 2021/155

Exploring Parallelism to Improve the Performance of FrodoKEM in Hardware

James Howe and Marco Martinoli and 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.

Category / Keywords: implementation / Post-Quantum Cryptography, Lattice-Based Cryptography, Hardware Security, FPGA, FrodoKEM

Original Publication (in the same form): Journal of Cryptographic Engineering

Date: received 12 Feb 2021

Contact author: james howe at pqshield com

Available format(s): PDF | BibTeX Citation

Version: 20210217:100101 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]