Conference Proceeding Article
Shortest path computation is one of the most common queries in location-based services (LBSs). Although particularly useful, such queries raise serious privacy concerns. Exposing to a (potentially untrusted) LBS the client’s position and her destination may reveal personal information, such as social habits, health condition, shopping preferences, lifestyle choices, etc. The only existing method for privacy-preserving shortest path computation follows the obfuscation paradigm; it prevents the LBS from inferring the source and destination of the query with a probability higher than a threshold. This implies, however, that the LBS still deduces some information (albeit not exact) about the client’s location and her destination. In this paper we aim at strong privacy, where the adversary learns nothing about the shortest path query. We achieve this via established PIR techniques, which we treat as black-box building blocks. Experiments on real, large-scale road networks verify the efficiency and practicality of our schemes.
Black boxes, Building blockes, Health condition, Information leakage, Lifestyle choices, Personal information, Privacy concerns, Privacy preserving, Private information retrieval, Road network, Shortest path, Shortest path computations
Databases and Information Systems | Numerical Analysis and Scientific Computing
Data Management and Analytics
Proceedings of the VLDB Endowment: 38th VLDB 2012, August 27-31, Istanbul, Turkey
City or Country
MOURATIDIS, Kyriakos and YIU, Man Lung.
Shortest Path Computation with No Information Leakage. (2012). Proceedings of the VLDB Endowment: 38th VLDB 2012, August 27-31, Istanbul, Turkey. 5, 692-703. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/1488
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.