Succinct Cryptography via Propositional Proofs

Abstract

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 private information retrieval from standard, cryptographic assumptions which achieve the ideal levels of succinctness. 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 succinctness in two such settings: • Can we construct succinct indistinguishability obfuscation (IO) for Turing machines? In particular, can we construct an obfuscated program whose size is independent of the input length? • Can we construct succinct non-interactive arguments (SNARGs) for all of NP? While the problems seem unrelated at first glance, the root difficulty seems to stem from a similar place: both primitives have non-falsifiable security definitions. In fact, this type of barrier exists for many other cryptographic primitives, including witness encryption. This leads to a central question which we refer to as the “non-falsifiability barrier”: how can we construct non-falsifiable primitives from falsifiable assumptions? In this thesis, 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 settings. Our main result is universal construction of both SNARGs and succinct IO for Turing machines from standard assumptions using propositional proofs. We then show several applications, including rate-1 IO for many programs, the first succinct secret sharin schemes for monotone circuits, and many more. Our results establish propositional proofs as a foundational tool for achieving succinctness across a broad range of cryptographic settings.