Measuring relationship anonymity in mix networks

ABSTRACT

Many applications of mix networks such as anonymousWeb browsing require relationship anonymity: it should be hard for the attacker to determine who is communicating with whom. Conventional methods for measuring anonymity, however, focus on sender anonymity instead. Sender anonymity guarantees that it is difficult for the attacker to determine the origin of any given message exiting the mix network, but this may not be sufficient to ensure relationship anonymity. Even if the attacker cannot identify the origin of messages arriving to some destination, relationship anonymity will fail if he can determine with high probability that at least one of the messages originated from a particular sender, without necessarily being able to recognize this message among others. We give a formal definition and a calculation methodology for relationship anonymity. Our techniques are similar to those used for sender anonymity, but, unlike sender anonymity, relationship anonymity is sensitive to the distribution of message destinations. In particular, Zipfian distributions with skew values characteristic of Web browsing provide especially poor relationship anonymity. Our methodology takes route selection algorithms into account, and incorporates information-theoretic metrics such as entropy and min-entropy. We illustrate our methodology by calculating relationship anonymity in several simulated mix networks.

REFERENCES

• 1: Oliver Berthold , Andreas Pfitzmann , Ronny Standtke, The disadvantages of free MIX routes and how to overcome them, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.30-45, January 2001, Berkeley, California, United States
• 2: BRESLAU, L., CAO, P., FAN, L., PHILLIPS, G., AND SHENKER, S. Web caching and Zipf-like distributions: evidence and implications. In Proc. INFOCOM (Volume 1) (1999), pp. 126--134.
• 3: David L. Chaum, Untraceable electronic mail, return addresses, and digital pseudonyms, Communications of the ACM, v.24 n.2, p.84-90, Feb. 1981 [doi>10.1145/358549.358563]
• 4: DíAZ, C., SEYS, S., CLAESSENS, J., AND PRENEEL, B. Towards measuring anonymity. In Proc. 2nd International Workshop on Privacy-Enhancing Technologies (2002), vol. 2482 of LNCS, pp. 54--68.
• 5: Roger Dingledine , Michael J. Freedman , David Hopwood , David Molnar, A Reputation System to Increase MIX-Net Reliability, Proceedings of the 4th International Workshop on Information Hiding, p.126-141, April 25-27, 2001
• 6: DINGLEDINE, R., SHMATIKOV, V., AND SYVERSON, P. Synchronous batching: from cascades to free routes. In Proc. 4th International Workshop on Privacy-Enhancing Technologies (2004), vol. 3424 of LNCS, pp. 186--206.
• 7: PFITZMANN, A., KöHNTOPP, M., AND SHOSTACK, A. Anonymity, unobservability, and pseudonymity - a proposal for terminology. Manuscript, June 2001.
• 8: Michael K. Reiter , Aviel D. Rubin, Crowds: anonymity for Web transactions, ACM Transactions on Information and System Security (TISSEC), v.1 n.1, p.66-92, Nov. 1998 [doi>10.1145/290163.290168]
• 9: SERJANTOV, A., AND DANEZIS, G. Towards an information theoretic metric for anonymity. In Proc. 2nd International Workshop on Privacy-Enhancing Technologies (2002), vol. 2482 of LNCS, pp. 41--53.
• 10: TÓTH, G., HORNÁK, Z., AND VAJDA, F. Measuring anonymity revisited. In Proc. 9th Nordic Workshop on Secure IT Systems (2004), pp. 85--90.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

Additional Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Security

Keywords:
anonymity, mix networks, privacy