Encryption with certified deletion (CD) allows Alice to outsource data to Bob in encrypted form, and later either provide Bob with the decryption key allowing him to recover the data, or request deletion of the ciphertext, in which case, Bob can verifiably delete the ciphertext. In the latter case Boob can produce a certificate that, if valid, ensures that even revealing the key does not leak any information about the plaintext to Bob. The functionality, while impossible to realize using classical information alone can be achieved using quantum information. Encryption with CD has been proposed both in the symmetrickey setting, using a one-time pad (OTP), and in the public-key setting (PKE-CD), where Bob has a key pair that can be reused. PKE-CD uses computational hardness assumptions that are vulnerable to advances in computing.In this work, we introduce and formalize hybrid encryption with certified deletion in the preprocessing model (pHE-CD) that avoids hardness assumptions, and propose two constructions. The constructions compose an information-theoretic key encapsulation mechanism (iKEM) with a data encapsulation mechanism (DEM) that provides certified deletion (DEM-CD) security, offering different security guarantees depending on the security properties of the DEM-CD. When DEM-CD is onetime information theoretically secure, the composition provides information-theoretic security for both encryption and certified deletion. When DEM-CD is computationally secure, the pHE-CD provides computational security for encryption and everlasting security for certified deletion, which means that confidentiality is computational prior to verification of deletion certificate, and becomes information theoretic, after successful verification of certificate, guaranteeing that the data has been removed from the adversary’s view in an information-theoretic sense. The construction is key efficient and uses a DEM-CD that is constructed using quantum coding and AES, providing quantum-resistant security for encryption without using any hardness assumption. Both pHE-CD schemes are for encryption of arbitrarily long messages. We discuss our results and directions for future work.