Measuring unlinkability revisited

ABSTRACT

Unlinkability describes the inability of an observer to decide whether certain items of interest are related or not. Privacy aware protocol designers need a consistent and meaningful unlinkability measure to asses protocols in face of different attacks. In this paper we show that entropy measures are not sufficient for measuring unlinkability. We propose an alternative measure that estimates the error made by an attacker. We show by example that our expected distance provides a consistent measure that offers a better estimation of message-unlinkability.

REFERENCES

• 1: Alastair R. Beresford , Frank Stajano, Mix Zones: User Privacy in Location-aware Services, Proceedings of the Second IEEE Annual Conference on Pervasive Computing and Communications Workshops, p.127, March 14-17, 2004
• 2: L. Buttyán, T. Holczer, and I. Vajda. On the effectiveness of changing pseudonyms to provide location privacy in vanets. In Security and Privacy in Ad hoc and Sensor Networks (ESAS), 2007.
• 3: D. Chaum, The dining cryptographers problem: unconditional sender and recipient untraceability, Journal of Cryptology, v.1 n.1, p.65-75, 1988
• 4: C. Díaz, S. Seys, J. Claessens, and B. Preneel. Towards measuring anonymity. In Designing Privacy Enhancing Technologies, 2002.
• 5: M. Franz, B. Meyer, and A. Pashalidis. Attacking unlinkability: The importance of context. In PET Symposium, 2007.
• 6: M.E. Hohn. Binary coefficients: A theoretical and empirical study. Math. Geology, 8(2):137--149, 1976.
• 7: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 8: Jacob Kogan, Introduction to Clustering Large and High-Dimensional Data, Cambridge University Press, New York, NY, 2007
• 9: Bradley Malin, k-Unlinkability: A privacy protection model for distributed data, Data & Knowledge Engineering, v.64 n.1, p.294-311, January, 2008 [doi>10.1016/j.datak.2007.06.016]
• 10: A. Pfitzmann and M. Hansen. Anonymity, unlinkability, unobservability, pseudonymity, and identity managment -- a consolidated proposal for terminology. Technical Report v0.31, 2008.
• 11: K. Sampigethaya, M. Li, L. Huang, , and R. Poovendran. Amoeba: Robust location privacy scheme for vanet. In Journal on Selected Areas in Communications (JSAC), 2007.
• 12: Bhaba R. Sarker, The resemblance coefficients in group technology: a survey and comparative study of relational metrics, Computers and Industrial Engineering, v.30 n.1, p.103-116, Jan. 1996 [doi>10.1016/0360-8352(95)00024-0]
• 13: A. Serjantov and G. Danezis. Towards an information theoretic metric for anonymity. In PET Workshop, 2002.
• 14: Claude E. Shannon , Warren Weaver, A Mathematical Theory of Communication, University of Illinois Press, Champaign, IL, 1963
• 15: S. Steinbrecher and S. Köpsell. Modelling unlinkability. In PET Workshop, 2003.
• 16: G. Tóth, Z. Hornák, and F. Vajda. Measuring anonymity revisited. In Nordic Workshop on Secure IT Systems, 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory

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:
Measurement, Security

Keywords:
anonymity, mobile communication, positional information, unlinkability