Privacy-Preserving Location-Based Services

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 A [subscript min]" (or minimum total length of a cloaked road segment set), i.e., the size of a cloaked area is at least "A [subscript min]". 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. [The dissertation citations contained here are published with the permission of ProQuest LLC. Further reproduction is prohibited without permission. Copies of dissertations may be obtained by Telephone (800) 1-800-521-0600. Web page: http://www.proquest.com/en-US/products/dissertations/individuals.shtml.]