Nicholas Spooner

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2020-182

September 30, 2020

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2020/EECS-2020-182.pdf

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.

Advisors: Alessandro Chiesa

---

BibTeX citation:

@phdthesis{Spooner:EECS-2020-182,
    Author= {Spooner, Nicholas},
    Title= {Succinct Non-Interactive Arguments for Arithmetic Circuits},
    School= {EECS Department, University of California, Berkeley},
    Year= {2020},
    Month= {Sep},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2020/EECS-2020-182.html},
    Number= {UCB/EECS-2020-182},
    Abstract= {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.},
}

EndNote citation:

%0 Thesis
%A Spooner, Nicholas 
%T Succinct Non-Interactive Arguments for Arithmetic Circuits
%I EECS Department, University of California, Berkeley
%D 2020
%8 September 30
%@ UCB/EECS-2020-182
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2020/EECS-2020-182.html
%F Spooner:EECS-2020-182