IACR Communications in Cryptology

Binding Security of Implicitly-Rejecting KEMs and Application to BIKE and HQC

Juliane Krämer, Patrick Struck, Maximiliane Weishäupl

Published Jul 7, 2025• 4 citations

Abstract

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.

DOI: 10.62056/ak2i893y6

Related papers

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

Nir Drucker, Shay Gueron, Dušan Kostić +1 more

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.

International Journal of Computer Mathematics Computer Systems TheoryMay 14, 202119 citations

Analysis of the FO Transformation in the Lattice-Based Post-Quantum Algorithms

Miguel Ángel González de la Torre, Luis Hernández Encinas, Araceli Queiruga‐Dios

Newer variants of the Fujisaki–Okamoto transformation are used in most candidates of the third round of the NIST Post-Quantum Cryptography standardization call in the category of public key encryption schemes. These transformations are applied to obtain a highly secure key encapsulation mechanism from a less secure public key encryption scheme. Furthermore, there are five candidates (three finalists and two alternatives) that passed to the third round of the process and whose security is based in lattice problems. This work analyzes the different ways in which the lattice-based candidates of the NIST call apply the Fujisaki–Okamoto transformation and the particularities of each application. The study of such differences and their repercussion in the design of the proposals will allow a better understanding of the algorithms. Moreover, we propose a modification of the Kyber algorithm—the only public key encryption candidate established as a PQC standard by NIST in its more recent publication—in order to avoid the re-encryption in the decapsulation algorithm and, in this way, to reduce the side channel attacks vulnerability.

MathematicsAug 17, 20222 citations

On The Multi-target Security of Post-Quantum Key Encapsulation Mechanisms

Lewis Glabush, Kathrin Hövelmanns, Douglas Stebila

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.

IACR Communications in CryptologyMay 4, 20262 citations

Faster Lattice-Based KEMs via a Generic Fujisaki-Okamoto Transform Using Prefix Hashing

Julien Duman, Kathrin Hövelmanns, Eike Kiltz +2 more

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.

ACM SIGSAC Conference on Computer and Communications Security (CCS)Nov 12, 202133 citations

Keeping Up with the KEMs: Stronger Security Notions for KEMs and Automated Analysis of KEM-based Protocols

Cas J. F. Cremers, Alexander Dax, Niklas Medinger

Key Encapsulation Mechanisms (KEMs) are a critical building block for hybrid encryption and modern security protocols, notably in the post-quantum setting. Given the asymmetric public key of a recipient, the primitive establishes a shared secret key between sender and recipient. In recent years, a large number of abstract designs and concrete implementations of KEMs have been proposed, e.g., in the context of the NIST process for post-quantum primitives.

ACM SIGSAC Conference on Computer and Communications Security (CCS)Dec 2, 202424 citations

On the Security and Efficiency of TLS 1.3 Handshake with Hybrid Key Exchange from CPA-Secure KEMs

Jinrong Chen, Wei Peng, Yi Wang +1 more

TLS 1.3 is a crucial protocol for securing modern internet communications. To facilitate a smooth transition to post-quantum security, hybrid key exchange, which combines classical key exchange algorithms with post-quantum key encapsulation mechanisms (KEMs), is proposed to enhance the security of the current TLS 1.3 handshake. However, existing drafts and implementations of hybrid key exchange for TLS 1.3 primarily rely on CCA-secure KEMs (i.e., secure against chosen-ciphertext attacks) based on the Fujisaki-Okamoto (FO) transform. The re-encryption step in their decapsulation algorithms not only introduces additional performance overhead but also raises the risk of side-channel attacks. Although Huguenin-Dumittan and Vaudenay (Eurocrypt 2022) and Zhou et al. (Asiacrypt 2024) demonstrated that the weaker CPA-secure KEMs (i.e., secure against chosen-plaintext attacks) suffice for constructing a secure TLS 1.3 handshake, their analyses were limited to single-KEM settings and did not consider the hybrid key exchange scenario. This work challenges the necessity of CCA security by proving that CPA-secure KEMs are sufficient for the TLS 1.3 handshake even in the hybrid key exchange setting. We provide the first formal security proofs for this claim, covering both the classical random oracle model (ROM) and the quantum random oracle model (QROM), thereby ensuring security against quantum adversaries. To validate the practical benefits, we conduct an extensive performance evaluation based on the latest OpenSSL implementation. Our results show that using CPA-secure KEMs yields up to 44.8% performance improvement at the key exchange layer and up to approximately 9% acceleration for the full TLS 1.3 handshake. Beyond performance gains, this approach reduces the codebase's attack surface by eliminating the re-encryption step, thereby mitigating a class of side-channel vulnerabilities. Our work positions CPA-secure KEMs as a secure, efficient, and practical alternative for standardizing and deploying post-quantum TLS 1.3 even with hybrid key exchange.

EntropyDec 8, 20256 citations