Anonymous Authentication Systems

Introduction

Authentication is a process, in which entity S determines whether entity C_h is an authorized one or not. In this chapter, an entity that authenticates entities is called a server, and entities to be authenticated are called clients. Usually server S authenticates client C_h while identifying it. For example, a computer system authenticates users by asking them to show their identities (IDs) and passwords to protect it from being used by unauthorized persons. Namely, a user can use the computer system when it shows an ID and a password and its showing password coincides with the one that is registered with the ID in advance, therefore the computer system in this example can know the correspondences between the users and the services that the users had received from it. However, there are cases where users want to receive services without disclosing their identities. Although a restroom in an office must be protected from trespassers for safety, employees in the office may not want to show their ID and password pairs for their every use of it, because the number of times they had used the restroom, etc. are privacies of the employees, for example. Anonymous authentication mechanisms enable the development of systems that cope with this kind of requirements, and constitute the foundations of almost all kinds of anonymous systems.

Here, to make authentication mechanisms practical, they must have functions to handle clients that lose their eligibilities and that forget their secrets necessary for the authentications (e.g. passwords), in addition to the basic authentication functions. Also in systems where clients are anonymous they may behave dishonestly after they had authenticated successfully, therefore it is desirable that the mechanisms can identify dishonest clients despite that they are anonymous. Then, requirements for anonymous authentication mechanisms can be summarized as below, they are

• 1.

  Only authorized clients are successfully authenticated. This requirement is intensified to untransferability, i.e.

  • a.

    Clients cannot give secrets necessary for authentications to others without losing their eligibilities, or

  • b.

    Anyone cannot impersonate an authorized client by stealing or being informed of secrets necessary for authentications,

• 2.

  No one except a client itself can know the identity of the client that is being authenticated,

• 3.

  No one except a client itself can link a sequence of its past authentication requests,

• 4.

  The server can invalidate eligibilities of clients that secede from the service providing system even without carrying out seceding procedures adequately,

• 5.

  The server can handle clients that forget their secrets necessary for their authentications, and

• 6.

  Although clients are anonymous, the server can identify clients that behaved dishonestly after they had been authenticated successfully, without revealing any privacy of other honest clients.

Among the above requirements, the 3rd and the 6th requirements are not essential, but strongly desirable. Although S cannot directly identify clients that had requested individual authentications even the 3rd requirement is not satisfied, a set of authentication requests from the same client suggest the identity of the client in many cases. Also, anonymous systems make entities cause various kinds of dishonest events much easier than usual systems do because entities are anonymous; therefore the capabilities of identifying dishonest clients are highly desired. Fortunately, any anonymous authentication mechanism can be made satisfy this requirement by exploiting dishonest entity detection mechanisms discussed in sections “Tokens” and “Anonymous Tags” in Part II. Namely, provided that dishonest events are detectable during clients are receiving services, S can identify dishonest clients by using anonymous tokens, and by using homomorphic anonymous tokens or anonymous tag based tokens S can identify them even if dishonest events are detected after the completions of services.