Paper 2019/944

Efficient zero-knowledge arguments in the discrete log setting, revisited

Max Hoffmann, Michael Klooß, and Andy Rupp


Zero-knowledge arguments have become practical, and widely used, especially in the world of Blockchain, for example in Zcash. This work revisits zero-knowledge proofs in the discrete logarithm setting. First, we identify and carve out basic techniques (partly being used implicitly before) to optimize proofs in this setting. In particular, the linear combination of protocols is a useful tool to obtain zero-knowledge and/or reduce communication. With these techniques, we are able to devise zero-knowledge variants of the logarithmic communication arguments by Bootle et al.\ (EUROCRYPT '16) and Bünz et al. (S\&P '18) thereby introducing almost no overhead. We then construct a conceptually simple commit-and-prove argument for satisfiability of a set of quadratic equations. Unlike previous work, we are not restricted to rank 1 constraint systems (R1CS). This is, to the best of our knowledge, the first work demonstrating that general quadratic constraints, not just R1CS, are a natural relation in the dlog (or ideal linear commitment) setting. This enables new possibilities for optimisation, as, eg., any degree $n^2$ polynomial $f(X)$ can now be ``evaluated'' with at most $2n$ quadratic constraints. Our protocols are modular. We easily construct an efficient, logarithmic size shuffle proof, which can be used in electronic voting. Additionally, we take a closer look at quantitative security measures, eg. the efficiency of an extractor. We formalise short-circuit extraction, which allows us to give tighter bounds on the efficiency of an extractor.

Note: Full version. Fixed acknowledgements and URL.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.ACM CCS 2019
zero-knowledge argumentquadratic equationsarithmetic circuit satisfiabilitydiscrete logarithm assumption
Contact author(s)
michael klooss @ kit edu
2019-11-21: last of 5 revisions
2019-08-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Max Hoffmann and Michael Klooß and Andy Rupp},
      title = {Efficient zero-knowledge arguments in the discrete log setting, revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2019/944},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.