Identification schemes are methods by which a user may prove his or her identity to somebody else, without revealing essential knowledge that may be used by either an eavesdropper or the recipient to impersonate the user. If Alice authenticates herself to Bob, with Carol eavesdropping, neither Bob nor Carol should be able to impersonate Alice in the future.
A number of such schemes have been described in cryptographic literature. The traditional form of identification is by use of a secret key or password. Alice identifies herself to a server by entering the password for her account. Unfortunately, this scheme is insecure, as an eavesdropper may replay previous messages (e.g. the password) from Alice to the server to impersonate Alice. This is an example of a unilateral identification scheme, as one person in the scheme identifies herself without obtaining identification from the other person.
A more common scheme is the use of digital signatures (see Question 3) and public-key cryptography using challenge-response protocols: Bob keeps challenging Alice with different questions and assesses the answers until he is satisfied that Alice is who she claims to be. In one such scheme, Bob generates a random number and transmits it to Alice. Alice generates a new random number and then digitally signs a message containing both her random number and Bob's. She then sends the signed message, together with her random number, to Bob. Bob verifies the signature to ensure that he is communicating with Alice (one such challenge is enough). This scheme is secure against an eavesdropper; it also prevent Bob from impersonating Alice later. Until this point, the protocol is a unilateral authentication scheme.
To identify himself, Bob may also sign the message containing both random numbers and send the signature back to Alice. Alice verifies the signature to assure herself of Bob's identity. This is an example of a mutual identification scheme, as both parties identify themselves to each other.
See [BDB92] for further information on identification schemes
and zero knowledge protocols (see Question 107), and see [Oka93]
for some examples of identification and signature schemes.