Robust, Anonymous RFID Authentication With Constant Key-Lookup

A considerable number of anonymous RFID authentication schemes have been proposed. However, current proposals either do not provide robust security guarantees, or suffer from scalability issues when the number of tags issued by the system is very large. This paper focuses on approaches that reconcile these important requirements. In particular, the paper seeks to reduce the complexity of identifying tags by the back-end server in anonymous RFID authentication protocols - what one terms the key-lookup problem. The paper proposes a compiler that transforms a generic RFID authentication protocol (supporting anonymity) into one that achieves the same guarantees with constant key-lookup cost even when the number of tags is very large (billions of tags and beyond).