3
$\begingroup$

From my understanding, random oracles (hash functions) are used in the Fiat-Shamir heuristic to generate non-interactive ZKPs. I think I have a good grasp of how interactive ZKPs in this scheme work, but I am still struggling to understand how proofs can become non-interactive, from a high-level perspective.

In the Alibaba Cave example, I understand how interactivity can be used to prove that one party has a secret S. I have seen examples where the prover generates a hash of the solution to predetermined challenges of statistical significance, but how could the verifier recreate the hash of that challenge?

$\endgroup$
1
$\begingroup$

Warning: Oversimplified.

Most, if not all interactive Zero-Knowledge proofs rely on the randomness of the verifier. Taking the Ali Baba cave example, since Alice cannot predict what path Bob wants her to come out of, it is statistically improbable that she will be able to fake the proof, especially when this "experiment" is done multiple times.

In case you don't know, a hash funtion is a pseudo-random function. This means that, given the same input, it will always generate the same output. A cryptographic hash function is a one-way function, one where it is infeasible to create a preimage attack, or simply put, finding X in H(X)=Y, given only Y.

The Fiat-Shamir heuristic simply replaces the verifier's randomness (and therefore the interaction) with a random oracle, or in concrete terms, a cryptographic hash function. Since the prover cannot predict the output of a cryptographic hash function, this provides the randomness necessary for the scheme to work.

In that case, Alice wants to prove that she can unlock the door in a cave C. She goes inside the cave, generates a hash H(C), and depending on the output, goes in either path A or B and comes out the other path. Bob, without ever telling Alice anything, simply checks that Alice went through the correct path (if H(C)=A or H(C)=B) and that she exited through the other path.

You could adapt this to make it harder to fake, by computing H(C||n) instead of H(C), where n is a number starting from 0 that increases by 1 every time the experiment is conducted, and running the experiment multiple times.

This Wikipedia article is a really good one and gives a more concrete example.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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