Revisiting a combinatorial approach toward measuring anonymity

ABSTRACT

Recently, Edman et al. proposed the system's anonymity level [10], a combinatorial approach to measure the amount of additional information needed to reveal the communication pattern in a mix-based anonymous communication system as a whole. The metric is based on the number of possible bijective mappings between the inputs and the outputs of the mix. In this work we show that Edman et al.'s approach fails to capture the anonymity loss caused by subjects sending or receiving more than one message. We generalize the system's anonymity level in scenarios where user relations can be modeled as yes/no relations to cases where subjects send and receive an arbitrary number of messages. Further, we describe an algorithm to compute the redefined metric.

REFERENCES

• 1: Dakshi Agrawal , Dogan Kesdogan, Measuring Anonymity: The Disclosure Attack, IEEE Security and Privacy, v.1 n.6, p.27-34, November 2003 [doi>10.1109/MSECP.2003.1253565]
• 2: 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]
• 3: Sebastian Clauß , Stefan Schiffner, Structuring anonymity metrics, Proceedings of the second ACM workshop on Digital identity management, November 03-03, 2006, Alexandria, Virginia, USA [doi>10.1145/1179529.1179539]
• 4: George Danezis , Roger Dingledine , Nick Mathewson, Mixminion: Design of a Type III Anonymous Remailer Protocol, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.2, May 11-14, 2003
• 5: Yuxin Deng, Jun Pang, and Peng Wu. Measuring anonymity with relative entropy. In Theodosis Dimitrakos, Fabio Martinelli, Peter Y. A. Ryan, and Steve A. Schneider, editors, Formal Aspects in Security and Trust, pages 65--79. Springer, LNCS 4691, 2006.
• 6: Claudia Diaz and Bart Preneel. Reasoning about the anonymity provided by pool mixes that generate dummy traffic. In Information Hiding, pages 309--325. Springer, LNCS 3200, 2004.
• 7: Claudia Diaz, Stefaan Seys, Joris Claessens, and Bart Preneel. Towards measuring anonymity. In Designing Privacy Enhancing Technologies, PET'02, pages 54--68. Springer-Verlag, LNCS 2482, 2002.
• 8: Claudia Diaz , Carmela Troncoso , Andrei Serjantov, On the Impact of Social Network Profiling on Anonymity, Proceedings of the 8th international symposium on Privacy Enhancing Technologies, p.44-62, July 23-25, 2008, Leuven, Belgium [doi>10.1007/978-3-540-70630-4_4]
• 9: Roger Dingledine , Nick Mathewson , Paul Syverson, Tor: the second-generation onion router, Proceedings of the 13th conference on USENIX Security Symposium, p.21-21, August 09-13, 2004, San Diego, CA
• 10: Matthew Edman, Fikret Sivrikaya, and Bülent Yener. A combinatorial approach to measuring anonymity. In Intelligence and Security Informatics, 2007 IEEE, pages 356--363, 2007.
• 11: Matthias Franz, Bernd Meyer, and Andreas Pashalidis. Attacking unlinkability: The importance of context. In Nikita Borisov and Philippe Golle, editors, Privacy Enhancing Technologies, pages 1--16. Springer, LNCS 4776, 2007.
• 12: David M. Goldschlag , Michael G. Reed , Paul F. Syverson, Hiding Routing Information, Proceedings of the First International Workshop on Information Hiding, p.137-150, May 30-June 01, 1996
• 13: Andreas Pfitzmann , Marit Köhntopp, Anonymity, unobservability, and pseudeonymity — a proposal for terminology, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.1-9, January 2001, Berkeley, California, United States
• 14: Michael Reed, Paul Syverson, and David Goldschlag. Anonymous Connections and Onion Routing. In IEEE Journal on Selected Areas in Communications, 16(4):482--494, 1998.
• 15: Alfred Rényi. On measures of entropy and information. In 4th Berkeley Symposium Mathematical Statistics and Probability, 1:547--561, 1961.
• 16: Andrei Serjantov and George Danezis. Towards an information theoretic metric for anonymity. In Designing Privacy Enhancing Technologies, PET'02, pages 41--53. Springer-Verlag, LNCS 2482, 2002.
• 17: Claude Shannon. A mathematical theory of communication. In The Bell System Technical Journal, 27:379--423:623--656, 1948.
• 18: Gergely Tóth, Zoltán Hornák, and Ferenc Vajda. Measuring anonymity revisited. In 9th Nordic Workshop on Secure IT Systems, pages 85--90, 2004.
• 19: Peter Palfrader Ulf Moller, Lance Cottrel and Len Sassaman. Mixmaster protocol - version 2. http://www.abditum.com/mixmaster-spec.txt, 2003.
• 20: Ye Zhu , Riccardo Bettati, Anonymity vs. Information Leakage in Anonymity Systems, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, p.514-524, June 06-10, 2005 [doi>10.1109/ICDCS.2005.13]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Complexity measures

General Terms:
Algorithms, Measurement, Theory

Keywords:
anonymity metric, combinatorics, graph theory, privacy