International Association for Cryptologic Research

International Association
for Cryptologic Research


Proof-Carrying Data From Arithmetized Random Oracles

Megan Chen , Boston University
Alessandro Chiesa , EPFL
Tom Gur , University of Warwick
Jack O'Connor , University of Warwick
Nicholas Spooner , University of Warwick
DOI: 10.1007/978-3-031-30617-4_13 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2023
Abstract: 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 [Eurocrypt'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. To prove the security of cryptographic constructs in the AROM, we give a non-trivial and efficient "lazy sampling" algorithm (a "stateful emulator") for the ARO up to some error. We obtain this construction by developing a toolkit for analyzing cryptographic constructions in the AROM, which uses algebraic query complexity techniques and the combinatorial nullstellensatz.
  title={Proof-Carrying Data From Arithmetized Random Oracles},
  author={Megan Chen and Alessandro Chiesa and Tom Gur and Jack O'Connor and Nicholas Spooner},