Computer Science Thesis Proposal

— 2:30pm

In Person and Virtual - ET - Reddy Conference Room, Gates Hillman 4405 and Zoom

JUSTIN RAIZES, Ph.D. Student, Computer Science Department, Carnegie Mellon University

Certified Deniability in a Quantum World

Certified deletion is an influential paradigm that allows a user to delegate sensitive information to another user, and later verify that this information has been destroyed. Since its proposal by Broadbent and Islam (TCC '20), certified deletion has been extended to a wide variety of primitives, such as fully-homomorphic ciphertexts, encryption secret keys, signatures, and even programs.

However, current definitions of certified deletion do not capture all of the advantages of deletion. For example, in revocable signatures, an adversary who deletes a signature on a message cannot output a valid signature for m, but may still be able to prove that it used to possess one. In other words, it proves that m was signed at some point.

The missing security property is the notion of deniability. Similarly to how Pass (CRYPTO '03) views deniability as a fundamental property of zero-knowledge, I view deniability as a fundamental property of certified deletion. Unfortunately, classical solutions for non-interactive deniability either lack public verifiability or reveal even more sensitive information in the future, contrary to the goals of certified deletion.

I propose to study how certified deletion can be strengthened to provide novel deniability guarantees for a wide variety of primitives, which I call certified deniability. These primitives include signatures, non-interactive zero-knowledge, and key leasing. Notably, the problem of deniable key leasing does not seem to have a classical counterpart to date. If time permits, I plan to extend these results to the related setting of unclonability under the name single-copy explainability, which guarantees that an adversary cannot turn one copy of some sensitive information into two copies that can both be explained - the validity of the other can be denied.

Thesis Committee:

Vipul Goyal (Chair) (Carnegie Mellon University / NTT Research)
Aayush Jain
Elaine Shi
Giulio Malavolta (Bocconi University / Max Planck Institute for Security and Privacy)

In Person and Zoom Participation. See announcement.

Add event to Google
Add event to iCal