Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

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

migrated from security.stackexchange.com Feb 7 at 8:45

This question came from our site for Information security professionals.

3 Answers

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.

share|improve this answer
1  
I wonder how many crypto schemes are involved when playing with yourself. –  SteveS Feb 6 at 17:07
    
Would this MAC for anonymous credentials be considered a non-interactive ZK proof? –  makerofthings7 Feb 6 at 17:47
    
"Zero-Knowledge" has a precise definition. This MAC protocol is not ZK (though it uses non-interactive ZK-proofs internally). –  Thomas Pornin Feb 6 at 18:01
add comment

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 (assumung that you have access to ideal heash 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.
share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.