Proving you know the password without saying it

Question

A cave has an entrance passage that forks into a left path and a right path. The two paths join at the back of the cave, but the junction is blocked by a magic door that opens only when the secret word is spoken. From the fork you cannot see the door.

Peggy claims to know the secret word. Victor is sceptical, but Peggy refuses to tell him the word, and she also refuses to let him watch her open the door.

Design a procedure by which Peggy can convince Victor, beyond reasonable doubt, that she knows the word, without Victor learning anything about the word or being able to convince anyone else.

Accepted Answer

The protocol. 1. Victor waits outside. Peggy enters and walks down either path, left or right, choosing at random, all the way to the door. 2. Victor comes to the fork and calls out "come back by the left path" or "come back by the right path", choosing at random. 3. Peggy appears from the path Victor named. If she happened to be on that side already, she simply walks back. If she was on the other side, she must open the door with the secret word and walk round. 4. Repeat steps 1 to 3 twenty times. Why it convinces Victor. If Peggy does not know the word, she can only come out the way she wen…

Proving you know the password without saying it

Your answer

Discussion

Learn the concepts

Related questions