# What is a Non-Interactive Zero Knowledge Proof?

I understand the concept of a Zero Knowledge Proof thanks to the easy to understand analogy of Alibaba's cave. However, this seems to require interaction between the verifier and the other party.

I have not found an explanation of non-interactive zero knowledge proofs (NIZK). The wikipedia article is way too complex for someone without advanced training to understand.

https://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof

Can someone explain the concept of non-interactive zero-knowledge in a simple way?

-

## migrated from security.stackexchange.comFeb 7 '14 at 8:45

This question came from our site for information security professionals.

Isn't this more of an algorithms question? How is this really related to security? – Daisetsu Feb 7 '14 at 1:50

A non-interactive ZK proof is when you play with yourself. Or, more accurately, with an impartial version of yourself.

In a normal ZK proof, the prover first issues a bunch of commitments, then the verifier issues challenges that the prover complies with; this proves anything only as long as the verifier is assumed to issue challenges normally without any prior understanding with the prover.

In a non-interactive ZK proof, the verifier is replaced by a hash function (or something similar) which is computed over the whole set of commitments: the hash function result is the challenge. If the hash function is really a random oracle then the prover cannot guess its output before trying it, i.e. before having produced his commitments, and that's where the security comes from.

-
I wonder how many crypto schemes are involved when playing with yourself. – Steve Feb 6 '14 at 17:07
"Zero-Knowledge" has a precise definition. This MAC protocol is not ZK (though it uses non-interactive ZK-proofs internally). – Thomas Pornin Feb 6 '14 at 18:01
@Steve: Schnorr Signature uses a non-interactive ZK proof. – David 天宇 Wong Dec 23 '14 at 13:04
How would the random oracle concept meet with the definition of zero-knowledge stating that there should exist a simulator who can reproduce the proof in probabilistic polinomial time? How can a simulator find the correct hashes if he does not know the original information? – Onheiron Feb 22 at 19:55
From now on, when I play with myself I will say "I'm making a non-interactive ZK proof" – cygnusv Jul 1 at 9:56

In very simplified terms, a NI-ZK proof works in 2 stages: First, you run the protocol with a simulator (who is just a verifier, but the random choices are done differently), and then you can give the transcript of the protocol to anyone and convince them that the proof is real.

The most important ways to achieve this are:

• In the random oracle model (assuming that you have access to ideal hash functions), you can use the Fiat Shamir heuristic: You replace the verifier with a simulator, and whenever the verifier would have to choose randomly, you use the hash function over the entire protocol so far (most importantly, the commitments of the prover) to emulate a random unpredictable choice. Since the hash function is deterministic, you can't change the value without changing the previous interactions. When you're done with the protocol, you can just take the transcript and give it to someone. However, there is a tradeoff in the security level: If the prover is able to cheat with a certain probability, then he could just try different commitments if he doesn't like the result of the hash function. So in order to get e.g. an error of less than $1/2^{80}$, you would need an error probability of less than $1/2^{160}$ with the hash function replacing true random choices. (And this is why it's called a heuristic, there is no proof for this)
• With a common reference string you can achieve NI-ZK. The common reference string is a random string of symbols, which is drawn from some probability distribution. The assumption is, that these random values are available to all parties, but no party has any influence on their actual choice. And if you simulate the ZK proof with the random choices according to the common reference string, you should get the same result as anyone else validating the protocol transcript. I believe you don't have to double the security parameter in this case (like for Fiat Shamir), but on the other hand a common reference string is harder to realize than a hash function.
-

Intuitively you want to think of NIZK as more of "static" proofs, where once you(the verifier) have a proof transcript (handed to you by the prover), you should be able to use that transcript to convince yourself about the (in)validity of the proof statement, Without needing any further assistance or queries to the verify.

In interactive proof systems, there are more rounds involving more queries and answers between the prover and verifier. NIZK proofs are almost always 1 round.

Now, on a high level overview one might actually wonder what is the use of this, so as it turns out, many protocols (like Undeniable signatures) that use ZKIP to prove the (in)validity of the signatures, are vulnerable to man-in-the-middle attacks, if they use an interactive version, the NIZK is particularly interesting there.

-