  Given a ciphertext, is it possible to prove the deletion of the underlying
plaintext? Since classical ciphertexts can be copied, clearly such a feat is
impossible using classical information alone. In stark contrast to this, we
show that quantum encodings enable 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; the scheme is
also robust against noise in these devices. Furthermore, we provide an analysis
that is suitable in the finite-key regime.
