Optimized implementation of QC‐MDPC code‐based cryptography

This paper presents a new enhanced version of the QcBits key encapsulation mechanism, which is a constant‐time implementation of the Niederreiter cryptosystem using QC‐MDPC codes. In this version, we updated the implementation parameters to meet the 128‐bit quantum security level, replaced some of the core algorithms to avoid using slower instructions, vectorized the entire code using the AVX‐512 instruction set extension, and applied several other techniques to achieve a competitive performance level. Our implementation takes 928, 259, and 5008 thousand Skylake cycles to perform batch key generation (cost per key), encryption, and uniform decryption, respectively. Comparing with the current state‐of‐the‐art implementation for QC‐MDPC codes, BIKE, our code is 1.9 times faster when decrypting messages.

• Publication year

  2018

• Venue

  Concurrency and Computation

• Publication date

  2018-12-16

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1002/cpe.5089
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A toolbox for software optimization of QC-MDPC code-based cryptosystems

  2019cited by this paper
• On Decoding Schemes for the MDPC-McEliece Cryptosystem

  2018cited by this paper
• QC-MDPC: A Timing Attack and a CCA2 KEM

  2018cited by this paper
• CAKE: Code-Based Algorithm for Key Encapsulation

  2017cited by this paper
• Area-Time Efficient Computation of Niederreiter Encryption on QC-MDPC Codes for Embedded Hardware

  2017cited by this paper
• A Side-Channel Assisted Cryptanalytic Attack Against QcBits

  2017cited by this paper
• Optimizing the Decoding Process of a Post-Quantum Cryptographic Algorithm

  2017cited by this paper
• A Key Recovery Attack on MDPC with CCA Security Using Decoding Errors

  2016cited by this paper
• QcBits: Constant-Time Small-Key Code-Based Cryptography

  2016influential reference
• Attacking Embedded ECC Implementations Through cmov Side Channels

  2016cited by this paper
• Vectorized Big Integer Operations for Cryptosystems on the Intel MIC Architecture

  2015influential reference
• Implementing QC-MDPC McEliece Encryption

  2015cited by this paper
• MDPC-McEliece: New McEliece variants from Moderate Density Parity-Check codes

  2013cited by this paper
• Fast and compact elliptic-curve cryptography

  2012influential reference
• Multiplication Instruction and its Usage for Computing the GCM Mode

  2010cited by this paper
• Algebraic Cryptanalysis of McEliece Variants with Compact Keys

  2010cited by this paper
• Compact McEliece Keys from Goppa Codes

  2009cited by this paper
• Attacking and defending the McEliece cryptosystem

  2008cited by this paper
• Side Channels in the McEliece PKC

  2008cited by this paper
• Mutual Information Analysis

  2008cited by this paper
• Handbook of Elliptic and Hyperelliptic Curve Cryptography

  2005cited by this paper
• Correlation Power Analysis with a Leakage Model

  2004cited by this paper
• High-Speed, Low-Complexity Systolic Designs of Novel Iterative Division Algorithms in GF(2^m)

  2004cited by this paper
• Differential Power Analysis

  1999cited by this paper
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

  1995cited by this paper
• On Computing Multiplicative Inverses in GF(2^m)

  1993cited by this paper
• Number theory

  1989cited by this paper
• A Fast Algorithm for Computing Multiplicative Inverses in GF(2^m) Using Normal Bases

  1988cited by this paper
• Elliptic curve cryptosystems

  1987cited by this paper
• On the inherent intractability of certain coding problems (Corresp.)

  1978cited by this paper
• A public key cryptosystem based on algebraic coding theory

  1978cited by this paper
• A method for obtaining digital signatures and public-key cryptosystems

  1978cited by this paper

• Evaluation of hardware and software implementations for NIST finalist and fourth-round post-quantum cryptography KEMs

  2024cites this paper
• A provably masked implementation of BIKE Key Encapsulation Mechanism

  2024cites this paper
• Faster Constant-Time Decoder for MDPC Codes and Applications to BIKE KEM

  2022cites this paper
• Mitigating 5G security challenges for next-gen industry using quantum computing

  2022cites this paper
• An Improvement of the Matrix-Matrix Multiplication Speed using 2D-Tiling and AVX512 Intrinsics for Multi-Core Architectures

  2021cites this paper
• Optimizing BIKE for the Intel Haswell and ARM Cortex-M4

  2021influential citation
• Cyber Security Cryptography and Machine Learning: Fourth International Symposium, CSCML 2020, Be'er Sheva, Israel, July 2–3, 2020, Proceedings

  2020cites this paper
• QC-MDPC decoders with several shades of gray

  2020influential citation
• Fast polynomial inversion for post quantum QC-MDPC cryptography

  2020influential citation
• Code-Based Cryptography

  2019influential citation
• Secure and efficient software implementation of QC-MDPC code-based cryptography

  2019cites this paper
• Efficient computation of positional population counts using SIMD instructions

  2019cites this paper
• Introducing Arithmetic Failures to Accelerate QC-MDPC Code-Based Cryptography

  2019cites this paper
• Foreword to the special issue of the workshop on high performance computing systems (XVIII Simpósio em Sistemas Computacionais de Alto Desempenho, WSCAD 2017)

  2019cites this paper