Complete and Improved FPGA Implementation of Classic McEliece

Authors

  • Po-Jen Chen GIEE, National Taiwan University, Taipei, Taiwan; CITI, Academia Sinica, Taipei, Taiwan
  • Tung Chou CITI, Academia Sinica, Taipei, Taiwan
  • Sanjay Deshpande CASLAB, Deptartment of Electrical Engineering, Yale University, New Haven, US
  • Norman Lahr ACE, Fraunhofer SIT, Darmstadt, Germany
  • Ruben Niederhagen IMADA, University of Southern Denmark, Odense, Denmark
  • Jakub Szefer CASLAB, Deptartment of Electrical Engineering, Yale University, New Haven, US
  • Wen Wang CASLAB, Deptartment of Electrical Engineering, Yale University, New Haven, US

DOI:

https://doi.org/10.46586/tches.v2022.i3.71-113

Keywords:

Classic McEliece, Key Encapsulation Mechanism, Code-Based Cryptography, PQC, FPGA, Hardware Implementation

Abstract

We present the first specification-compliant constant-time FPGA implementation of the Classic McEliece cryptosystem from the third-round of NIST’s Post-Quantum Cryptography standardization process. In particular, we present the first complete implementation including encapsulation and decapsulation modules as well as key generation with seed expansion. All the hardware modules are parametrizable, at compile time, with security level and performance parameters. As the most time consuming operation of Classic McEliece is the systemization of the public key matrix during key generation, we present and evaluate three new algorithms that can be used for systemization while complying with the specification: hybrid early-abort systemizer (HEA), single-pass early-abort systemizer (SPEA), and dual-pass earlyabort systemizer (DPEA). All of the designs outperform the prior systemizer designs for Classic McEliece by 2.2x to 2.6x in average runtime and by 1.7x to 2.4x in time-area efficiency. We show that our complete Classic McEliece design for example can perform key generation in 5.2 ms to 20 ms, encapsulation in 0.1 ms to 0.5 ms, and decapsulation in 0.7 ms to 1.5 ms for all security levels on an Xlilinx Artix 7 FPGA. The performance can be increased even further at the cost of resources by increasing the level of parallelization using the performance parameters of our design.

Downloads

Published

2022-06-08

Issue

Section

Articles

How to Cite

Complete and Improved FPGA Implementation of Classic McEliece. (2022). IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022(3), 71-113. https://doi.org/10.46586/tches.v2022.i3.71-113