Database Reader Tag Finally,we assume that having a rational adversary pre- cludes attacks such as deleting or shuffling entries in the Request database since such actions do not help the adversary identify a (a)a=(101,n)a (b)B=(101.ID]e user.This is reasonable since such disruption attacks increases (c)a)B the risk of detection.We will discuss more about defending ((10LnB(a)) against such attacks in the Section IV. ((101.n).(a]8) Store ((101.n],(a)). IV.STRAWMAN SOLUTIONS 山le. We motivate our solutions by considering the limitations of seemingly possible solutions.For all these strawman solutions. we assume a more powerful RFID tag that can do symmetric Fig.3.Strawman protocol 2.The tag ID is 101 key encryption is used.We always assume the user is the owner of RFID tag 101. B.Strawman 2 A.Strawman I We can modify a technique from [26]to improve the query performance.Now,each RFID tag maintains two keys that it Database Reader Tag keeps secret,i.e.tag 101 will have k1101,k2102.We remove Request the superscript and use k1 and k2 to denote keys to simplify (a (101n the presentation.The protocol is shown in Fig.3,and after 101,n2 10L,n the data is collected,the table resembles Table III. Store (101,n].time,loc TABLE IⅢ DATABASE TABLE BY STRAWMAN 2 D Time Location Fig.2.Strawman protocol 1.The tag ID is 101 101,n1k1,{a1B 10:00am Office 1 102,n2k1:a2B, 10.00am In this simple protocol,we let the RFID tag return its 10L,n3k1,a3B1 10:15am Office 2 ， encrypted ID in the form of [ID,nk where n is a random number,and k is the tag's secret key.For completeness,we show this interaction in Fig.2.Now,in the database.we have This approach also provides the same protections against an adversary as the earlier strawman protocol,since knowing TABLE II (101,n1}k1,[o}3 does not lead to knowing 101.Fur- DATABASE TABLE FROM STRAWMAN I thermore,the adversary cannot link {101,n,[1}8,and ID Time Location (101,n3k1,[o3)8 together since a different random n is 101,n1k 10.00am Office 1 used. 102,n2k2 10.00am Office 3 When a user queries the database,he will issue a"Select 101,n3k1 10:15am Office 2 from DB where ID=3 and Time=10:00am",where 1 t T1 3={101,IDk2 where ki and k2 are the secret keys of tags 101 and 102 respectively.We see that this approach protects privacy since The database will encrypt the first portion of each ID field the adversary observing this table cannot learn the actual IDs, with B,and check whether it matches the second portion.If 101 and 102,of the tags.There is also no linkability,since it does,the database will return that entry to the user.For (101,nk and {101,n3hk,use different random numbers example,encrypting {101,n}k with B will match {o)s, n and n3 while encrypting the same ID,thus resulting in and hence this entry belongs to the user.Since {101,nhk is different ciphertexts. protected via k1 which is only know by the user,the database The problem with this solution arrises when the user wants does not have to verify the user.It is clear that strawman 2 is to query the database.He can no longer simply do a"Select more efficient than strawman 1. from DB where ID=101",since all the ID attributes now However,once an adversary observes B.the adversary can have a random number component.The user cannot recall the determine future time and locations that B have visited.For nI and n3 values used since the limited storage capacity of the instance,using B,the adversary know that the same tag visited RFID tag means these random numbers have to be generated Office 2 at time 10:15 am.The reason is that while at time on-the-fly and never archived.The only option is for the user 10:15 am we have {101,n3}k1 which uses a different n3,the to retrieve the entire table,and attempt to decrypt each entry's same B is used,since B ={101,ATTR)k2.The ATTR is ID field until he finds the all the entries with IDs equal to a fixed value in the database and cannot be changed by the his own.This is clearly inefficient given the large size of the user.Thus,strawman 2 only prevents linkability so long as table. the adversary never observes a user querying the database. 55Finally, we assume that having a rational adversary pre￾cludes attacks such as deleting or shuffling entries in the database since such actions do not help the adversary identify a user. This is reasonable since such disruption attacks increases the risk of detection. We will discuss more about defending against such attacks in the Section IV. IV. STRAWMAN SOLUTIONS We motivate our solutions by considering the limitations of seemingly possible solutions. For all these strawman solutions, we assume a more powerful RFID tag that can do symmetric key encryption is used. We always assume the user is the owner of RFID tag 101. A. Strawman 1 Database Reader Tag Request (a){101,n}k Store{101,n}k , time, loc {101,n}k {101,n}k Fig. 2. Strawman protocol 1. The tag ID is 101. In this simple protocol, we let the RFID tag return its encrypted ID in the form of {ID, n}k where n is a random number, and k is the tag’s secret key. For completeness, we show this interaction in Fig.2. Now, in the database, we have TABLE II DATABASE TABLE FROM STRAWMAN 1 ID Time Location 1. {101, n1}k1 10:00am Office 1 2. {102, n2}k2 10:00am Office 3 3. {101, n3}k1 10:15am Office 2 · · · · · · · · · · · · where k1 and k2 are the secret keys of tags 101 and 102 respectively. We see that this approach protects privacy since the adversary observing this table cannot learn the actual IDs, 101 and 102, of the tags. There is also no linkability, since {101, n1}k1 and {101, n3}k1 use different random numbers n1 and n3 while encrypting the same ID, thus resulting in different ciphertexts. The problem with this solution arrises when the user wants to query the database. He can no longer simply do a “Select * from DB where ID=101”, since all the ID attributes now have a random number component. The user cannot recall the n1 and n3 values used since the limited storage capacity of the RFID tag means these random numbers have to be generated on-the-fly and never archived. The only option is for the user to retrieve the entire table, and attempt to decrypt each entry’s ID field until he finds the all the entries with IDs equal to his own. This is clearly inefficient given the large size of the table. Database Reader Tag Request α β β α (c){ } (b) {101,ID} (a) {101,n} k2 k1 = = ({101,n}k1,{α}β ) time , loc Store ({101,n}k1,{α}β ), ({101,n}k1,{α}β ) Fig. 3. Strawman protocol 2. The tag ID is 101. B. Strawman 2 We can modify a technique from [26] to improve the query performance. Now, each RFID tag maintains two keys that it keeps secret, i.e. tag 101 will have k1 101, k2 102. We remove the superscript and use k1 and k2 to denote keys to simplify the presentation. The protocol is shown in Fig. 3, and after the data is collected, the table resembles Table III. TABLE III DATABASE TABLE BY STRAWMAN 2 ID Time Location 1. {101, n1}k1, {α1}β1 10:00am Office 1 2. {102, n2}k1, {α2}β2 10:00am Office 3 3. {101, n3}k1, {α3}β1 10:15am Office 2 · · · · · · · · · · · · This approach also provides the same protections against an adversary as the earlier strawman protocol, since knowing {101, n1}k1, {α1}β1 does not lead to knowing 101. Fur￾thermore, the adversary cannot link {101, n1}k1, {α1}β1 and {101, n3}k1, {α3}β1 together since a different random n is used. When a user queries the database, he will issue a “Select * from DB where ID=βˆ and Time=10:00am”, where βˆ = {101, ID}k2 The database will encrypt the first portion of each ID field with βˆ, and check whether it matches the second portion. If it does, the database will return that entry to the user. For example, encrypting {101, n1}k1 with βˆ will match {α1}β1 , and hence this entry belongs to the user. Since {101, n1}k1 is protected via k1 which is only know by the user, the database does not have to verify the user. It is clear that strawman 2 is more efficient than strawman 1. However, once an adversary observes βˆ, the adversary can determine future time and locations that βˆ have visited. For instance, using βˆ, the adversary know that the same tag visited Office 2 at time 10:15 am. The reason is that while at time 10:15 am we have {101, n3}k1 which uses a different n3, the same β is used, since β = {101, AT T R}k2. The AT T R is a fixed value in the database and cannot be changed by the user. Thus, strawman 2 only prevents linkability so long as the adversary never observes a user querying the database. 55