Abstract: Firstly, an ID-based signature scheme is proposed based on pairings. The bilinearity and non-degeneration of pairings are explored to make the verification result of the signature vary only with the identity of the signer. Then an anonymous authentication scheme is proposed based on the signature scheme. During the authentication, a user chooses a pseudonym by him／herself; then server computes the user’s account index from the pseudonym in order to identify and authenticate the user. With our scheme, users are able to travel incognito and to change their passwords at will. Furthermore, there is no need for server to maintain a table of users’ passwords or pseudonyms. To the best of our knowledge, the proposed scheme realizes for the first time both user anonymity and authentication security requirements over the insecure channel.

Key words: identity-based signature, anonymous authentication, bilinear parings