An optimal probabilistic solution for information confinement, privacy, and security in RFID systems

Roberto Di Pietro*, Refik Molva

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

20 Scopus citations


In this paper, we provide the following contributions to enhance the security of RFID based systems. First, we assume that among multiple servers storing the information related to the tags some of them can be compromised. For this new threat scenario, we devise a technique to make RFID identification server dependent, providing a different unique secret key shared by a tag and a server. The solution proposed requires the tag to store just a single key, thus fitting the constraints on tag's memory. Second, we provide a probabilistic tag identification scheme that requires the server to perform just bitwise operations and simple list manipulation primitives, thus speeding up the identification process. The tag identification protocol assures privacy, security and resilience to DoS attacks thanks to its stateless nature. Moreover, we extend the tag identification protocol to achieve mutual authentication and resilience to replay attacks. The proposed identification protocol, unlike other probabilistic protocols, never rejects a legitimate tag. Furthermore, the identification protocol requires the reader to access the local database (DB) of tags' keys O(n) timeswhere n is the number of tags in the systemwhile it has been shown in the literature that a privacy preserving identification protocol requires a reader to access Θ(n) times this DB. In this sense, our protocol is optimal. Finally, the three features suggested in this paper, namely, reader-dependent key management, tag identification, and mutual authentication, can be independently adopted to build alternative solutions.

Original languageEnglish (US)
Pages (from-to)853-863
Number of pages11
JournalJournal of Network and Computer Applications
Issue number3
StatePublished - May 2011

Bibliographical note

Funding Information:
This work has been supported in part by the French Government through the RFID-AP ANR project; the Spanish Ministry of Education through projects TSI2007-65406-C03-01 “E-AEGIS” and CONSOLIDER CSD2007-00004 “ARES”; and by the Government of Catalonia under Grant 2009 SGR 1135.


  • Information confinement
  • Privacy
  • Probabilistic algorithm
  • RFID systems
  • Security

ASJC Scopus subject areas

  • Hardware and Architecture
  • Computer Science Applications
  • Computer Networks and Communications


Dive into the research topics of 'An optimal probabilistic solution for information confinement, privacy, and security in RFID systems'. Together they form a unique fingerprint.

Cite this