Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-028 | 18th February 2026 03:52

Weak Zero-Knowledge and One-Way Functions

RSS-Feed




TR26-028
Authors: Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan
Publication: 22nd February 2026 16:26
Downloads: 25
Keywords: 


Abstract:

We study the implications of the existence of weak Zero-Knowledge (ZK) protocols for worst-case hard languages. These are protocols that have completeness, soundness, and zero-knowledge errors (denoted $\epsilon_c$, $\epsilon_s$, and $\epsilon_z$, respectively) that might not be negligible. Under the assumption that there are worst-case hard languages in NP, we show the following:

1. If all languages in NP have NIZK proofs or arguments satisfying $ \epsilon_c+\epsilon_s+\epsilon_z < 1 $, then One-Way Functions (OWFs) exist.

This covers all possible non-trivial values for these error rates. It additionally implies that if all languages in NP have such NIZK proofs and $\epsilon_c$ is negligible, then they also have NIZK proofs where all errors are negligible. Previously, these results were known under the more restrictive condition $ \epsilon_c+\sqrt{\epsilon_s}+\epsilon_z < 1 $ [Chakraborty et al., CRYPTO 2025].

2. If all languages in NP have $k$-round public-coin ZK proofs or arguments satisfying $ \epsilon_c+\epsilon_s+(2k-1).\epsilon_z < 1 $, then OWFs exist.

3. If, for some constant $k$, all languages in NP have $k$-round public-coin ZK proofs or arguments satisfying $ \epsilon_c+\epsilon_s+k.\epsilon_z < 1 $, then infinitely-often OWFs exist.



ISSN 1433-8092 | Imprint