Skip to Main content Skip to Navigation
Conference papers

On the Decoding Failure Rate of QC-MDPC Bit-Flipping Decoders

Abstract : Quasi-cyclic moderate density parity check codes allow the design of McEliece-like public-key encryption schemes with compact keys and a security that provably reduces to hard decoding problems for quasi-cyclic codes. In particular, QC-MDPC are among the most promising code-based key encapsulation mechanisms (KEM) that are proposed to the NIST call for standardization of quantum safe cryptography (two proposals, BIKE and QC-MDPC KEM). The first generation of decoding algorithms suffers from a small, but not negligible, decoding failure rate (DFR in the order of 10⁻⁷ to 10⁻¹⁰). This allows a key recovery attack presented by Guo, Johansson, and Stankovski (GJS attack) at Asiacrypt 2016 which exploits a small correlation between the faulty message patterns and the secret key of the scheme, and limits the usage of the scheme to KEMs using ephemeral public keys. It does not impact the interactive establishment of secure communications (e.g. TLS), but the use of static public keys for asynchronous applications (e.g. email) is rendered dangerous. Understanding and improving the decoding of QC-MDPC is thus of interest for cryptographic applications. In particular, finding parameters for which the failure rate is provably negligible (typically as low as 2⁻⁶⁴ or 2⁻¹²⁸) would allow static keys and increase the applicability of the mentioned cryptosystems. We study here a simple variant of bit-flipping decoding, which we call step-by-step decoding. It has a higher DFR but its evolution can be modeled by a Markov chain, within the theoretical framework of Julia Chaulet's PhD thesis. We study two other, more efficient, decoders. One is the textbook algorithm. The other is (close to) the BIKE decoder. For all those algorithms we provide simulation results, and, assuming an evolution similar to the step-by-step decoder, we extrapolate the value of the DFR as a function of the block length. This will give an indication of how much the code parameters must be increased to ensure resistance to the GJS attack.
Complete list of metadata

https://hal.inria.fr/hal-03139797
Contributor : Valentin Vasseur Connect in order to contact the contributor
Submitted on : Friday, February 12, 2021 - 12:19:37 PM
Last modification on : Friday, January 21, 2022 - 3:16:41 AM
Long-term archiving on: : Thursday, May 13, 2021 - 6:43:40 PM

File

2018-1207.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Nicolas Sendrier, Valentin Vasseur. On the Decoding Failure Rate of QC-MDPC Bit-Flipping Decoders. PQCrypto 2019 - Post-Quantum Cryptography 10th International Conference, May 2019, Chongqing, China. pp.404--416, ⟨10.1007/978-3-030-25510-7_22⟩. ⟨hal-03139797⟩

Share

Metrics

Les métriques sont temporairement indisponibles