You are looking at a specific version 20191025:122618 of this paper. See the latest version.

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

Note: Full version. Fixed Typos and clarify that verification timings are irrelevant and optimised verification does not improve over prior work.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ACM CCS 2019
Keywords
zero-knowledge argumentquadratic equationsarithmetic circuit satisfiabilitydiscrete logarithm assumption
Contact author(s)
michael klooss @ kit edu
History
2019-11-21: last of 5 revisions
2019-08-19: received
See all versions
Short URL
https://ia.cr/2019/944
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.