An Efficient Quantum Coding for Certified Deletion, and its Applications.*

When you delete a file from Google Drive, can you be confident that no copy remains with the company? While this poses an insurmountable challenge for classical (digital) information, quantum technology can provide an attractive solution. Certified deletion is a property of cryptographic systems that guarantees to a user that their data has been permanently erased.

Certified deletion of digital data for symmetric key encryption (SKECD) systems was proposed by Broadbent and Islam (TCC 2020) and later extended to public-key encryption systems (PKECD). SKECD and PKECD  allow the encryptor to verify if their request for deletion of a delegated ciphertext is honored, and provide an important security property that is only achievable quantumly. We consider the desirable case where the certificate of deletion is a classical bit string, while the ciphertext can have classical and quantum components. In all existing schemes, the latter component is constructed using conjugate coding. The schemes, however, have differences in terms of deletion security model and assumptions (information theoretic or everlasting, and with or without QROM assumption), as well as quantum communication channel (noisy or noiseless).

In our work, we consider ciphertext efficiency when the quantum channel is noiseless, and propose a new quantum coding scheme called Quantum Polynomial Encoding (QPE) and an accompanying security theorem when part of the QPE codeword is hidden from the adversary, which leads to a new general construction of a  PKECD with everlasting certified deletion security from any quantum encryption scheme that satisfies a certain quantum indistinguishability property.

The PKECD ciphertext has only a quantum component with constant expansion rate  (the ratio of the message length in bits to the ciphertext length in qubits is a constant). The best-known comparable result is for the PKECD construction of Bartusek et al. (Crypto 2023) that has an expansion rate of O(log(n)) where n is the security parameter.