We present a variant of the classic in-place bit-flipping decoder, frequently used with Low- and Moderate-Density Parity Check (LDPC/MDPC) codes, which allows a statistical analysis of the achievable decoding failure rate (DFR) in worst-case conditions. Such evaluation is of paramount importance in code-based post-quantum cryptography (PQC) where the ability to achieve indistinguishability under adaptive chosen ciphertext attacks strictly depends on being able to ensure very low DFR values (e.g., in the order of 2 - 128 or lower) that, as such, are practically impossible to validate via numerical simulation. We provide theoretical evidence of the proposed approach and demonstrate its correctness through numerical examples. Moreover, we investigate the effect of changing the bit flipping decision threshold on the provided worst case analysis. Finally, we give design parameters for code-based cryptosystems employing Quasi-Cyclic LDPC/MDPC codes, able to achieve the security levels required in the NIST PQC standardization initiative which is currently in progress.

Analysis of In-Place Randomized Bit-Flipping Decoders for the Design of LDPC and MDPC Code-Based Cryptosystems

Barenghi A.;Pelosi G.;
2021

Abstract

We present a variant of the classic in-place bit-flipping decoder, frequently used with Low- and Moderate-Density Parity Check (LDPC/MDPC) codes, which allows a statistical analysis of the achievable decoding failure rate (DFR) in worst-case conditions. Such evaluation is of paramount importance in code-based post-quantum cryptography (PQC) where the ability to achieve indistinguishability under adaptive chosen ciphertext attacks strictly depends on being able to ensure very low DFR values (e.g., in the order of 2 - 128 or lower) that, as such, are practically impossible to validate via numerical simulation. We provide theoretical evidence of the proposed approach and demonstrate its correctness through numerical examples. Moreover, we investigate the effect of changing the bit flipping decision threshold on the provided worst case analysis. Finally, we give design parameters for code-based cryptosystems employing Quasi-Cyclic LDPC/MDPC codes, able to achieve the security levels required in the NIST PQC standardization initiative which is currently in progress.
Communications in Computer and Information Science
978-3-030-90427-2
978-3-030-90428-9
Bit-flipping decoding
Code-based cryptosystems
Decoding failure rate
LDPC codes
MDPC codes
Post-quantum cryptosystems
Quasi-cyclic codes
computer security
File in questo prodotto:
File Dimensione Formato  
main.pdf

accesso aperto

Descrizione: main article
: Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione 546.12 kB
Formato Adobe PDF
546.12 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: http://hdl.handle.net/11311/1201190
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact