Privacy Preserving Scheme for Location-Based Services
- 1 Laboratoire d’Electronique et de Communications—LEC, Ecole Mohammadia d’Ingénieurs—EMI, Université Mohammed V-Agdal—UM5A. BP, Rabat, Morocco
- 2 University of Ontario Institute of Technology, Oshawa, Canada
- 3 Laboratoire d’Electronique et de Communications—LEC, Ecole Mohammadia d’Ingénieurs—EMI, Université Mohammed V-Agdal—UM5A. BP, Rabat, Morocco
- 4 University of Ontario Institute of Technology, Oshawa, Canada
Abstract
Homomorphic encryption schemes make it possible to perform arithmetic operations, like additions and multiplications, over encrypted values. This capability provides enhanced protection for data and offers new research directions, including blind data processing. Using homomorphic encryption schemes, a Location-Based Service (LBS) can process encrypted inputs to retrieve encrypted location-related information. The retrieved encrypted data can only be decrypted by the user who requested the data. The technology still faces two main challenges: the encountered processing time and the upper limit imposed on the allowed number of operations. However, the protection of users’ privacy achieved through this technology makes it attractive for more research and enhancing. In this paper we use homomorphic encryption schemes to build a fully secure system that allows users to benefit from location-based services while preserving the confidentiality and integrity of their data. Our novel system consists of search circuits that allow an executor ( i.e. LBS server) to receive encrypted inputs/requests and then perform a blind search to retrieve encrypted records that match the selection criterion. A querier can send the user’s position and the service type he/she is looking for, in encrypted form, to a server and then the server would respond to the request without any knowledge of the contents of the request and the retrieved records. We further propose a prototype that improves the practicality of our system.
- Clarinox Technologies Pty Ltd., “Real Time Location Systems,” 2009. http://www.clarinox.com/docs/whitepapers/RealTime_main.pdf
- M. Gruteser and D. Grunwald, “Anonymous Usage of Location-Based Services through Spatial and Temporal Cloaking,” Proceedings of the 1st International Conference on Mobile Systems, Applications and Services, San Francisco, 5-8 May 2003, pp. 31-42. doi:10.1145/1066116.1189037
- C. Y. Chow, M. F. Mokbel and X. Liu, “A Peer-to-Peer Spatial Cloaking Algorithm for Anonymous LocationBased Services,” Proceedings of the 14th Annual ACM International Symposium on Advances in Geographic Information Systems, Arlington, 10-11 November 2006, pp. 171-178. doi:10.1145/183471.1183500
- B. Gedik and L. Liu, “Location Privacy in Mobile Systems a Personalized Anonymization Model,” Proceedings of the 25th International Conference on Distributed Computing System of the IEEE ICDCS, Columbus, 10 June 2005, pp. 620-629. doi:10.1109/ICDCS.2005.48
- M. F. Mokbel, C. Y. Chow and W. G. Aref, “The New Casper: Query Processing for Location Services without Compromising Privacy,” Proceedings of the VLDB 2006, Seoul, 12-15 September 2006, pp. 763-774.
- D. Reid, “An Algorithm for Tracking Multiple Targets,” IEEE Transactions on Automatic Control, Vol. 24, No. 6, 1979, pp. 843-854. doi:10.1109/TAC.1979.1102177
- B. Gedik and L. Liu, “A Customizable k-Anonymity Model for Protecting Location Privacy,” Technical Report, Georgia Institute of Technology, Atlanta, 2004.
- H. Kido, Y. Yanagisawa and T. Satoh, “An Anonymous Communication Technique Using Dummies for LocationBased Services,” Proceedings of the International Conference on Pervasive Services of the IEEE ICPS 05, Santorini, 11-14 July 2005, pp. 88-97. doi:10.1109/PERSER.2005.1506394
- T. You, W. Peng and W. Lee, “Protect Moving Trajectories with Dummies,” Proceedings of the International Conference on Mobile Data Management, Mannheim, 1 May 2007, pp. 278-282. doi:10.1109/MDM.2007.58
- G. Ghinita, P. Kalnis, A. Khoshgozaran, C. Shahabi and K.-L. Tan, “Private Queries in Location-Based Services: Anonymizers Are Not Necessary,” Proceedings of the SIGMOD 08, Vancouver, 9-12 June 2008, pp. 121-132.
- C. Gentry and Z. Ramzan, “Single-Database Private InFormation Retrieval with Constant Communication Rate,” Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, Lisboa, 11-15 July 2005, pp. 803-815.