Weak Zero-Knowledge and One-Way Functions
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917279000690688 |
|---|---|
| author | Chatterjee, Rohit Li, Yunqi Vasudevan, Prashant Nalini |
| author_facet | Chatterjee, Rohit Li, Yunqi Vasudevan, Prashant Nalini |
| contents | 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 $ε_c$, $ε_s$, and $ε_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 $ ε_c+ε_s+ ε_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 $ε_c$ is negligible, then they also have NIZK proofs where all errors are negligible. Previously, these results were known under the more restrictive condition $ ε_c+\sqrt{ε_s}+ε_z < 1 $ [Chakraborty et al., CRYPTO 2025].
2. If all languages in NP have $k$-round public-coin ZK proofs or arguments satisfying $ ε_c+ε_s+(2k-1).ε_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 $ ε_c+ε_s+k.ε_z < 1 $, then infinitely-often OWFs exist. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_16156 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Weak Zero-Knowledge and One-Way Functions Chatterjee, Rohit Li, Yunqi Vasudevan, Prashant Nalini Cryptography and Security 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 $ε_c$, $ε_s$, and $ε_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 $ ε_c+ε_s+ ε_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 $ε_c$ is negligible, then they also have NIZK proofs where all errors are negligible. Previously, these results were known under the more restrictive condition $ ε_c+\sqrt{ε_s}+ε_z < 1 $ [Chakraborty et al., CRYPTO 2025]. 2. If all languages in NP have $k$-round public-coin ZK proofs or arguments satisfying $ ε_c+ε_s+(2k-1).ε_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 $ ε_c+ε_s+k.ε_z < 1 $, then infinitely-often OWFs exist. |
| title | Weak Zero-Knowledge and One-Way Functions |
| topic | Cryptography and Security |
| url | https://arxiv.org/abs/2602.16156 |