Paper 2019/1441

A Code-specific Conservative Model for the Failure Rate of Bit-flipping Decoding of LDPC Codes with Cryptographic Applications

Paolo Santini, Alessandro Barenghi, Gerardo Pelosi, Marco Baldi, and Franco Chiaraluce

Abstract

Characterizing the decoding failure rate of iteratively decoded Low- and Moderate-Density Parity Check (LDPC/MDPC) codes is paramount to build cryptosystems based on them, able to achieve indistinguishability under adaptive chosen ciphertext attacks. In this paper, we provide a statistical worst-case analysis of our proposed iterative decoder obtained through a simple modification of the classic in-place bit-flipping decoder. This worst case analysis allows both to derive the worst-case behavior of an LDPC/MDPC code picked among the family with the same length, rate and number of parity checks, and a code-specific bound on the decoding failure rate. The former result allows us to build a code-based cryptosystem enjoying the $\delta$-correctness property required by IND-CCA2 constructions, while the latter result allows us to discard code instances which may have a decoding failure rate significantly different from the average one (i.e., representing weak keys), should they be picked during the key generation procedure.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Bit-flipping decodingcryptographydecoding failure rateLDPC codesMDPC codesweak keys
Contact author(s)
alessandro barenghi @ polimi it
History
2019-12-12: received
Short URL
https://ia.cr/2019/1441
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1441,
      author = {Paolo Santini and Alessandro Barenghi and Gerardo Pelosi and Marco Baldi and Franco Chiaraluce},
      title = {A Code-specific Conservative Model for the Failure Rate of Bit-flipping  Decoding of LDPC Codes with Cryptographic Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1441},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1441}},
      url = {https://eprint.iacr.org/2019/1441}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.