Efficient Zero-Knowledge Arguments in the Discrete Log Setting, Revisited
Efficient Zero-Knowledge Arguments in the Discrete Log Setting, Revisited
复制标题
DOI：
10.1145/3319535.3354251
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Max Hoffmann;Michael Klooß;Andy Rupp
中科院分区：
文献类型：
--
作者：
Max Hoffmann;Michael Klooß;Andy Rupp
零知识的论点已经变得实用，并被广泛使用，特别是在区块链的世界中，例如在Zcash中。这项工作重温零知识证明在离散对数设置。首先，我们确定和开拓基本技术（部分被隐式使用之前），以优化在这种设置的证明。特别地，协议的线性组合是获得零知识和/或减少通信的有用工具。通过这些技术，我们能够设计出布特尔等人（EUROCITY PT '16）和Bünz等人（S&P '18）的对数通信参数的零知识变体，从而几乎不引入开销。然后，我们构建了一个概念上简单的提交和证明参数的满足一组二次方程。与以前的工作不同，我们不限于秩1约束系统（R1 CS）。据我们所知，这是第一个工作证明，一般的二次约束，而不仅仅是R1 CS，是一个自然的关系，在dlog（或理想的线性承诺）设置。这为优化提供了新的可能性，例如，任何n2次多项式f（X）现在可以用至多2n个二次约束来“评估”。我们的协议是模块化的。我们很容易构造一个有效的，对数大小的洗牌证明，它可以用于电子投票。此外，我们还仔细研究了定量安全措施，例如。萃取器的效率我们正式短路提取，这使我们能够给更严格的限制提取器的效率。
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 optimise 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 n2 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.