Yaxin Tu will will present her General Exam "Separating Succinct Non-Interactive Arguments from Cryptographic Assumptions" on April 15, 2025 at 12pm in CS 401. Committee: Alex Lombardi (adviser), Ran Raz(adviser), and Pravesh Kothari . Link to abstract and reading list: [ https://docs.google.com/document/d/1FmkljJIThGRgeHYmuChrSgzIas9uP2mUL41lulMC... | https://docs.google.com/document/d/1FmkljJIThGRgeHYmuChrSgzIas9uP2mUL41lulMC... ] Abstract: An argument system (computationally sound proof) for NP is succinct and non-interactive, if it contains a single prover-to-verifier message whose length is polylogarithmic the instance and witness sizes. In the past decade, the question of what cryptographic assumptions are sufficient and/or necessary for constructing SNARG, has received answers in both directions. On the one hand, the work of Gentry-Wichs’13 exhibits a barrier of using standard assumptions to construct SNARG, showing that efficient black-box reductions cannot prove the security of any SNARG construction based on any falsifiable cryptographic assumption. On the other hand, a recent line of work bypasses the Gentry-Wichs barrier by constructing SNARG based on iO and one-way functions, with a super-polynomial time security reduction. We prove an impossibility result that rules out black-box constructions of SNARG from polynomially-secure iO and one-way functions. Our result extends the Gentry-Wichs barrier, showing that there’s no black-box SNARG construction from even non-falsifiable assumptions like iO, with an efficient security reduction. Our result also shows that the super-polynomial time reduction is inherent for black-box constructions of SNARG from iO.