Cryptology ePrint Archive: Report 2021/1557
Performance bounds for QC-MDPC codes decoders
Marco Baldi and Alessandro Barenghi and Franco Chiaraluce and 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.
Category / Keywords: public-key cryptography / QC-MDPC codes, Decoding failure rate, Bit-Flipping decoder, Maximum likelihood decoder Error floor, Post-quantum cryptography, Code-based cryptography
Original Publication (with minor differences): in Proceedings of International Workshop on Code-Based Cryptography (CBCrypto 2021)
Date: received 26 Nov 2021
Contact author: alessandro barenghi at polimi it
Available format(s): PDF | BibTeX Citation
Version: 20211129:122400 (All versions of this report)
Short URL: ia.cr/2021/1557
[ Cryptology ePrint archive ]