PDF

Description

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.

Details

Title
Succinct Non-Interactive Arguments for Arithmetic Circuits
Creator
Spooner, Nicholas, Author
Published
EECS Department, University of California at Berkeley, Berkeley, California, 9/30/2020
Full Collection Name
Electrical Engineering & Computer Sciences Technical Reports
Type
Text
Format
technical reports
Extent
211 p
Language
eng
Usage Statement
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).
Collection

Files

Statistics

from
to
Export
Download Full History