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

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

doi:10.1007/978-3-662-49896-5_12

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

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	Advances in Cryptology – EUROCRYPT 2016
Subtitle of host publication	35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II
Editors	Marc Fischlin, Jean-Sébastien Coron
Publisher	Springer
Pages	327-357
ISBN (Electronic)	9783662498965
ISBN (Print)	9783662498958
DOIs	https://doi.org/10.1007/978-3-662-49896-5_12
Publication status	Published - 28 Apr 2016
Event	35th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2016) - Vienna, Austria Duration: 8 May 2016 → 12 May 2016

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	9666
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	35th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2016)
Country/Territory	Austria
City	Vienna
Period	8/05/16 → 12/05/16

Keywords

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

Access to Document

10.1007/978-3-662-49896-5_12Licence: None: All rights reserved

Cite this

Bootle, J., Cerulli, A., Chaidos, P., Groth, J., & Petit, C. (2016). Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. In M. Fischlin, & J.-S. Coron (Eds.), Advances in Cryptology – EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II (pp. 327-357). (Lecture Notes in Computer Science; Vol. 9666). Springer. https://doi.org/10.1007/978-3-662-49896-5_12

Bootle, Jonathan ; Cerulli, Andrea ; Chaidos, Pyrros et al. / Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. Advances in Cryptology – EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II. editor / Marc Fischlin ; Jean-Sébastien Coron. Springer, 2016. pp. 327-357 (Lecture Notes in Computer Science).

@inproceedings{5bf7bb2459b74273b4074ed269567960,

title = "Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting",

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.",

keywords = "sigma-protocol , zero-knowledge argument , arithmetic circuit , discrete logarithm assumption",

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

year = "2016",

month = apr,

day = "28",

doi = "10.1007/978-3-662-49896-5_12",

language = "English",

isbn = "9783662498958",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "327--357",

editor = "Marc Fischlin and Coron, {Jean-S{\'e}bastien }",

booktitle = "Advances in Cryptology – EUROCRYPT 2016",

note = "35th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2016) ; Conference date: 08-05-2016 Through 12-05-2016",

}

Bootle, J, Cerulli, A, Chaidos, P, Groth, J & Petit, C 2016, Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. in M Fischlin & J-S Coron (eds), Advances in Cryptology – EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II. Lecture Notes in Computer Science, vol. 9666, Springer, pp. 327-357, 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2016), Vienna, Austria, 8/05/16. https://doi.org/10.1007/978-3-662-49896-5_12

Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. / Bootle, Jonathan; Cerulli, Andrea; Chaidos, Pyrros et al.
Advances in Cryptology – EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II. ed. / Marc Fischlin; Jean-Sébastien Coron. Springer, 2016. p. 327-357 (Lecture Notes in Computer Science; Vol. 9666).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Bootle, Jonathan

AU - Cerulli, Andrea

AU - Chaidos, Pyrros

AU - Groth, Jens

AU - Petit, Christophe

PY - 2016/4/28

Y1 - 2016/4/28

N2 - 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.

AB - 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.

KW - sigma-protocol

KW - zero-knowledge argument

KW - arithmetic circuit

KW - discrete logarithm assumption

U2 - 10.1007/978-3-662-49896-5_12

DO - 10.1007/978-3-662-49896-5_12

M3 - Conference contribution

SN - 9783662498958

T3 - Lecture Notes in Computer Science

SP - 327

EP - 357

BT - Advances in Cryptology – EUROCRYPT 2016

A2 - Fischlin, Marc

A2 - Coron, Jean-Sébastien

PB - Springer

T2 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2016)

Y2 - 8 May 2016 through 12 May 2016

ER -

Bootle J, Cerulli A, Chaidos P, Groth J, Petit C. Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. In Fischlin M, Coron JS, editors, Advances in Cryptology – EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II. Springer. 2016. p. 327-357. (Lecture Notes in Computer Science). doi: 10.1007/978-3-662-49896-5_12

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

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this