2026-08-14T00:27:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27098 2026-08-12T06:00:27Z ddc:004 open_access

Weak Zero-Knowledge and One-Way Functions Chatterjee, Rohit Li, Yunqi Vasudevan, Prashant Nalini One-way functions zero-knowledge 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+√{ε_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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rohit Chatterjee and Yunqi Li and Prashant Nalini Vasudevan 2026 Is Part Of LIPIcs, Volume 385, 7th Conference on Information-Theoretic Cryptography (ITC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITC.2026.5 urn:nbn:de:0030-drops-270987 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2026.5 eng https://creativecommons.org/licenses/by/4.0/legalcode