Drucker, NirGueron, ShayKostic, Dusan2021-12-042021-12-042021-12-042021-12-0110.1016/j.ic.2021.104799https://infoscience.epfl.ch/handle/20.500.14299/183578WOS:000721215200050New post-quantum Key Encapsulation Mechanism (KEM) designs, evaluated as part of the NIST PQC standardization Project, pose challenging tradeoffs between communication bandwidth and computational overheads. Several KEM designs evaluated in Round-2 of the project are based on QC-MDPC codes. BIKE-2 uses the smallest communication bandwidth, but its key generation requires a costly polynomial inversion. In this paper, we provide details on the optimized polynomial inversion algorithm for QC-MDPC codes (originally proposed in the conference version of this work). This algorithm makes the runtime of BIKE-2 key generation tolerable. It brings a speedup of 11.4x over the commonly used NTL library, and 83.5x over OpenSSL. We achieve additional speedups by leveraging the latest Intel's Vector-PCLMULQDQ instructions, 14.3x over NTL and 103.9x over OpenSSL. Our algorithm and implementation were the reason that BIKE team chose BIKE-2 as the only scheme for its Round-3 specification (now called BIKE). (C) 2021 The Authors. Published by Elsevier Inc.Computer Science, Theory & MethodsMathematics, AppliedComputer ScienceMathematicspolynomial inversionbikeqc-mdpc codesconstant-time algorithmconstant-time implementationnist pqc round-3text::journal::journal article::research article