Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16]

Journal of Information Science and Engineering, Vol. 32 No. 4, pp. 887-901 (July 2016)

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

Department of Computer Science and Information Engineering
National Taipei University
New Taipei City, 237 Taiwan
E-mail: {jcchang; hsinlung}

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 compromised 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 timememory- 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(t2). 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.

Keywords: RFID identification, hash-based protocols, time-memory-trade-off, constanttime- identification, RFID privacy

Full Text () Retrieve PDF document (201607_05.pdf)

Received April 13, 2015; revised October 19, 2015; accepted November 2, 2015.
Communicated by Jiann-Liang Chen.
* A preliminary version of this paper appears in Proceedings of the 10th IEEE International Conference on Ubiquitous Intelligence and Computing. This work was supported by MOST-102-2221-E-305-008 -MY3.