Paper 2019/1423

QC-MDPC decoders with several shades of gray

Nir Drucker, Shay Gueron, and Dusan Kostic

Abstract

QC-MDPC code-based KEMs rely on decoders that have a small or even negligible Decoding Failure Rate (DFR). These decoders should be efficient and implementable in constant-time. One example for a QC-MDPC KEM is the Round-2 candidate of the NIST PQC standardization project, "BIKE". We have recently shown that the Black-Gray decoder achieves the required properties. In this paper, we deffine several new variants of the Black-Gray decoder. One of them, called Black-Gray-Flip, needs only 7 steps to achieve a smaller DFR than Black-Gray with 9 steps, for the same block size. On current AVX512 platforms, our BIKE-1 (Level-1) constant-time decapsulation is 1:9x faster than the previous decapsulation with Black-Gray. We also report an additional 1:25x decapsulating speedup using the new AVX512-VBMI2 and vector-PCLMULQDQ instructions available on "Ice-Lake" micro-architecture.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
BIKEQC-MDPC codesconstant-time implementationQC-MDPC decoders
Contact author(s)
drucker nir @ gmail com
shay gueron @ gmail com
dusan kostic @ epfl ch
History
2019-12-10: received
Short URL
https://ia.cr/2019/1423
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1423,
      author = {Nir Drucker and Shay Gueron and Dusan Kostic},
      title = {QC-MDPC decoders with several shades of gray},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1423},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1423}},
      url = {https://eprint.iacr.org/2019/1423}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.