Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

49 Citations (Scopus)

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 zeroknowledge 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.
Original languageEnglish
Title of host publicationAdvances in Cryptology – EUROCRYPT 2016
Subtitle of host publication35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II
EditorsMarc Fischlin, Jean-Sébastien Coron
PublisherSpringer
Pages327-357
ISBN (Electronic)9783662498965
ISBN (Print)9783662498958
DOIs
Publication statusPublished - 28 Apr 2016
Event35th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2016) - Vienna, Austria
Duration: 8 May 201612 May 2016

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9666
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference35th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2016)
Country/TerritoryAustria
CityVienna
Period8/05/1612/05/16

Keywords

  • sigma-protocol
  • zero-knowledge argument
  • arithmetic circuit
  • discrete logarithm assumption

Fingerprint

Dive into the research topics of 'Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting'. Together they form a unique fingerprint.

Cite this