On the performance bound of structured key-based RFID authentication

Designing fast and secure RFID private authentication with structured key management is one of the most essential components for RFID-enabled large-scale object management. Since group keys are shared by some tags in structured key-based authentication, physical tampering of tags, so called the compromise attack, may enable the adversary to obtain group keys stored in the compromised tags, which in turn can be used to distinguish other tags. All existing structured key-based protocols try to reduce the common group key effect to preserve high privacy. However, the theoretical bound of weak privacy achievable by structured key-based authentication remains unknown. In this paper, we investigate weak privacy in RFID authentication. To this end, we first formulate a mathematical model which identifies the probability of two tags being linked with respect to the number of group keys. Our model shows that the existing solutions are far from the ultimate goal in weak privacy. Then, we propose a k-neighbor graph-based RFID authentication (KNGA) protocol, where random walk over a k-neighbor graph is performed. In addition, we show that KNGA achieves the performance bound, and we then quantify the degree of privacy by anonymity. Finally, the extensive simulations demonstrate that the proposed protocol successfully achieves its design goals.