Fast polynomial inversion for post quantum QC-MDPC cryptography

By Nir Drucker, Shay Gueron, Dusan Kostic
2020
Download Copy BibTeX
Copy BibTeX
The NIST PQC standardization project evaluates multiple new designs for post-quantum Key Encapsulation Mechanisms (KEMs). Some of them present challenging tradeoffs between communication band-width 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 pa-per shows an optimized constant-time polynomial inversion method that makes the computation costs of BIKE-2 key generation tolerable. We re-port a speedup of 11.8×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.3× over NTL and 96.8× over OpenSSL. With this, BIKE-2 becomes a competitive variant of BIKE.

Latest news

US, CA, Santa Clara
Amazon is looking for a passionate, talented, and inventive Applied Scientist with a strong machine learning background to help build industry-leading language technology. Our mission is to provide a delightful experience to Amazon’s customers by pushing the envelope in Natural Language Processing (NLP), Generative AI, Large Language Model (LLM), Natural Language Understanding (NLU), Machine Learning (ML), Retrieval-Augmented Generation, Responsible AI, Agent, Evaluation, and Model Adaptation. As part of our AI team in Amazon AWS, you will work alongside internationally recognized experts to develop novel algorithms and modeling techniques to advance the state-of-the-art in human language technology. Your work will directly impactRead more