THE QUANTUM INTELLIGENCER

Hybrid Encryption with Certified Deletion: Achieving Verifiable Data Erasure in the Quantum Preprocessing Model In Plain English: This research tackles the problem of proving that someone has truly deleted your data after you ask them to—something that can't be reliably done with today’s computers. The authors created a new encryption method that uses quantum technology to let you get a verifiable receipt confirming the data is gone for good. They combined two layers of protection: one to securely lock the data and another to verify deletion. This matters because it could lead to more trustworthy cloud storage and data-sharing systems, where users can be sure their private information isn’t kept longer than allowed—even by powerful future computers or hackers. Summary: The paper introduces and formalizes hybrid encryption with certified deletion in the preprocessing model (pHE-CD), a novel cryptographic framework enabling verifiable and irreversible deletion of outsourced data using quantum information. While classical methods cannot guarantee certified deletion due to fundamental information-theoretic limitations, quantum-based protocols make this possible. The proposed pHE-CD framework combines an information-theoretic key encapsulation mechanism (iKEM) with a data encapsulation mechanism that supports certified deletion (DEM-CD), forming a two-layer hybrid encryption scheme. Two constructions are presented: the first provides information-theoretic certified deletion, ensuring both confidentiality and deletion guarantees hold against computationally unbounded adversaries; the second offers everlasting certified deletion, where confidentiality is initially computational but becomes information-theoretically secure upon successful verification of deletion. The schemes achieve IND-$q_e$-CPA security and support encryption of arbitrarily long messages. By employing a quantum-safe DEM-CD based on quantum coding and AES, the second construction achieves quantum-resistant security with significantly shorter keys than the message length. The paper leaves as future work the instantiation of the framework using quantum-enabled KEMs (qKEMs). This approach enhances practicality and scalability while maintaining strong security in anticipation of quantum computing threats. Key Points: - Certified deletion enables a data owner to verify that outsourced data has been irreversibly erased. - Classical information alone cannot achieve certified deletion - quantum information is required. - The pHE-CD framework combines iKEM and DEM-CD to enable hybrid encryption with certified deletion. - Two security models are introduced: information-theoretic certified deletion and everlasting certified deletion. - Information-theoretic certified deletion provides security even against computationally unbounded adversaries. - Everlasting certified deletion upgrades confidentiality to information-theoretic secrecy after deletion verification. - The constructions achieve IND-$q_e$-CPA security and support arbitrarily long messages. - Quantum-safe DEM-CD using quantum coding and AES allows for compact, future-proof encryption keys. - The framework is designed for the preprocessing model, which assumes a trusted setup phase. - Instantiation with quantum-enabled KEMs (qKEM) is left for future research. Notable Quotes: - "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." - "The functionality, while impossible using classical information alone, can be achieved using quantum information." - "Our pHE-CD schemes provide IND-$q_e$-CPA notion of security and support encryption of arbitrarily long messages." - "Upon successful verification of the deletion certificate, the message becomes information-theoretically hidden from an adversary that is computationally unbounded." Data Points: - The paper does not include specific dates, numerical metrics, or experimental results in the abstract - however, it references formal security notions such as IND-$q_e$-CPA and mentions support for encryption of arbitrarily long messages. The use of AES in conjunction with quantum coding is noted as part of the quantum-safe DEM-CD construction. The term 'qKEM' is referenced as a future direction for instantiation. Controversial Claims: - The claim that certified deletion is impossible using classical information alone rests on specific cryptographic assumptions and may be challenged if new models of verifiable computation or trusted hardware emerge. Additionally, the reliance on the preprocessing model assumes a trusted setup phase, which may not be feasible in all real-world environments and could be seen as a limitation. The assertion that everlasting certified deletion upgrades to information-theoretic security post-deletion depends on the integrity of quantum measurements and may be questioned under adversarial physical conditions or side-channel attacks. Technical Terms: - certified deletion, hybrid encryption, preprocessing model, pHE-CD, information-theoretic security, everlasting security, key encapsulation mechanism (KEM), data encapsulation mechanism (DEM), iKEM, DEM-CD, IND-$q_e$-CPA, quantum information, quantum-safe cryptography, quantum coding, one-time pad (OTP), computationally unbounded adversary, verifiable deletion, quantum-enabled KEM (qKEM), post-quantum security —Ada H. Pemberley Dispatch from The Prepared E0