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

Megan Chen, Alessandro Chiesa, and Nicholas Spooner

##### 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 $\mathcal{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 $\mathcal{O}$ for all languages in $\mathsf{NP}^{\mathcal{O}}$. Such a SNARK can directly prove a computation about its own verifier. This capability leads to proof-carrying data (PCD) in the oracle model $\mathcal{O}$ based solely on the existence of (standard-model) collision-resistant hash functions. 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 in the LCROM. Then we construct such an accumulation scheme for the special case of a low degree random oracle.

Available format(s)
Category
Foundations
Publication info
A major revision of an IACR publication in EUROCRYPT 2022
Keywords
succinct argumentsproof-carrying datarandom oracles
Contact author(s)
megchen @ bu edu
alessandro chiesa @ epfl ch
nicholas spooner @ warwick ac uk
History
Short URL
https://ia.cr/2022/383

CC BY

BibTeX

@misc{cryptoeprint:2022/383,
author = {Megan Chen and Alessandro Chiesa and Nicholas Spooner},
title = {On Succinct Non-Interactive Arguments in Relativized Worlds},
howpublished = {Cryptology ePrint Archive, Paper 2022/383},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/383}},
url = {https://eprint.iacr.org/2022/383}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.