What is a Non-Interactive Zero Knowledge Proof?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

Consider the NP language SAT. A Non-Interactive proof for SAT is the following:

• The Prover given an instance of SAT (namely, a boolean formula on n-variable) return to the Verifier a valid assignment.

• The verifier given an instance and a proof applies the assignment defined by the proof on the instance and check if it evaluate to 1.

Obviously, this proof system is not Zero-Knowledge, in fact here the verifier learns that the instance is in SAT but also learn the a valid assignment for the instance sets, for example, the variable x_1 to 0 and the variable x_6 to 1.

Now, we would like to have the same concept of ZK in the setting above where there is no interaction between the prover and the verifier. So the idea of NIZK is a proof system where a prover can produce a proof without any interaction, and this proof should be reveal the only knowledge that the instance is valid.

The standard definition of ZK assumes the existence of a simulator that provide "good-looking" proof without having access to the witness. It is easy to see that this definition cannot be used here straightly. Why? well, if such simulator exists then either we break the soundness or the language is in BPP. The simulator, in fact, can produce valid good-looking proof for instance $x\in L$ but what happen if we feed it with an instance $x\not\in L$: there are two cases: 1) it produces a good-looking proof, but now we have an adversary that breaks soundness (namely, a machine that can convince the verifier with a proof for a false statement), 2) it cannot produce a good-looking proof, but now we have a probabilistic machine that can decide the language $L$ efficiently, therefore $L \in BPP$.

Because of this impossibility result, we need to give to the simulator some extra power, one way to do this is to relying on a trusted-setup assumption as the CRS model. This is how usually NIZK are formulated:

There exists some good randomnes in the sky which is a common parameter for the verifier and the prover, and the NIZK provided by the prover depends on it.

The simulator gains some extra power because, in the ideal world, it can control the randomness that comes from the sky.

So to define (or one, more precisely, to define one of the possible flavor of NIZK) one require the existence two simulators $S_0,S_1$ where the first one can generated a good looking common reference string (with a trapdoor known only by the simulator) and the second can generate good-looking proof for valid statement.

In the random oracle model the concept is similar, the good randomness that comes from the sky is the RO, the simulator as extra power because it can programs/interact with the RO.

Answer 4

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.