(2025-07) On Weak NIZKs, One-way Functions and Amplification

Abstract

An $({ϵ}_{\mathsf{s}},{ϵ}_{\mathsf{zk}})$-weak non-interactive zero knowledge (NIZK) argument has soundness error at most ${ϵ}_{\mathsf{s}}$ and zero-knowledge error at most ${ϵ}_{\mathsf{zk}}$. We show that as long as $\mathsf{NP}$ is hard in the worst case, the existence of an $({ϵ}_{\mathsf{s}},{ϵ}_{\mathsf{zk}})$-weak NIZK proof or argument for $\mathsf{NP}$ with ${ϵ}_{\mathsf{zk}}+\sqrt{{ϵ}_{\mathsf{s}}}<1$ implies the existence of one-way functions. To obtain this result, we introduce and analyze a strong version of universal approximation that may be of independent interest.

As an application, we obtain NIZK amplification theorems based on very mild worst-case complexity assumptions. Specifically, [Bitansky-Geier, CRYPTO’24] showed that $({ϵ}_{\mathsf{s}},{ϵ}_{\mathsf{zk}})$-weak NIZK proofs (with ${ϵ}_{\mathsf{s}}$ and ${ϵ}_{\mathsf{zk}}$ constants such that ${ϵ}_{\mathsf{s}}+{ϵ}_{\mathsf{zk}}<1$) can be amplified to make their errors negligible, but needed to assume the existence of one-way functions. Our results can be used to remove the additional one-way function assumption and obtain NIZK amplification theorems that are (almost) unconditional; only requiring the mild worst-case assumption that if $\mathsf{NP}\subseteq ioP/poly$, then $\mathsf{NP}\subseteq \mathsf{BPP}$.