You have just finished exploring a huge cave with a long tunnel that eventually connects with itself, with a magic door in the middle. The magic door has no knob -- instead it requires a secret password to open. When it is closed, the cave can be thought of as an entrance tunnel with two tunnels (tunnel A and tunnel B) branching off of it. These are shown below:

(A map of the cave)

    | |
    | |
    | |
 ___| |___
|  _____  |
| |     | |
| |     | |
| |_____| |
|    #    |
|____#____|

You tell your claim to another person, who is interested but wants proof that you know the secret. You want to show you know, but don't want to share the secret with a stranger. How can you prove to him beyond a reasonable doubt that you know the secret password?

(Assume the other person must stay in the entrance tunnel of the cave.)

Note: In case you can only open it one way, you would like the observer not even to learn which way you can open it.

Guys, go look up "zero-knowledge proofs". This is the classic exemplar for that type of proof/algorithm.

Verifier stands at the mouth of the cave, where they cannot see the door or hear the password.

Prover initially starts at one side of the door which is randomly determined, and unknown to the Verifier.

Verifier shouts out asking the Prover to appear at either the left or right tunnel.

In the simple case where the door is two-way, if the Prover knows the password to open the door, they can fulfill the Verifier's request 100% of the time. If not, they can only fulfill the request 50% of the time.

Repeated iterations will have 0.5^n (n trials) probability of success if the Verifier doesn't know the password. Verifier can choose a sufficiently high n to satisfy themselves of the fact that the Prover actually knows the password.

As for the twist, whereby the door is one way only, the Prover must manipulate the probabilities so that they deliberately fail the test in such a way as to keep the proportion of failures to go from L to R the same as the proportion of failures to go R to L. So long as this property holds on average over repeated trials and the fail rate is not greater than 50%, the Prover should still be able to convince the Verifier that they know the password (and they can even explain to the Verifier that they are deliberately failing in order to protect the second secret: which way the door opens).

The Verifier can still attack the second secret by repeatedly asking the Prover to appear from the same side, eliminating one class of failure (thus making it impossible to equate L->R failures with R->L failures). However, since the Prover may choose which tunnel they start in, and this information is unavailable to the Verifier, they still have this avenue of manipulating the probabilities open to them. This would kind of mess up the analysis, since the Prover, after seeing a repeated set of identical requests, doesn't know whether the Verifier is deliberately using this strategy or will change it in later trials, but if they've decided on the number of trials they're going to have from the outset, they still have scope to manipulate their starting position and failure rates in such a way that both the Verifier is convinced (the success rate is significantly better than chance) and no information about the direction of the door is leaked.

Some commenters mentioned using a rope to prove a full circuit. This would be fine except for the need to preserve the second secret: the Prover wants to be able to repudiate the particular path they took, and a loop in the rope that can't be shrunk to zero would prevent them from repudiating the exact sequence of events (going to starting point + going through door + leaving cave) they took in the trial. Thus introducing a rope makes the second secret insecure.

Posted by Moira on 2009-01-22 00:05:03