UC Berkeley

This thesis describes a family of new constructions of "succinct" non-interactive arguments (SNARGs) for arithmetic circuit satisfiability. An argument is a protocol by which a prover can convince a verifier of the truth of some statement; in this work, the statement will be of the form "there exists w such C(x,w) = 1", where C is an arithmetic circuit. By "succinct", we mean that the communication is polylogarithmic in the size of C.

All of these constructions are unconditionally secure in the random oracle and quantum random oracle models. In particular, they do not require any private setup. This is achieved in each case by designing an interactive oracle proof and then applying a transformation of Ben-Sasson, Chiesa and Spooner. We show that our argument systems are both asymptotically efficient and feasible in practice, demonstrating the usefulness of this approach.

More specifically, we obtain the following.

1. A succinct non-interactive argument (Aurora) for general arithmetic circuits, with verification time linear in the size of the circuit.

2. A succinct non-interactive argument for "structured" arithmetic circuits, with verification time polylogarithmic in the size of the circuit.

3. A succinct non-interactive argument with preprocessing (Fractal) for general arithmetic circuits, where the verification time (after offline preprocessing) is polylogarithmic in the size of the circuit.