Paper 2021/979

Constant-Overhead Zero-Knowledge for RAM Programs

Nicholas Franzese, Jonathan Katz, Steve Lu, Rafail Ostrovsky, Xiao Wang, and 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 $N$ and the running time $T$ 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 ($2^{24}$ 32-bit words) using only 34 bytes of communication per access, a more than $80\times$ 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 $\approx$ 320 bytes per cycle, more than $10\times$ 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.ACM CCS 2021
DOI
10.1145/3460120.3484800
Keywords
zero-knowledge proofs
Contact author(s)
wangxiao @ cs northwestern edu
History
2021-09-11: revised
2021-07-22: received
See all versions
Short URL
https://ia.cr/2021/979
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2021/979}},
      url = {https://eprint.iacr.org/2021/979}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.