Privacy-preserving location-based services.

University of Minnesota Ph.D. dissertation. May 2010. Major: Computer Science. Advisors: Dr. Mohamed F. Mokbel and Dr. Tian He. 1 computer file (PDF); xii, 209 pages.Location-based services (LBS for short) providers require users' current locations to answer their location-based queries, e.g., range and nearest-neighbor queries. Revealing personal location information to potentially untrusted service providers could create privacy risks for users. To this end, our objective is to design a privacy-preserving framework for LBS where users can obtain LBS and preserve their location privacy. In this thesis, we propose privacy-preserving LBS frameworks for different environments: (1) client-server environments in Euclidean space (the Casper system), (2) client-server environments in road networks, (3) mobile peer-to-peer environments, and (4) location monitoring services in wireless sensor networks (the TinyCasper system). In general, these frameworks have two main modules, namely, location anonymization and privacy- aware query processing. The location anonymization module blurs an user's exact location into a cloaked area (or a cloaked road segment set in road network environments) that satisfies the user's privacy requirements. The proposed frameworks support the two most popular privacy requirements, k-anonymity, i.e., a user is indistinguishable among k users, and minimum area Amin (or minimum total length of a cloaked road segment set), i.e., the size of a cloaked area is at least Amin. The user is able to specify his/her privacy requirements in a privacy profile and change the privacy profile at any time. The privacy-aware query processing module is embedded inside a database server to provide LBS based on cloaked areas (or cloaked road segment sets). To prove the concept of our privacy-preserving LBS frameworks, we implement system prototypes for Casper and TinyCasper. For each proposed privacy-preserving LBS framework, we conduct extensive experiments to evaluate the performance of its location anonymization and privacy-aware query processing modules. All experiment results show that the proposed frameworks are scalable and efficient with respect to large numbers of users, large numbers of queries, and various privacy requirements, and they provide high quality services in terms of the accuracy of query answers and the query response time