💻 computer science

Non-Trivial Zero-Knowledge Implies One-Way Functions

Assuming $\mathsf{NP} \not \subseteq \mathsf{ioP/poly}$ , this paper establishes that the existence of non-trivial zero-knowledge arguments (where the sum of completeness, soundness, and zero-knowledge errors is bounded away from 1) for $\mathsf{NP}$ implies the existence of one-way functions, thereby closing a critical gap in the high-error regime for both non-interactive and interactive settings.

Original authors: Suvradip Chakraborty, James Hulett, Dakshita Khurana, Kabir Tomer

Published 2026-02-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Suvradip Chakraborty, James Hulett, Dakshita Khurana, Kabir Tomer

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Magic Trick" and the "Lock"

Imagine you are trying to prove to a friend that you know the secret combination to a safe, but you don't want to tell them the combination. You perform a Zero-Knowledge Proof (ZK). It's like a magic trick where you convince the friend you have the key without ever showing it.

For decades, cryptographers have asked a fundamental question: What is the absolute minimum "magic" required to make these tricks work?

The answer they've been looking for is One-Way Functions (OWFs). Think of a One-Way Function as a "digital lock" that is incredibly easy to lock (multiply two huge numbers) but incredibly hard to unlock (factor the result) without the key. If these locks exist, we can build almost all of modern cryptography.

The big mystery was: Do we need these "digital locks" to exist just to have a Zero-Knowledge proof, or can we do the trick with weaker, "flimsier" magic?

The Problem: The "Almost-Perfect" Trick

In the past, researchers proved that if you have a perfect Zero-Knowledge proof (where the chance of cheating or leaking info is tiny, like 1 in a billion), then One-Way Functions must exist.

But what if the proof isn't perfect? What if it's a bit sloppy?

Maybe the prover sometimes fails to convince the verifier (Completeness error).
Maybe a cheater can sometimes trick the verifier (Soundness error).
Maybe the verifier learns a tiny bit of info (Zero-Knowledge error).

If the sum of these errors is less than 1 (meaning the proof is still "non-trivial" and actually does something useful), does that still force One-Way Functions to exist?

Previous research said "No, not necessarily." They thought if the errors were too high (close to 1), the proof was too weak to prove anything about digital locks.

The Breakthrough: The "Repetition" Strategy

This paper says: "Yes! Even a sloppy, non-trivial proof implies One-Way Functions exist."

Here is how they figured it out, using a simple analogy:

1. The "Bad" Simulator (The Counter-Example)

Imagine a magician (the Simulator) who is supposed to fake the proof. In a "bad" scenario, the magician might pick a random card. Sometimes the card is a "winning" card, sometimes it's a "losing" card.

If the magician picks a "losing" card, the proof fails.
If the magician picks a "winning" card, the proof works.

Previous methods tried to catch the magician by looking at the card once. If the errors were high, the magician could just say, "Oh, I picked a losing card this time," and the math would break down. The proof seemed useless.

2. The "Repetition" Rescue

The authors of this paper realized: Why look at the card just once? Let's ask the magician to pick a card 1,000 times!

The Strategy: Instead of checking one proof, the researchers imagine a "Super-Verifier" who asks the simulator to generate the proof over and over again.
The Logic: If the simulator is truly "bad" (meaning it's just guessing and not actually knowing the secret), it will eventually run out of "winning" cards. It will fail to produce a valid proof most of the time.
The Result: By repeating the process, the "noise" (errors) gets washed out. Even if the original proof was sloppy, the pattern of the simulator's failures reveals that it doesn't actually know the secret.

This is like trying to find a needle in a haystack. If you look once, you might miss it. But if you look a thousand times, you are guaranteed to find it if it's there. If you don't find it after a thousand tries, you know the needle wasn't there to begin with.

The "Public Coin" vs. "Private Coin" Twist

The paper also deals with a technical distinction:

Public Coin: The verifier flips a coin in the open. Everyone sees the result. (Easy to simulate).
Private Coin: The verifier flips a coin behind a screen. (Harder to simulate).

The authors show that if you have a "Private Coin" proof, it's so hard to simulate that the act of hiding the coin flip itself acts like a One-Way Function (a digital lock). If you can't simulate the private coin flip, you've already found a lock.

The "So What?" (Why does this matter?)

This paper closes a huge gap in our understanding of cryptography.

No "Free Lunch": You cannot build a useful Zero-Knowledge proof without the fundamental building blocks of cryptography (One-Way Functions). Even a "weak" proof requires "strong" math.
Amplification: Because we now know that any non-trivial proof implies One-Way Functions exist, we can use those functions to "fix" the sloppy proof. We can take a proof with high errors and mathematically "amplify" it until it becomes a perfect, standard proof.
- Analogy: Imagine you have a blurry photo. This paper proves that if the photo has any recognizable detail, you can use a specific tool (the One-Way Function) to sharpen it into a high-definition image.

Summary in One Sentence

This paper proves that any Zero-Knowledge proof that actually works (even a sloppy one) is strong enough to prove that "digital locks" (One-Way Functions) exist, and therefore, we can use that proof to build perfect, secure cryptographic systems.

1. Problem Statement

The paper addresses a fundamental question in cryptography and complexity theory: What are the minimal assumptions required to construct Zero-Knowledge (ZK) proof systems?

Historically, it was known that ZK for NP implies the existence of One-Way Functions (OWFs) under the assumption that NP is hard on average. More recently, Hirahara and Nanashima (HN24) showed that even the worst-case hardness of NP (specifically $NP \not\subseteq ioP/poly$ ) suffices to derive OWFs from ZK, provided the ZK system has negligible errors.

However, a significant gap remained regarding non-trivial ZK systems with large (non-negligible) errors.

The Gap: A ZK system is considered "trivial" if the sum of its completeness error ( $\epsilon_c$ ), soundness error ( $\epsilon_s$ ), and zero-knowledge error ( $\epsilon_{zk}$ ) is $\ge 1$ . Such systems can be constructed without any cryptographic assumptions (e.g., by randomly choosing to always accept, always reject, or reveal the witness).
The Question: If a ZK system is non-trivial (i.e., $\epsilon_c + \epsilon_s + \epsilon_{zk} < 1$ ), does it still imply the existence of One-Way Functions? Previous techniques relied heavily on the errors being small (negligible) and failed when errors were large (e.g., $\epsilon_s + \epsilon_{zk} \approx 1$ ).

2. Methodology and Technical Approach

The authors develop a new framework to bridge the gap between non-trivial ZK and OWFs, moving beyond the limitations of previous "Universal Extrapolation" (UE) and "Universal Approximation" (UA) techniques.

A. The Core Insight: Repetition and "Good" Common Reference Strings (CRS)

Previous works (Ostrovsky-Wigderson, Chakraborty et al.) failed in the high-error regime because they treated the simulator's output as a single distribution. The authors observe that in high-error regimes, the simulator might output "bad" proofs (which are far from real proofs) with high probability, masking the distinction between real and simulated transcripts.

To overcome this, they introduce a repetition strategy:

Sampling: Instead of sampling a single simulated proof, the algorithm samples many proofs for the same Common Reference String (CRS).
Classification: They classify CRSs as "Good" or "Bad":
- Good CRS: The simulator, conditioned on this CRS, produces an accepting proof with non-negligible probability.
- Bad CRS: The simulator almost never produces an accepting proof.
The Argument: If a language $L$ is hard, the real prover always accepts. If the simulator outputs a "Bad" CRS with high probability, the zero-knowledge property is violated because the real prover would accept (on a Bad CRS) while the simulator would not.
Amplification: By repeating the sampling process polynomially, the algorithm can distinguish between $x \in L$ and $x \notin L$ with high confidence, provided $\epsilon_c + \epsilon_s + \epsilon_{zk} < 1$ .

B. Extension to Interactive Protocols

Extending this to interactive (multi-round) ZK is significantly harder because the prover cannot check if a message leads to acceptance without knowing future verifier randomness.

Malicious Prover ( $\tilde{P}$ ): The authors define an inefficient "malicious prover" that, given a partial transcript, samples many possible next messages from the simulator and chooses the one that maximizes the probability of the verifier accepting.
Efficiency via Estimation: To make this efficient, they use Universal Extrapolation to sample candidate messages and estimate their success probability via simulation (since the verifier is public-coin and stateless).
Handling Private Coins: For private-coin protocols, they show that unless auxiliary-input OWFs exist, any constant-round private-coin protocol can be converted to a public-coin one. Thus, non-trivial private-coin ZK implies auxiliary-input OWFs.

C. Decision-to-Inversion Reduction

The core of the proof constructs a Decision-to-Inversion Reduction.

They assume OWFs do not exist.
This implies the existence of a Universal Extrapolation (UE) machine.
Using UE, they construct an algorithm $A$ that decides the language $L$ (which is assumed to be outside $ioP/poly$).
The algorithm $A$ uses the ZK protocol and the UE machine to distinguish between real and simulated transcripts.
If $A$ succeeds, it contradicts the assumption that $L \notin ioP/poly$ , thereby proving that OWFs must exist.

3. Key Contributions and Results

The paper establishes the following main theorems (informal):

Non-Trivial NIZK $\implies$ OWF:
If $NP \not\subseteq ioP/poly$ and there exists a non-trivial Non-Interactive Zero-Knowledge (NIZK) argument for NP (where $\epsilon_c + \epsilon_s + \epsilon_{zk} < 1$ ), then One-Way Functions exist.
- Significance: This improves upon prior work (CHK25) which required stricter bounds like $\epsilon_{zk} + \sqrt{\epsilon_s} < 1$ . The new result holds for any non-trivial error regime.
Non-Trivial Public-Coin ZK $\implies$ Auxiliary-Input OWF:
If $NP \not\subseteq ioP/poly$ and there exists a non-trivial, constant-round, public-coin ZK argument for NP, then auxiliary-input One-Way Functions exist.
- Significance: This is the first characterization of OWFs from worst-case hardness for interactive ZK with large errors.
Non-Trivial Private-Coin ZK $\implies$ Auxiliary-Input OWF:
If $NP \not\subseteq ioP/poly$ and there exists a non-trivial, constant-round, private-coin ZK argument, then auxiliary-input OWFs exist.
- Mechanism: This relies on a reduction showing that if auxiliary-input OWFs do not exist, private-coin protocols can be converted to public-coin ones.
Amplification of ZK:
The results imply that non-trivial ZK proofs can be amplified to standard (negligible error) ZK proofs, almost unconditionally.
- If $NP \subseteq BPP$ , trivial ZK exists.
- If $NP \not\subseteq ioP/poly$ , the existence of non-trivial ZK implies OWFs. Since OWFs + Weak ZK $\implies$ Standard ZK (via known amplification theorems), non-trivial ZK implies standard ZK.

4. Significance and Impact

Completeness of Characterization: The paper provides a complete characterization of the complexity of ZK. It proves that any non-trivial ZK system (even with large errors) is cryptographically as strong as One-Way Functions, assuming worst-case hardness of NP. There is no "weak" ZK that is easier to construct than OWFs.
Removing Assumptions for Amplification: Previously, amplifying weak NIZKs to strong NIZKs required assumptions like Public-Key Encryption or specific error bounds. This work shows that under the mild complexity assumption ( $NP \not\subseteq ioP/poly$ ), non-trivial NIZKs can be amplified to standard NIZKs using only the implied OWFs.
New Techniques for High-Error Regimes: The introduction of the "Good/Bad CRS" classification and the repetition-based analysis offers a new toolkit for analyzing cryptographic protocols with non-negligible errors, which may have applications beyond ZK.
Clarifying the Role of Errors: The work definitively shows that the barrier to constructing OWFs from ZK is not the size of the error, but whether the system is trivial (sum of errors $\ge 1$ ) or non-trivial.

In summary, this work closes a major gap in our understanding of the foundations of cryptography, proving that the existence of any non-trivial Zero-Knowledge proof system for NP is sufficient to build the fundamental primitive of One-Way Functions.