Randomized Skip Lists-based private authentication for large-scale RFID systems

The performance of key authentication and the degree of privacy in large-scale RFID systems are considered by many researchers as tradeoffs. Based on how keys are managed in the system, the privacy preserving tag authentications proposed in the past can be categorized into tree-based and group-based approaches. While a tree-based approach achieves high performance in key authentication, it suffers from the issue of low privacy should a fraction of tags be compromised. On the contrary, while group-based key authentication is relatively invulnerable to compromise attacks, it is not scalable to the large number of tags. In this paper, we propose a new private tag authentication protocol based on skip lists, named Randomized Skip Lists-based Authentication. Without sacrificing the authentication performance, our scheme provides a strong privacy preserving mechanism.