Scalable RFID Pseudonym Protocol

In this paper we address the issue of scalability in RFID pseudonym protocols. Many previously proposed protocols suffer from scalability issues because they require a linear search to identify or authenticate a tag. Some RFID protocols, however, only require constant time for tag identification, but, unfortunately, all previously proposed schemes of this type have serious shortcomings. We propose a novel RFID authentication protocol based on the Song-Mitchell protocol, that takes O(1) work to authenticate a tag, and meets the privacy, security and performance requirements identified here. The proposed scheme also supports tag delegation and ownership transfer in an efficient way.