Search papers, labs, and topics across Lattice.
This paper investigates the relationship between weak Zero-Knowledge (ZK) protocols and the existence of One-Way Functions (OWFs) under the assumption of worst-case hard languages in NP. The authors demonstrate that if all languages in NP have Non-Interactive Zero-Knowledge (NIZK) proofs with error rates summing to less than 1, then OWFs exist, improving upon prior work with a weaker condition. Furthermore, they show that similar conditions on $k$-round public-coin ZK proofs imply the existence of OWFs or infinitely-often OWFs.
Weaker-than-ever zero-knowledge protocols are now shown to imply the existence of one-way functions, even when completeness, soundness, and zero-knowledge error rates are non-negligible.
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.
