Paper 2020/298

Fast polynomial inversion for post quantum QC-MDPC cryptography

Nir Drucker, Shay Gueron, and Dusan Kostic


The NIST PQC standardization project evaluates multiple new designs for post-quantum Key Encapsulation Mechanisms (KEMs). Some of them present challenging tradeoffs between communication bandwidth and computational overheads. An interesting case is the set of QC-MDPC based KEMs. Here, schemes that use the Niederreiter framework require only half the communication bandwidth compared to schemes that use the McEliece framework. However, this requires costly polynomial inversion during the key generation, which is prohibitive when ephemeral keys are used. One example is BIKE, where the BIKE-1 variant uses McEliece and the BIKE-2 variant uses Niederreiter. This paper shows an optimized constant-time polynomial inversion method that makes the computation costs of BIKE-2 key generation tolerable. We report a speedup of 11.8x over the commonly used NTL library, and 55.5 over OpenSSL. We achieve additional speedups by leveraging the latest Intel's Vector-PCLMULQDQ instructions on a laptop machine, 14.3x over NTL and 96.8x over OpenSSL. With this, BIKE-2 becomes a competitive variant of BIKE.

Available format(s)
Publication info
Preprint. MINOR revision.
Polynomial inversionBIKEQC-MDPC codesconstanttime algorithmconstant-time implementation
Contact author(s)
drucker nir @ gmail com
shay gueron @ gmail com
dusan kostic @ epfl ch
2020-03-09: received
Short URL
Creative Commons Attribution


      author = {Nir Drucker and Shay Gueron and Dusan Kostic},
      title = {Fast polynomial inversion for post quantum {QC}-{MDPC} cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2020/298},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.