Date Added: Jul 2010
An RFID reader must authenticate its designated tags in order to prevent tag forgery and counterfeiting. At the same time, due to privacy requirements of many applications, a tag should remain anonymous and untraceable to an adversary during the authentication process. In this paper, the authors propose an "HB-like" protocol for privacy-preserving authentication of RFID tags. Previous protocols for privacy-preserving authentication were based on PRF computations. Their protocol can instead be used on low-cost tags that may be incapable of computing traditional PRFs. Moreover, since the underlying computations in HB protocols are very efficient, their protocol also reduces reader-side load compared to PRF-based protocols.