research-article

A secure and scalable identification for hash-based RFID systems using updatable pre-computation

Authors:

Yasunobu Nohara,

Sozo InoueAuthors Info & Claims

WiSec '10: Proceedings of the third ACM conference on Wireless network security

Pages 65 - 74

https://doi.org/10.1145/1741866.1741878

Published: 22 March 2010 Publication History

Abstract

In this paper, we propose a secure identification scheme for RFID with efficient time and memory, and also an efficient update of pre-computed values on the server side. Although RFID ( Radio Frequency IDentification ) is becoming popular with pervasive computing environments, a privacy problem still remains, where an adversary can trace users' behavior by linking identification log by adversary readers. For this problem, a hash-chain scheme has been proposed as a secure identification for low-cost RFID tags, and its long identification time has been reduced by Avoine et al. using pre-computation on the server side. However, Avoine's scheme uses static pre-computation, and therefore pre-computed values include ones which are already used and no longer used. An efficient update of pre-computation is needed to remove these wasted values and this can reduce memory usage. In this paper, we optimize a lookup of pre-computed values using d-left hashing, which is a fast lookup technique, and provide efficient update of pre-computed values. We also show reasonable analytical evaluation and experimental result for memory and pre-computation/identification/update time.

References

[1]

Japan railway east press release. http://www.jreast.co.jp/press/2009/20091014.pdf. (in Japanese).

[2]

M. Abe and W. Ogata. Application of privacy protection RFID methods to large-scale systems. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, J91-A(3):399--410, Mar. 2008. in Japanese.

[3]

G. Avoine and P. Oechslin. A scalable and provably secure hash-based RFID protocol. In 2nd International Workshop on Pervasive Computing and Communications Security -- PerSec2005, pages 110--114. IEEE Computer Society Press, Mar. 2005.

Digital Library

[4]

B.H. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422--426, July 1970.

Digital Library

[5]

F. Bonomi, M. Mitzenmacher, R. Panigrahy, S. Singh, and G. Varghese. An improved construction for counting Bloom filters. In 14th Annual European Symposium on Algorithms -- ESA 2006, volume 4168 of LNCS, pages 684--695, 2006.

Digital Library

[6]

A. Broder and M. Mitzenmacher. Using multiple hash functions to improve IP lookups. In Proceedings of 20th Annual Joint Conference of the IEEE Computer and Communications Societies -- INFOCOM 2001, volume 3, pages 1454--1463 vol.3, 2001.

[7]

M. Burmester, B. de Medeiros, and R. Motta. Robust, anonymous RFID authentication with constant key-lookup. In Cryptology ePrint Archive Report, volume 2007-402. IACR, 2007.

[8]

S. Canard and I. Coisel. Data synchronization in privacy-preserving RFID authentication schemes. In Conference on RFID Security, Budaperst, Hongria, July 2008.

[9]

J.-S. Chou, G.-C. Lee, and C.-J. Chan. A novel mutual authentication scheme based on quadratic residues for RFID systems. In Cryptology ePrint Archive Report, volume 2007-224. IACR, 2007.

[10]

M. Conti, R.D. Pietro, L.V. Mancini, and A. Spognardi. RIPP-FS: an RFID identification, privacy preserving protocol with forward secrecy. In International Workshop on Pervasive Computing and Communication Security -- PerSec 2007, pages 229--234, New York, USA, Mar. 2007. IEEE, IEEE Computer Society Press.

Digital Library

[11]

D. Henrici and P. Muller. Providing security and privacy in RFID systems using triggered hash chains. In Proceedings of the 2008 Sixth Annual IEEE International Conference on Pervasive Computing and Communications, pages 50--59, Washington, DC, USA, 2008. IEEE Computer Society.

Digital Library

[12]

D. Molnar and D. Wagner. Privacy and security in library : RFID issues, practices, and architectures. In 11th ACM Conference on Computer and Communications Security -- CCS2004, pages 210--219. ACM Press, Nov. 2004.

Digital Library

[13]

National Institute of Standards and Technology, Federal Information Processing Standards Publication 180-2. SECURE HASH STANDARD, 2002.

[14]

Y. Nohara, S. Inoue, K. Baba, and H. Yasuura. Quantitative evaluation of unlinkable ID matching schemes. In 2005 ACM Workshop on Privacy in the Electronic Society -- WPES2005, pages 55--60. ACM Press, Nov. 2005.

Digital Library

[15]

Y. Nohara, S. Inoue, and H. Yasuura. A secure high-speed identification scheme for RFID using Bloom filters. In Proc. of 3rd International Conference on Availability, Security and Reliability -- ARES2008, pages 717--722. IEEE Computer Society, Mar. 2008.

Digital Library

[16]

P. Oechslin. Making a faster cryptanalytic time-memory trade-off. In Advances in Cryptology -- CRYPTO 2003, volume 2729 of LNCS, pages 617--630, 2003.

[17]

M. Ohkubo, K. Suzuki, and S. Kinoshita. Cryptographic approach to a privacy friendly tag. In RFID Privacy Workshop@MIT, Nov. 2003.

[18]

M. Ohkubo, K. Suzuki, and S. Kinoshita. Hash-chain based forward-secure privacy protection scheme for low-cost RFID. In 2004 Symposium on Cryptography and Information Security -- SCIS2004, volume 1, pages 719--724, Jan. 2004.

[19]

M. O'Neill. Low-cost SHA-1 hash function architecture for RFID tags. In Workshop on RFID Security 2008, Budapest, Hungary, July 2008.

[20]

B. Song and C.J. Mitchell. RFID authentication protocol for low-cost tags. In V.D. Gligor, J. Hubaux, and R. Poovendran, editors, ACM Conference on Wireless Network Security, WiSec'08, pages 140--147, Alexandria, Virginia, USA, Apr. 2008. ACM Press.

Digital Library

[21]

H. Song, S. Dharmapurikar, J. Turner, and J. Lockwood. Fast hash table lookup using extended Bloom filter: an aid to network processing. In SIGCOMM '05: Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, pages 181--192, New York, NY, USA, 2005. ACM Press.

Digital Library

[22]

C.C. Tan, B. Sheng, and Q. Li. Severless search and authentication protocols for RFID. In PerCom2007, pages 3--12. IEEE Computer Society, 2007.

Digital Library

[23]

S.A. Weis, S.E. Sarma, R.L. Rivest, and D.W. Engels. Security and privacy aspects of low-cost radio frequency identification systems. In 1st International Conference on Security in Pervasive Computing -- SPC2003, volume 2802 of LNCS, pages 201--212. Springer, 2004.

Cited By

Pal AKant K(2021)A Neighborhood Aware Caching and Interest Dissemination Scheme for Content Centric NetworksIEEE Transactions on Network and Service Management10.1109/TNSM.2021.307932618:3(3900-3917)Online publication date: Sep-2021
https://doi.org/10.1109/TNSM.2021.3079326
Lv JXi NRao X(2020)A Fully Anonymous Authentication Scheme Based on Medical EnvironmentAlgorithms and Architectures for Parallel Processing10.1007/978-3-030-38991-8_32(484-498)Online publication date: 22-Jan-2020
https://doi.org/10.1007/978-3-030-38991-8_32
Pal AKant K(2017)NACID: A Neighborhood Aware Caching and Interest Dissemination in Content Centric Networks2017 26th International Conference on Computer Communication and Networks (ICCCN)10.1109/ICCCN.2017.8038370(1-9)Online publication date: Jul-2017
https://doi.org/10.1109/ICCCN.2017.8038370
Show More Cited By

Index Terms

A secure and scalable identification for hash-based RFID systems using updatable pre-computation
1. Information systems
  1. World Wide Web
    1. Web applications
      1. Internet communications tools
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Empirical software validation
  2. Software organization and properties
    1. Software functional properties
      1. Formal methods

Recommendations

A Secure High-Speed Identification Scheme for RFID Using Bloom Filters
ARES '08: Proceedings of the 2008 Third International Conference on Availability, Reliability and Security

As pervasive computing environments become popular, RFID tags are introduced into our daily life. However, there exists a privacy problem that an adversary can trace users' behavior by linking the tag's ID. Although a hash-chain scheme can solve this ...
Scalable RFID Systems: A Privacy-Preserving Protocol with Constant-Time Identification

In RFID literature, most “privacy-preserving” protocols require the reader to search all tags in the system in order to identify a single tag. In another class of protocols, the search complexity is reduced to be logarithmic in the number of tags, but ...
Towards Scalable Identification in RFID Systems

The search efficiency of radio frequency identification (RFID) protocols remains a challenging issue. There are many proposals that address the security and privacy issues of RFID, but most of them require reader work that is linear with the number of ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

WiSec '10: Proceedings of the third ACM conference on Wireless network security

March 2010

186 pages

ISBN:9781605589237

DOI:10.1145/1741866

General Chair:
Susanne Wetzel
Stevens Institute of Technology, USA
,
Program Chairs:
Cristina Nita-Rotaru
Purdue University, USA
,
Frank Stajano
University of Cambridge, UK

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

In-Cooperation

SIGMOBILE: ACM Special Interest Group on Mobility of Systems, Users, Data and Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 March 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

WISEC '10

Sponsor:

SIGSAC

WISEC '10: Third ACM Conference on Wireless Network Security

March 22 - 24, 2010

New Jersey, Hoboken, USA

Acceptance Rates

Overall Acceptance Rate 98 of 338 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
312
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pal AKant K(2021)A Neighborhood Aware Caching and Interest Dissemination Scheme for Content Centric NetworksIEEE Transactions on Network and Service Management10.1109/TNSM.2021.307932618:3(3900-3917)Online publication date: Sep-2021
https://doi.org/10.1109/TNSM.2021.3079326
Lv JXi NRao X(2020)A Fully Anonymous Authentication Scheme Based on Medical EnvironmentAlgorithms and Architectures for Parallel Processing10.1007/978-3-030-38991-8_32(484-498)Online publication date: 22-Jan-2020
https://doi.org/10.1007/978-3-030-38991-8_32
Pal AKant K(2017)NACID: A Neighborhood Aware Caching and Interest Dissemination in Content Centric Networks2017 26th International Conference on Computer Communication and Networks (ICCCN)10.1109/ICCCN.2017.8038370(1-9)Online publication date: Jul-2017
https://doi.org/10.1109/ICCCN.2017.8038370
Avoine GBingol MCarpent XYalcin S(2013)Privacy-Friendly Authentication in RFID SystemsIEEE Transactions on Mobile Computing10.1109/TMC.2012.17412:10(2037-2049)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1109/TMC.2012.174

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents