Degree of anonymity

Degree of anonymity

In anonymity networks (e.g. Tor, Crowds, Mixmaster, Tarzan, etc.) it is important to be able to measure quantitatively the guarantee that is given to the system. The degree of anonymity d is a device that was proposed at the 2002 Privacy Enhancing Technology (PET) conference. There were two papers that put forth the idea of using entropy as the basis for formally measuring anonymity: "Towards an Information Theoretic Metric for Anonymity", and "Towards Measuring Anonymity". The ideas presented are very similar with minor differences in the final definition of d.



Anonymity networks have been developed and many have introduced methods of proving the anonymity guarantees that are possible, originally with simple Chaum Mixes and Pool Mixes the size of the set of users was seen as the security that the system could provide to a user. This had a number of problems; intuitively if the network is international then it is unlikely that a message that contains only Urdu came from the United States, and vice-versa. Information like this and via methods like the predecessor attack and intersection attack helps an attacker increase the probability that a user sent the message.

Example With Pool Mixes

AD Pool Mix.jpg As an example consider the network shown above, in here A,B,C and D are users (senders), Q,R,S, and T are servers (receivers), the boxes are mixes, and \{A, B\} \in T, \{A, B, C\} \in S and \{A, B, C, D\} \in Q, R where \in denotes the anonymity set. Now as there are pool mixes let the cap on the number of incoming messages to wait before sending be 2; as such if A,B, or C is communicating with R and S receives a message then S knows that it must have come from ??E?? (as the links between the mixes can only have 1 message at a time). This is in no way reflected in S's anonymity set, but should be taken into account in the analysis of the network.

Degree of Anonymity

The degree of anonymity takes into account the probability associated with each user, it begins by defining the entropy of the system (here is where the papers differ slightly but only with notation, we will use the notation from [1].):
H(X) := \sum_{i=0}^{N-1} \left[p_i \cdot \lg\left(\frac{1}{p_i}\right)\right], where H(X) is the entropy of the network, N is the number of nodes in the network, and pi is the probability associated with node i. Now the maximal entropy of a network occurs when there is uniform probability associated with each node (\frac{1}{N}) and this yields H_M := H(X) \gets \lg(N). The degree of anonymity (now the papers differ slightly in the definition here, [2] defines a bounded degree where it is compared to HM and [3] gives an unbounded definition—using the entropy directly, we will consider only the bounded case here) is defined as
d := 1 - \frac{H_M - H(X)}{H_M} = \frac{H(X)}{H_M}. Using this anonymity systems can be compared and evaluated using a quantitatively analysis.

Definition of Attacker

These papers also served to give concise definitions of an attacker:

an internal attacker controls nodes in the network, whereas an external can only compromise communication channels between nodes.
an active attacker can add, remove, and modify any messages, whereas a passive attacker can only listen to the messages.
a local attacker has access to only part of the network, whereas a global can access the entire network.

Example d

In the papers there are a number of example calculations of d, we will walk through some of them here.


In Crowds there is a global probability of forwarding (pf), which is the probability a node will forward the message internally instead of routing it to the final destination. Let there be C corrupt nodes and N total nodes. In Crowds the attacker is internal, passive, and local. Trivially H_M \gets \lg (N - C), and overall the entropy is H(x) \gets \frac{N - p_f \cdot (N - C - 1) }{N} \cdot \lg\left[\frac{N}{N - p_f \cdot (N - C - 1)}\right] + p_f \cdot \frac{N - C - 1}{N} \cdot \lg\left[N/p_f\right], d is this value divided by HM[4].

Onion routing

In onion routing let's assume the attacker can exclude a subset of the nodes from the network, then the entropy would easily be H(X) \gets \lg(S), where S is the size of the subset of non-excluded nodes. Under an attack model where a node can both globally listen to message passing and is a node on the path this decreases to H(X) \gets \lg(L), where L is the length of the onion route (this could be larger or smaller than S), as there is no attempt in onion routing to remove the correlation between the incoming and outgoing messages.

Applications of this metric

In 2004, Diaz, Sassaman, and DeWitte presented an analysis[5] of two anonymous remailers using the Serjantov and Danezis metric, showing one of them to provide zero anonymity under certain realistic conditions.

See also


  1. ^ See Towards Measuring Anonymity Claudia Diaz and Stefaan Seys and Joris Claessens and Bart Preneel (April 2002). Roger Dingledine and Paul Syverson. ed. "Towards measuring anonymity" ([dead link]Scholar search). Proceedings of Privacy Enhancing Technologies Workshop (PET 2002) (Springer-Verlag, LNCS 2482). Retrieved 2005-11-10. 
  2. ^ See Towards an Information Theoretic Metric for Anonymity Andrei Serjantov and George Danezis (April 2002). Roger Dingledine and Paul Syverson. ed. "Towards an Information Theoretic Metric for Anonymity". Proceedings of Privacy Enhancing Technologies Workshop (PET 2002) (Springer-Verlag, LNCS 2482). Archived from the original on July 19, 2004. Retrieved 2005-11-10. 
  3. ^ See Comparison Between Two Practical Mix Designs Clauda Diaz and Len Sassaman and Evelyn Dewitte (September 2004). Dieter Gollmann. ed. "Comparison Between Two Practical Mix Designs". Proceedings of European Symposium on Research in Computer Security (ESORICS 2004) (Springer-Verlag, LNCS 3193). Retrieved 2008-06-06. 

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Anonymity — This article is about identification. For anonymity in Wikipedia, see Wikipedia:Anonymity. For other uses, see Anonymous (disambiguation) and Anonymus (disambiguation). Anonymity is derived from the Greek word ἀνωνυμία, anonymia, meaning without… …   Wikipedia

  • Anonymous P2P — An anonymous P2P computer network is a particular type of peer to peer network in which the users are anonymous or pseudonymous by default. The primary difference between regular and anonymous networks is in the routing method of their respective …   Wikipedia

  • Deindividuation — is a concept in social psychology regarding the loosening of social norms in groups. Sociologists also study the phenomenon of deindividuation, but the level of analysis is somewhat different. For the social psychologist, the level of analysis is …   Wikipedia

  • Crowds — For other uses, see Crowd. Crowds is a proposed anonymity network that gives probable innocence in the face of a large number of attackers. Crowds was designed by Michael K. Reiter and Aviel D. Rubin and defends against internal attackers and a… …   Wikipedia

  • Proxy server — For Wikipedia s policy on editing from open proxies, please see Wikipedia:Open proxies. Communication between two computers (shown in grey) connected through a third computer (shown in red) acting as a proxy. In …   Wikipedia

  • Onion routing — is a technique for anonymous communication over a computer network. Messages are repeatedly encrypted and then sent through several network nodes called onion routers. Like someone unpeeling an onion, each onion router removes a layer of… …   Wikipedia

  • Anonymous web browsing — is browsing the World Wide Web while hiding the user s IP address and any other personally identifiable information from the websites that one is visiting. Contents 1 Achieving Anonymity 2 Limitations to Proxy Servers 3 Cookies …   Wikipedia

  • List of mathematics articles (D) — NOTOC D D distribution D module D D Agostino s K squared test D Alembert Euler condition D Alembert operator D Alembert s formula D Alembert s paradox D Alembert s principle Dagger category Dagger compact category Dagger symmetric monoidal… …   Wikipedia

  • RIGHTS, HUMAN — The following article deals with the subject of human rights, their essence and the contents of various fundamental rights as reflected in the sources of Jewish Law. The interpretation of Israel s Basic Laws concerning human rights in accordance… …   Encyclopedia of Judaism

  • Assassination market — An assassination market is a prediction market or dead pool where any party can place a bet (using anonymous electronic money, and pseudonymous remailers) on the date of death of a given individual, and collect a payoff if they guess the date… …   Wikipedia