Zero-Knowledge Mechanisms

We now briefly discuss an even stronger cryptographic primitive that can support entity authentication. Zero-knowledge mechanisms bring security benefits but have practical costs. Nevertheless, it’s worth at least discussing the idea behind them, just to indicate that they are feasible even though they’re not as commonly implemented in real systems as the previously discussed techniques.

Motivation for zero-knowledge

The entity authentication techniques we have looked at so far have two properties we might deem undesirable:

• Requirement for mutual trust: Firstly, they are all based on some degree of trust between the entities involved. For example, passwords often require the user to agree with the server, using a password to establish trust, even if the server only stores a hashed version of the password. As another example, the dynamic password scheme based on challenge-response requires the smart token and the server to share a key. However, there are situations in which entity authentication might be required between two potential adversaries who don’t trust one another enough to share any information.

• Leaking of information: Secondly, they’ll give away some potentially useful information on each occasion they are used. Conventional passwords are catastrophic since the password is fully exposed when it’s entered, and in some cases, it may even remain exposed when transmitted across a network. Our example dynamic password scheme is much better. However, it still reveals valid challenge-response pairs each time it runs (more on this in a later lesson).

It would seem unlikely that entity authentication could be provided in such a way that no shared trust is necessary and no knowledge at all is given away during an authentication attempt. Yet, amazingly, zero-knowledge mechanisms can do precisely this.

The requirement for a zero-knowledge mechanism is that one entity (the prover) must be able to provide assurance of their identity to another entity (the verifier) in such a way that the verifier can’t impersonate the prover later, even after the verifier has observed and verified many different successful authentication attempts.

Zero-knowledge analogy

We’ll avoid discussing the details of any zero-knowledge mechanism but instead present a popular analogy in which we’ll play the role of the verifier. As depicted below, the setting is a cave shaped in a loop with a split entrance. The cave’s back is blocked by a stone doorway that can only be opened using a secret key phrase. We want 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 won’t be able to pass through the doorway.

The guide, who will be our prover (the entity authentication claimant), is unwilling to tell us the key phrase since we might go on our tour without hiring them otherwise. Since the guide won’t tell us the key phrase, we need to devise a test of the guide’s knowledge before we agree to hire them.

The guide has a further concern. For all they know, we might be from a rival guiding company, and we are trying to learn the key phrase. They want to make sure that, no matter how rigorous a test is run, we won’t learn anything that could help us determine the key phrase.

Putting it another way, the guide wants to make sure the test is a zero-knowledge mechanism that verifies their claim to knowing the key phrase.