Accurate, Secure, and Efficient Semi-Constrained Navigation Over Encrypted City Maps

TY - JOUR

T1 - Accurate, Secure, and Efficient Semi-Constrained Navigation Over Encrypted City Maps

AU - Li, Meng

AU - Chen, Yifei

AU - Gao, Jianbo

AU - Wu, Jingyu

AU - Zhang, Zijian

AU - He, Jialing

AU - Zhu, Liehuang

AU - Conti, Mauro

AU - Lin, Xiaodong

N1 - Publisher Copyright: © 2004-2012 IEEE.

PY - 2025

Y1 - 2025

N2 - Navigation services enable users to find the shortest path from a starting point S to a destination D, reducing time, gas, and traffic congestion. Still, navigation users risk the exposure of their sensitive location data. Our motivation arises from how users can accurately, securely, and efficiently navigate from S to Dwhile passing through k unordered stops, i.e., midway locations with a non-fixed visiting order. In this work, we formally define Semi-Constrained Navigation (SCN) and present a novel scheme Hermestoachieveaccurate,secure, andefficient SCN. Specifically, weproposeadivide-and-conquerapproachtostrikeagoodbalance betweenaccuracyandefficiency. It recursively depth-first-searches the whole area (a navigation tree) and invokes five carefully-crafted strategies stop-by-stop to compute three subpaths in three se quential subareas. We construct a path-distance oracle to encrypt the road graph and securely implement the strategies by using homomorphic encryption and garble circuits. We formally prove the security in the random oracle model and analyze the search complexity to be less than O(k2). We experiment over a real-world city map and compare with six baselines. Results show that path search with k = 4 among N = 1000 intersections requires 5.58 seconds with a 3.2% distance deviation rate and an 82.5% path similarity.

AB - Navigation services enable users to find the shortest path from a starting point S to a destination D, reducing time, gas, and traffic congestion. Still, navigation users risk the exposure of their sensitive location data. Our motivation arises from how users can accurately, securely, and efficiently navigate from S to Dwhile passing through k unordered stops, i.e., midway locations with a non-fixed visiting order. In this work, we formally define Semi-Constrained Navigation (SCN) and present a novel scheme Hermestoachieveaccurate,secure, andefficient SCN. Specifically, weproposeadivide-and-conquerapproachtostrikeagoodbalance betweenaccuracyandefficiency. It recursively depth-first-searches the whole area (a navigation tree) and invokes five carefully-crafted strategies stop-by-stop to compute three subpaths in three se quential subareas. We construct a path-distance oracle to encrypt the road graph and securely implement the strategies by using homomorphic encryption and garble circuits. We formally prove the security in the random oracle model and analyze the search complexity to be less than O(k2). We experiment over a real-world city map and compare with six baselines. Results show that path search with k = 4 among N = 1000 intersections requires 5.58 seconds with a 3.2% distance deviation rate and an 82.5% path similarity.

KW - Navigation services

KW - accuracy

KW - efficiency

KW - security

KW - unordered stops

UR - https://www.scopus.com/pages/publications/85213408377

U2 - 10.1109/TDSC.2024.3521396

DO - 10.1109/TDSC.2024.3521396

M3 - Article

AN - SCOPUS:85213408377

SN - 1545-5971

VL - 22

SP - 2642

EP - 2658

JO - IEEE Transactions on Dependable and Secure Computing

JF - IEEE Transactions on Dependable and Secure Computing

IS - 3

ER -