Shortest path computation with no information leakage

Kyriakos Mouratidis, Man Lung Yiu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

60 Citations (Scopus)


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, shop- ping preferences, lifestyle choices, etc. The only existing method for privacy-preserving shortest path computation follows the obfus- cation 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 estab- lished private information retrieval techniques, which we treat as black-box building blocks. Experiments on real, large-scale road networks assess the practicality of our schemes.
Original languageEnglish
Pages (from-to)692-703
Number of pages12
JournalProceedings of the VLDB Endowment
Issue number8
Publication statusPublished - 1 Jan 2012

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • General Computer Science


Dive into the research topics of 'Shortest path computation with no information leakage'. Together they form a unique fingerprint.

Cite this