UCSB CS Theory Colloquium Series
Fall 2021
|
Friday, December 3, 2pm, Phelps 2510 Speaker: Andrea Coladangelo (UC Berkeley/Simons) Title: Deniable Encryption in a Quantum World Abstract: (Sender-)Deniable encryption provides a very strong privacy guarantee: a sender who is coerced by an attacker into "opening" their ciphertext after-the-fact, is able to generate "fake'' local random choices that are consistent with any plaintext of their choice. The only known fully-efficient constructions of public-key deniable encryption rely on indistinguishability obfuscation (iO) (which currently can only be based on sub-exponential hardness assumptions). In this work, we study (sender-)deniable encryption in a setting where the encryption procedure is a quantum algorithm, but the ciphertext is classical. We study extensions of the notion of deniable encryption to this setting. Our first extension parallels the classical one. We give a fully efficient construction satisfying this notion, assuming only the quantum hardness of the Learning with Errors (LWE) problem. We observe that at the heart of this quantum advantage is a new phenomenon, that we formalize in the stronger notion of "unexplainability", which is impossible to achieve classically. (this is joint work with Shafi Goldwasser and Umesh Vazirani) |