UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

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

Bootle, J; Cerulli, A; Chaidos, P; Groth, J; Petit, C; (2016) Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting. In: Fischlin, M and Coron, JS, (eds.) Advances in Cryptology – EUROCRYPT 2016. (pp. pp. 327-357). Springer Nature Green open access

[img]
Preview
Text
263.pdf - Accepted version

Download (594kB) | Preview

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.

Type: Proceedings paper
Title: Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting
Event: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques
Location: Vienna, Austria
Dates: 8th-12th May 2016
ISBN-13: 978-3-662-49895-8
Open access status: An open access version is available from UCL Discovery
DOI: 10.1007/978-3-662-49896-5_12
Publisher version: https://doi.org/10.1007/978-3-662-49896-5_12
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords: Sigma-protocol, Zero-knowledge argument, Arithmetic circuit, Discrete logarithm assumption
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/10090338
Downloads since deposit
37Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item