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 δ=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.
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 δ=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.
In this work, we continue the analysis of the binding properties of implicitly-rejecting key-encapsulation mechanisms (KEMs) obtained via the Fujisaki-Okamoto (FO) transform. These binding properties, in earlier literature known under the term robustness, thwart attacks that can arise when using KEMs in complex protocols. Recently, Cremers et al. (CCS'24) introduced a framework for binding notions, encompassing previously existing but also new ones. While implicitly-rejecting FO-KEMs have been analyzed with respect to multiple of these notions, there are still several gaps. We complete the picture by providing positive and negative results for the remaining notions. Further, we show how to apply our results to the code-based KEMs BIKE and HQC, which were round-4 candidates in NIST's PQC standardization process. Through this, we close a second gap as our results complete the analysis of the binding notions for the NIST round-4 KEMs. Finally, we give a modified version of the FO transform that achieves all binding notions.
In this paper, we rethink the ciphertext equality check step of the decapsulation procedure of Saber, which is one out of four KEM finalists in the third round NIST PQC standardization process. Through this investigation, we pursue cryptographic answers to some important questions. Those are why the re-encryption process of Fujisaki-Okamoto transformation, which is commonly used method to satisfy IND-CCA security in most existing lattice-based KEM algorithms including Saber, is especially necessary in the case of Saber, whether the re-encryption process can be further simplified, and whether the ciphertext equality check must be performed over the entire (re-encrypted/originally received) ciphertexts?
Practical deployments of key encapsulation mechanisms (KEMs) may entail large servers each using their public keys to communicate with potentially millions of clients simultaneously. While the standard IND-CCA security definition for KEMs considers only a single challenge public key and single challenge ciphertext, it can be relevant to consider multi-target scenarios where the adversary aims to break one of many challenge ciphertexts, for one of many challenge public keys. Many post-quantum KEMs have been built by applying the Fujisaki-Okamoto (FO) transform to a public key encryption (PKE) scheme. Although the FO transform incurs only a few bits of security loss for the standard, single-challenge IND-CCA property, this does not hold in the multi-target setting. Attacks have been identified against standards-track FO-based KEMs with 128-bit message spaces (FrodoKEM-640 and HQC-128) which become feasible if the adversary is given many challenge ciphertexts (say, 2^64). These attacks exploit the deterministic encryption induced by the FO transform which allows the IND-CCA experiment to be reduced to a search problem on the message space, which in some cases may not be large enough to avoid collisions between pre-computation and challenge values. A cost effective way to amplify the hardness of this search problem is to add a random but public salt during encapsulation. While revised versions of FrodoKEM and HQC have used salts, there has been no proof showing that salting provides multi-ciphertext security. In this work, we formally analyze a salted variant of the Fujisaki-Okamoto transform, in the classical and quantum random oracle model (ROM); for the classical ROM, we show that multi-target IND-CCA security of the resulting KEM tightly reduces to the multi-target IND-CPA security of the underlying PKE. Our results imply that, for FrodoKEM and HQC at the 128-bit security level, replacing the FO transform with the salted variant can recover 62 bits of multi-target security, at the cost of a very small overhead increase.
Constructing an efficient CCA-secure KEM is generally done by first constructing a passively-secure PKE scheme, and then applying the Fujisaki-Okamoto (FO) transformation. The original FO transformation was designed to offer security in a single user setting. A stronger notion, known as multi-user security, considers the attacker's advantage in breaking one of many user's ciphertexts. Bellare et al. (EUROCRYPT 2000) showed that standard single user security implies multi-user security with a multiplicative tightness gap equivalent to the number of users.
Combiners for cryptographic schemes are a common way to increase security using redundancy. The security notions for public key encryption (PKE) combiners can be extended beyond the standard IND-CCA security to achieve even stronger security notions. In the indistinguishability under adaptive strong multiple chosen-ciphertext attack (IND-sMCCA) security notion, the adversary has additional oracle access to the underlying cipher components of the combiner. Recently, combiners have received more attention because of the possibility of combining classical and post-quantum (PQ) cryptography. This allows for the use of novel PQ algorithms while still having the security guarantees of the classical algorithms. In order to examine the security against quantum adversaries, the quantum random oracle model (QROM) has become the most relevant security model. However, there are no PKE combiners that achieve IND-sMCCA security in the QROM, even though this security notion describes much better the current state where classical, PQ, and combined schemes are deployed at the same time. In this paper, we close this gap by providing a new PKE combiner that is IND-sMCCA secure in the QROM. Our construction is more efficient and lean than the existing PKE combiners, considering the primitives used and the ciphertext size. We accomplish this by applying the Fujisaki-Okamoto (FO) transformation to a PKE combiner of Asmuth and Blakley. To achieve IND-sMCCA security for the combiner, the PKE components must be OW-CCA secure. However, when using weaker (OW-CPA secure) PKE components, we still achieve standard IND-CCA security for the combiner. The security reductions are given in the ROM and the QROM, achieving bounds of different tightness.
This thesis is an in-depth introduction to NIST's post-quantum Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM). We begin by introducing the problem at the core of ML-KEM, known as the Module Learning With Errors (MLWE) problem. In this problem, an adversary attempts to distinguish between samples selected from a specific distribution and samples from uniformly random samples. We also discuss the hardness of the MLWE problem, under the conjecture that certain lattice problems over modules are hard. ML-KEM utilizes a variant of the Fujisaki-Okamoto transformation, which employs a weakly secure Public-Key Encryption (PKE) scheme to construct a strongly secure key-encapsulation mechanism in the Random Oracle Model (ROM). We explain the working principle of the MLWE-based public-key encryption scheme and demonstrate how ML-KEM is constructed from it. Finally, we analyze the security of ML-KEM. We provide a tight security bound for IND-CCA security of ML-KEM in ROM, under the assumption that the underlying PKE is IND-CPA secure. Additionally, we present two security theorems in the Quantum Random Oracle Model (QROM). The first theorem establishes non-tightly IND-CCA security of ML-KEM in QROM if the MLWE problem is hard to solve. The second theorem assumes that the deterministic PKE is ciphertext-indistinguishable. Under this assumption, we derive a tighter bound for the IND-CCA security of ML-KEM in QROM.