Theoretical analysis of decoding failure rate of non-binary QC-MDPC codes

Kirill Vedenev; Yury Kosolapov

Paper 2023/1224

Theoretical analysis of decoding failure rate of non-binary QC-MDPC codes

Kirill Vedenev

, Southern Federal University

Yury Kosolapov

, Southern Federal University

Abstract

In this paper, we study the decoding failure rate (DFR) of non-binary QC-MDPC codes using theoretical tools, extending the results of previous binary QC-MDPC code studies. The theoretical estimates of the DFR are particularly significant for cryptographic applications of QC-MDPC codes. Specifically, in the binary case, it is established that exploiting decoding failures makes it possible to recover the secret key of a QC-MDPC cryptosystem. This implies that to attain the desired security level against adversaries in the CCA2 model, the decoding failure rate must be strictly upper-bounded to be negligibly small. In this paper, we observe that this attack can also be extended to the non--binary case as well, which underscores the importance of DFR estimation. Consequently, we study the guaranteed error-correction capability of non-binary QC-MDPC codes under one-step majority logic (OSML) decoder and provide a theoretical analysis of the 1-iteration parallel symbol flipping decoder and its combination with OSML decoder. Utilizing these results, we estimate the potential public-key sizes for QC-MDPC cryptosystems over $\mathbb{F}_4$ for various security levels. We find that there is no advantage in reducing key sizes when compared to the binary case.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: code--based cryptography non--binary MDPC codes symbol flipping decoding failure rate
Contact author(s): vedenevk @ gmail com
puzzlestorage @ gmail com
History: 2023-08-15: approved; 2023-08-12: received; See all versions
Short URL: https://ia.cr/2023/1224
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1224,
      author = {Kirill Vedenev and Yury Kosolapov},
      title = {Theoretical analysis of decoding failure rate of non-binary QC-MDPC codes},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1224},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1224}},
      url = {https://eprint.iacr.org/2023/1224}
}