## CryptoDB

### Paper: On Succinct Non-Interactive Arguments in Relativized Worlds

Authors: Megan Chen , Boston University Alessandro Chiesa , EPFL Nicholas Spooner , University of Warwick Search ePrint Search Google Slides EUROCRYPT 2022 Succinct non-interactive arguments of knowledge (SNARKs) are cryptographic proofs with strong efficiency properties. Applications of SNARKs often involve proving computations that include the SNARK verifier, a technique called recursive composition. Unfortunately, SNARKs with desirable features such as a transparent (public-coin) setup are known only in the random oracle model (ROM). In applications this oracle must be heuristically instantiated and used in a non-black-box way. In this paper we identify a natural oracle model, the low-degree random oracle model, in which there exist transparent SNARKs for all NP computations *relative to this oracle*. Informally, letting $O$ be a low-degree encoding of a random oracle, and assuming the existence of (standard-model) collision-resistant hash functions, there exist SNARKs relative to $O$ for all languages in $NP^{O}$. Such a SNARK can directly prove a computation about its own verifier. To analyze this model, we introduce a more general framework, the *linear code random oracle model* (LCROM). We show how to obtain SNARKs in the LCROM for computations that query the oracle, given an *accumulation scheme* for oracle queries. Then we construct such an accumulation scheme for the special case of a low degree random oracle.
##### BibTeX
@inproceedings{eurocrypt-2022-31899,
title={On Succinct Non-Interactive Arguments in Relativized Worlds},
publisher={Springer-Verlag},
author={Megan Chen and Alessandro Chiesa and Nicholas Spooner},
year=2022
}