CryptoDB
On Weak NIZKs, One-way Functions and Amplification
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2025 |
| Abstract: | 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. |
BibTeX
@inproceedings{crypto-2025-35740,
title={On Weak NIZKs, One-way Functions and Amplification},
publisher={Springer-Verlag},
author={James Hulett and Dakshita Khurana and Suvradip Chakraborty},
year=2025
}