A Hybrid RFID Protocol Against Tracking Attacks

The authors study the problem how to construct an RFID mutual authentication protocol between tags and readers. Juels (in Journal on Selected Areas in Communications, 2006) proposed an open question which asks whether there exists a fully privacy-preserving RFID authentication protocol in which the time complexity of a successful authentication phase can be done in sub-linear time o(n) where n is the number of tags participating in the RFID system. In this paper, the authors answer this question positively in an amortized view.