TY - GEN
T1 - Constant-Overhead Zero-Knowledge for RAM Programs
AU - Franzese, Nicholas
AU - Katz, Jonathan
AU - Lu, Steve
AU - Ostrovsky, Rafail
AU - Wang, Xiao
AU - Weng, Chenkai
N1 - Funding Information:
views, opinions, and/or findings expressed are those of the author(s) and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government. Work of Jonathan Katz was also supported by NSF award #1563722. Work of Rafail Ostrovsky was also supported by NSF award #2001096, US-Israel BSF grant 2015782, a Google Faculty Award, a JP Morgan Faculty Award, an IBM Faculty Research Award, a Xerox Faculty Research Award, an OKAWA Foundation Research Award, a B. John Garrick Foundation Award, a Teradata Research Award, a Lockheed-Martin Research Award, and the Sunday Group. Work of Xiao Wang was also supported by NSF award #2016240, and research awards from Facebook and PlatON Network. Distribution Statement “A” (Approved for Public Release, Distribution Unlimited).
Funding Information:
This material is based upon work supported in part by DARPA under Contract Nos. HR001120C0087 and HR00112020025. The
Publisher Copyright:
© 2021 ACM.
PY - 2021/11/12
Y1 - 2021/11/12
N2 - 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 (224 32-bit words) using only 34∼bytes of communication per access, a more than 80x 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 10x 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.
AB - 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 (224 32-bit words) using only 34∼bytes of communication per access, a more than 80x 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 10x 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.
UR - http://www.scopus.com/inward/record.url?scp=85119322806&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85119322806&partnerID=8YFLogxK
U2 - 10.1145/3460120.3484800
DO - 10.1145/3460120.3484800
M3 - Conference contribution
AN - SCOPUS:85119322806
T3 - Proceedings of the ACM Conference on Computer and Communications Security
SP - 178
EP - 191
BT - CCS 2021 - Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security
PB - Association for Computing Machinery
T2 - 27th ACM Annual Conference on Computer and Communication Security, CCS 2021
Y2 - 15 November 2021 through 19 November 2021
ER -