value to the RFID tag,resulting in similar w values at different attack as follows.Consider an RFID tag at 10:00 am was read locations.This allows that tag to be linked to two locations, outside"Office 1".There will be an entry in the TS thus violating privacy.Our choice of h(ID,n)does not have Time Random value this problem since the ct will automatically increment after 10:00am n each query,resulting in different w values each time. where n=h(s+ct).The corresponding entry in LS will be VI.ADDITIONAL DISCUSSION D Location Here we consider disruption attacks that do not impact user wOffice 1 privacy but can disrupt regular user operations. Now let the adversary compromises TS,and changes the A.Detect deleted data time variable from 10:00 am to 11:00 am.The user querying TS with "Select from TS where Random Value =n", The adversary controlling either TS or LS can decide will receive the answer 11:00 am.The same user now querying to delete selected entries from the respective tables.The LS with w=h(ID,n)will believe that he was outside Office adversary can do this simply to disrupt the database operations, 1 at 11:00 am instead of 10:00 am.Since no data was deleted, or to conceal other malicious activities.Consider for instance the user using the technique for detecting missing data above an adversary planning to steal something from an office.The will not find any problems.The adversary that compromises adversary can attack the TS or LS to avoid storing any LS can execute the same attack by changing "Office 1"to tag data collected around that time or location to cover his “Office2” tracks.Possible witnesses that check the system to verify their The reason this attack is successful is because there is locations will determine that they were not actually present at nothing linking the value n to 10:00 am,nor the value w that time. to "Office 1".We can modify our protocols to let the RFID Recall that when a user wishes to query "Select from reader transmit both the t and RrD information when querying LS where ID=w",he will first build a Table VII to determine a tag.The tag will then compute a new variable e where his target time.To determine whether any data has been deleted,the user can expand Table VII to include enumerate all e=h(ID,n,t,Rid) previous ct values until up to the current ct value in his RFID tag.He then queries the TS until to determine the n value and return this value to be stored in LS.Thus,the table in corresponding to each ct.If the adversary has compromised LS will become TS and deleted his entry at a particular time,the n value D Location corresponding to that time will be missing.In other words,if w,E Office 1 the user has some counter value ct;where there is no n value After the user queries for his location from LS,he will in Table V matches h(s+cti),the user will suspect that his compute e by hashing his ID with the n value and time values data has been deleted. he received from TS,and the location provided in LS.If If the user can obtain all the n values corresponding to his ct matches e,the user will accept the answer. values,he then queries the LS for each w associated with each We can use a separate mechanism to detect whether an n.If the adversary has deleted his entry from LS,the user will adversary has compromised an RFID reader to an incorrect not receive any location associated with one of his ws.Note t or RIp values.When LS receives the data from an RFID that the adversary can only select entries to delete based on reader,it can check whether the contained Rrp matches the either time,if controlling TS,or location if controlling LS. RFID reader IP address that transmitted the data.A warning The adversary cannot single out a particular tag's information will be flagged if there is a discrepancy.The same check can to be deleted since he cannot distinguish between two tags. be performed by TS to verify if the reader used an incorrect The adversary can compromised the RFID reader instead of t value. TS or LS so that the reader does not broadcast any requests. The adversary controlling TS can use this e to determine When this happens,no tag data exists in either TS or LS, the location of user if he is able to associate an n value with and the RFID tag will not be triggered increment it's ct e since he will then be able to search LS for a matching e value.While a user can infer from"gaps"in the time and value.The adversary cannot obtain e directly since this value location information from TS and LS that a particular RFID is never forwarded to TS.The adversary cannot deduce this reader might be compromised,the user cannot be certain since value from n and t because e requires knowing RID and ID, the gaps may also be caused by environmental conditions or both which the adversary does not know faculty readers.Nonetheless,the occurrence of such gaps will For the adversary controlling LS,the addition of e can be trigger an investigation and detect any compromised readers. used to track a user if the adversary can observe the LS table and determine two identical e values.This will imply that the B.Detect tampered data same user visited both locations.However,each e contains a Instead of deleting the data,the adversary can choose to time t from the RFID reader which will never repeat itself, tamper with the time or location information and launch an and the adversary controlling LS cannot manipulate the reader 59value to the RFID tag, resulting in similar ω values at different locations. This allows that tag to be linked to two locations, thus violating privacy. Our choice of h(ID, n) does not have this problem since the ct will automatically increment after each query, resulting in different ω values each time. VI. ADDITIONAL DISCUSSION Here we consider disruption attacks that do not impact user privacy but can disrupt regular user operations. A. Detect deleted data The adversary controlling either T S or LS can decide to delete selected entries from the respective tables. The adversary can do this simply to disrupt the database operations, or to conceal other malicious activities. Consider for instance an adversary planning to steal something from an office. The adversary can attack the T S or LS to avoid storing any tag data collected around that time or location to cover his tracks. Possible witnesses that check the system to verify their locations will determine that they were not actually present at that time. Recall that when a user wishes to query “Select * from LS where ID=ω”, he will first build a Table VII to determine his target time. To determine whether any data has been deleted, the user can expand Table VII to include enumerate all previous ct values until up to the current ct value in his RFID tag. He then queries the T S until to determine the n value corresponding to each ct. If the adversary has compromised T S and deleted his entry at a particular time, the n value corresponding to that time will be missing. In other words, if the user has some counter value cti where there is no n value in Table V matches h(s + cti), the user will suspect that his data has been deleted. If the user can obtain all the n values corresponding to his ct values, he then queries the LS for each ω associated with each n. If the adversary has deleted his entry from LS, the user will not receive any location associated with one of his ωs. Note that the adversary can only select entries to delete based on either time, if controlling T S, or location if controlling LS. The adversary cannot single out a particular tag’s information to be deleted since he cannot distinguish between two tags. The adversary can compromised the RFID reader instead of T S or LS so that the reader does not broadcast any requests. When this happens, no tag data exists in either T S or LS, and the RFID tag will not be triggered increment it’s ct value. While a user can infer from “gaps” in the time and location information from T S and LS that a particular RFID reader might be compromised, the user cannot be certain since the gaps may also be caused by environmental conditions or faculty readers. Nonetheless, the occurrence of such gaps will trigger an investigation and detect any compromised readers. B. Detect tampered data Instead of deleting the data, the adversary can choose to tamper with the time or location information and launch an attack as follows. Consider an RFID tag at 10:00 am was read outside “Office 1”. There will be an entry in the T S Time Random value 1. 10:00 am n where n = h(s + ct). The corresponding entry in LS will be ID Location 1. ω Office 1 Now let the adversary compromises T S, and changes the time variable from 10:00 am to 11:00 am. The user querying T S with “Select * from T S where Random Value = n”, will receive the answer 11:00 am. The same user now querying LS with ω = h(ID, n) will believe that he was outside Office 1 at 11:00 am instead of 10:00 am. Since no data was deleted, the user using the technique for detecting missing data above will not find any problems. The adversary that compromises LS can execute the same attack by changing “Office 1” to “Office 2”. The reason this attack is successful is because there is nothing linking the value n to 10:00 am, nor the value ω to “Office 1”. We can modify our protocols to let the RFID reader transmit both the t and RID information when querying a tag. The tag will then compute a new variable ǫ where ǫ = h(ID, n, t, Rid). and return this value to be stored in LS. Thus, the table in LS will become ID Location 1. ω, ǫ Office 1 After the user queries for his location from LS, he will compute ǫˆ by hashing his ID with the n value and time values he received from T S, and the location provided in LS. If ǫˆ matches ǫ, the user will accept the answer. We can use a separate mechanism to detect whether an adversary has compromised an RFID reader to an incorrect t or RID values. When LS receives the data from an RFID reader, it can check whether the contained RID matches the RFID reader IP address that transmitted the data. A warning will be flagged if there is a discrepancy. The same check can be performed by T S to verify if the reader used an incorrect t value. The adversary controlling T S can use this ǫ to determine the location of user if he is able to associate an n value with ǫ since he will then be able to search LS for a matching ǫ value. The adversary cannot obtain ǫ directly since this value is never forwarded to T S. The adversary cannot deduce this value from n and t because ǫ requires knowing RID and ID, both which the adversary does not know. For the adversary controlling LS, the addition of ǫ can be used to track a user if the adversary can observe the LS table and determine two identical ǫ values. This will imply that the same user visited both locations. However, each ǫ contains a time t from the RFID reader which will never repeat itself, and the adversary controlling LS cannot manipulate the reader 59