to reuse an older t value.Thus,the adversary cannot link two [13]U.Hengartner and P.Steenkiste,"Access control to people locations to the same user. location information,"ACM Trans.Inf.Syst.Secur,2005. Finally.the adversary controlling the RFID reader may [14]J.I.Hong and J.A.Landay,"An architecture for privacy- sensitive ubiquitous computing,"in International conference on attempt to reuse old t values to track a user.The adversary can Mobile systems,applications,and services (MobiSys),2004. program the RFID reader to always use the same time t value, [15]G.Myles,A.Friday,and N.Davies,"Preserving privacy in The idea here is to try to get an RFID tag to return a response environments with location-based applications,"IEEE Pervasive that has been repeated before.This way,the adversary can Computing,2003. determine that that same tag has move pass the reader twice [16]A.Kapadia,T.Henderson,J.J.Fielding,and D.Kotz,"Virtual walls:Protecting digital privacy in pervasive environments,"in Here,we let e to contain an always changing value n which Proceedings of the Fifth International Conference on Pervasive is dependent on an incrementing counter ct.Therefore,even Computing (Pervasive),2007. if the samesame t,RID and ID values are used,the resulting [17]T.Kriplean,E.Welbourne,N.Khoussainova,V.Rastogi, e will not be the same. M.Balazinska,G.Borriello,T.Kohno,and D.Suciu,"Physical access control for captured rfid data,"IEEE Pervasive Comput- VII.CONCLUSION ing2007. [18]V.Rastogi,E.Welbourne,N.Khoussainova,T.Kriplean, As ubiquitous systems move towards real world deploy- M.Balazinska,G.Borriello,T.Kohno,and D.Suciu,"Express- ments,privacy systems that do not rely on trusted servers will ing privacy policies using authorization views,"in Workshop on become increasing important.We believe that our work is an Ubicomp Privacy,(Ubicomp),2007. initial step towards more robust alternatives.Our future work [19]T.Rodden,A.Friday,H.Muller,and A.Dix,"A lightweight ap- considers two extensions.The first is to allow users to delegate proach to managing privacy in location-based services,equator data access control to other users,and the second is to explore 02-058,"University of Nottingham and Lancaster University and University of Bristol,Tech.Rep.CSTR-07-006,2002. techniques to improve range query performance. [20]S.Weis,S.Sarma,R.Rivest,and D.Engels,"Security and Privacy Aspects of Low-Cost Radio Frequency Identification ACKNOWLEDGMENT Systems,"in International Conference on Security in Pervasive We would like to thank all the reviewers (including ear- Computing,2003. lier WiSec reviwers)for their comments.This project was [21]D.Molnar and D.Wagner,"Privacy and Security in Library supported in part by US NSF grants CNS-0721443,CNS- RFID:Issues,Practices,and Architectures,"in Conference on Computer and Communications Security,2004. 0831904.CAREER Award CNS-0747108 [22]K.Ouafi and R.C.-W.Phan,"Privacy of Recent RFID Authen- tication Protocols,"in 4th International Conference on Informa- REFERENCES tion Security Practice and Experience -ISPEC 2008.2008. [1]D.Hahnel,W.Burgard,D.Fox,K.Fishkin,and M.Philipose,"Mapping [23]D.X.Song,D.Wagner,and A.Perrig."Practical techniques for and localization with rfid technology,"in IEEE International Conference searches on encrypted data,"in IEEE Symposium on Security on Robotics and Automation,2004. and Privacy,2000. [2]V.Stanford,"Pervasive computing goes the last hundred feet with rfid [24]D.Boneh,G.D.Crescenzo,R.Ostrovsky,and G.Persiano, systems."IEEE Pervasive Computing.2003. "Public key encryption with keyword search,"in EUROCRYPT, [3]E.Bertino and R.Sandhu,"Database security-concepts,approaches,and 2004. challenges,"IEEE Transactions on Dependable and Secure Computing, [25]S.Wang,X.Ding,R.H.Deng,and F.Bao,"Private information 2005. retrieval using trusted hardware,"in European Symposium On [4]C.Ramaswamy,R.Sandhu,R.Ramaswamy,and R.S,"Role-based access control features in commercial database management systems, Research In Computer Security (ESORICS),2006. inIn Proceedings of 21st NIST-NCSC National Information Systems [26]Z.Yang.S.Zhong.and R.N.Wright,"Privacy-preserving Security Conference,1998. queries on encrypted data,"in European Symposium On Re- [5]R.Agrawal,J.Kiernan,R.Srikant,and Y.Xu."Hippocratic databases," search In Computer Security (ESORICS),2006. in VLDB.2002. [27]R.Dingledine,N.Mathewson,and P.Syverson,"Tor:the [6]"Commerce Department:we lose laptops,"2006,http://arstechnica. second-generation onion router,"in USENIX Security Sympo- com/security/news/2006/09/7809.ars. sim,2004. [71“FBI lost160 laptops in last44 months,”2007,http:/∥ [28]G.Avoine and P.Oechslin,"A Scalable and Provably Secure arstechnica.com/old/content/2007/02/8821.ars. Hash Based RFID Protocol,"in International Workshop on [8]“A Chronology of Data Breaches,”2009, http://www. Pervasive Computing and Communication Security (PerSec), privacyrights.org/ar/ChronDataBreaches.htm. 2005. [9]D.Anthony,T.Henderson,and D.Kotz,"Privacy in location- [29]C.Castelluccia and G.Avoine,"Noisy Tags:A Pretty Good Key aware computing environments,"IEEE Pervasive Computing, Exchange Protocol for RFID Tags,"in International Conference 2007. on Smart Card Research and Advanced Applications (CARDIS). [10]S.Lederer,J.I.Hong,X.Jiang,A.K.Dey,J.A. 2006. Landay,and J.Mankoff,"Towards everyday privacy for [30]R.D.Pietro and R.Molva,"Information Confinement,Privacy, ubiquitous computing,Computer Science Division,University and Security in RFID Systems,"in European Symposium On of California,Berkeley,Tech.Rep.UCB-CSD-03-1283 Research In Computer Security (ESORICS),2007. 2003.[Online].Available:http://www.cs.berkeley.edu/projects/ [31]T.Ristenpart,G.Maganis,A.Krishnamurthy,and T.Kohno io/publications/privacy-techreport03a.pdf "Privacy-preserving location tracking of lost or stolen devices: 111]A.Beresford and F.Stajano,"Location privacy in pervasive cryptographic techniques and replacing trusted third parties with computing,"IEEE Pervasive Computing,2003. DHTs,"in Usenix Security Symposium,2008. 112]A.R.Beresford and F.Stajano,"Mix zones:User privacy in [32]G.Tsudik,"Ya-trap:Yet another trivial rfid authentication location-aware services,"in Pervasive Computing and Commu- protocol,"in PERCOMW.2006. nications Workshops (PERCOMW),2004. 60to reuse an older t value. Thus, the adversary cannot link two locations to the same user. Finally, the adversary controlling the RFID reader may attempt to reuse old t values to track a user. The adversary can program the RFID reader to always use the same time t value, The idea here is to try to get an RFID tag to return a response that has been repeated before. This way, the adversary can determine that that same tag has move pass the reader twice. Here, we let ǫ to contain an always changing value n which is dependent on an incrementing counter ct. Therefore, even if the same same t, RID and ID values are used, the resulting ǫ will not be the same. VII. CONCLUSION As ubiquitous systems move towards real world deploy￾ments, privacy systems that do not rely on trusted servers will become increasing important. We believe that our work is an initial step towards more robust alternatives. Our future work considers two extensions. The first is to allow users to delegate data access control to other users, and the second is to explore techniques to improve range query performance. ACKNOWLEDGMENT We would like to thank all the reviewers (including ear￾lier WiSec reviwers) for their comments. This project was supported in part by US NSF grants CNS-0721443, CNS- 0831904, CAREER Award CNS-0747108. REFERENCES [1] D. Hahnel, W. Burgard, D. Fox, K. Fishkin, and M. Philipose, “Mapping and localization with rfid technology,” in IEEE International Conference on Robotics and Automation, 2004. [2] V. Stanford, “Pervasive computing goes the last hundred feet with rfid systems,” IEEE Pervasive Computing, 2003. [3] E. Bertino and R. Sandhu, “Database security-concepts, approaches, and challenges,” IEEE Transactions on Dependable and Secure Computing, 2005. [4] C. Ramaswamy, R. Sandhu, R. Ramaswamy, and R. S, “Role-based access control features in commercial database management systems,” in In Proceedings of 21st NIST-NCSC National Information Systems Security Conference, 1998. [5] R. Agrawal, J. Kiernan, R. Srikant, and Y. Xu, “Hippocratic databases,” in VLDB, 2002. [6] “Commerce Department: we lose laptops,” 2006, http://arstechnica. com/security/news/2006/09/7809.ars. [7] “FBI lost 160 laptops in last 44 months,” 2007, http:// arstechnica.com/old/content/2007/02/8821.ars. [8] “A Chronology of Data Breaches,” 2009, http://www. privacyrights.org/ar/ChronDataBreaches.htm. [9] D. Anthony, T. Henderson, and D. Kotz, “Privacy in location￾aware computing environments,” IEEE Pervasive Computing, 2007. [10] S. Lederer, J. I. Hong, X. Jiang, A. K. Dey, J. A. Landay, and J. Mankoff, “Towards everyday privacy for ubiquitous computing,” Computer Science Division, University of California, Berkeley, Tech. Rep. UCB-CSD-03-1283, 2003. [Online]. Available: http://www.cs.berkeley.edu/projects/ io/publications/privacy-techreport03a.pdf [11] A. Beresford and F. Stajano, “Location privacy in pervasive computing,” IEEE Pervasive Computing, 2003. [12] A. R. Beresford and F. Stajano, “Mix zones: User privacy in location-aware services,” in Pervasive Computing and Commu￾nications Workshops (PERCOMW), 2004. [13] U. Hengartner and P. Steenkiste, “Access control to people location information,” ACM Trans. Inf. Syst. Secur., 2005. [14] J. I. Hong and J. A. Landay, “An architecture for privacy￾sensitive ubiquitous computing,” in International conference on Mobile systems, applications, and services (MobiSys), 2004. [15] G. Myles, A. Friday, and N. Davies, “Preserving privacy in environments with location-based applications,” IEEE Pervasive Computing, 2003. [16] A. Kapadia, T. Henderson, J. J. Fielding, and D. Kotz, “Virtual walls: Protecting digital privacy in pervasive environments,” in Proceedings of the Fifth International Conference on Pervasive Computing (Pervasive), 2007. [17] T. Kriplean, E. Welbourne, N. Khoussainova, V. Rastogi, M. Balazinska, G. Borriello, T. Kohno, and D. Suciu, “Physical access control for captured rfid data,” IEEE Pervasive Comput￾ing, 2007. [18] V. Rastogi, E. Welbourne, N. Khoussainova, T. Kriplean, M. Balazinska, G. Borriello, T. Kohno, and D. Suciu, “Express￾ing privacy policies using authorization views,” in Workshop on Ubicomp Privacy, (Ubicomp), 2007. [19] T. Rodden, A. Friday, H. Muller, and A. Dix, “A lightweight ap￾proach to managing privacy in location-based services, equator- 02-058,” University of Nottingham and Lancaster University and University of Bristol, Tech. Rep. CSTR-07-006, 2002. [20] S. Weis, S. Sarma, R. Rivest, and D. Engels, “Security and Privacy Aspects of Low-Cost Radio Frequency Identification Systems,” in International Conference on Security in Pervasive Computing, 2003. [21] D. Molnar and D. Wagner, “Privacy and Security in Library RFID: Issues, Practices, and Architectures,” in Conference on Computer and Communications Security, 2004. [22] K. Ouafi and R. C.-W. Phan, “Privacy of Recent RFID Authen￾tication Protocols,” in 4th International Conference on Informa￾tion Security Practice and Experience – ISPEC 2008, 2008. [23] D. X. Song, D. Wagner, and A. Perrig, “Practical techniques for searches on encrypted data,” in IEEE Symposium on Security and Privacy, 2000. [24] D. Boneh, G. D. Crescenzo, R. Ostrovsky, and G. Persiano, “Public key encryption with keyword search,” in EUROCRYPT, 2004. [25] S. Wang, X. Ding, R. H. Deng, and F. Bao, “Private information retrieval using trusted hardware,” in European Symposium On Research In Computer Security (ESORICS), 2006. [26] Z. Yang, S. Zhong, and R. N. Wright, “Privacy-preserving queries on encrypted data,” in European Symposium On Re￾search In Computer Security (ESORICS), 2006. [27] R. Dingledine, N. Mathewson, and P. Syverson, “Tor: the second-generation onion router,” in USENIX Security Sympo￾sium, 2004. [28] G. Avoine and P. Oechslin, “A Scalable and Provably Secure Hash Based RFID Protocol,” in International Workshop on Pervasive Computing and Communication Security (PerSec), 2005. [29] C. Castelluccia and G. Avoine, “Noisy Tags: A Pretty Good Key Exchange Protocol for RFID Tags,” in International Conference on Smart Card Research and Advanced Applications (CARDIS), 2006. [30] R. D. Pietro and R. Molva, “Information Confinement, Privacy, and Security in RFID Systems,” in European Symposium On Research In Computer Security (ESORICS), 2007. [31] T. Ristenpart, G. Maganis, A. Krishnamurthy, and T. Kohno, “Privacy-preserving location tracking of lost or stolen devices: cryptographic techniques and replacing trusted third parties with DHTs,” in Usenix Security Symposium, 2008. [32] G. Tsudik, “Ya-trap: Yet another trivial rfid authentication protocol,” in PERCOMW, 2006. 60