URIs, or physical addresses (e.g., IP addresses). Most of the previously mentioned approaches support anonymity (of sender or receiver) in C 2009 by Taylor & Francis Group, LLC Anonymity in SIP transit and do not have extensions to support the transactions unlinkability feature. Finally, TOR, the second generation Onion Routing service, might be immune to this location tracing attack, basically because it supports ren- dezvous points and location-hidden services. A promising privacy system that overcomes these drawbacks is Mist. Mist [10] handles the problem of routing a message though a network while keeping the sender's location private from intermediate routers, the receiver and potential eavesdroppers. The system consists of a number of routers, called Mist routers, ordered in a hierarchical structure. According to Mist, special routers, called "Portals", are aware of the user's location, without knowing the corresponding identity, while "Lighthouse" routers are aware of the user's identity without knowing his/her exact location. We will discuss Mist in more detail in the next section. When practical issues arise, proxy servers offer anonymity services on the World Wide Web. For instance the Anonymizer.com provides proxy services via rewriting URLs such that a link to e.g., http://www.you.gr might be rewritten ashttps://anonymity.proxy.net/www.you.gr. SSL encryption is used to ensure confidentiality of the connections between the end-user and the proxy server. Another theoretical model for ensuring anonymity is the k-anonymity con- cept [17,18] which was earlier introduced in the context of relational data privacy. It addresses the question of how a data holder can release its pri- vate data with guarantees that the individual subjects of the data cannot be identified while the data remain practically useful [19]. Regarding LBSs and mobile clients, location k-anonymity refers to the k-anonymity usage of loca- tion information. A subject's location is considered k-anonymous if and only if the location informat