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