Paper 2021/155

Exploring Parallelism to Improve the Performance of FrodoKEM in Hardware

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


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.

Available format(s)
Publication info
Published elsewhere. Journal of Cryptographic Engineering
Post-Quantum CryptographyLattice-Based CryptographyHardware SecurityFPGAFrodoKEM
Contact author(s)
james howe @ pqshield com
2021-02-17: received
Short URL
Creative Commons Attribution


      author = {James Howe and Marco Martinoli and Elisabeth Oswald and Francesco Regazzoni},
      title = {Exploring Parallelism to Improve the Performance of FrodoKEM in Hardware},
      howpublished = {Cryptology ePrint Archive, Paper 2021/155},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.