1970-01-01

(2026-02) Non-Trivial Zero-Knowledge Implies One-Way Functions

• [[Suvradip Chakraborty]]
• [[James Hulett]]
• [[Dakshita Khurana]]
• [[Kabir Tomer]]

2026-02-19

• #cryptography
• #paper

Abstract

A recent breakthrough [Hirahara and Nanashima, STOC’2024] established that if $\mathsf{NP} \not \subseteq \mathsf{ioP/poly}$, the existence of zero-knowledge (ZK) with negligible errors for $\mathsf{NP}$ implies the existence of one-way functions (OWFs). This work obtains a characterization of one-way functions from the worst-case complexity of zero-knowledge in the high-error regime.

Assuming $\mathsf{NP} \not \subseteq \mathsf{ioP/poly}$, we show that any non-trivial, constant-round public-coin ZK argument for NP implies the existence of OWFs, and therefore also (standard) four-message zero-knowledge arguments for $\mathsf{NP}$. Here, we call a ZK argument non-trivial if the sum of its completeness, soundness and zero-knowledge errors is bounded away from 1.

As a special case, we also prove that non-trivial non-interactive ZK (NIZK) arguments for $\mathsf{NP}$ imply the existence of OWFs. Using known amplification techniques, this also provides an unconditional transformation from weak to standard NIZK proofs for all meaningful error parameters. Prior work [Chakraborty, Hulett and Khurana, CRYPTO’2025] was limited to NIZKs with constant zero-knowledge error $\varepsilon_{\mathsf{zk}}$ and soundness error $\varepsilon_{\mathsf{s}}$ satisfying $\varepsilon_{\mathsf{zk}} + \sqrt{\varepsilon_{\mathsf{s}}} < 1$.