International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Aurora: Transparent Succinct Arguments for R1CS

Authors:
Eli Ben-Sasson
Alessandro Chiesa
Michael Riabzev
Nicholas Spooner
Madars Virza
Nicholas P. Ward
Download:
DOI: 10.1007/978-3-030-17653-2_4
Search ePrint
Search Google
Abstract: We design, implement, and evaluate a zero knowledge succinct non-interactive argument (SNARG) for Rank-1 Constraint Satisfaction (R1CS), a widely-deployed NP language undergoing standardization. Our SNARG has a transparent setup, is plausibly post-quantum secure, and uses lightweight cryptography. A proof attesting to the satisfiability of n constraints has size $$O(\log ^2 n)$$O(log2n); it can be produced with $$O(n \log n)$$O(nlogn) field operations and verified with O(n). At 128 bits of security, proofs are less than $${250}\,\mathrm{kB}$$250kB even for several million constraints, more than $$10{\times }$$10× shorter than prior SNARGs with similar features.A key ingredient of our construction is a new Interactive Oracle Proof (IOP) for solving a univariate analogue of the classical sumcheck problem [LFKN92], originally studied for multivariate polynomials. Our protocol verifies the sum of entries of a Reed–Solomon codeword over any subgroup of a field.We also provide $$\texttt {libiop}$$libiop, a library for writing IOP-based arguments, in which a toolchain of transformations enables programmers to write new arguments by writing simple IOP sub-components. We have used this library to specify our construction and prior ones, and plan to open-source it.
BibTeX
@article{eurocrypt-2019-29332,
  title={Aurora: Transparent Succinct Arguments for R1CS},
  booktitle={Advances in Cryptology – EUROCRYPT 2019},
  series={Advances in Cryptology – EUROCRYPT 2019},
  publisher={Springer},
  volume={11476},
  pages={103-128},
  doi={10.1007/978-3-030-17653-2_4},
  author={Eli Ben-Sasson and Alessandro Chiesa and Michael Riabzev and Nicholas Spooner and Madars Virza and Nicholas P. Ward},
  year=2019
}