Modern SNARGitecture: New Constructions of Succinct Non-interactive Arguments

Cryptographic proof systems enable a prover to convince a computationally weak verifier that a statement is true. In this thesis, we study Succinct Non-interactive ARGuments (SNARGs), where the communication from the prover is simply a short certificate. Soundness of the SNARG guarantees that no adversary can trick the verifier into accepting false statements, under a cryptographic hardness assumption.

A compelling question, unresolved despite decades of research, is whether we can construct a simple SNARG which can certify any NP statement from standard assumptions. We reduce this question to proving a mathematical conjecture about multivariate polynomials over the reals, by constructing a SNARG for NP which is sound under the learning with errors assumption if the conjecture is true.

On the other hand, we show how to achieve much better efficiency by focusing on restricted classes of languages, by constructing a SNARG for batch languages which requires less public setup than is possible for general-purpose SNARGs.

In our third contribution, we consider locally verifiable distributed SNARGs, where the prover wants to certify a property of a network, and each node in the network is a verifier with limited access to the statement. We construct a SNARG which is sound even when the cheating prover can statically corrupt part of the network.