Paper 2026/2805

SNARKs from LWE via Non-black-box Reductions

Abstract

We construct the first succinct non-interactive arguments of knowledge (SNARKs) from the polynomial-hardness of Learning with Errors (LWE) for a subclass of UP languages whose witness unambiguity has a polynomial-size Extended Frege ($\mathcal{EF}$) proof. Our construction achieves the following soundness guarantee: For any fixed sequence of false instances $\{x_\lambda\}_{\lambda\in\mathbb{N}}$, there exists a (non-constructive) constant $c>0$ such that, whenever the uniform random CRS length exceeds $\lambda^c$, the construction achieves infinitely-often soundness for this sequence $\{x_\lambda\}_{\lambda\in\mathbb{N}}$: for any polynomial-time cheating prover $\{\mathcal{A}_\lambda\}_{\lambda\in\mathbb{N}}$, the probability that $\mathcal{A}_\lambda$ outputs an accepting proof for $x_\lambda$ is negligible for infinitely many $\lambda$. As intermediate results, we also obtain: - SNARGs for any NP language that has polynomial-size $\mathcal{EF}$ proofs of witness unambiguity for all instances outside of the language, based on polynomial-hard LWE, achieving the same style of soundness guarantee. - SNARKs for all true instances in any language $L \in \mathsf{UP}$ where every instance has a polynomial-size $\mathcal{EF}$ proof of witness unambiguity, under polynomial hardness of LWE, without soundness guarantees for false instances. To achieve our main result, we employ a non-black-box soundness reduction. Along the way, we introduce a new logical proof system, the \emph{Cryptographic Extended Frege} ($\mathcal{CEF}$) system, which extends $\mathcal{EF}$ with rules for formalizing the indistinguishability in cryptographic security proofs. Building on the Encrypt-hash-and-BARG framework of [Jin–Kalai–Lombardi–Vaikuntanathan, STOC’24], we further obtain SNARGs for NP languages that have $\mathcal{CEF}$ proofs of non-membership, which may be of independent interest.