International Association
for Cryptologic Research

An $(\epsilon_s, \epsilon_{zk})$-weak non-interactive zero knowledge (NIZK) proof system has soundness error at most $\epsilon_s$ and zero-knowledge error at most $\epsilon_{zk}$. We show that as long as NP is hard in the worst case, the existence of $(\epsilon_s, \epsilon_zk)$-weak NIZK arguments for NP with $\epsilon_{zk} + \sqrt{\epsilon_s} < 1$ for constants $\epsilon_{zk}$ and $\epsilon_s$ implies the existence of one-way functions. As an application, we obtain NIZK amplification theorems based on very mild worst-case complexity assumptions. Specifically, [Bitansky-Geier, CRYPTO'24] showed that $(\epsilon_s, \epsilon_{zk})$-weak NIZK proofs 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 NP $\subseteq$ ioP/poly, then NP $\subseteq$ BPP.

We obtain publicly verifiable Succinct Non-Interactive Arguments (SNARGs) for arbitrary deterministic computations and bounded space non-deterministic computation from well-studied group-based assumptions. In particular, assuming the sub-exponential hardness of the Decisional Diffie-Hellman (DDH) and Quadratic Residuosity (QR) assumptions, we obtain the following results, where n denotes the length of the instance: 1. A SNARG for any language that can be decided in non-deterministic time T and space S with communication complexity and verifier runtime(n+S)·T^{o(1)}. 2. A SNARG for any language that can be decided in deterministic time T with communication complexity n·T^{o(1)} and verifier runtime n·T^{o(1)}.