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

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

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
zero knowledgeMPC-in-the-HeadRAM
Contact author(s)
cyprien delpechdesaintguilhem @ kuleuven be
emmanuela orsini @ kuleuven be
titouan tanguy @ kuleuven be
History
2022-03-15: last of 4 revisions
2022-03-07: received
See all versions
Short URL
https://ia.cr/2022/313
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/313,
      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{https://eprint.iacr.org/2022/313}},
      url = {https://eprint.iacr.org/2022/313}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.