Paper 2016/263

Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting

Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Jens Groth, and Christophe Petit

Abstract

We provide a zero-knowledge argument for arithmetic circuit satisfiability with a communication complexity that grows logarithmically in the size of the circuit. The round complexity is also logarithmic and for an arithmetic circuit with fan-in 2 gates the computation of the prover and verifier is linear in the size of the circuit. The soundness of our argument relies solely on the well-established discrete logarithm assumption in prime order groups. At the heart of our new argument system is an efficient zero-knowledge argument of knowledge of openings of two Pedersen multicommitments satisfying an inner product relation, which is of independent interest. The inner product argument requires logarithmic communication, logarithmic interaction and linear computation for both the prover and the verifier. We also develop a scheme to commit to a polynomial and later reveal the evaluation at an arbitrary point, in a verifiable manner. This is used to build an optimized version of the constant round square root complexity argument of Groth (CRYPTO 2009), which reduces both communication and round complexity.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in EUROCRYPT 2016
Keywords
Sigma-protocolzero-knowledge argumentarithmetic circuitdiscrete logarithm assumption
Contact author(s)
jonathan bootle 14 @ ucl ac uk
andrea cerulli 13 @ ucl ac uk
pyrros chaidos 10 @ ucl ac uk
christophe f petit @ gmail com
j groth @ ucl ac uk
History
2016-03-08: received
Short URL
https://ia.cr/2016/263
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/263,
      author = {Jonathan Bootle and Andrea Cerulli and Pyrros Chaidos and Jens Groth and Christophe Petit},
      title = {Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting},
      howpublished = {Cryptology ePrint Archive, Paper 2016/263},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/263}},
      url = {https://eprint.iacr.org/2016/263}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.