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:2601.10542 · IEEE International Symposium on Information Theory (ISIT)

Hybrid Encryption with Certified Deletion in Preprocessing Model

Kunal Dey, Reihaneh Safavi–Naini

Published Jun 1, 2026• 1 citation
arXivHTMLPDF

Abstract

Certified deletion allows Alice to outsource data to Bob and, at a later time, obtain a verifiable guarantee that the file has been irreversibly deleted at her request. This functionality, while impossible using classical information alone, can be achieved using quantum information. Existing approaches rely either on one-time pad (OTP) encryption or on computational hardness assumptions that may be vulnerable to future advances in classical or quantum computing. In this work, we introduce and formalize hybrid encryption with certified deletion in the preprocessing model (pHE-CD) and propose two constructions. Each construction composes an information-theoretic key encapsulation mechanism (iKEM) with a data encapsulation mechanism that provides certified deletion (DEM-CD) security, offering different security guarantees depending on the properties of DEM-CD. When DEM-CD is one-time information-theoretically secure, the composition provides information-theoretic security for both encryption and certified deletion. When DEM-CD is computationally secure, the composed construction provides computationally secure (post-quantum) encryption and everlasting certified deletion, where confidentiality is computational until the deletion certificate is successfully verified. After successful verification, confidentiality becomes unconditional. That is, successful verification of the deletion certificate guarantees that the data has been removed information-theoretically from the adversary's view. Both pHE-CD constructions support the encryption of arbitrarily long messages. Construction 2 is key-efficient and uses a DEM-CD built from quantum coding and AES, providing quantum-safe security for encryption. We conclude by discussing the implications of our results and directions for future research.

DOI
10.1109/isit62367.2026.11653785

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

Semi-Quantum Cryptography with Certified Deletion

Yael Tauman Kalai, Justin Raizes

Certified deletion allows a client to upload encrypted data to a server as a quantum state, then later request that the server delete their data and detect whether the server complies. If verification passes, then the data on the server will remain hidden even if the decryption key is later leaked. In publicly verifiable certified deletion, the verification key is published so that anyone may check for deletion compliance. In this work, we give a general compiler to publicly verifiable certified deletion that allows the client to initially upload the *quantum* ciphertext using purely *classical* communication, assuming the post-quantum hardness of LWE in the plain model. Our approach can be applied to a wide variety of primitives, including commitments and public-key, attribute-based, identity-based, and fully-homomorphic encryption. Moreover, our constructions allow the client to classically manage the encrypted data beyond just verifying its deletion. The classical client may non-destructively audit the ciphertext via a Proof of No Intrusion to check whether it has been leaked to a third party. The classical client may also retrieve the data while simultaneously verifying its deletion from the server. Thus, they do not have to choose between retrieving the data and protecting it against future key leakage. As our core technical contribution, we give a classical-communication protocol and simulation technique that allows adapting purification-based security arguments for BB84-style states which are prepared through classical interaction. It makes the required purification available in a hybrid experiment, despite the classical transcript uniquely determining the prepared state in a real execution.

cs.CRCross-listedarXiv:2609.38915•Oct 1, 2026•0 citations

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

Information-theoretic Key Encapsulation and its Applications

Setareh Sharifian, Reihaneh Safavi–Naini

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.

arXiv:2102.02243•Feb 3, 2021•0 citations

Registered Attribute-Based Encryption with Publicly Verifiable Certified Deletion, Everlasting Security, and More

Shayeef Murshid, Ramprasad Sarkar, Mriganka Mandal

Certified deletion ensures that encrypted data can be irreversibly deleted, preventing future recovery even if decryption keys are later exposed. Although existing works have achieved certified deletion across various cryptographic primitives, they rely on central authorities, leading to inherent escrow vulnerabilities. This raises the question of whether certified deletion can be achieved in decentralized frameworks such as Registered Attribute-Based Encryption (RABE) that combines fine-grained access control with user-controlled key registration. This paper presents the first RABE schemes supporting certified deletion and certified everlasting security. Specifically, we obtain the following: - We first design a privately verifiable RABE with Certified Deletion (RABE-CD) scheme by combining our newly proposed shadow registered ABE (Shad-RABE) with one-time symmetric key encryption with certified deletion. - We then construct a publicly verifiable RABE-CD scheme using Shad-RABE, witness encryption, and one-shot signatures, allowing any party to validate deletion certificates without accessing secret keys. - We also extend to privately verifiable RABE with Certified Everlasting Deletion (RABE-CED) scheme, integrating quantum-secure RABE with the certified everlasting lemma. Once a certificate is produced, message privacy becomes information-theoretic even against unbounded adversaries. -We finally realize a publicly verifiable RABE-CED scheme by employing digital signatures for the BB84 states, allowing universal verification while ensuring that deletion irreversibly destroys information relevant to decryption.

arXiv:2603.07646•Mar 8, 2026•0 citations

Quantum Encryption with Certified Deletion

Islam, Rabib

In the context of classical information, every message is composed of 0s and 1s; these messages can generally be copied at will. However, when quantum phenomena are used to model information, this guarantee no longer exists. This difference gives rise to a range of cryptographic possibilities when one considers encoding certain messages as quantum information. In our case, we analyze a potential benefit of encoding part of an encryption scheme’s ciphertext as quantum information. We call this type of ciphertext a quantum ciphertext. In particular, quantum ciphertexts are useful when one wants to be able to prove the deletion of the plaintext underlying a ciphertext. Since classical ciphertexts can be copied, clearly such feat is impossible using classical information alone. However, we show that quantum encodings allow such certified deletion. More precisely, we show that it is possible to encrypt classical data into a quantum ciphertext such that the recipient of the ciphertext can produce a classical string which proves to the originator that the recipient has relinquished any chance of recovering the plaintext, should the decryption key be revealed. Our scheme is feasible with current quantum technology: the honest parties only require quantum devices for single-qubit preparation and measurements, and the scheme is robust against noise in these devices. Furthermore, we provide a proof of security which requires only a finite amount of communication, and which therefore avoids the common technique of relying on the analysis of an asymptotic case.

•Jan 20, 2020•39 citations
Certified deletion allows Alice to outsource data to Bob and, at a later time, obtain a verifiable guarantee that the file has been irreversibly deleted at her request. This functionality, while impossible using classical information alone, can be achieved using quantum information. Existing approaches rely either on one-time pad (OTP) encryption or on computational hardness assumptions that may be vulnerable to future advances in classical or quantum computing. In this work, we introduce and formalize hybrid encryption with certified deletion in the preprocessing model (pHE-CD) and propose two constructions. Each construction composes an information-theoretic key encapsulation mechanism (iKEM) with a data encapsulation mechanism that provides certified deletion (DEM-CD) security, offering different security guarantees depending on the properties of DEM-CD. When DEM-CD is one-time information-theoretically secure, the composition provides information-theoretic security for both encryption and certified deletion. When DEM-CD is computationally secure, the composed construction provides computationally secure (post-quantum) encryption and everlasting certified deletion, where confidentiality is computational until the deletion certificate is successfully verified. After successful verification, confidentiality becomes unconditional. That is, successful verification of the deletion certificate guarantees that the data has been removed information-theoretically from the adversary's view. Both pHE-CD constructions support the encryption of arbitrarily long messages. Construction 2 is key-efficient and uses a DEM-CD built from quantum coding and AES, providing quantum-safe security for encryption. We conclude by discussing the implications of our results and directions for future research.
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.
Certified deletion allows a client to upload encrypted data to a server as a quantum state, then later request that the server delete their data and detect whether the server complies. If verification passes, then the data on the server will remain hidden even if the decryption key is later leaked. In publicly verifiable certified deletion, the verification key is published so that anyone may check for deletion compliance. In this work, we give a general compiler to publicly verifiable certified deletion that allows the client to initially upload the *quantum* ciphertext using purely *classical* communication, assuming the post-quantum hardness of LWE in the plain model. Our approach can be applied to a wide variety of primitives, including commitments and public-key, attribute-based, identity-based, and fully-homomorphic encryption. Moreover, our constructions allow the client to classically manage the encrypted data beyond just verifying its deletion. The classical client may non-destructively audit the ciphertext via a Proof of No Intrusion to check whether it has been leaked to a third party. The classical client may also retrieve the data while simultaneously verifying its deletion from the server. Thus, they do not have to choose between retrieving the data and protecting it against future key leakage. As our core technical contribution, we give a classical-communication protocol and simulation technique that allows adapting purification-based security arguments for BB84-style states which are prepared through classical interaction. It makes the required purification available in a hybrid experiment, despite the classical transcript uniquely determining the prepared state in a real execution.
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.
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.
Certified deletion ensures that encrypted data can be irreversibly deleted, preventing future recovery even if decryption keys are later exposed. Although existing works have achieved certified deletion across various cryptographic primitives, they rely on central authorities, leading to inherent escrow vulnerabilities. This raises the question of whether certified deletion can be achieved in decentralized frameworks such as Registered Attribute-Based Encryption (RABE) that combines fine-grained access control with user-controlled key registration. This paper presents the first RABE schemes supporting certified deletion and certified everlasting security. Specifically, we obtain the following: - We first design a privately verifiable RABE with Certified Deletion (RABE-CD) scheme by combining our newly proposed shadow registered ABE (Shad-RABE) with one-time symmetric key encryption with certified deletion. - We then construct a publicly verifiable RABE-CD scheme using Shad-RABE, witness encryption, and one-shot signatures, allowing any party to validate deletion certificates without accessing secret keys. - We also extend to privately verifiable RABE with Certified Everlasting Deletion (RABE-CED) scheme, integrating quantum-secure RABE with the certified everlasting lemma. Once a certificate is produced, message privacy becomes information-theoretic even against unbounded adversaries. -We finally realize a publicly verifiable RABE-CED scheme by employing digital signatures for the BB84 states, allowing universal verification while ensuring that deletion irreversibly destroys information relevant to decryption.
In the context of classical information, every message is composed of 0s and 1s; these messages can generally be copied at will. However, when quantum phenomena are used to model information, this guarantee no longer exists. This difference gives rise to a range of cryptographic possibilities when one considers encoding certain messages as quantum information. In our case, we analyze a potential benefit of encoding part of an encryption scheme’s ciphertext as quantum information. We call this type of ciphertext a quantum ciphertext. In particular, quantum ciphertexts are useful when one wants to be able to prove the deletion of the plaintext underlying a ciphertext. Since classical ciphertexts can be copied, clearly such feat is impossible using classical information alone. However, we show that quantum encodings allow such certified deletion. More precisely, we show that it is possible to encrypt classical data into a quantum ciphertext such that the recipient of the ciphertext can produce a classical string which proves to the originator that the recipient has relinquished any chance of recovering the plaintext, should the decryption key be revealed. Our scheme is feasible with current quantum technology: the honest parties only require quantum devices for single-qubit preparation and measurements, and the scheme is robust against noise in these devices. Furthermore, we provide a proof of security which requires only a finite amount of communication, and which therefore avoids the common technique of relying on the analysis of an asymptotic case.