On constant-time QC-MDPC decoding with negligible failure rate

Nir Drucker, Shay Gueron, and Dusan Kostic

Abstract

The QC-MDPC code-based KEM Bit Flipping Key Encapsulation (BIKE) is one of the Round-2 candidates of the NIST PQC standardization project. It has a variant that is proved to be IND-CCA secure. The proof models the KEM with some black-box ("ideal") primitives. Specifically, the decapsulation invokes an ideal primitive called "decoder", required to deliver its output with a negligible Decoding Failure Rate (DFR). The concrete instantiation of BIKE substitutes this ideal primitive with a new decoding algorithm called "Backflip", that is shown to have the required negligible DFR. However, it runs in a variable number of steps and this number depends on the input and on the key. This paper proposes a decoder that has a negligible DFR and also runs in a fixed (and small) number of steps. We propose that the instantiation of BIKE uses this decoder with our recommended parameters. We study the decoder's DFR as a function of the scheme's parameters to obtain a favorable balance between the communication bandwidth and the number of steps that the decoder runs. In addition, we build a constant-time software implementation of the proposed instantiation, and show that its performance characteristics are quite close to the IND-CPA variant. Finally, we discuss a subtle gap that needs to be resolved for every IND-CCA secure KEM (BIKE included) where the decapsulation has nonzero failure probability: the difference between average DFR and "worst-case" failure probability per key and ciphertext.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
code-based cryptographyMDPC codesconstant time decodingdecoding failure rate
Contact author(s)
dusan kostic @ epfl ch
History
Short URL
https://ia.cr/2019/1289

CC BY

BibTeX

@misc{cryptoeprint:2019/1289,
author = {Nir Drucker and Shay Gueron and Dusan Kostic},
title = {On constant-time QC-MDPC decoding with negligible failure rate},
howpublished = {Cryptology ePrint Archive, Paper 2019/1289},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/1289}},
url = {https://eprint.iacr.org/2019/1289}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.