Paper Info
Title
Subquadratic Snargs In The Random Oracle Model
Abstract
In a seminal work, Micali (FOGS 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 E. For (t, epsilon)-security, the argument size of all known SNARGs in the ROM (including Micali's) is (O) over tilde((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: (O) over tilde((log(t/epsilon))(2)). 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.
Year
DOI
Venue
2021
10.1007/978-3-030-84242-0_25
ADVANCES IN CRYPTOLOGY (CRYPTO 2021), PT I
Keywords
DocType
Volume
Succinct arguments, Random oracle, Probabilistically checkable proofs
Conference
12825
ISSN
Citations 
PageRank 
0302-9743
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Alessandro Chiesa189946.20
Eylon Yogev213.73