Constant-Overhead Zero-Knowledge for RAM Programs

Nicholas Franzese; Jonathan Katz; Steve Lu; Rafail Ostrovsky; Xiao Wang; Chenkai Weng

Paper 2021/979

Constant-Overhead Zero-Knowledge for RAM Programs

Nicholas Franzese

Jonathan Katz

Steve Lu

Rafail Ostrovsky

Xiao Wang

Chenkai Weng

Abstract

We show a constant-overhead interactive zero-knowledge (ZK) proof system for RAM programs, that is, a ZK proof in which the communication complexity as well as the running times of the prover and verifier scale linearly in the size of the memory and the running time of the underlying RAM program. Besides yielding an asymptotic improvement of prior work, our implementation gives concrete performance improvements for RAM-based ZK proofs. In particular, our implementation supports ZK proofs of private read/write accesses to 64 MB of memory ( 32-bit words) using only 34 bytes of communication per access, a more than improvement compared to the recent BubbleRAM protocol. We also design a lightweight RISC CPU that can efficiently emulate the MIPS-I instruction set, and for which our ZK proof communicates only 320 bytes per cycle, more than less than the BubbleRAM CPU. In a 100 Mbps network, we can perform zero-knowledge executions of our CPU (with 64 MB of main memory and 4 MB of program memory) at a clock rate of 6.6 kHz.

Note: This version fixes minor typos

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. ACM CCS 2021
DOI: 10.1145/3460120.3484800
Keywords: zero-knowledge proofs
Contact author(s): jkatz2 @ gmail com
History: 2022-12-19: last of 2 revisions; 2021-07-22: received; See all versions
Short URL: https://ia.cr/2021/979
License: CC BY

BibTeX

@misc{cryptoeprint:2021/979,
      author = {Nicholas Franzese and Jonathan Katz and Steve Lu and Rafail Ostrovsky and Xiao Wang and Chenkai Weng},
      title = {Constant-Overhead Zero-Knowledge for {RAM} Programs},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/979},
      year = {2021},
      doi = {10.1145/3460120.3484800},
      url = {https://eprint.iacr.org/2021/979}
}