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

Linear-Time Zero-Knowledge Proofs for Arithmetic Circuit Satisfiability

Bootle, J; Cerulli, A; Groth, J; Hajiabadi, M; Jakobsen, S; (2017) Linear-Time Zero-Knowledge Proofs for Arithmetic Circuit Satisfiability. In: Takagi, T and Peyrin, T, (eds.) Advances in Cryptology – ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security: Proceedings, Part III. (pp. pp. 336-365). Springer: Cham, Switzerland. Green open access

[thumbnail of Main.pdf]
Preview
Text
Main.pdf - Accepted Version

Download (898kB) | Preview

Abstract

We give computationally efficient zero-knowledge proofs of knowledge for arithmetic circuit satisfiability over a large field. For a circuit with N addition and multiplication gates, the prover only uses O(N)O(N) multiplications and the verifier only uses O(N)O(N) additions in the field. If the commitments we use are statistically binding, our zero-knowledge proofs have unconditional soundness, while if the commitments are statistically hiding we get computational soundness. Our zero-knowledge proofs also have sub-linear communication if the commitment scheme is compact. Our construction proceeds in three steps. First, we give a zero-knowledge proof for arithmetic circuit satisfiability in an ideal linear commitment model where the prover may commit to secret vectors of field elements, and the verifier can receive certified linear combinations of those vectors. Second, we show that the ideal linear commitment proof can be instantiated using error-correcting codes and non-interactive commitments. Finally, by choosing efficient instantiations of the primitives we obtain linear-time zero-knowledge proofs.

Type: Proceedings paper
Title: Linear-Time Zero-Knowledge Proofs for Arithmetic Circuit Satisfiability
Event: ASIACRYPT 2017, 23rd International Conference on the Theory and Applications of Cryptology and Information Security, 3-7 December 2017, Hong Kong, China
ISBN-13: 9783319706993
Open access status: An open access version is available from UCL Discovery
DOI: 10.1007/978-3-319-70700-6_12
Publisher version: https://doi.org/10.1007/978-3-319-70700-6_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: Zero-knowledge, Arithmetic circuit, Ideal linear commitments
UCL classification: UCL
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/10039786
Downloads since deposit
447Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item