
On SNARGs for NP and Nullstellensatz Proofs
Alex Lombardi, a cryptographer at Princeton University, presents this Institute for Advanced Study seminar on whether succinct non-interactive arguments (SNARGs) can be built for all of NP under standard cryptographic assumptions. He lays out a candidate non-adaptive SNARG construction and proves its soundness two ways: first under the learning with errors assumption, or alternatively under bilinear maps, and second under a new mathematical conjecture bounding the coefficient size of Nullstellensatz proofs for membership in a specific polynomial ideal, building on Potechin and Zhang's 2024 work. Lombardi walks through the construction itself, the security analysis connecting cryptographic hardness to this algebraic conjecture, and the current state of evidence for and against the conjecture. The talk is based on joint work with Lali Devadas, Sam Hopkins, Yael Kalai, Pravesh Kothari, and Surya Mathialagan, and sits at the intersection of computational complexity, cryptography, and real algebraic geometry.