This vulnerability does not occur in [26]because in their a simple incremental counter ct.We use subscripts i when encrypted database,all fields are encrypted by the user and denoting more than one reader or tag. stored into the table.In other words,“10:l5am”and“Office We denote the RFID tag identifier as w,and w will be stored 2"are all encrypted separately.The "B"used to encrypted under the"ID"attribute in the LS.For instance,when there is “10:00am'and“10:l5am”will be{10:00am,Time}k2and no security at all,the w value is just ID,in strawman protocol {10:15 am,Time}k2,so knowing the B value of 10:00 am 1,the w value will be {ID,nhk,and in strawman protocol 2 does not reveal anything about 10:15 am.We cannot do the w=({101,n}k1,[a}B).A summary of the notation used in same in an RFID based tracking system because the RFID tag this paper is given in Table IV. cannot determine the time and location independently TABLE IV C.Discussion SUMMARY OF NOTATIONS From the strawman protocols,we can make the following RFID reader observations.First,a direct encryption of data by the RFID Tag tag (strawman 1)protects user privacy even if the database Timestamp Server Location Server is compromised.However,this approach has slow query Tag's secret,known only to tag owner performance since the database cannot return only the user's Tag's ID,known only to tag owner data to him.Second,the solution cannot merely focus on Tag's counter value,known only to tag owner building an encrypted database,but must also consider the Tag identifier timestamp,stored in TS user query process.The protocol has to ensure that the user's location,stored in LS query does not reveal useful information that an adversary Nonce generated by tag can use to violate user's privacy (strawman 2).Finally,unlike Nonce generated by LS more powerful laptop devices [31].the RFID tag cannot maintain an internal clock to determine time by itself,not capture IP address or GPS coordinates to determine its location V.RFID PROTOCOL independently.While [32]gives a solution for the RFID tag The intuition behind our protocol is for the RFID tag to to determine time,it is unclear that the same techniques can generate two pieces of data each time it responds to an RFID be applied to location information since the tag movements is reader.The reader will store one piece of data associated with unpredictable. the time the tag was read in the TS,and the other piece of The intuition behind our approach is to utilize separate data associated with the location of the tag in the LS.An database servers to perform different roles in the RFID track- adversary compromising either LS or TS will be unable to ing system,as well as store different types of data in each violate the privacy of the RFID tag.When a legitimate user server.There are two roles in the RFID tracking system,where wishes to query the databases,he will query both TS and LS the tag was read (location),and at what time the tag was separately and combine the result to satisfy his query.The read (time).Our approach uses two database servers,one to overview of an RFID reader collecting data and user querying control and store time data and the other to control and store the servers is shown in Fig.4. location data.In this paper,we assume that the adversary can only compromise one of the following,(a)the database Reading RFID tag Querying database storing time information,(b)the database storing location LS information,(c)a small number of RFID readers. TS We justify this assumption because the two servers can be housed at different physical locations,running different operating systems,and managed by a separate group of system administrators.This raises the bar for an adversary User to compromise both servers.Also,given the large number of 、 (1)Query TS to obtain time RFID readers deployed,it is reasonable to assume that the (1)Read data from tag. data.then query LS to get adversary cannot control a majority of them. (2)Return time data location data. to TS,location data to DS (2)Combine both to satisfy The following notations are used to describe our protocols. query. The server controlling the timestamps is the timestamp server TS,and the server controlling the location is the location Fig.4.(L)Obtaining data from tags.(R)Querying databases for data. server LS.We use terms server and database interchangeably in this paper.While both TS and LS can communicate with the RFID readers,only the LS knows the location of these A.Collecting data from tag RFID readers.We denote an RFID reader as R,and an RFID Fig.5 shows the protocol for collecting data from an RFID tag as T.Each T maintain its own secret s,ID and a simple tag.When a reader queries the RFID tag in Step (1),the tag incremental counter ct.The values of s,ID,and ct are kept will first generate a random number n by hashing its secret s secret and only known to the tag owner.The tag also maintains with the current counter value,ct.The tag will then increment 56This vulnerability does not occur in [26] because in their encrypted database, all fields are encrypted by the user and stored into the table. In other words, “10:15 am” and “Office 2” are all encrypted separately. The “β” used to encrypted “10:00 am” and “10:15 am” will be {10:00 am, T ime}k2 and {10:15 am, T ime}k2, so knowing the β value of 10:00 am does not reveal anything about 10:15 am. We cannot do the same in an RFID based tracking system because the RFID tag cannot determine the time and location independently. C. Discussion From the strawman protocols, we can make the following observations. First, a direct encryption of data by the RFID tag (strawman 1) protects user privacy even if the database is compromised. However, this approach has slow query performance since the database cannot return only the user’s data to him. Second, the solution cannot merely focus on building an encrypted database, but must also consider the user query process. The protocol has to ensure that the user’s query does not reveal useful information that an adversary can use to violate user’s privacy (strawman 2). Finally, unlike more powerful laptop devices [31], the RFID tag cannot maintain an internal clock to determine time by itself, not capture IP address or GPS coordinates to determine its location independently. While [32] gives a solution for the RFID tag to determine time, it is unclear that the same techniques can be applied to location information since the tag movements is unpredictable. The intuition behind our approach is to utilize separate database servers to perform different roles in the RFID track￾ing system, as well as store different types of data in each server. There are two roles in the RFID tracking system, where the tag was read (location), and at what time the tag was read (time). Our approach uses two database servers, one to control and store time data and the other to control and store location data. In this paper, we assume that the adversary can only compromise one of the following, (a) the database storing time information, (b) the database storing location information, (c) a small number of RFID readers. We justify this assumption because the two servers can be housed at different physical locations, running different operating systems, and managed by a separate group of system administrators. This raises the bar for an adversary to compromise both servers. Also, given the large number of RFID readers deployed, it is reasonable to assume that the adversary cannot control a majority of them. The following notations are used to describe our protocols. The server controlling the timestamps is the timestamp server T S, and the server controlling the location is the location server LS. We use terms server and database interchangeably in this paper. While both T S and LS can communicate with the RFID readers, only the LS knows the location of these RFID readers. We denote an RFID reader as R, and an RFID tag as T . Each T maintain its own secret s, ID and a simple incremental counter ct. The values of s, ID, and ct are kept secret and only known to the tag owner. The tag also maintains a simple incremental counter ct. We use subscripts i when denoting more than one reader or tag. We denote the RFID tag identifier as ω, and ω will be stored under the “ID” attribute in the LS. For instance, when there is no security at all, the ω value is just ID, in strawman protocol 1, the ω value will be {ID, n}k, and in strawman protocol 2, ω = ({101, n}k1, {α}β). A summary of the notation used in this paper is given in Table IV. TABLE IV SUMMARY OF NOTATIONS R RFID reader T Tag T S Timestamp Server LS Location Server s Tag’s secret, known only to tag owner ID Tag’s ID, known only to tag owner ct Tag’s counter value, known only to tag owner ω Tag identifier t timestamp, stored in TS loc location, stored in LS n Nonce generated by tag Nls Nonce generated by LS V. RFID PROTOCOL The intuition behind our protocol is for the RFID tag to generate two pieces of data each time it responds to an RFID reader. The reader will store one piece of data associated with the time the tag was read in the T S, and the other piece of data associated with the location of the tag in the LS. An adversary compromising either LS or T S will be unable to violate the privacy of the RFID tag. When a legitimate user wishes to query the databases, he will query both T S and LS separately and combine the result to satisfy his query. The overview of an RFID reader collecting data and user querying the servers is shown in Fig. 4. TS LS (1) Query TS to obtain time data, then query LS to get location data. (2) Combine both to satisfy query. User TS LS (1) Read data from tag. (2) Return time data to TS, location data to DS Reading RFID tag Querying database Fig. 4. (L) Obtaining data from tags. (R) Querying databases for data. A. Collecting data from tag Fig. 5 shows the protocol for collecting data from an RFID tag. When a reader queries the RFID tag in Step (1), the tag will first generate a random number n by hashing its secret s with the current counter value, ct. The tag will then increment 56