This paper proposes a new generic Encrypt-thenMAC (EtM) transformation for constructing IND-CCA secure Key Encapsulation Mechanisms (KEMs) in the post-quantum setting. The transformation builds on a public-key encryption scheme satisfying one-wayness under plaintext-checking attacks (OW-PCA) and an existentially unforgeable MAC, and formally achieves tight IND-CCA security in the random oracle model via a rigorous security reduction. Unlike the widely used FujisakiOkamoto (FO) transformation, our approach eliminates the need for ciphertext re-encryption during decapsulation-a major source of computational overhead and side-channel vulnerability in lattice-based implementations. We instantiate the transformation using the ML-KEM (FIPS 203) subroutine, yielding the ML-KEM-EtM variant. Experimental results show that ML-KEMEtM reduces decapsulation cycle counts by$72-79 {\%}$across security levels, with only a modest increase in encapsulation cost$(1.8-7.3 {\%})$and ciphertext size$(1.0-2.1 {\%})$. The scheme thus offers a practical and efficient a lternative to F O-based KEMs, especially in performance-critical scenarios such as post-quantum TLS handshakes, where decapsulation efficiency is paramount.
This paper proposes a new generic Encrypt-thenMAC (EtM) transformation for constructing IND-CCA secure Key Encapsulation Mechanisms (KEMs) in the post-quantum setting. The transformation builds on a public-key encryption scheme satisfying one-wayness under plaintext-checking attacks (OW-PCA) and an existentially unforgeable MAC, and formally achieves tight IND-CCA security in the random oracle model via a rigorous security reduction. Unlike the widely used FujisakiOkamoto (FO) transformation, our approach eliminates the need for ciphertext re-encryption during decapsulation-a major source of computational overhead and side-channel vulnerability in lattice-based implementations. We instantiate the transformation using the ML-KEM (FIPS 203) subroutine, yielding the ML-KEM-EtM variant. Experimental results show that ML-KEMEtM reduces decapsulation cycle counts by72−79%across security levels, with only a modest increase in encapsulation cost(1.8−7.3%)and ciphertext size(1.0−2.1%). The scheme thus offers a practical and efficient a lternative to F O-based KEMs, especially in performance-critical scenarios such as post-quantum TLS handshakes, where decapsulation efficiency is paramount.
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.
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.
Key Encapsulation Mechanism (KEM) is a foundational cryptography primitive, which can provide secure symmetric cryptographic key material for transmission by using public key algorithms. Until now, many Chosen-Ciphertext (IND-CCA) secure KEM schemes are constructed from Chosen-Plaintext (IND-CPA) or One-Way (OW-CPA) secure PKE via the generic Fujisaki-Okamoto (FO) transformations (TCC 2017). However, the security relies on the Random Oracle Model (ROM). To the best of our knowledge, there are no IND-CCA secure KEM schemes based on Learning Parity with Noise (LPN) assumption that can against post quantum attacks in the standard model. In this work, we propose the first direct construction of LPN-based KEM, which is secure in the standard model. In particular, we use double-trapdoor technique to answer adversary’s decryption queries correctly and a Target Collision Resistant (TCR) hash function to check the validity of the ciphertext. The encapsulated key is determined by a special LPN problem (with no random oracle required). The scheme is IND-CCA secure against post-quantum attacks under the low-noise LPN assumptions by a series of games and the security reduction is tight. Compared with previous schemes on 128-bit security level, our CCA-secure scheme only holds 50.78MB public keys, 62.50MB secret keys and 4.54KB ciphertexts, which is more efficient than the schemes of Döttlinget al.(ASIACRYPT 2012), Kiltzet al.(PKC 2014) and Yuet al.(CRYPTO 2016) ((7.27GB, 7.24GB, 7.03KB), (80.89MB, 46.23MB, 6.80KB) and (70.95MB, 70.65MB, 86.50KB) respectively).
Abstract The rapid progress of quantum computing threatens widely deployed public-key cryptosystems such as RSA and Diffie–Hellman, accelerating the transition toward post-quantum cryptography (PQC). During this migration, hybrid key encapsulation mechanisms (KEMs) that combine classical and post-quantum primitives are strongly recommended by standardization bodies and cybersecurity agencies. However, existing hybrid designs mainly focus on combining post-quantum KEMs with Diffie–Hellman–style constructions, while the systematic integration of standardized classical public-key encryption (PKE) schemes with post-quantum KEMs remains largely unexplored. In this work, we introduce two generic hybrid constructions, and , that combine a classical PKE scheme with a post-quantum KEM satisfying ciphertext second-preimage resistance (C2PRI). We prove that both constructions achieve IND-CCA security in the standard model. The refined construction additionally relies on a new security notion of the classical PKE scheme, termed partial ciphertext second-preimage resistance (PC2PRI), which captures second-preimage resistance when a designated ciphertext component is fixed. This new property enables shared-key derivation from only a designated PKE ciphertext component in . Finally, we provide a systematic analysis of the PC2PRI property for several standardized classical encryption schemes, including ECIES, PSEC, and SM2.
Large-scale quantum computers capable of implementing Shor's algorithm pose a significant threat to the security of the most widely used public-key cryptographic schemes. This risk has motivated substantial efforts by standards bodies and government agencies to identify and standardize quantum-safe cryptographic systems. Among the proposed solutions, lattice-based cryptography has emerged as the foundation for some of the most promising protocols. This paper describes FrodoKEM, a family of conservative key-encapsulation mechanisms (KEMs) whose security is based on generic, “unstructured” lattices. FrodoKEM is proposed as an alternative to the more efficient lattice schemes that utilize algebraically structured lattices, such as the recently standardized ML-KEM scheme. By relying on generic lattices, FrodoKEM minimizes the potential for future attacks that exploit algebraic structures while enabling simple and compact implementations. Our plain C implementations demonstrate that, despite its conservative design and parameterization, FrodoKEM remains practical. For instance, the full protocol at NIST security level 1 runs in approximately 0.97 ms on a server-class processor, and 4.98 ms on a smartphone-class processor. FrodoKEM obtains (single-target) IND-CCA security using a variant of the Fujisaki-Okamoto transform, applied to an underlying public-key encryption scheme called FrodoPKE. In addition, using a new tool called the Salted Fujisaki-Okamoto (SFO) transform, FrodoKEM is also shown to tightly achieve multi-target security, without increasing the FrodoPKE message length and with a negligible performance impact, based on the multi-target IND-CPA security of FrodoPKE.
Driven by advances in the standardization of NIST’s Post-Quantum Cryptography (PQC) algorithms, research on constructing Password Authenticated Key Exchange (PAKE) protocols using Key Encapsulation Mechanisms (KEMs) has gained considerable attention. Several PAKE protocols have established precise security requirements for the underlying KEM. Arriaga et al. introduced a PAKE protocol called CHIC, which requires the KEM to achieve anonymity under plaintext-checkable attacks (ANO-1PCA). An anonymous KEM does not leak any information about which public key was used for encryption. It protects the identities and privacy of participants and is critical in preventing identity-guessing attacks, therefore, anonymity is also called key-privacy. The anonymity of NIST PQC Round-3 candidates has recently been analyzed, some of which satisfied ANO-CCA.Huguenin-Dumittan and Vaudenay proposed two efficient constructions, TCHand TH, to create KEM from public-key encryption (PKE) schemes. Jiang et al. introduced TRHbased on TH. These constructions can transform any OW-CPA PKE into an IND-qCCA KEM efficiently and avoid re-encryption. However, prior to this work, no research has been conducted to determine whether these constructions preserve or lift anonymity.In this paper, we proved that for any OW-CPA, DS-IND PKE, the construction KEMRH= TRH[PKE,H] achieves ANO1-CCA in the quantum random oracle model (QROM). We then construct a KEM called KyberRH, and provide an algorithm for the CHIC protocol using KyberRH.