Our circuit generator is the first to be universal: it does not need to know the program, but only a bound on its running time. Moreover, the size of the output circuit depends additively (rather than multiplicatively) on program size, allowing verification of larger programs.
The cryptographic proof system improves proving and verification times, by leveraging new algorithms and a pairing library tailored to the protocol.
We evaluated our system for programs with up to 10,000 instructions, running for up to 32,000 machine steps, each of which can arbitrarily access random-access memory; and also demonstrated it executing programs that use just-in-time compilation. Our proofs are 230 bytes long at 80 bits of security, or 288 bytes long at 128 bits of security. Typical verification time is 5 milliseconds, regardless of the original program's running time.
Category / Keywords: cryptographic protocols / zero-knowledge, succinct arguments, computationally-sound proofs Original Publication (with minor differences): USENIX Security 2014 Date: received 30 Dec 2013, last revised 5 Feb 2019 Contact author: alexch at csail mit edu Available format(s): PDF | BibTeX Citation Note: The updated version fixes an error in Appendix B, found by Ariel Gabizon. Version: 20190205:162518 (All versions of this report) Short URL: ia.cr/2013/879