Cryptography Reference
In-Depth Information
choice of
entrances to
inner cave
stone
doorway
A
B
main cave
entrance
Figure 8.4.
Popular analogy of a zero-knowledge mechanism
8.6.2
Zero-knowledge analogy
We will avoid discussion of the details of any zero-knowledge mechanism, but
instead present a popular analogy in which we will play the role of verifier. The
setting is a cave shaped in a loop with a split entrance, as depicted in Figure 8.4.
The back of the cave is blocked by a stone doorway that can only be opened by
using a secret key phrase. We wish to hire a guide to make a circular tour of the
entire cave system but need to make sure in advance that our guide knows the
key phrase, otherwise we will not be able to pass through the doorway. The guide,
who will be our prover (the entity authentication claimant), is not willing to tell
us the key phrase, otherwise there is a risk that we might go on our own tour
without hiring him. Thus we need to devise a test of the guide's knowledge before
we agree to hire him.
The guide has a further concern. For all he knows, we are from a rival guiding
company and are trying to learn the key phrase. He wants to make sure that no
matter how rigorous a test is run, we will not learn
anything
that could help us to
try to work out what the key phrase is. Putting it another way, he wants to make
sure that the test is a zero-knowledge mechanism that verifies his claim to know
the key phrase.
So here is what we do:
1. We wait at the main cave entrance and send the guide down the cave to the
place where it splits into two tunnels, labelled
A
and
B
. We cannot see this
tunnel split from the main entrance, so we send a trusted observer down with
him, just to make sure he does not cheat during the test.
2. The guide randomly picks a tunnel entrance and proceeds to the stone door.
3. We toss a coin. If it is heads then we shout down the cave that we want the
guide to come out through tunnel
A
. If it is tails then we shout down the cave
that we want the guide to come out through tunnel
B
.
4. The observer watches to see which tunnel the guide emerges from.
