Cryptology ePrint Archive: Report 2021/281

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 ε. 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.

Category / Keywords: foundations / succinct arguments; random oracle; probabilistically checkable proofs

Date: received 4 Mar 2021, last revised 7 Mar 2021

Contact author: alexch at berkeley edu,eylony@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20210307:093222 (All versions of this report)

Short URL: ia.cr/2021/281


[ Cryptology ePrint archive ]