### Subquadratic SNARGs in the Random Oracle Model

Alessandro Chiesa and Eylon Yogev

##### Abstract

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,\epsilon)$-secure* if every t-query malicious prover can convince the verifier of a false statement with probability at most &#949;. For $(t,\epsilon)$-security, the argument size of all known SNARGs in the ROM (including Micali's) is $\tilde{O}((\log (t/\epsilon))^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: $\tilde{O}(\log (t/\epsilon) \cdot \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/\epsilon))$, is achievable in the ROM.

Available format(s)
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
succinct argumentsrandom oracleprobabilistically checkable proofs
Contact author(s)
alexch @ berkeley edu
eylony @ gmail com
History
2021-03-07: revised
See all versions
Short URL
https://ia.cr/2021/281

CC BY

BibTeX

@misc{cryptoeprint:2021/281,
author = {Alessandro Chiesa and Eylon Yogev},
title = {Subquadratic SNARGs in the Random Oracle Model},
howpublished = {Cryptology ePrint Archive, Paper 2021/281},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/281}},
url = {https://eprint.iacr.org/2021/281}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.