Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM SIGSAC Conference on Computer and Communications Security (CCS)

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

Published Dec 2, 2024• 29 citations
Publisher

Abstract

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.

DOI
10.1145/3658644.3670283

Related papers

Post-Quantum Hybrid Encryption from Correlated Randomness: QKEM and Biometric KEMs

Reihaneh Safavi–Naini

The Key Encapsulation Mechanism (KEM) is a widely used public-key cryptographic primitive that has evolved into numerous variants and found diverse applications in recent years. In this talk, we explore KEMs in the setting of correlated randomness, where Alice and Bob, instead of using public keys, have access to correlated samples from a shared random source.

•Oct 13, 2025•0 citations

Hybrid KEM constructions from classical PKEs and post-quantum KEMs

Bo Zhou, Yukai Zhang, Haodong Jiang +1 more

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.

Cybersecurity•Oct 28, 2026•0 citations

A Secure Key Encapsulation Mechanism in Quantum Hybrid Settings

Brian Goncalves

Quantum computers pose a long-term threat to many currently used cryptographic schemes as they are able to efficiently solve the computational problems those schemes are based on. This threat has lead to research into quantum-resistant cryptographic schemes to eventually replace those currently used, as well as research into how to ease the transition from classical schemes to quantum-resistant ones. One approach to address these issues is to use a combiner that creates hybrid schemes, that is schemes which are classically and quantum-resistant, to protect against quantum attacks and maintain current security guarantees. Such combiners are used as a way to provide trust from different schemes and their differing computational difficulty assumptions rather than a single scheme. which may later become vulnerable. An important type of scheme that must be secure against both classical and quantum attacks are key encapsulation mechanisms (KEMs), as they are commonly used for constructing public-key encryption and key exchange protocols. We first define new security notions for KEMs modeling attackers of various levels of quantum power ranging from fully classical to fully quantum. We then construct a combiner that creates hybrid schemes for key encapsulation mechanisms which is secure against adversaries with varying levels of quantum power over time and can be implemented efficiently. Our construction provides an efficient method to combine KEMs using an additional scheme. This construction is also general enough that it can be implemented in settings such as key exchange protocols, like those used in the Transport Layer Security (TLS) protocol for web browsers, without affecting existing structure meaningfully.

•Jan 1, 2018•0 citations

Post-Quantum Anonymity of Key Encapsulation Mechanism and Its Applications in Password Authenticated Key Exchange Protocols

JiaYv An, Yankun Gao, Lei Han

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.

IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom)•Nov 14, 2025•1 citation

Hybrid Key Encapsulation Mechanisms

Goncalves, Brian

Quantum computers pose a long-term threat to many currently used cryptographic schemes as they are able to efficiently solve the computational problems those schemes are based on. This threat has lead to research into quantum-resistant cryptographic schemes to eventually replace those currently used, as well as research into how to ease the transition from classical schemes to quantum-resistant ones. One approach to address these issues is to use a combiner that creates hybrid schemes, that is schemes which are classically and quantum-resistant, to protect against quantum attacks and maintain current security guarantees. Such combiners are used as a way to provide trust from different schemes and their differing computational difficulty assumptions rather than a single scheme. which may later become vulnerable. An important type of scheme that must be secure against both classical and quantum attacks are key encapsulation mechanisms (KEMs), as they are commonly used for constructing public-key encryption and key exchange protocols. We first define new security notions for KEMs modeling attackers of various levels of quantum power ranging from fully classical to fully quantum. We then construct a combiner that creates hybrid schemes for key encapsulation mechanisms which is secure against adversaries with varying levels of quantum power over time and can be implemented efficiently. Our construction provides an efficient method to combine KEMs using an additional scheme. This construction is also general enough that it can be implemented in settings such as key exchange protocols, like those used in the Transport Layer Security (TLS) protocol for web browsers, without affecting existing structure meaningfully.

•Jan 1, 2018•0 citations

Lattice-based Key-sharing Schemes: A Survey

Prasanna Ravi, James Howe, Anupam Chattopadhyay +1 more

Public-key cryptography is an indispensable component used in almost all of our present-day digital infrastructure. However, most if not all of it is predominantly built upon hardness guarantees of number theoretic problems that can be broken by large-scale quantum computers in the future. Sensing the imminent threat from continued advances in quantum computing, NIST has recently initiated a global-level standardization process for quantum resistant public-key cryptographic primitives such as public-key encryption, digital signatures, and key encapsulation mechanisms. While the process received proposals from various categories of post-quantum cryptography, lattice-based cryptography features most prominently among all the submissions. Lattice-based cryptography offers a very attractive alternative to traditional public-key cryptography mainly due to the variety of lattice-based schemes offering varying flavors of security and efficiency guarantees. In this article, we survey the evolution of lattice-based key-sharing schemes (public-key encryption and key encapsulation schemes) and cover various aspects ranging from theoretical security guarantees, general algorithmic frameworks, practical implementation aspects, and physical attack security, with special focus on lattice-based key-sharing schemes competing in the NIST’s standardization process.

ACM Computing Surveys•Jan 2, 2021•40 citations
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.
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.
Quantum computers pose a long-term threat to many currently used cryptographic schemes as they are able to efficiently solve the computational problems those schemes are based on. This threat has lead to research into quantum-resistant cryptographic schemes to eventually replace those currently used, as well as research into how to ease the transition from classical schemes to quantum-resistant ones. One approach to address these issues is to use a combiner that creates hybrid schemes, that is schemes which are classically and quantum-resistant, to protect against quantum attacks and maintain current security guarantees. Such combiners are used as a way to provide trust from different schemes and their differing computational difficulty assumptions rather than a single scheme. which may later become vulnerable. An important type of scheme that must be secure against both classical and quantum attacks are key encapsulation mechanisms (KEMs), as they are commonly used for constructing public-key encryption and key exchange protocols. We first define new security notions for KEMs modeling attackers of various levels of quantum power ranging from fully classical to fully quantum. We then construct a combiner that creates hybrid schemes for key encapsulation mechanisms which is secure against adversaries with varying levels of quantum power over time and can be implemented efficiently. Our construction provides an efficient method to combine KEMs using an additional scheme. This construction is also general enough that it can be implemented in settings such as key exchange protocols, like those used in the Transport Layer Security (TLS) protocol for web browsers, without affecting existing structure meaningfully.
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.
Quantum computers pose a long-term threat to many currently used cryptographic schemes as they are able to efficiently solve the computational problems those schemes are based on. This threat has lead to research into quantum-resistant cryptographic schemes to eventually replace those currently used, as well as research into how to ease the transition from classical schemes to quantum-resistant ones. One approach to address these issues is to use a combiner that creates hybrid schemes, that is schemes which are classically and quantum-resistant, to protect against quantum attacks and maintain current security guarantees. Such combiners are used as a way to provide trust from different schemes and their differing computational difficulty assumptions rather than a single scheme. which may later become vulnerable. An important type of scheme that must be secure against both classical and quantum attacks are key encapsulation mechanisms (KEMs), as they are commonly used for constructing public-key encryption and key exchange protocols. We first define new security notions for KEMs modeling attackers of various levels of quantum power ranging from fully classical to fully quantum. We then construct a combiner that creates hybrid schemes for key encapsulation mechanisms which is secure against adversaries with varying levels of quantum power over time and can be implemented efficiently. Our construction provides an efficient method to combine KEMs using an additional scheme. This construction is also general enough that it can be implemented in settings such as key exchange protocols, like those used in the Transport Layer Security (TLS) protocol for web browsers, without affecting existing structure meaningfully.
Public-key cryptography is an indispensable component used in almost all of our present-day digital infrastructure. However, most if not all of it is predominantly built upon hardness guarantees of number theoretic problems that can be broken by large-scale quantum computers in the future. Sensing the imminent threat from continued advances in quantum computing, NIST has recently initiated a global-level standardization process for quantum resistant public-key cryptographic primitives such as public-key encryption, digital signatures, and key encapsulation mechanisms. While the process received proposals from various categories of post-quantum cryptography, lattice-based cryptography features most prominently among all the submissions. Lattice-based cryptography offers a very attractive alternative to traditional public-key cryptography mainly due to the variety of lattice-based schemes offering varying flavors of security and efficiency guarantees. In this article, we survey the evolution of lattice-based key-sharing schemes (public-key encryption and key encapsulation schemes) and cover various aspects ranging from theoretical security guarantees, general algorithmic frameworks, practical implementation aspects, and physical attack security, with special focus on lattice-based key-sharing schemes competing in the NIST’s standardization process.