Zero Knowledge in the Cave

[Nomen Nescio]

Zero Knowledge in the Cave

There is a cave with a large entry room.  From this room lead two
passageways, 1 and 2.  Each of 1 and 2 branches into a myriad of smaller
passages, twisting and turning through the massive rock formation.
The passageways go on for miles and have never been fully explored.

One of the big questions has been whether passageways 1 and 2 ever
connect up.  Is there a way of getting from 1 to 2?  Many have
searched, but none have ever succeeded.  Most people believe that
no connection will ever be found.

At least, no one used to.  Now an explorer comes to you and claims to
have found a passage from 1 to 2, not a very long one, either.  He will
prove it to you, but to you alone.  Being a secretive type, he wants no
one else to know.  If you accompany him to the cave, he will prove the
existence of the passageway to you.

But there's a problem.  You carry a video camera and record everything
that you see.  If he shows you the existence of the passage, you will
be able to show the video tape to others, and they will learn of its
existence as well.

Not to worry, he says.  Come with me.  So you enter the large entry room
of the cave together.

Now the simplest thing to do in order to demonstrate the existence of the
connection would be for him to leave through passage 1 and return through
passage 2.  He could easily do this.  However, your film record of the
event would prove to anyone else who saw it that there was a connection.
Another way must be found.  The explorer tells you what to do.

Following his instructions, you leave the entry room for a few minutes,
while the explorer enters one of the passageways.  You then re-enter the
room, and loudly call out one of the passageway numbers, either 1 or 2.
In a few minutes, the explorer comes out of the requested passageway.
You then leave the cave and repeat the process many times.  Each time, the
reporter enters one of the passageways unknown to you; when you return and
name one of them, he is able without fail to exit from the named passage.

You reason that if there were no connection between the passageways,
the only way the explorer could come out the passage that you named
would be if he had gone in that same one.  He would have to guess
which one you were going to choose, and if he were right, he could
come out that one.  But you have repeated the test dozens of times.
The chances that someone could guess right so often is infinitisimal.
The only logical explanation is that the passageway does exist.

Excited, you return to the tavern where you met the explorer and show
the other patrons your tape.  But to your surprise, they just laugh.
They don't deny that the tape is real, that the explorer did come out
of the passageway you named.  But they don't believe in the connection.

Instead, they claim you are in league with the explorer in an attempt to
perpetrate a fraud.  You have simply predetermined together the sequence
of numbers you would call out.  Each of you has memorized the sequence,
and so each time the explorer is able to anticipate the number you will
call next.  He enters that passage and is able, after a suitable pause,
to exit from that same one when you call its number.

You leave the bar, frustrated.  You are convinced that the connection
exists, but even though the tape shows all of the evidence that was so
convincing to you, no one else finds it persuasive.  The explorer has
achieved his goal of proving the existence of the connection to you and
you alone.

Questions for the student:

1. How could you have done things differently, to produce a tape that
would be convincing to others?

2. What counter-measures and conditions could the explorer have put in
place to prevent you from getting a convincing tape in this manner?

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com