## CryptoDB

### Paper: Subquadratic SNARGs in the Random Oracle Model

Authors: Alessandro Chiesa , UC Berkeley Eylon Yogev , Tel Aviv University DOI: 10.1007/978-3-030-84242-0_25 (login may be required) Search ePrint Search Google Slides CRYPTO 2021 In a seminal work, Micali (FOCS 1994) gave the first succinct non-interactive argument (SNARG) in the random oracle model (ROM). The construction combines a PCP and a cryptographic commitment, and has several attractive features: it is plausibly post-quantum; it can be heuristically instantiated via lightweight cryptography; and it has a transparent (public-coin) parameter setup. However, it also has a significant drawback: a large argument size. In this work, we provide a new construction that achieves a smaller argument size. This is the first progress on the Micali construction since it was introduced over 25 years ago. A SNARG in the ROM is (t,ε)-secure if every t-query malicious prover can convince the verifier of a false statement with probability at most ε. For (t,ε)-security, the argument size of all known SNARGs in the ROM (including Micali's) is Õ((log (t/ε))^2) bits, *even* if one were to rely on conjectured probabilistic proofs well beyond current techniques. In practice, these costs lead to SNARGs that are much larger than constructions based on other (pre-quantum and costly) tools. This has led many to believe that SNARGs in the ROM are inherently quadratic. We show that this is not the case. We present a SNARG in the ROM with a sub-quadratic argument size: Õ(log (t/ε) * log t). Our construction relies on a strong soundness notion for PCPs and a weak binding notion for commitments. We hope that our work paves the way for understanding if a linear argument size, that is O(log (t/ε)), is achievable in the ROM.
##### BibTeX
@inproceedings{crypto-2021-31110,
title={Subquadratic SNARGs in the Random Oracle Model},
publisher={Springer-Verlag},
doi={10.1007/978-3-030-84242-0_25},
author={Alessandro Chiesa and Eylon Yogev},
year=2021
}