International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: On Succinct Non-Interactive Arguments in Relativized Worlds

Megan Chen , Boston University
Alessandro Chiesa , EPFL
Nicholas Spooner , University of Warwick
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2022
Abstract: 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.
Video from EUROCRYPT 2022
  title={On Succinct Non-Interactive Arguments in Relativized Worlds},
  author={Megan Chen and Alessandro Chiesa and Nicholas Spooner},