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 cryptographynon--binary MDPC codessymbol flippingdecoding 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
Creative Commons Attribution
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},
      url = {https://eprint.iacr.org/2023/1224}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.