Privacy-preserving Group Authentication for RFID Tags Using Bit-Collision Patterns

When authenticating a group of RFID tags, a common method is to authenticate each tag with some challenge-response exchanges. However, sequentially authenticating individual tags one by one might not be desirable, especially when considering that a reader often has to deal with multiple tags within a limited period, since it will incur long scanning time and heavy communication costs. To address these problems, we put forward a novel efficient group authentication protocol where a group of tags can be authenticated simultaneously with only one challenge and one response. The protocol is built on a new designed symmetric key based algorithm and the bit-collision pattern technique, so that authentication responses transmitted by multiple tags in a group at the same time will result in a verifiable bit-collision pattern that represents the authentication response for the entire group. The proposed approach can significantly reduce the authentication time and communication cost in sense that the verifier can authenticate the entire group within a period that is comparable to the time taken to perform a single tag authentication and requires only one challenge. In addition, we extend our protocol to support privacy-preserving property which prevents the tagged items from being tracked by illegitimate parties. A thorough security analysis shows that the proposed protocol can resist common practical attacks and experimental results show that the protocol is very efficient in terms of time and communication costs. We also discuss important practical aspects that should be considered when implementing these protocols.