Timestamp Location Server Server Reader Tag the ID 101 is protected by a random number n.To query Request, LS,the user must first determine the value of n he used at 10:00 am.In our protocol,we let n=h(s.ct)and increment (1)(a)n=h(s,ct) ct immediately afterwards.While the tag cannot recall the (b)ct=ct+ (c)o=h(id,n) random n value used at 10:00 am,the owner of the tag can (3) 0,n determine the current value of ct in the tag.(We assume that --n (2) there is a command to recover this.Knowing the secret s @.R as well as the initial and current value ct,the user can re- (4) generate all the random n values the RFID tag has used so far.For instance,the user can generate a list The user then Fig.5.Reader-tag interaction.The dotted line in step (3)denotes that the TABLE VII reader transmits directly to the timestamp server,bypassing the location server. TABLE MAINTAINED BY USER n time the ct by one (Step 1b),and create the identifier w as h(ID.n). cti_1 h(s,cti_1) Finally,in Step (2),the tag returns w,n to the reader. cti h(s,cti) When the reader receives this tuple,the reader will append ctit1 h(s,cti+1) 。，， , the current timestamp t together with n,and send that to the TS in Step(3).This messages bypasses the LS completely. queries the TS database using meaning the LS never learns n.Then,the reader will append the reader's ID,Ri,and w,and send everything to the LS in Select Time from TS where Random Value ni,(1) step (4).Using Ri,the LS can determine the reader's. where ni=h(s,cti). TABLE V After receiving the time corresponding to ni from Table V, TABLE MAINTAINED BY TS the user determine whether the returned time is larger than or smaller than his target time of 10:00 am.If the returned Time Random value 10.00am ni time is larger,the user will pick another an smaller ct value, 10.00am nj compute n,and query the TS again.If the returned time is 10:5am nk smaller,the user will pick a target ct value.Using a simple binary search,the user only needs to execute O(log n)queries to TS. At the end of the protocol,the TS maintains a table shown With the user now knowing his n corresponding to 10:00 in Table V.The TS table has 2 attributes,time,and a random am,he can now query the LS server using the following query. value.The random values associated with time 10:00 am for instance,are all the n values transmitted by all the RFID Select from LS where ID-w, (2) readers.Each n value represent a different RFID tag.Similarly. where w=h(101,n). TABLE VI C.Security analysis TABLE MAINTAINED BY LS We consider the security of our system after the adversary ID Location compromises the TS,the LS and the reader Ri.Since we 1 Office 1 Office 3 allow anyone to query the databases,the adversary controlling w3 Office 2 the TS for instance,can also query the LS like a regular user. Compromise TS server:The adversary succeeds in attack- ing TS if he can determine which w in LS belongs to a user, the LS maintains a table shown in Table VI.The LS table has or if the adversary can determine that two w values belong to 2 attributes,the tag identifier w and the location that tag was the same person.The reason for focusing on ws is because read.Each entry in the LS table represent a different RFID through w,the adversary determine the whereabouts of a user. tag response.Note that the LS does not update the table in The adversary controlling TS is able to access all the real time,and thus the ordering of entries do not indicate the records such as those in Table V,as well as observe multiple time an RFID tag was read. queries (Query 1)made by a user and the corresponding response.The adversary can also query the LS using infor- B.Querying the database mation from his observations. Let the user wanting to learn his location at 10:00 am.He We begin by examining what the adversary can learn from will need to query LS using the w value h(101,n),where n controlling TS.For a single RFID tag T:with secret s;being is the value he choose at 10:00 am.Notice that the LS table queried twice,the n results from h(s,ct)and h(s,(ct+1))will is similar to strawman protocol I's table.In both instances, be different since the ct value is automatically incremented 57Timestamp Server Location Server Reader Tag Request (c) h(id, n) (b) ct ct 1 (a) n h(s, ct) = = + = ω ω,n t,n ω,Ri (1) (2) (3) (4) Fig. 5. Reader-tag interaction. The dotted line in step (3) denotes that the reader transmits directly to the timestamp server, bypassing the location server. the ct by one (Step 1b), and create the identifier ω as h(ID, n). Finally, in Step (2), the tag returns ω, n to the reader. When the reader receives this tuple, the reader will append the current timestamp t together with n, and send that to the T S in Step (3). This messages bypasses the LS completely, meaning the LS never learns n. Then, the reader will append the reader’s ID, Ri , and ω, and send everything to the LS in step (4). Using Ri , the LS can determine the reader’s. TABLE V TABLE MAINTAINED BY T S Time Random value 1. 10:00 am ni 2. 10:00 am nj 3. 10:15 am nk · · · · · · · · · At the end of the protocol, the T S maintains a table shown in Table V. The T S table has 2 attributes, time, and a random value. The random values associated with time 10:00 am for instance, are all the n values transmitted by all the RFID readers. Each n value represent a different RFID tag. Similarly, TABLE VI TABLE MAINTAINED BY LS ID Location 1. ω1 Office 1 2. ω2 Office 3 3. ω3 Office 2 · · · · · · · · · the LS maintains a table shown in Table VI. The LS table has 2 attributes, the tag identifier ω and the location that tag was read. Each entry in the LS table represent a different RFID tag response. Note that the LS does not update the table in real time, and thus the ordering of entries do not indicate the time an RFID tag was read. B. Querying the database Let the user wanting to learn his location at 10:00 am. He will need to query LS using the ω value h(101, n), where n is the value he choose at 10:00 am. Notice that the LS table is similar to strawman protocol 1’s table. In both instances, the ID 101 is protected by a random number n. To query LS, the user must first determine the value of n he used at 10:00 am. In our protocol, we let n = h(s, ct) and increment ct immediately afterwards. While the tag cannot recall the random n value used at 10:00 am, the owner of the tag can determine the current value of ct in the tag. (We assume that there is a command to recover this.) Knowing the secret s as well as the initial and current value ct, the user can re￾generate all the random n values the RFID tag has used so far. For instance, the user can generate a list The user then TABLE VII TABLE MAINTAINED BY USER ct n time · · · · · · · · · cti−1 h(s, cti−1) ? cti h(s, cti) ? cti+1 h(s, cti+1) ? · · · · · · · · · queries the T S database using Select Time from T S where Random Value = ni , (1) where ni = h(s, cti). After receiving the time corresponding to ni from Table V, the user determine whether the returned time is larger than or smaller than his target time of 10:00 am. If the returned time is larger, the user will pick another an smaller ct value, compute n, and query the T S again. If the returned time is smaller, the user will pick a target ct value. Using a simple binary search, the user only needs to execute O(log n) queries to T S. With the user now knowing his n corresponding to 10:00 am, he can now query the LS server using the following query. Select * from LS where ID=ω, (2) where ω = h(101, n). C. Security analysis We consider the security of our system after the adversary compromises the T S, the LS and the reader Ri . Since we allow anyone to query the databases, the adversary controlling the T S for instance, can also query the LS like a regular user. Compromise T S server: The adversary succeeds in attack￾ing T S if he can determine which ω in LS belongs to a user, or if the adversary can determine that two ω values belong to the same person. The reason for focusing on ωs is because through ω, the adversary determine the whereabouts of a user. The adversary controlling T S is able to access all the records such as those in Table V, as well as observe multiple queries (Query 1) made by a user and the corresponding response. The adversary can also query the LS using infor￾mation from his observations. We begin by examining what the adversary can learn from controlling T S. For a single RFID tag Ti with secret si being queried twice, the n results from h(s, ct) and h(s,(ct+1)) will be different since the ct value is automatically incremented 57