The design of quantum-resistant cryptographic primitives has gained attraction lately, especially thanks to the U.S.A. National Institute of Standards and Technology (NIST) initiative, which is selecting a portfolio of primitives for standardization. A prime position in the set of asymmetric encryption primitives is occupied by the ones relying on decoding random linear error correction codes as their trapdoor. Among these primitives, the LEDAcrypt and BIKE cryptosystems have been admitted to the second round of the standardization initiative. They are based on the adoption of iteratively decoded Low- and Moderate-Density Parity Check (LDPC/MDPC) codes. Characterizing the decoding failure rate of such codes under iterative decoding is paramount to the security of both the LEDAcrypt and BIKE second round candidates to achieve indistinguishability under adaptive chosen ciphertext attacks (IND-CCA2). For these codes, we propose a new iterative decoder, obtained through a simple modification of the classic in-place bit-flipping decoder and, in this paper, we provide a statistical worst-case analysis of its performance. This result allows us to design parameters for LDPC/MDPC code-based cryptosystems with guaranteed extremely low failure rates (e.g., 2-128 ), fitting the hard requirement imposed by IND-CCA2 constructions.

A Failure Rate Model of Bit-flipping Decoders for QC-LDPC and QC-MDPC Code-based Cryptosystems

A. Barenghi;G. Pelosi;
2020-01-01

Abstract

The design of quantum-resistant cryptographic primitives has gained attraction lately, especially thanks to the U.S.A. National Institute of Standards and Technology (NIST) initiative, which is selecting a portfolio of primitives for standardization. A prime position in the set of asymmetric encryption primitives is occupied by the ones relying on decoding random linear error correction codes as their trapdoor. Among these primitives, the LEDAcrypt and BIKE cryptosystems have been admitted to the second round of the standardization initiative. They are based on the adoption of iteratively decoded Low- and Moderate-Density Parity Check (LDPC/MDPC) codes. Characterizing the decoding failure rate of such codes under iterative decoding is paramount to the security of both the LEDAcrypt and BIKE second round candidates to achieve indistinguishability under adaptive chosen ciphertext attacks (IND-CCA2). For these codes, we propose a new iterative decoder, obtained through a simple modification of the classic in-place bit-flipping decoder and, in this paper, we provide a statistical worst-case analysis of its performance. This result allows us to design parameters for LDPC/MDPC code-based cryptosystems with guaranteed extremely low failure rates (e.g., 2-128 ), fitting the hard requirement imposed by IND-CCA2 constructions.
2020
Proceedings of the 17th International Joint Conference on e-Business and Telecommunications, ICETE 2020 - Volume 2: SECRYPT
978-989-758-446-6
Bit-flipping Decoding, Code-based Cryptosystems, Decoding Failure Rate, LDPC Codes, MDPC Codes, Quasi-cyclic Codes, Post-quantum Cryptosystems
File in questo prodotto:
File Dimensione Formato  
SECRYPT_2020_118_CR.pdf

accesso aperto

Descrizione: main article
: Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione 353.44 kB
Formato Adobe PDF
353.44 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/1144467
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 3
social impact