Real world example of non-interactive zero knowledge proofs?

Question

I am very interested in finding out more about the non-interactive zero knowledge proofs after reading the simplified and abstract examples about zero knowledge proofs themselves here.

For the NI-ZK, most answers over here are either very technical or on a very generic level that i have a hard time understanding it.

I do understand the concept for using NI-ZK with a common shared string (CRS): Instead of having a challenge from the Verifier, the Prover simulates it. But the CRS is completely known to the Prover and he can look at the consequence of possible commitments, refraining from them if he may be wrong, can't he? If i use the example on wikipedia for ZK proofs:

In this story, Peggy has uncovered the secret word used to open a magic door in a cave. The cave is shaped like a ring, with the entrance on one side and the magic door blocking the opposite side. Victor wants to know whether Peggy knows the secret word; but Peggy, being a very private person, does not want to reveal her knowledge (the secret word) to Victor or to reveal the fact of her knowledge to the world in general.

They label the left and right paths from the entrance A and B. First, Victor waits outside the cave as Peggy goes in. Peggy takes either path A or B; Victor is not allowed to see which path she takes. Then, Victor enters the cave and shouts the name of the path he wants her to use to return, either A or B, chosen at random. Providing she really does know the magic word, this is easy: she opens the door, if necessary, and returns along the desired path.

Now if we replace Victor with a CRS, Peggy would f.e. enter at entry A and look at a position that is the equivalent of her decision (or where would she look?) whether she should leave the cave at A or B, in this case B. But why doesnt she just look it up beforehand? She has the CRS and she knows where she would have to look at if she took either sides - she can just see that if she goes to A first, she is supposed to come out at B. So instead of really committing to A, she secretly sneaks into B and gets out there without having to pass the magic gate.

Answer 1

The argument about Peggy being able to start over is not about NI-ZK proofs, it is about zero knowledge in general.

Zero knowledge does not give you a definite certainty that Peggy actally has the claimed knowledge. In your example, the probability of Peggy being able to cheat is $1/2$ after one round. If we do this for two rounds, the probability that she cheated twice succssfully is $1/4$. This goes on, until there is a satisfying probability, e.g. that Peggy could only cheat with probability of $1/2^{80}$ for 80 rounds.

Now, if we require in a NI-ZK proof that Peggy created a transcript with 80 rounds, she would have to start over for $2^{80}$ times to find such a transcript, if she doesn't have the ability to go back just one round. This has to be enforced, which is done in the Fiat Shamir heuristic by hashing all the previous results. In the CRS model this is achieved by defining the reference string only with a certain distribution and granting no one authority over this choice. This assumption implies, that Peggy can not just go back one step. If she starts over from the beginning, the entire string would change.

From a practical point of view, this is a challenge. The most commonly suggested practical solution would be a trusted third part, like for certificate authorities. But the effort of creating and publishing common reference strings is quite a lot more complex than building a PKI.

For some interesting arguments about this, and a possibly different realization I would suggest reading Cryptography in the Multi-string Model by Groth and Ostrovsky. Especially the introduction is quite interesting and their proposed new setup assumption.

Considering most usages of a CRS in the sense of NI-ZK is that there is usually some property, which is then used in order to prove the ZK property. In regular ZK you give the simulator some kind of advantage, e.g. being able to rewind one step. In this model you use some kind of commitments, which are binding in the real protocol but the advantage of the simulator is that he can decomit his previous commitsments to anything.

Answer 2

The prover can "look at the ... be wrong".
If she doesn't "just look it up beforehand", then that's because
the challenge-function was chosen in some extremely clever way,
and I'm not aware of any reason why such a way should exist.

(Alternatively, they're just after arguments, rather than proofs.)


There are two known ways of constructing NIZK Proofs:

One plugs XB-enhanced trapdoor approximate-bijections
into this paper and these two lecture-note pdfs.
The other uses a commitment scheme that will be binding for
real setup strings and equivocable for simulation setup strings.


I'm not aware of any "real world example"s for understanding the concept.

Answer 3

Any standard Digital Signature algorithm is basically a Zero-Knowledge Proof of Knowledge of the Private Key corresponding to the commonly known Public Key, where the Verifier challenge is derived in part from the message to be signed.