Paper 2026/1180

SNARGs for NP from Unprovability of Mathematical Theorems

Abstract

Modern cryptography relies on the intractability of computational problems. We present an approach to building cryptography from a new source of hardness: \emph{proving mathematical theorems}. Our main result is a construction of succinct non-interactive arguments (SNARGs) for NP under a new, but natural, assumption on the hardness of proving lower bounds in proof complexity. Specifically, our assumption states that it is impossible to prove, within a weak bounded arithmetic theory, the correctness of certifying hard tautologies against Extended Frege. This assumption is inspired by an informal mathematical challenge proposed by Razborov [Ann. Math. '15], and can be viewed as a generalization of an unconditional unprovability result due to Krajíček and Pudlák [J. Symb. Log. '89]. Our construction is a simple variant of the SNARG construction of Jin, Kalai, Lombardi, and Vaikuntanathan [STOC '24]. While the soundness of their construction was proven only for a subclass of NP, we prove its soundness for all of NP under our assumption. At the heart of our result is the observation that cryptographic reasoning is simple in a formal sense: the security proof of most cryptographic primitives can be formalized in a weak theory. In particular, we show how to formalize the scheme of Jin et al. in Jeřábek's theory $\mathsf{APC}_1$ [J. Symb. Log. '07], a weak theory of bounded arithmetic.