ion community [2]: "anonymity is the state of being not identifiable within a set of subjects, the anonymity set". The anonymity set is a sensible met- ric since it associates the sender or receiver anonymity with a set of people and their actions. For instance the receiver anonymity set is the set of peo- ple who could have received a message intercepted by an attacker. Obviously the cardinality of the anonymity set is a measure of anonymity. A user is k- anonymous, or has k-anonymity, if he/she is one of at least k users within a specific anonymity set associated with a particular action. Recently, Serjantov and Danezis defined an information theoretic measure of anonymity [3]: each member of the anonymity set is assigned a probability equal to the likelihood that the member performed the anonymous action. Shannon's entropy is then used to quantify the level of uncertainty, or anonymity, that the members of the anonymity set achieve collectively with respect to their action. To apply the anonymity set concept in SIP we should discriminate roles and actions. Even if various servers, intermediate proxies, and end-entities contribute on SIP, the set of actions, or service building blocks, that they contribute is actually very restricted. Subscription, registration, location (or redirection), call forwarding (or routing), call setup initiation-termination, and, optionally, authentication. Some additional, but proprietary services, such as anti-spitting, could also be reported. This set of actions normally is performed by the entities belonging into two district sets of service providers: those of the callee and those of the caller. Thus, if we consider a model in which an attacker wishes to reveal the identity of the calling parties, we can then define four legitimate parties in a SIP session: the caller, the callee, the service provider of the caller, and the service provider of the callee. In this direction we can define some privacy protection classes: - Caller's absolute anonymity, in which the caller does not 