Quantitative evaluation of unlinkable ID matching schemes

ABSTRACT

As pervasive computing environments become popular, RFID devices, such as contactless smart cards and RFID tags, are introduced into our daily life. However, there exists a privacy problem that a third party can trace user's behavior by linking device's ID.The concept of unlinkability, that a third party cannot recognize whether some outputs are from the same user, is important to solve the privacy problem. A scheme using hash function satisfies unlinkability against a third party by changing the outputs of RFID devices every time. However, the schemes are not scalable since the server needs O(N) hash calculations for every ID matching, where N is the number of RFID devices.In this paper, we propose the K-steps ID matching scheme, which can reduce the number of the hash calculations on the server to O(log N). Secondly, we propose a quantification of unlinkability using conditional entropy and mutual information. Finally, we analyze the K-steps ID matching scheme using the proposed quantification, and show the relation between the time complexity and unlinkability.

REFERENCES

• 1: Stephan A. Weis, Sanjay E. Sarma, Ronald L. Rivest, and Daniel W. Engels, "Security and Privacy Aspects of Low-Cost Radio Frequency Identification Systems", International Conference on Security in Pervasive Computing 2003, LNCS 2802, pp.201--212, 2004.
• 2: Miyako Ohkubo, Koutarou Suzuki and Shingo Kinoshita, "Cryptographic Approach to a Privacy Friendly Tag", RFID Privacy Workshop@MIT, 2003.
• 3: Miyako Ohkubo, Koutarou Suzuki, Shingo Kinoshita, "Hash-Chain Based Forward-Secure Privacy Protection Scheme for Low-Cost RFID", Proc. of the 2004 Symposium on Cryptography and Information Security(SCIS2004), Vol.1, pp.719--724, Jan. 2004.
• 4: Gildas Avoine , Philippe Oechslin, A Scalable and Provably Secure Hash-Based RFID Protocol, Proceedings of the Third IEEE International Conference on Pervasive Computing and Communications Workshops, p.110-114, March 08-12, 2005 [doi>10.1109/PERCOMW.2005.12]
• 5: 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
• 6: Claudia Díaz, Stefaan Seys, Joris Claessens, and Bart Preneel, "Towards measuring anonymity", Workshop on Privacy Enhancing Technologies 2002, LNCS 2482, pp. 54--68, 2002.
• 7: Andrei Serjantov and George Danezis, "Towards an Information Theoretic Metric for Anonymity", Workshop on Privacy Enhancing Technologies 2002, LNCS 2482, pp. 41--53, 2002.
• 8: Claudia Díaz, Joris Claessens, Stefaan Seys, and Bart Preneel, "Information Theory and Anonymity", Proceedings of the 23rd Symposium on Information Theory, pp. 179--186, May. 2002.
• 9: Sandra Steinbrecher and Stefan Köpsell, "Modelling unlinkability", Workshop on Privacy Enhancing Technologies 2003, LNCS2760, pp. 32--47, 2003.
• 10: Yasunobu Nohara, Sozo Inoue, Kensuke Baba, and Hiroto Yasuura, "Unlinkable ID Matching Protocol for Large-scale RFID Systems", Proc. of the 2005 Symposium on Cryptography and Information Security (SCIS2005), Vol.3, pp.1567--1572, Jan. 2005. (in Japanese)
• 11: David Molnar , David Wagner, Privacy and security in library RFID: issues, practices, and architectures, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030112]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.3 Tradeoffs among Complexity Measures

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

General Terms:
Measurement, Security

Keywords:
RFID security, degree of unlinkability, k-steps ID matching, privacy