Paper 2021/1557
Performance bounds for QC-MDPC codes decoders
Marco Baldi, Alessandro Barenghi, Franco Chiaraluce, Gerardo Pelosi, and Paolo Santini
Abstract
Quasi-Cyclic Moderate-Density Parity-Check (QC-MDPC) codes are receiving increasing attention for their advantages in the context of post-quantum asymmetric cryptography based on codes. However, a fundamentally open question concerns modeling the performance of their decoders in the region of a low decoding failure rate (DFR). We provide two approaches for bounding the performance of these decoders, and study their asymptotic behavior. We first consider the well-known Maximum Likelihood (ML) decoder, which achieves optimal performance and thus provides a lower bound on the performance of any sub-optimal decoder. We provide lower and upper bounds on the performance of ML decoding of QC-MDPC codes and show that the DFR of the ML decoder decays polynomially in the QC-MDPC code length when all other parameters are fixed. Secondly, we analyze some hard to decode error patterns for Bit-Flipping (BF) decoding algorithms, from which we derive some lower bounds on the DFR of BF decoders applied to QC-MDPC codes.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Minor revision. in Proceedings of International Workshop on Code-Based Cryptography (CBCrypto 2021)
- Keywords
- QC-MDPC codesDecoding failure rateBit-Flipping decoderMaximum likelihood decoder Error floorPost-quantum cryptographyCode-based cryptography
- Contact author(s)
- alessandro barenghi @ polimi it
- History
- 2021-11-29: received
- Short URL
- https://ia.cr/2021/1557
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/1557,
author = {Marco Baldi and Alessandro Barenghi and Franco Chiaraluce and Gerardo Pelosi and Paolo Santini},
title = {Performance bounds for QC-MDPC codes decoders},
howpublished = {Cryptology ePrint Archive, Paper 2021/1557},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/1557}},
url = {https://eprint.iacr.org/2021/1557}
}
