Linear-time zero-knowledge proofs for arithmetic circuit satisfiability

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

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

30 Scopus citations

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

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Proceedings
EditorsTsuyoshi Takagi, Thomas Peyrin
PublisherSpringer Verlag
Pages336-365
Number of pages30
ISBN (Print)9783319706993
DOIs
StatePublished - 2017
Event23rd Annual International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2017 - Hong Kong, Hong Kong
Duration: Dec 3 2017Dec 7 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10626 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference23rd Annual International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2017
Country/TerritoryHong Kong
CityHong Kong
Period12/3/1712/7/17

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Linear-time zero-knowledge proofs for arithmetic circuit satisfiability'. Together they form a unique fingerprint.

Cite this