Zero Knowledge in the Cave

[Major Variola (ret)]

At 04:20 AM 5/15/03 +0200, Nomen Nescio wrote:
>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.

If so, and if "many have tried", then either:
they have not been systematic xor the passage is deeply in there.
The explorer's traversal rate constrains its depth.

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.

He is risking that you have not put a tracer on him.  So he has a UV
lamp
and a geiger counter.  And carries a fully closed breathing system,
trails
brush behind him to conceal footsteps, etc.
And has sanitized the cave to a much larger depth than he uses.

>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.

Why is the film record assumed more reliable than your recollection?

The time it takes him to demonstrate it constrains the depth of the
solution.

Perhaps he will require you to dose yourself with a time-distorting
amnesic
(E.g., tequila :-) which will make others not believe you?

>Another way must be found.  The explorer tells you what to do.

Merely showing that something can be done (nukes, a blue LED,
public key crypto) motivates others to investigate more,
even without the ability to reverse engineer an instance.
Again, the time it takes for the explorer to solve it constrains
solutions.

>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.

As a counter to the "twin" deception, you give him a tamper-"proof"
sealed token which lets you know that its "him" that emerged.  This does
not
work if Paul Kocher is the explorer :-)

>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.

I don't see why it matters that the entry point is unknown to the
tester.

>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.

This would be rational (to you) even if the entry point is unknown AND
he never
calls off a test.

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.

Infinitismal for large versions of "dozens"

>The only logical explanation is that the passageway does exist.

If the token is untampered with, ie no "identity" fraud.  How good
are the explorer's Flaps & Seals & Forgery friends?

>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?

Use a more believable RNG.  (Eg parity of hash of closing Dow Jones
price
that day, assuming you can't control this (without a lot of
collaborators),
and its publicly verifiable.)  Keep filming as you rush the tape to the
bar.
(If you have a good video processing lab, you might have faked all
outcomes
well in advance, however.  Are we assuming tape is always trustworthy?)

The "zero (public) knowledge" part seems to depend on the observer's
private (but publicly untrustable) generation of random choices.  Is
that the point?

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

He could generate counter-tapes which are also submitted to the bar,
reducing trust in your tapes.  The tequila he splashes you with also
helps
(the UFO abduction discrediting attack on credibility :-)
As does the sudden appearance of extra funds in your bank account.
(Humans reason about other humans motivations.)

Stimulating puzzle.

Of course, we only have to believe what we can verify (or we can
start a religion..), so if it is true in reality, others can verify it,
xor
it was a folie-a-deux, a commonplace phenomenon since the invention
of language.

-----
DSM-IV: Diagnostic criteria for 305.90 Caffeine Intoxication
  A. Recent consumption of caffeine, usually in excess of 250 mg (e.g.,
more than 2-3 cups of brewed coffee).