Intriguingly, the laws of physics allow protocols executed by quantum computers to realize security guarantees that are impossible for classical computers. One of these new possibilities is the ability to temporarily send ciphertexts to a user, then later verify that the encoded message has been destroyed in an information-theoretic sense.

Broadbent and Islam (TQC) introduced this notion, called certified deletion, in the context of encryption. However, there are many more scenarios in which verifiable deletion is useful. For example, a software rental company might want to temporarily send their software to a user, then request that the user destroys the copy at the end of the rental period. In this thesis, we expand the realm of certified deletion to cryptographic primitives beyond just encryption. We define and construct the following objects with certified deletion:

• Obfuscation with Certified Deletion allows a company to lend a program to a user, allowing them to evaluate it as they wish. Then, when the user no longer wish to rent the program, they can destroy it and prove to the issuer that they are no longer able to evaluate the program. Obfuscation with certified deletion also enables several new applications such as certifiably deletable secret keys.
• Secret Sharing with Certified Deletion allows a user to distribute shares of a secret to several parties. In the event of a data breach, the user can request that the affected party deletes their shares, rendering them useless for stealing the secret.
• Signatures with Certified Deniability allow a signer to endorse a statement in a single message. After the receiver has verified the signature, they can destroy it and prove to the signer that they are no longer able to provide convincing evidence - of any kind - that the signer endorsed this statement. We also show how to construct the related primitive of NIZKs with certified deniability.
  Certified deniability is a new, more comprehensive paradigm for certified deletion that rules out additional attacks not explicitly considered by prior definitions.

181 pages

Thesis Committee:
Vipual Goyal (Chair)
Aayush Jain
Elaine Shi
Giulio Malavolta (Bocconi University)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu