Non-Trivial Zero-Knowledge Implies One-Way Functions
2026-02-19 • Cryptography and Security
Cryptography and Security
AI summaryⓘ
The authors build on recent work showing that if zero-knowledge proofs for NP problems have very low error, then one-way functions must exist. They extend this by proving that even zero-knowledge arguments with larger errors (called non-trivial, meaning their total error is less than 1) imply one-way functions, both for non-interactive and interactive protocols. This fills a previously open gap where the sum of certain error terms was at least 1. Their results provide new insights into how worst-case zero-knowledge complexity relates to fundamental cryptographic primitives like one-way functions.
NPzero-knowledge argumentsnon-interactive zero-knowledge (NIZK)one-way functionscompleteness errorsoundness errorzero-knowledge errorinteractive proofspublic-coin protocolsworst-case complexity
Authors
Suvradip Chakraborty, James Hulett, Dakshita Khurana, Kabir Tomer
Abstract
A recent breakthrough [Hirahara and Nanashima, STOC'2024] established that if $\mathsf{NP} \not \subseteq \mathsf{ioP/poly}$, the existence of zero-knowledge with negligible errors for $\mathsf{NP}$ implies the existence of one-way functions (OWFs). In this work, we obtain a characterization of one-way functions from the worst-case complexity of zero-knowledge {\em in the high-error regime}. We say that a zero-knowledge argument is {\em non-trivial} if the sum of its completeness, soundness and zero-knowledge errors is bounded away from $1$. Our results are as follows, assuming $\mathsf{NP} \not \subseteq \mathsf{ioP/poly}$: 1. {\em Non-trivial} Non-Interactive ZK (NIZK) arguments for $\mathsf{NP}$ imply the existence of OWFs. Using known amplification techniques, this result also provides an unconditional transformation from weak to standard NIZK proofs for all meaningful error parameters. 2. We also generalize to the interactive setting: {\em Non-trivial} constant-round public-coin zero-knowledge arguments for $\mathsf{NP}$ imply the existence of OWFs, and therefore also (standard) four-message zero-knowledge arguments for $\mathsf{NP}$. Prior to this work, one-way functions could be obtained from NIZKs that had constant zero-knowledge error $ε_{zk}$ and soundness error $ε_{s}$ satisfying $ε_{zk} + \sqrt{ε_{s}} < 1$ [Chakraborty, Hulett and Khurana, CRYPTO'2025]. However, the regime where $ε_{zk} + \sqrt{ε_{s}} \geq 1$ remained open. This work closes the gap, and obtains new implications in the interactive setting. Our results and techniques could be useful stepping stones in the quest to construct one-way functions from worst-case hardness.