Fall 2019

Subquadratic SNARGs in the Random Oracle Model

Monday, December 7th, 2020 10:00 am10:40 am

Add to Calendar


Eylon Yogev (Boston University and Tel Aviv University)

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 many attractive features. However, it also has a significant drawback: a large argument size.

In this talk, I will describe 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. 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 is achievable in the ROM.

Joint work with Alessandro Chiesa