CryptoDB
On Succinct Non-Interactive Arguments in Relativized Worlds
| Authors: |
|
|---|---|
| Download: | |
| 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
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
}