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.
Category / Keywords: cryptographic protocols / Interactive proofs; Zero knowledge proofs Date: received 8 Oct 2020 Contact author: zhangyp at tamu edu,jiaheng_zhang@berkeley edu,wangnick@sjtu edu cn,yinuo@berkeley edu Available format(s): PDF | BibTeX Citation Version: 20201009:113732 (All versions of this report) Short URL: ia.cr/2020/1247