Paper 2019/1482

Transparent Polynomial Delegation and Its Applications to Zero Knowledge Proof

Jiaheng Zhang, Tiancheng Xie, Yupeng Zhang, and Dawn Song

Abstract

We present a new succinct zero knowledge argument scheme for layered arithmetic circuits without trusted setup. The prover time is $O(C + n \log n)$ and the proof size is $O(D \log C + \log^2 n)$ for a $D$-depth circuit with $n$ inputs and $C$ gates. The verification time is also succinct, $O(D \log C + \log^2 n)$, if the circuit is structured. Our scheme only uses lightweight cryptographic primitives such as collision-resistant hash functions and is plausibly post-quantum secure. We implement a zero knowledge argument system, Virgo, based on our new scheme and compare its performance to existing schemes. Experiments show that it only takes 53 seconds to generate a proof for a circuit computing a Merkle tree with 256 leaves, at least an order of magnitude faster than all other succinct zero knowledge argument schemes. The verification time is 50ms, and the proof size is 253KB, both competitive to existing systems. Underlying Virgo is a new transparent zero knowledge verifiable polynomial delegation scheme with logarithmic proof size and verification time. The scheme is in the interactive oracle proof model and may be of independent interest.

Note: Update email

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. IEEE Symposium on Security and Privacy 2020
Keywords
Zero knowledge proofinteractive proofpolynomial delegation
Contact author(s)
jiaheng_zhang @ berkeley edu
tiancx @ berkeley edu
zhangyp @ tamu edu
History
2020-07-16: last of 2 revisions
2019-12-24: received
See all versions
Short URL
https://ia.cr/2019/1482
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1482,
      author = {Jiaheng Zhang and Tiancheng Xie and Yupeng Zhang and Dawn Song},
      title = {Transparent Polynomial Delegation and Its Applications to Zero Knowledge Proof},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/1482},
      year = {2019},
      url = {https://eprint.iacr.org/2019/1482}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.