Paper 2022/1043

A Study of Error Floor Behavior in QC-MDPC Codes

Sarah Arpin, University of Colorado Boulder
Tyler Raven Billingsley, St. Olaf College
Daniel Rayor Hast, Boston University
Jun Bo Lau, University of California, San Diego
Ray Perlner, National Institute of Standards and Technology
Angela Robinson
Abstract

We present experimental findings on the decoding failure rate (DFR) of BIKE, a fourth-round candidate in the NIST Post-Quantum Standardization process, at the 20-bit security level. We select parameters according to BIKE design principles and conduct a series of experiments. We directly compute the average DFR on a range of BIKE block sizes and identify both the waterfall and error floor regions of the DFR curve. We then study the influence on the average DFR of three sets $\mathcal{C}$, $\mathcal{N}$, and $2\mathcal{N}$ of near-codewords --- vectors of low weight that induce syndromes of low weight --- defined by Vasseur in 2021. We find that error vectors leading to decoding failures have small maximum support intersection with elements of these sets; further, the distribution of intersections is quite similar to that of sampling random error vectors and counting the intersections with $\mathcal{C}$, $\mathcal{N}$, and $2\mathcal{N}$. Our results indicate that these three sets are not sufficient in classifying vectors expected to cause decoding failures. Finally, we study the role of syndrome weight on the decoding behavior and conclude that the set of error vectors that lead to decoding failures differ from random vectors by having low syndrome weight.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
BIKE error-correcting codes McEliece PQC QC-MDPC
Contact author(s)
Sarah Arpin @ colorado edu
billings @ rose-hulman edu
drhast @ bu edu
jblau @ ucsd edu
ray perlner @ nist gov
angela robinson @ nist gov
History
2022-08-17: approved
2022-08-11: received
See all versions
Short URL
https://ia.cr/2022/1043
License
No rights reserved
CC0

BibTeX

@misc{cryptoeprint:2022/1043,
      author = {Sarah Arpin and Tyler Raven Billingsley and Daniel Rayor Hast and Jun Bo Lau and Ray Perlner and Angela Robinson},
      title = {A Study of Error Floor Behavior in QC-MDPC Codes},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1043},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1043}},
      url = {https://eprint.iacr.org/2022/1043}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.