Authentication and anonymity usually are inconsistent. To obtain services, a user must be authenticated. Much of the sensitive information of the user will be exposed to service providers. In order to protect privacy, users must communicate with service providers in an anonymous way. But if the user does not show his true identity, how can the service provider believe that the user is true. This paper presents a secure anonymity authentication protocol for ubiquitous computing which allows service providers to authenticate anonymous users. Anonymity is achieved by separating the linkability of the user's identity information and the action of the user. By finding out objects linkability relationship, we also address an anonymity measure to analyze anonymity and detect the concealing security exposure.

1.   Anonymity Authentication There exist three principals in the anonymity authentication protocol: the user, the service discoverer, and the service provider. The anonymity authentication protocol contains two authentication stages. First, the authentication between the user and the service discoverer which determines the user whether he has the right to access the requested resource. And then the service discoverer makes use of blind signature on the user's public key as a ticket. Second, the service provider authenticates the user, in which the service provider judges the user whether is the genuine user.

2.   Anonymity Measure Linkability is the relation between objects (such as subjects, events, actions etc.) in a system before and after an action occurs. Unlinkability is the sufficient condition of anonymity.

Definition 1 (function decision) Let R denote the object set, X and Y be subsets of R, and X≠Y. If Y can be known from X with probability p, then say X function decision Y, recorded as: X → Y(p).

Definition 2 (function decision set) To the object set R, the function decision set is the set F of function decisions among the objects known by attackers.

Definition 3 (function decision implication) If F is the function decision set known by attackers, let R denote the object set, X and Y be subsets of R, and X≠Y. If X → Y(p) can be deduced from F, then say F implication X → Y(p).

Definition 4 (function decision closure) All the function decision sets implicated by F are called the closure of F, written as F⁺.

Whether user anonymity is protected can be judged by seeing if there are relations between users' location/actions and users' identity in F⁺.