## 2 Some Requirements for Anonymous Authentication
### The Protocol for Charging Mobile Users  
For each mobile user, \(MS\), the system operator, \(H\), calculates her/his bill through the following steps on the due date, \(\gamma\):  
1. \(MS\) returns her/his real identity and unused ticket, \((m^{+},\delta^{*},\sigma^{*},\gamma,s^{*})\), to \(H\) before the due date. 2. \(H\) checks that the ticket does not exist in its database and sends the ticket to the judge device. 3. The judge device verifies if the ticket is valid via (4) and checks if the \(\gamma\) has expired. If true, it computes \((w,r_{j})=D_{sk_{j}}(\sigma^{*})\) and returns the spending value \(w\) to \(H\). 4. \(H\) adds \(w\) to the bill of \(MS\) and deletes the record which indicates that \(MS\) has ever requested a ticket. 5. Send the bill to \(MS\). Besides, if the mobile user wants to request a ticket after the due date, \(\gamma\), she/he should perform the protocol of Section 3.3 again. Our scheme adopts credit-based charging, i.e. the system charges each mobile user after it has finished a sequence of services for the user, just as the practical situation in the real world. It is different from the others which provided approaches of debit-based charging, i.e. each mobile user has to purchase payment token(s) before she/he starts accessing the services provided by the system [6; 12]. What are the differences between charging mobile users in advance and charging them after the services? The followings are the reasons why we design our scheme to charge mobile users via a credit-based way. 1. Adaptability. In current GSM services, almost all of the systems adopt credit-based ways to charge users. 2. Reducing the relations between any two rounds of communication with one token only. There are two possible ways to charge a mobile user in advance (debit-based ways), which are described as follows: 1. The mobile user purchases a set of payment tokens from the system previously where each of the tokens is with a unit of value. In each round of communication, the mobile user sends a proper number of tokens to the system for payment. In this case, it is difficult for the system to derive the relation between any two rounds of communication since the tokens are independent one another. However, this will consume much storage and communication cost for recording and transmitting these tokens. 2. The mobile user purchases only one payment token from the system previously where the token is with a specific value \(w\). In the following round of communication, the mobile user sends the token to the system for payment and then the system returns a new token with value \((w\,-\,w_{1})\) if the user consumes \(w_{1}\) value of that token. In this mechanism, the mobile user just needs to store one token. However, this will cause defective privacy. When the system returns one token with value \((w\,-\,w_{1})\) to the user, the system knows that the user will use the token with value \((w-w_{1})\) in the next round. There exists a relation between these two rounds of communication. Our scheme allows a user to store one token and greatly reduces the relations between any two rounds of communication from the system's point of view. All of the users return their unused tickets to the system for charging and thus the system knows the total spending value of every user in the previous time slot. However, it is difficult for the system to trace a specific user by finding out all of her/his spending values from the spending value pool which contains all spending values of all users in the previous time slot. This is the **subset sum problem**, shown below, which is NP-Hard [19]. The proposed system makes it computationally infeasible to link any two rounds of communication with the assumption of large subset sizes. **Definition 1**.