Dora: Processor Expressiveness is (Nearly) Free in Zero-Knowledge for RAM Programs

Aarushi Goel; Mathias Hall-Andersen; Gabriel Kaptchuk

Paper 2023/1749

Dora: Processor Expressiveness is (Nearly) Free in Zero-Knowledge for RAM Programs

Aarushi Goel, NTT Research

Mathias Hall-Andersen, Galois and Aarhus University

Gabriel Kaptchuk, Boston University and University of Maryland

Abstract

Existing protocols for proving the correct execution of a RAM program in zero-knowledge are plagued by a processor expressiveness trade-oﬀ : supporting fewer instructions results in smaller processor circuits (which improves performance), but may result in more program execution steps because non-supported instruction must be emulated over multiple processor steps (which diminishes performance). We present Dora, a concretely eﬃcient zero-knowledge protocol for RAM programs that sidesteps this tension by making it (nearly) free to add additional instructions to the processor. The computational and communication complexity of proving each step of a computation in Dora, is constant in the number of supported instructions. Dora is also highly generic and only assumes the existence of linearly homomorphic commitments. We implement Dora and demonstrate that on commodity hardware it can prove the correct execution of a processor with thousands of instruction, each of which has thousands of gates, in just a few milliseconds per step.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: Zero-Knowlegde RAM Programs
Contact author(s): aarushi goel @ ntt-research com
ma @ cs au dk
kaptchuk @ bu edu
History: 2023-11-13: approved; 2023-11-12: received; See all versions
Short URL: https://ia.cr/2023/1749
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1749,
      author = {Aarushi Goel and Mathias Hall-Andersen and Gabriel Kaptchuk},
      title = {Dora: Processor Expressiveness is (Nearly) Free in Zero-Knowledge for RAM Programs},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1749},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1749}},
      url = {https://eprint.iacr.org/2023/1749}
}