Abstract

Despite all the success in modern cryptography, there are still some tasks in cryptography where achieving the “ideal” efficiency from standard assumptions has evaded us. Consider the following two settings:
 
* Can we construct succinct non-interactive arguments (SNARGs) for all of NP?
* Can we construct indistinguishability obfuscation (IO) for Turing machines? In particular, can we achieve an obfuscation size which is independent of the input length? 
 
While the problems seem unrelated at first glance, the root difficulty seems to stem from a similar place: both primitives have non-falsifiable security notions. In fact, this type of barrier exists for many other cryptographic primitives, including witness encryption. This leads to a central question: how can we construct non-falsifiable primitives from falsifiable assumptions?
 
In this talk, I’ll show how we can leverage “propositional proofs” to overcome the non-falsifiability barrier. I will then discuss how to use this idea to achieve succinctness in both the iO and SNARG settings.