Lune

NDSS2016Top-tier venue

Privacy-Preserving Shortest Path Computation

David J. Wu, Joe Zimmerman, Jérémy Planul, John C. Mitchell

Abstract

Navigation is one of the most popular cloud computing services. But in virtually all cloud-based navigation systems, the client must reveal her location and destination to the cloud service provider in order to learn the fastest route. In this work, we present a cryptographic protocol for navigation on city streets that provides privacy for both the client's location and the service provider's routing data. Our key ingredient is a novel method for compressing the next-hop routing matrices in networks such as city street maps. Applying our compression method to the map of Los Angeles, for example, we achieve over tenfold reduction in the representation size. In conjunction with other cryptographic techniques, this compressed representation results in an efficient protocol suitable for fully-private real-time navigation on city streets. We demonstrate the practicality of our protocol by benchmarking it on real street map data for major cities such as San Francisco and Washington, D.C. This is the extended version of a paper by the same name that appeared at the Network and Distributed System Security Symposium (NDSS) in February, 2016. Permission to freely reproduce all or part of this paper for noncommercial purposes is granted provided that copies bear this notice and the full citation on the first page. Reproduction for commercial purposes is strictly prohibited without the prior written consent of the Internet Society, the first-named author (for reproduction of an entire paper only), and the author's employer if the paper was prepared within the scope of employment.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

11 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Feature Inference Attack on Model Predictions in Vertical Federated Learning cites Privacy Preserving Vertical Federated Learning for Tree-based Models
  • Falcon: A Privacy-Preserving and Interpretable Vertical Federated Learning System cites Feature Inference Attack on Model Predictions in Vertical Federated Learning
  • Falcon: A Privacy-Preserving and Interpretable Vertical Federated Learning System cites Privacy Preserving Vertical Federated Learning for Tree-based Models
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers11

  1. Privacy Preserving Vertical Federated Learning for Tree-based ModelsYuncheng Wu, Shaofeng Cai, Xiaokui Xiao, Gang Chen et al.VLDB 2020 · 259 citations
  2. Feature Inference Attack on Model Predictions in Vertical Federated LearningXinjian Luo, Yuncheng Wu, Xiaokui Xiao, Beng Chin OoiICDE 2021 · 212 citations
  3. SPIRAL: Fast, High-Rate Single-Server PIR via FHE CompositionSamir Jordan Menon, David J. WuS&P 2022 · 153 citations
  4. ObliDB: Oblivious Query Processing for Secure DatabasesSaba Eskandarian, Matei ZahariaVLDB 2020 · 127 citations
  5. Falcon: A Privacy-Preserving and Interpretable Vertical Federated Learning SystemYuncheng Wu, Naili Xing, Gang Chen, Tien Tuan Anh Dinh et al.VLDB 2023 · 47 citations

Related papers

  1. TRACE: Real-time Compression of Streaming Trajectories in Road NetworksTianyi Li, Lu Chen, Christian S. Jensen, Torben Bach PedersenVLDB 2021 · 73 citations
  2. A Privacy-Enhanced and Personalized Safe Route Planner with Crowdsourced Data and ComputationFariha Tabassum Islam, Tanzima Hashem, Rifat ShahriyarICDE 2021 · 19 citations
  3. Continuously Monitoring Alternative Shortest Paths on Road NetworksLingxiao Li, Muhammad Aamir Cheema, Mohammed Eunus Ali, Hua Lu et al.VLDB 2020 · 22 citations
  4. Privacy-Preserving Approximate Nearest Neighbor Search on High-Dimensional DataYingfan Liu, Yandi Zhang, Jiadong Xie, Hui Li et al.ICDE 2025 · 2 citations
  5. Generating Landmark Navigation Instructions from Maps as a Graph-to-Text ProblemRaphael Schumann, Stefan RiezlerACL 2021
Dusk over the sea between two cliffs drawn in fine vertical lines