About Low DFR for QC-MDPC Decoding

Nicolas Sendrier and Valentin Vasseur

Abstract

McEliece-like code-based key exchange mechanisms using QC-MDPC codes can reach IND-CPA security under hardness assumptions from coding theory, namely quasi-cyclic syndrome decoding and quasi-cyclic codeword finding. To reach higher security requirements, like IND-CCA security, it is necessary in addition to prove that the decoding failure rate (DFR) is negligible, for some decoding algorithm and a proper choice of parameters. Getting a formal proof of a low DFR is a difficult task. Instead, we propose to ensure this low DFR under some additional security assumption on the decoder. This assumption relates to the asymptotic behavior of the decoder and is supported by several other works. We define a new decoder, Backflip, which features a low DFR. We evaluate the Backflip decoder by simulation and extrapolate its DFR under the decoder security assumption. We also measure the accuracy of our simulation data, in the form of confidence intervals, using standard techniques from communication systems.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
code-based cryptographyQC-MDPC codeBIKEbit flipping algorithm
Contact author(s)
nicolas sendrier @ inria fr
valentin vasseur @ inria fr
History
Short URL
https://ia.cr/2019/1434

CC BY

BibTeX

@misc{cryptoeprint:2019/1434,
author = {Nicolas Sendrier and Valentin Vasseur},
title = {About Low DFR for QC-MDPC Decoding},
howpublished = {Cryptology ePrint Archive, Paper 2019/1434},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/1434}},
url = {https://eprint.iacr.org/2019/1434}
}

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