[Thesis Defense] Succinct Cryptography via Propositional Proofs

The goal in modern cryptography is to obtain security while minimizing the use of computational resources.  In recent years, we have been incredibly successful in our pursuit for efficiency, even for cryptographic tasks that were thought to be “science fiction”. For example, we have constructions of fully homomorphic encryption and indistinguishability obfuscation for circuits from standard, falsifiable cryptographic assumptions.

 However, there are still some tasks in cryptography where achieving the “ideal” efficiency from standard assumptions has evaded us. In this thesis, we study the problem of achieving efficiency in the form succinctness in two such 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, we show how to leverage “propositional proofs” to overcome the non-falsifiability barrier, and make substantial progress in the goal of achieving succinctness in both of these settings. Our results include universal constructions of both SNARGs and IO for Turing machines from standard assumptions. We then show that these constructions are secure as long as there exists some construction for the respective primitive that has a “propositional proof” of its correctness property. We also demonstrate a general template for constructing adaptively sound SNARGs for NP, and give an instantiation via subexponential IO and LWE. We further apply our techniques to improve succinctness in other cryptographic settings such as secret sharing. Our results establish propositional proofs as a foundational tool for achieving succinctness across a broad range of cryptographic settings.

https://mit.zoom.us/j/95528753473