Paper 2022/313

Efficient Proof of RAM Programs from Any Public-Coin Zero-Knowledge System

Cyprien Delpech de Saint Guilhem, Emmanuela Orsini, Titouan Tanguy, and Michiel Verbauwhede


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).

Available format(s)
Public-key cryptography
Publication info
Preprint. Minor revision.
zero knowledgeMPC-in-the-HeadRAM
Contact author(s)
cyprien delpechdesaintguilhem @ kuleuven be
emmanuela orsini @ kuleuven be
titouan tanguy @ kuleuven be
2022-03-15: last of 4 revisions
2022-03-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Cyprien Delpech de Saint Guilhem and Emmanuela Orsini and Titouan Tanguy and Michiel Verbauwhede},
      title = {Efficient Proof of RAM Programs from Any Public-Coin Zero-Knowledge System},
      howpublished = {Cryptology ePrint Archive, Paper 2022/313},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.