How to Certify Deletion with Constant-Length Verification Key

The certified deletion process involves transmitting a ciphertext and confirming its deletion via a digital certificate. In this context, the term “deletion” refers to the fact that no information-processing procedure can decipher the cyphertext if the certificate is valid. Those familiar with cryptography can recognize this type of cipher as being computationally secure before and informationally secure after deletion. Let <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\lambda$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> be the security parameter and length of the message sent. We proposed a method for Certified Deletion that needs only <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\lambda$</tex> bit of verification key, while to my knowledge, all the prior works need at least <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\lambda n)$</tex> bit of verification key. Imagine someone who wants to store 1GB of data on a server in a deletable manner; then the previous methods need to store 1GB of metadata, while ours do not. Our method uses PRF (short for Pseudo-random Functions) to generate certificates and its key as the verification key. Also, we conclude our result in a general form as the prior works [1]–[3] did. So, applying our result the same way as in the prior works gets the same applications. The key's length concerns storage costs and key leakage risks, and we are the first to attempt to reduce that. General ways to realize Certified Deletion are known [1], [2] and our result can be seen as an essential adaption to improve efficiency in practice.