Subquadratic SNARGs in the Random Oracle Model
Alessandro Chiesa
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 talk I will describe a construction that achieves a smaller argument size. This is the first progress on the Micali construction since it was introduced over 25 years ago. This is joint work with Eylon Yogev.
Bio:
Alessandro Chiesa is a faculty member in computer science at EPFL and UC Berkeley. He conducts research in complexity theory, cryptography, and security, with a focus on the theoretical foundations and practical implementations of cryptographic proofs that are short and easy to verify. He is a co-author of several zkSNARK libraries, and is a co-inventor of the Zerocash protocol. He has co-founded Zcash and StarkWare Industries. He received S.B. degrees in Computer Science and in Mathematics, and a Ph.D. in Computer Science, from MIT. He is a recipient of a Sloan Research Fellowship (2021), an Okawa Foundation Research Grant (2020), and Google Faculty Research Awards (2018 and 2017). He was included in MIT Technology Review's "35 Innovators Under 35" list in 2018.