Fast and secure tag authentication in large-scale RFID systems using skip graphs

Fast and secure object monitoring and management using Radio Frequency Identification (RFID) technologies is crucial to Internet of Things (IoT) systems. Structured key-based private authentication protocols securely identify individual RF tags in the logarithmic order by having group keys shared by several tags. However, should some portion of tags in the system be physically compromised, the degree of privacy of the other tags will decrease. This is because tampered group keys disclosed from the compromised tags can be correlated. Thus, preserving the degree of tags' privacy in keeping with fast authentication speed is equivalent to reducing the correlation probability of group keys. Toward this goal, we propose Randomized Skip Graphs-Based Authentication (RSGA) that significantly improves the tags' privacy in terms of anonymity with reasonable amount of key storage cost by using a skip graph key structure. Then, we augment RSGA with a key updating mechanism to securely update secret keys and a path pruning algorithm to further facilitate its authentication process. Our extensive computer simulation as well as mathematical analyses present that the proposed RSGA achieves its design goals.