Cryptology ePrint Archive: Report 2019/944

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

Max Hoffmann and Michael Klooß and Andy Rupp

Abstract: 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.

Category / Keywords: cryptographic protocols / zero-knowledge argument, quadratic equations, arithmetic circuit satisfiability, discrete logarithm assumption

Original Publication (with major differences): ACM CCS 2019

Date: received 18 Aug 2019, last revised 21 Nov 2019

Contact author: michael klooss at kit edu

Available format(s): PDF | BibTeX Citation

Note: Full version. Fixed acknowledgements and URL.

Version: 20191121:182818 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]