Quantitative evaluation of unlinkable ID matching schemes

Yasunobu Nohara, Sozo Inoue, Kensuke Baba, Hiroto Yasuura

Research output: Chapter in Book/Report/Conference proceedingConference contribution

20 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationWPES'05
Subtitle of host publicationProceedings of the 2005 ACM Workshop on Privacy in the Electronic Society
PublisherAssociation for Computing Machinery (ACM)
Number of pages6
ISBN (Print)1595932283, 9781595932280
Publication statusPublished - 2005
Externally publishedYes
EventWPES'05: 2005 ACM Workshop on Privacy in the Electronic Society - Alexandria, VA, United States
Duration: Nov 7 2005Nov 7 2005

Publication series

NameWPES'05: Proceedings of the 2005 ACM Workshop on Privacy in the Electronic Society


OtherWPES'05: 2005 ACM Workshop on Privacy in the Electronic Society
Country/TerritoryUnited States
CityAlexandria, VA

All Science Journal Classification (ASJC) codes

  • Engineering(all)


Dive into the research topics of 'Quantitative evaluation of unlinkable ID matching schemes'. Together they form a unique fingerprint.

Cite this