Welcome to the resource topic for 2022/313
Title:
Efficient Proof of RAM Programs from Any Public-Coin Zero-Knowledge System
Authors: Cyprien Delpech de Saint Guilhem, Emmanuela Orsini, Titouan Tanguy, Michiel Verbauwhede
Abstract:We present the first constant-round and concretely efficient zero-knowledge proof protocol for RAM programs using any stateless zero-knowledge proof system for Boolean or arithmetic circuits. Both the communication complexity and the prover and verifier run times asymptotically scale linearly in the size of the memory and the run time of the RAM program; we demonstrate concrete efficiency with performance results of our C++ implementation. At the core of this work is an arithmetic circuit which verifies the consistency of a list of memory access tuples in zero-knowledge. Using this circuit, we construct a protocol to realize an ideal array functionality using a generic stateless and public-coin zero-knowledge functionality. We prove its UC security and show how it can then be expanded to provide proofs of entire RAM programs. We also extend the Limbo zero-knowledge protocol (ACM CCS 2021) to UC-realize the zero-knowledge functionality that our protocol requires. The C++ implementation of our array access protocol extends that of Limbo and provides interactive proofs with 40 bits of statistical security with an amortized cost of 0.42ms of prover time and 2.8KB of communication per memory access, independently of the size of the memory; with multi-threading, this cost is reduced to 0.12ms and 1.8KB respectively. This performance of our public-coin protocol approaches that of private-coin protocol BubbleRAM (ACM CCS 2020, 0.15ms and 1.5KB per access).
ePrint: https://eprint.iacr.org/2022/313
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .