Computer Science/Discrete Mathematics Seminar I

We revisit the question of whether it is possible to build succinct non-interactive arguments (SNARGs) for all of NP under standard cryptographic assumptions. In particular, we give a candidate non-adaptive SNARG for NP and prove its soundness under

• the learning with errors assumption (or other standard assumptions such as bilinear maps), and 
• a mathematical conjecture about multivariate polynomials over the reals. In more detail, our conjecture is an upper bound on the minimum total coefficient size of Nullstellensatz proofs (Potechin-Zhang, ICALP 2024) of membership in a concrete polynomial ideal.

In this talk, we will discuss the construction, security analysis, and our current understanding of the conjecture. 

Based on joint work with Lali Devadas, Sam Hopkins, Yael Kalai, Pravesh Kothari, and Surya Mathialagan.