Paper 2018/045

Efficient Batch Zero-Knowledge Arguments for Low Degree Polynomials

Jonathan Bootle and Jens Groth


The work of Bootle et al. (EUROCRYPT 2016) constructs an extremely efficient zero-knowledge argument for arithmetic circuit satisfiability in the discrete logarithm setting. However, the argument does not treat relations involving commitments, and furthermore, for simple polynomial relations, the complex machinery employed is unnecessary. In this work, we give a framework for expressing simple relations between commitments and field elements, and present a zero-knowledge argument which is considerably more efficient than Bootle et al. in the case where the polynomials in the relation have low degree. Our method also directly yields a batch protocol, which allows many copies of the same relation to be more efficiently proved and verified in a single argument. We instantiate our protocol with concrete polynomial relations to construct zero-knowledge arguments for membership proofs, polynomial evaluation proofs, and range proofs. Our work can be seen as a unified explanation of the underlying ideas of these protocols. In some of these instantiations we also achieve better efficiency than the state of the art.

Available format(s)
Publication info
Published by the IACR in PKC 2018
Sigma-protocolzero-knowledge argumentbatch-verificationdiscrete logarithm assumption
Contact author(s)
jonathan bootle 14 @ ucl ac uk
j groth @ ucl ac uk
2018-01-10: received
Short URL
Creative Commons Attribution


      author = {Jonathan Bootle and Jens Groth},
      title = {Efficient Batch Zero-Knowledge Arguments for Low Degree Polynomials},
      howpublished = {Cryptology ePrint Archive, Paper 2018/045},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.