Paper 2017/872

Linear-Time Zero-Knowledge Proofs for Arithmetic Circuit Satisfiability

Jonathan Bootle, Andrea Cerulli, Essam Ghadafi, Jens Groth, Mohammad Hajiabadi, and Sune K. Jakobsen

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) multiplications and the verifier only uses 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.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in ASIACRYPT 2017
Keywords
Zero-knowledgearithmetic circuitideal linear commitments
Contact author(s)
jonathan bootle 14 @ ucl ac uk
andrea cerulli 13 @ ucl ac uk
essam ghadafi @ googlemail com
j groth @ ucl ac uk
m hajiabadi @ ucl ac uk
s jakobsen @ ucl ac uk
History
2017-09-13: received
Short URL
https://ia.cr/2017/872
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/872,
      author = {Jonathan Bootle and Andrea Cerulli and Essam Ghadafi and Jens Groth and Mohammad Hajiabadi and Sune K.  Jakobsen},
      title = {Linear-Time Zero-Knowledge Proofs for Arithmetic Circuit Satisfiability},
      howpublished = {Cryptology ePrint Archive, Paper 2017/872},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/872}},
      url = {https://eprint.iacr.org/2017/872}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.