Cryptology ePrint Archive: Report 2019/1482

Transparent Polynomial Delegation and Its Applications to Zero Knowledge Proof

Jiaheng Zhang and Tiancheng Xie and 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.

Category / Keywords: cryptographic protocols / Zero knowledge proof, interactive proof, polynomial delegation

Original Publication (with minor differences): IEEE Symposium on Security and Privacy 2020

Date: received 23 Dec 2019, last revised 16 Jul 2020

Contact author: jiaheng_zhang at berkeley edu,tiancx@berkeley edu,zhangyp@tamu edu

Available format(s): PDF | BibTeX Citation

Note: Update email

Version: 20200716:155825 (All versions of this report)

Short URL: ia.cr/2019/1482


[ Cryptology ePrint archive ]