Paper 2022/313

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

Cyprien Delpech de Saint Guilhem, KU Leuven
Emmanuela Orsini, KU Leuven
Titouan Tanguy, KU Leuven
Michiel Verbauwhede, KU Leuven
Abstract

We show a compiler that allows to prove the correct execution of RAM programs using any zero-knowledge system for circuit satisfiability. 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 such a circuit, we obtain 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. We concretely instantiate our construction with an efficient MPC-in-the-Head proof system, Limbo (ACM CCS 2021). The C++ implementation of our 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
Published elsewhere. SCN 2022
Keywords
zero knowledge MPC-in-the-Head RAM
Contact author(s)
cyprien delpechdesaintguilhem @ kuleuven be
History
2022-07-30: last of 5 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},
      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.