How can we build a ZKP simulator for “Were is waldo?”?

Question

The following link illustrates two possible methods for solving the "Where is Waldo?" puzzle in zero knowledge. http://www.anagram.com/jcrap/Volume_0_1/crv0n1-3.pdf

Let's consider the first method:

How can a Simulator be built for any of the method described above?

I believe that the question above can answered only once the protocol view has been defined. And here is where I am stuck.

One option is to define the view as a video recording of the interactions between Alice and Bob. This video should also include the full cavity search performed by Bob on Alice as this is part of the interaction.
If this is the view used for the protocol, how can a simulator build this view without having knowledge of Waldo's position?
After the cavity search has been performed, Alice (or whoever impersonates Alice) must have knowledge of Waldo position in order to complete the protocol successfully.

If the cavity search is omitted by the recording, then a simulator can build a view without having knowledge of Waldo's position as the cut-out image of Waldo can be replaced with any image of Waldo.

However, I believe that the cavity search should be part of the recording as it is part of the interaction between Alice and Bob.

Answer 1

I think that it would be more suitable to model this as witness hiding, meaning that after the proof it should be still be "computationally hard" to find Waldo. The best place to learn about witness indistinguishability and hiding is either in Oded Goldreich's Foundations of Cryptography (volume 1), or in Uri Feige's PhD Thesis.

In general, witness indistinguishability is a property that just says that it's not possible to distinguish which witness the prover knows. It is not hard to show that zero-knowledge implies witness indistinguishability, but it gets more interesting. For example, parallel repetition of witness indistinguishable proofs preserves witness indistinguishability and reduces soundness. Thus, it is possible to construct 3-round witness indistinguishable proofs for any language in NP (something that is not possible for zero knowledge, at least not for black-box zero knowledge).

Feige also defines witness hiding, which means that if a language is hard and one cannot extract a witness, then even after the proof the verifier cannot extract a witness. For example, consider a randomly sampled tuple $(g,h,g^x,h^x)$. Then, a prover could prove that this tuple indeed is of this form (what we call a Diffie-Hellman tuple) using a zero-knowledge proof. Alternatively, in some cases it may be enough to just prove that it is of this form in a way that ensures that a cheating verifier cannot learn $x$ (or any other witness to this fact). As such, witness hiding is the "one-way function" analog of zero-knowledge; it is much weaker, but makes sense in some cases. Feige showed that any witness indistinguishable proof with two "computationally independent witnesses" (meaning that one cannot learn one witness without the other) is witness hiding.