Paper 2023/587

Proof-Carrying Data From Arithmetized Random Oracles

Megan Chen, Boston University
Alessandro Chiesa, École Polytechnique Fédérale de Lausanne
Tom Gur, University of Warwick
Jack O'Connor, University of Warwick
Nicholas Spooner, University of Warwick

Proof-carrying data (PCD) is a powerful cryptographic primitive that allows mutually distrustful parties to perform distributed computation in an efficiently verifiable manner. Known constructions of PCD are obtained by recursively-composing SNARKs or related primitives. SNARKs with desirable properties such as transparent setup are constructed in the random oracle model. However, using such SNARKs to construct PCD requires heuristically instantiating the oracle and using it in a non-black-box way. Chen, Chiesa and Spooner (EC'22) constructed SNARKs in the low-degree random oracle model, circumventing this issue, but instantiating their model in the real world appears difficult. In this paper, we introduce a new model: the arithmetized random oracle model (AROM). We provide a plausible standard-model (software-only) instantiation of the AROM, and we construct PCD in the AROM, given only a standard-model collision-resistant hash function. Furthermore, our PCD construction is for arbitrary-depth compliance predicates. We obtain our PCD construction by showing how to construct SNARKs in the AROM for computations that query the oracle, given an accumulation scheme for oracle queries in the AROM. We then construct such an accumulation scheme for the AROM. We give an efficient "lazy sampling" algorithm (an emulator) for the ARO up to some error. Our emulator enables us to prove the security of cryptographic constructs in the AROM and that zkSNARKs in the ROM also satisfy zero-knowledge in the AROM. The algorithm is non-trivial, and relies on results in algebraic query complexity and the combinatorial nullstellensatz.

Available format(s)
Publication info
A major revision of an IACR publication in EUROCRYPT 2023
proof-carrying datarandom oraclearithmetization
Contact author(s)
megchen @ bu edu
alessandro chiesa @ epfl ch
tom gur @ warwick ac uk
Jack O-Connor @ warwick ac uk
nicholas spooner @ warwick ac uk
2023-04-28: approved
2023-04-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Megan Chen and Alessandro Chiesa and Tom Gur and Jack O'Connor and Nicholas Spooner},
      title = {Proof-Carrying Data From Arithmetized Random Oracles},
      howpublished = {Cryptology ePrint Archive, Paper 2023/587},
      year = {2023},
      doi = {10.1007/978-3-031-30617-4_13},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.