On the applicability of the Fujisaki–Okamoto transformation to the BIKE KEM

Abstract

The QC-MDPC code-based KEM BIKE is one of the Round-3 candidates of the NIST PQC standardization project. Its Round-2 specification document described variants claiming to have IND-CCA security. The security proof used the Fujisaki–Okamoto transformation and a decoder targeting a Decoding Failure Rate (DFR) of $2^{-128}$ (for Level-1 security). However, several aspects needed to be amended in order for the IND-CCA proof to hold. The main issue is that using a decoder with DFR of $2^{-128}$ does not necessarily imply that the underlying PKE is δ-correct with $\delta =2^{-128}$, as required. In this paper, we handle the necessary aspects to ensure the security claim is correct. In particular, we close the gap in the proof by defining the notion of message-agnostic PKE. We show that the PKEs underlying the BIKE versions are message-agnostic. This implies that BIKE with a decoder that has a sufficiently low DFR is also an IND-CCA KEM.

Keywords:

• BIKE
• post-quantum cryptography
• NIST
• QC-MDPC codes
• Fujisaki–Okamoto

2010 Mathematics Subject Classifications:

• 94A60
• 11T71

Acknowledgments

The BIU Center for Research in Applied Cryptography and Cyber Security, and the Center for Cyber Law and Policy at the University of Haifa, both in conjunction with the Israel National Cyber Bureau in the Prime Minister's Office.

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1 Generally, this is used as a shared key for a symmetric encryption scheme.

2 This corresponds to the BIKE-2 variant described in [2].

3 This corresponds to the BIKE-3 variant described in [2].

Additional information

Funding

This research was supported by: NSF-BSF (United States-Israel Binational Science Foundation) [grant number 2018640]; NSF Grant CNS (Division of Computer and Network Systems) [grant number 1906360]; The Israel Science Foundation [grant number 3380/19].