On Constant-Time-Identification and Privacy-Preserving RFID Protocols: Trade-Off between Time and Memory

We study hash-based identification protocols in RFID systems which obtain privacy against active adversaries who can perform compromised attacks. Here, an active adversary can track a tag via successful or unsuccessful identifications with legal or illegal readers. In IEEE Transactions on Parallel and Distributed Systems, Alomair, Clark, Cuellar and Poovendran propose a novel hash-based RFID identification protocol called constant-time-identification protocol (CTI). Their protocol is provably against active adversaries who can perform compromise attack. However, in order to obtain high privacy in their protocol, the database in CTI is required to have quite large memory space. In this work, we try to reduce the memory complexity of the database in CTI while preserving the same level of privacy. We discover that there is a large gap between tag´s identification time and tag´s response time in the protocol CTI. We trade-off tag identification time for the sake of reducing the memory space. By using the well-known time-memory-trade-off techniques, we can obtain this goal. With a performance analysis, we show that the memory space of our modified protocol can be reduced by a factor t compared to that of CTI where the number of hash operations for one tag´s identification is O(t^2). Via a case study, we show that our modified protocol is able to save about 89% fraction of memory space of CTI in some practical setting of RFID systems while increasing the tag identification time.