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

arXiv:2102.02243

Information-theoretic Key Encapsulation and its Applications

Setareh Sharifian, Reihaneh Safavi–Naini

Published Feb 3, 2021• 0 citations
arXivHTMLPDF

Abstract

A hybrid encryption scheme is a public-key encryption system that consists of a public-key part called the key encapsulation mechanism (KEM), and a (symmetric) secret-key part called data encapsulation mechanism (DEM): the public-key part is used to generate a shared secret key between two parties, and the symmetric key part is used to encrypt the message using the generated key. Hybrid encryption schemes are widely used for secure communication over the Internet. In this paper, we initiate the study of hybrid encryption in preprocessing model which assumes access to initial correlated variables by all parties (including the eavesdropper). We define information-theoretic KEM (iKEM) that, together with a (computationally) secure DEM, results in a hybrid encryption scheme in preprocessing model. We define the security of each building block, and prove a composition theorem that guarantees (computational) qe-chosen plaintext (CPA) security of the hybrid encryption system if the iKEM and the DEM satisfy qe-chosen encapculation attack and one-time security, respectively. We show that iKEM can be realized by a one-way SKA (OW-SKA) protocol with a revised security definition. Using an OW-SKA that satisfies this revised definition of security effectively allows the secret key that is generated by the OW-SKA to be used with a one-time symmetric key encryption system such as XORing a pseudorandom string with the message, and provide qe-CPA security for the hybrid encryption system.We discuss our results and directions for future work.

DOI
10.48550/arxiv.2102.02243

Related papers

Information-theoretic Key Encapsulation and its Application to Secure Communication

Setareh Sharifian, Reihaneh Safavi–Naini

A hybrid encryption scheme consists of a public-key part called the key encapsulation mechanism (KEM), that is used to generate and establish a shared secret key between two parties, and a (symmetric) secret-key part called the data encapsulation mechanism (DEM) that encrypts the data using the shared key. Hybrid encryption schemes are widely used for securing Internet communication. In this paper, we initiate the study of hybrid encryption in preprocessing model which assumes access to initial correlated variables by all parties (including the eavesdropper), and define information-theoretic KEM (iKEM) that together with a (computationally) secure DEM, results in a hybrid encryption scheme in preprocessing model. We define security of each building block, and prove a composition theorem that guarantees (computational) q-chosen-plaintext attack (CPA) security of the hybrid encryption system if the iKEM and the DEM satisfy q-chosen-encapsulation attack security and one-time security, respectively. We show that an iKEM can be realized by an information-theoretic one-way secret key agreement (OW-SKA) protocol where a single message is transmitted from Alice to Bob, with a new security definition that allows$q$queries to Alice. Using a OW-SKA that satisfies this new definition of security, effectively allows the established secret key to be used with a onetime symmetric key encryption system that can be implemented, for example, by XORing the output of a (computationally) secure pseudorandom generator with the message, to provide secure encryption of$q$arbitrary messages (polynomially bounded length). We discuss our results and directions for future work.

IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•6 citations

Hybrid Encryption in Correlated Randomness Model

Reihaneh Safavi–Naini, Setareh Sharifian

A hybrid encryption scheme uses a key encapsulation mechanism (KEM) to generate and establish a shared secret key with the decrypter, and a secret key data encapsulation mechanism (DEM) to encrypt the data using the key that is established by the DEM. The decrypter recovers the key using the ciphertext that is generated by the KEM, and uses it to decrypt the ciphertext that is generated by the DEM.We motivate and propose hybrid encryption in correlated randomness model where all participants including the eavesdropper, have access to samples of their respective correlated random variables. We define information-theoretic KEM (iKEM), and prove a composition theorem for iKEM and DEM that allows us to construct an efficient hybrid encryption system in correlated randomness model, providing post-quantum security. The construction uses an information-theoretic one-way secret key agreement (OW-SKA) protocol that satisfies a new security definition, and a one-time symmetric key encryption system that can be implemented by XORing the output of a (computationally) secure pseudorandom generator with the message. We discuss our results and directions for future work.

IEEE Information Theory Workshop (ITW)•Oct 17, 2021•1 citation

CCA-Secure Hybrid Encryption in Correlated Randomness Model and KEM Combiners

Somnath Panja, Setareh Sharifian, Shaoquan Jiang +1 more

A hybrid encryption (HE) system is an efficient public key encryption system for arbitrarily long messages. An HE system consists of a public key component called key encapsulation mechanism (KEM), and a symmetric key component called data encapsulation mechanism (DEM). The HE encryption algorithm uses a KEM generated key k to encapsulate the message using DEM, and send the ciphertext together with the encapsulaton of k, to the decryptor who decapsulates k and uses it to decapsulate the message using the corresponding KEM and DEM components. The KEM/DEM composition theorem proves that if KEM and DEM satisfy well-defined security notions, then HE will be secure with well defined security. We introduce HE in correlated randomness model where the encryption and decryption algorithms have samples of correlated random variables that are partially leaked to the adversary. Security of the new KEM/DEM paradigm is defined against computationally unbounded or polynomially bounded adversaries. We define iKEM and cKEM with respective information theoretic computational security, and prove a composition theorem for them and a computationally secure DEM, resulting in secure HEs with proved computational security (CPA and CCA) and without any computational assumption. We construct two iKEMs that provably satisfy the required security notions of the composition theorem. The iKEMs are used to construct two efficient quantum-resistant HEs when used with an AES based DEM. We also define and construct combiners with proved security that combine the new KEM/DEM paradigm of HE with the traditional public key based paradigm of HE.

arXiv:2401.00983•Jan 2, 2024•1 citation

Secure Composition of Quantum Key Distribution and Symmetric Key Encryption

Kunal Dey, Reihaneh Safavi–Naini

Quantum key distribution (QKD) allows Alice and Bob to share a secret key with proven information-theoretic security. Composability-based security proofs for QKD ensure that using the established key to encrypt a message using a one-time-pad encryption system, will result in information-theoretic secrecy for the communication. In this paper, we consider the problem of using a QKD established key with a secure symmetrickey based encryption system with computational security, and use an extension of the framework of hybrid encryption to prove security of the composition. We use an extension of the original framework of hybrid encryption to correlated randomness setting (Sharifian et al. in ISIT 2021) and propose a quantum-enabled Key Encapsulation Mechanism (qKEM) that is used to construct a quantum-enabled hybrid encryption ($q H E$) system, and prove a composition theorem for the security of the qHE. We construct a qKEM with proven security using an existing QKD (Portmann et al. in Rev. of Mod. Physics 2022). Using this qKEM with a secure Data Encapsulation Mechanism (DEM), that can be constructed using a one-time symmetric key encryption scheme, results in an efficient encryption scheme for unrestricted length messages with proved security against an adversary with access to (efficient) quantum computations. Thus a key-efficient post-quantum secure encryption with proved security and without using any computational assumptions.

arXiv:2501.08435•IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•4 citations

Secure Cryptographic Workflow in the Standard Model.

Manuel Barbosa, Pooya Farshim

Abstract. Following the work of Al-Riyami et al. we define the notion of key encapsulation mechanism supporting cryptographic workflow (WF-KEM) and prove a KEM-DEM composition theorem which extends the notion of hybrid encryption to cryptographic workflow. We then generically construct a WF-KEM from an identity-based encryption (IBE) scheme and a secret sharing scheme. Chosen ciphertext security is achieved using one-time signatures. Adding a public-key encryption scheme we are able to modify the construction to obtain escrow-freeness. We prove all our constructions secure in the standard model. Keywords. Cryptographic Workflow. Key Encapsulation. Secret Sharing. Identity-Based Encryption.

•Jan 1, 2006•0 citations

Chosen-Ciphertext Secure Fuzzy Identity-Based Key Encapsulation without ROM.

Liming Fang, Jiandong Wang, Yongjun Ren +2 more

Abstract. We use hybrid encryption with Fuzzy Identity-Based Encryption (Fuzzy-IBE) schemes, and present the first and efficient fuzzy identity-based key encapsulation mechanism (Fuzzy-IB-KEM) schemes which are chosen-ciphertext secure (CCA) without random oracle in the selective-ID model. To achieve these goals, we consider Fuzzy-IBE schemes as consisting of separate key and data encapsulation mechanisms (KEM-DEM), and then give the definition of Fuzzy-IB-KEM. Our main idea is to enhance Sahai and Waters ' "large universe " construction, chosen-plaintext secure (CPA) Fuzzy-IBE, by adding some redundant information to the ciphertext to make it CCA-secure.

•Jan 1, 2008•5 citations
A hybrid encryption scheme is a public-key encryption system that consists of a public-key part called the key encapsulation mechanism (KEM), and a (symmetric) secret-key part called data encapsulation mechanism (DEM): the public-key part is used to generate a shared secret key between two parties, and the symmetric key part is used to encrypt the message using the generated key. Hybrid encryption schemes are widely used for secure communication over the Internet. In this paper, we initiate the study of hybrid encryption in preprocessing model which assumes access to initial correlated variables by all parties (including the eavesdropper). We define information-theoretic KEM (iKEM) that, together with a (computationally) secure DEM, results in a hybrid encryption scheme in preprocessing model. We define the security of each building block, and prove a composition theorem that guarantees (computational) qe-chosen plaintext (CPA) security of the hybrid encryption system if the iKEM and the DEM satisfy qe-chosen encapculation attack and one-time security, respectively. We show that iKEM can be realized by a one-way SKA (OW-SKA) protocol with a revised security definition. Using an OW-SKA that satisfies this revised definition of security effectively allows the secret key that is generated by the OW-SKA to be used with a one-time symmetric key encryption system such as XORing a pseudorandom string with the message, and provide qe-CPA security for the hybrid encryption system.We discuss our results and directions for future work.
A hybrid encryption scheme consists of a public-key part called the key encapsulation mechanism (KEM), that is used to generate and establish a shared secret key between two parties, and a (symmetric) secret-key part called the data encapsulation mechanism (DEM) that encrypts the data using the shared key. Hybrid encryption schemes are widely used for securing Internet communication. In this paper, we initiate the study of hybrid encryption in preprocessing model which assumes access to initial correlated variables by all parties (including the eavesdropper), and define information-theoretic KEM (iKEM) that together with a (computationally) secure DEM, results in a hybrid encryption scheme in preprocessing model. We define security of each building block, and prove a composition theorem that guarantees (computational) q-chosen-plaintext attack (CPA) security of the hybrid encryption system if the iKEM and the DEM satisfy q-chosen-encapsulation attack security and one-time security, respectively. We show that an iKEM can be realized by an information-theoretic one-way secret key agreement (OW-SKA) protocol where a single message is transmitted from Alice to Bob, with a new security definition that allowsqqqqueries to Alice. Using a OW-SKA that satisfies this new definition of security, effectively allows the established secret key to be used with a onetime symmetric key encryption system that can be implemented, for example, by XORing the output of a (computationally) secure pseudorandom generator with the message, to provide secure encryption ofqqqarbitrary messages (polynomially bounded length). We discuss our results and directions for future work.
A hybrid encryption scheme uses a key encapsulation mechanism (KEM) to generate and establish a shared secret key with the decrypter, and a secret key data encapsulation mechanism (DEM) to encrypt the data using the key that is established by the DEM. The decrypter recovers the key using the ciphertext that is generated by the KEM, and uses it to decrypt the ciphertext that is generated by the DEM.We motivate and propose hybrid encryption in correlated randomness model where all participants including the eavesdropper, have access to samples of their respective correlated random variables. We define information-theoretic KEM (iKEM), and prove a composition theorem for iKEM and DEM that allows us to construct an efficient hybrid encryption system in correlated randomness model, providing post-quantum security. The construction uses an information-theoretic one-way secret key agreement (OW-SKA) protocol that satisfies a new security definition, and a one-time symmetric key encryption system that can be implemented by XORing the output of a (computationally) secure pseudorandom generator with the message. We discuss our results and directions for future work.
A hybrid encryption (HE) system is an efficient public key encryption system for arbitrarily long messages. An HE system consists of a public key component called key encapsulation mechanism (KEM), and a symmetric key component called data encapsulation mechanism (DEM). The HE encryption algorithm uses a KEM generated key k to encapsulate the message using DEM, and send the ciphertext together with the encapsulaton of k, to the decryptor who decapsulates k and uses it to decapsulate the message using the corresponding KEM and DEM components. The KEM/DEM composition theorem proves that if KEM and DEM satisfy well-defined security notions, then HE will be secure with well defined security. We introduce HE in correlated randomness model where the encryption and decryption algorithms have samples of correlated random variables that are partially leaked to the adversary. Security of the new KEM/DEM paradigm is defined against computationally unbounded or polynomially bounded adversaries. We define iKEM and cKEM with respective information theoretic computational security, and prove a composition theorem for them and a computationally secure DEM, resulting in secure HEs with proved computational security (CPA and CCA) and without any computational assumption. We construct two iKEMs that provably satisfy the required security notions of the composition theorem. The iKEMs are used to construct two efficient quantum-resistant HEs when used with an AES based DEM. We also define and construct combiners with proved security that combine the new KEM/DEM paradigm of HE with the traditional public key based paradigm of HE.
Quantum key distribution (QKD) allows Alice and Bob to share a secret key with proven information-theoretic security. Composability-based security proofs for QKD ensure that using the established key to encrypt a message using a one-time-pad encryption system, will result in information-theoretic secrecy for the communication. In this paper, we consider the problem of using a QKD established key with a secure symmetrickey based encryption system with computational security, and use an extension of the framework of hybrid encryption to prove security of the composition. We use an extension of the original framework of hybrid encryption to correlated randomness setting (Sharifian et al. in ISIT 2021) and propose a quantum-enabled Key Encapsulation Mechanism (qKEM) that is used to construct a quantum-enabled hybrid encryption (qHEq H EqHE) system, and prove a composition theorem for the security of the qHE. We construct a qKEM with proven security using an existing QKD (Portmann et al. in Rev. of Mod. Physics 2022). Using this qKEM with a secure Data Encapsulation Mechanism (DEM), that can be constructed using a one-time symmetric key encryption scheme, results in an efficient encryption scheme for unrestricted length messages with proved security against an adversary with access to (efficient) quantum computations. Thus a key-efficient post-quantum secure encryption with proved security and without using any computational assumptions.
Abstract. Following the work of Al-Riyami et al. we define the notion of key encapsulation mechanism supporting cryptographic workflow (WF-KEM) and prove a KEM-DEM composition theorem which extends the notion of hybrid encryption to cryptographic workflow. We then generically construct a WF-KEM from an identity-based encryption (IBE) scheme and a secret sharing scheme. Chosen ciphertext security is achieved using one-time signatures. Adding a public-key encryption scheme we are able to modify the construction to obtain escrow-freeness. We prove all our constructions secure in the standard model. Keywords. Cryptographic Workflow. Key Encapsulation. Secret Sharing. Identity-Based Encryption.
Abstract. We use hybrid encryption with Fuzzy Identity-Based Encryption (Fuzzy-IBE) schemes, and present the first and efficient fuzzy identity-based key encapsulation mechanism (Fuzzy-IB-KEM) schemes which are chosen-ciphertext secure (CCA) without random oracle in the selective-ID model. To achieve these goals, we consider Fuzzy-IBE schemes as consisting of separate key and data encapsulation mechanisms (KEM-DEM), and then give the definition of Fuzzy-IB-KEM. Our main idea is to enhance Sahai and Waters ' "large universe " construction, chosen-plaintext secure (CPA) Fuzzy-IBE, by adding some redundant information to the ciphertext to make it CCA-secure.