## 2 Some Requirements for Anonymous Authentication  
In mobile network environments, we need the following requirements for anonymous authentication. 1. Dynamic anonymous identity: When an anonymous user uses the same anonymous identity to roam over the mobile network for all sessions, her/his identity may be exposed by analyzing her/his behavior. We think that an anonymous user should use different anonymous identities for different sessions when she/he roams over the mobile network. 2. No relation between any two aliases: The privacy of a mobile user will be broken if the relations between any two aliases of the user are disclosed. 3. No mapping table, which contains the mapping between each real identity and its corresponding anonymous identity, stored in the system operator: The system operator authenticates an anonymous user directly without maintaining a database to record a mapping between all of the user's anonymous identities and the user's real identity. This will make it possible for the user to gain her/his privacy against the system, and the system can save its storage space. 4. Authenticated key agreement: After anonymous authentication between the system and an anonymous user, a shared session key will be established. If the user shares a long-term key with the system in advance and derives the session key via the shared long-term key, the system can trace her/him by recognizing the long-term key embedded in the session key. Hence, in order to preserve user anonymity, the system and the user have to establish their session key without sharing any key or information in advance. Besides, all session keys should be mutually independent from each other. 5. Traceability in some situations: If there exist malicious users, a trusted third party must be able to revoke their privacy. An anonymous authentication protocol should own the feature of revokable anonymity in order to deal with the above situation. 6. Credit-based chargeability: When a user conceals her/his identity from the system operator, it will be hard for the system to charge the anonymous user after she/he utilizes the network services. An anonymous authentication scheme for mobile communications should allow the system operator to charge anonymous mobile users via the popularized credit-based way without revealing their identities. The credit-based chargeability in the proposed system means that any user does not need to pay, even pay with a credit card, before she/he uses the services of the system. Every consumption of the user will be accumulated in her/his ticket. The ticket has a life cycle and the user should return the ticket to the system at the end of the cycle, say the end of each month. Finally, the system will send the user a bill which includes the total amount of the consumption retrieved from the ticket. 7. **The Proposed Protocols** First, we define and explain some notations as follows:  
1. \(MS\), \(H\), \(V\): These are three participants in our protocols. \(MS\) is a mobile user, \(H\) is the server of the home network, and \(V\) is the server of a visiting network. 2. \(ID_{MS}\): the real identity of \(MS\). 3. \(E_{x}\), \(D_{x}\): \(E_{x}\) is a semantic secure encryption function [15] and \(D_{x}\) is the decryption function corresponding to \(E_{x}\) where \(x\) can be an input symmetric key or public/private key. 4. \(k_{ms_{h}}\), \(k_{ms_{y}}\), \(k_{y_{h}}\): The shared session keys between \(MS\) and \(H\), \(MS\) and \(V\), and \(V\) and \(H\), respectively. 5. \((pk_{J},sk_{J})\) and \((pk_{V},sk_{V})\): \((pk_{J},sk_{J})\) is the public/private key pair of the judge and \((pk_{V},sk_{V})\) is the public/private key pair of \(V\). 6. \(l_{r}\): a security parameter. 7. \(F_{1}\), \(F_{2}\), and \(F_{3}\): three one-way hash functions. 8. A judge device: The judge issues a tamper-resistant device which contains {a random-number generator, a symmetric-key cryptosystem, a public-key cryptosystem, a public-private key pair of the judge, \(F_{1}\), \(F_{2}\)}. This device will be integrated into the system of \(H\).