Paper 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 *
Metadata
- Available format(s)
-
PDF
- 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
- 2021-03-07: received
- See all versions
- Short URL
- https://ia.cr/2021/281
- License
-
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}, url = {https://eprint.iacr.org/2021/281} }