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