1
$\begingroup$

"The Ali Baba cave" example of ZKP is pictured below. There is no need for a probabilistic ZKP protocol to prove to the verifier of the statement (that the prover has the key to the door). It can be proved deterministically without the prover revealing any knowledge/information.

Assume that both the verifier and prover are both initially positioned at one side of the door. The verifier first walks back to the entrance. The prover opens the door and walks to the entrance to meet the verifier using the opposite route that the verifier took. Hence the prover proves to the verifier deterministically, without the need for repeated experiments. enter image description here

$\endgroup$
5
  • $\begingroup$ I can't understand what you are asking or what kind of answer you are looking for. Please edit your question to clarify what your question is. $\endgroup$
    – D.W.
    Jan 24, 2022 at 22:45
  • $\begingroup$ @D.W. I am referring to the "The Ali Baba cave" example of ZKP. There is no need for a probabilistic protocol to prove to the verifier of this statement. It can be proved deterministically without the prover revealing any knowledge/information. My question is why is ZKP used in this example. $\endgroup$
    – Anon
    Jan 24, 2022 at 22:48
  • $\begingroup$ Please don't explain in the comments -- please edit your post so it's clear what you're asking. I know the example but I don't know what you're asking. I suspect you have some assumptions or premises that may be faulty but I can't tell based on your current question, so it might be helpful to provide more context and more of your reasoning. $\endgroup$
    – D.W.
    Jan 24, 2022 at 22:50
  • $\begingroup$ @D.W. Is my explanation clearer? $\endgroup$
    – Anon
    Jan 24, 2022 at 23:05
  • $\begingroup$ @Anon, you can imagine that the door is controlled by a lock that is visible from both sides of the door. When the prover is opening the door, the verifier can actually observe (the shape of) the key. Thus, your deterministic protocol cannot be zero-knowledge. $\endgroup$
    – John L.
    Jan 25, 2022 at 3:14

2 Answers 2

1
$\begingroup$

Yes, in cave example, it is possible to prove with a deterministic protocol. Why do people use a probabilistic proof in the cave example? Because that follows more closely to how most computational zero knowledge proofs work. Most computational zero knowledge proofs are probabilistic, and this is intended to be an analogy that helps you understand computational zero knowledge proofs. For computational zero knowledge proofs, it's usually not so easy to make a deterministic proof; often it's easier to find a probabilistic proof. The cave example is only an example intended to help give you some intuition that will be helpful to you when you study computational zero knowledge proofs, so don't worry too much about the details.

$\endgroup$
1
$\begingroup$

The example proves something stronger. Alice proves to Bob that she knows the secret word, but she actually only proves it to Bob. This is the reason, as in your illustration, Bob is initially waiting outside the cave.

Suppose that Bob was equipped with a camera and that Bob followed her to the entrance. Then he would have proof (on camera) that she knows the secret word.

But in the situation you have, even if Bob records the entire process, no-one would be convinced that Alice knows the secret word; Alice and Bob could have agreed on the order beforehand.

(Of course, he could still prove it for the world if he recorded the coin flips, what do I know ...)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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