### Doubly Efficient Interactive Proofs for General Arithmetic Circuits with Linear Prover Time

Jiaheng Zhang, Tianyi Liu, Weijie Wang, Yinuo Zhang, Dawn Song, Xiang Xie, and Yupeng Zhang

##### Abstract

We propose a new doubly efficient interactive proof protocol for general arithmetic circuits. The protocol generalizes the doubly efficient interactive proof for layered circuits proposed by Goldwasser, Kalai and Rothblum to arbitrary circuits while preserving the optimal prover complexity that is strictly linear to the size of the circuits. The proof size remains succinct for low depth circuits and the verifier time is sublinear for structured circuits. We then construct a new zero knowledge argument scheme for general arithmetic circuits using our new interactive proof protocol together with polynomial commitments. Not only does our new protocol achieve optimal prover complexity asymptotically, but it is also efficient in practice. Our experiments show that it only takes 1 second to generate the proof for a circuit with 600,000 gates, which is 7 times faster than the original interactive proof protocol on the corresponding layered circuit. The proof size is 229 kilobytes and the verifier time is 0.56 second. Our implementation can take general arithmetic circuits generated by existing tools directly, without transforming them to layered circuits with high overhead on the size of the circuits.

Available format(s)
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Interactive proofsZero knowledge proofs
Contact author(s)
zhangyp @ tamu edu
jiaheng_zhang @ berkeley edu
tianyi @ tamu edu
wangnick @ sjtu edu cn
yinuo @ berkeley edu
xiexiang @ matrixelements com
dawnsong @ berkeley edu
History
2021-05-19: revised
See all versions
Short URL
https://ia.cr/2020/1247

CC BY

BibTeX

@misc{cryptoeprint:2020/1247,
author = {Jiaheng Zhang and Tianyi Liu and Weijie Wang and Yinuo Zhang and Dawn Song and Xiang Xie and Yupeng Zhang},
title = {Doubly Efficient Interactive Proofs for General Arithmetic Circuits with Linear Prover Time},
howpublished = {Cryptology ePrint Archive, Paper 2020/1247},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1247}},
url = {https://eprint.iacr.org/2020/1247}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.