Accurate, Secure, and Efficient Semi-Constrained Navigation with Multiple Spatial Restrictions

Graph-Based Service (GBS) facilitates navigation in multiple scenarios. Although convenient, it requires users to upload their locations to an untrusted navigation server. Such interaction violates location privacy of users who prioritize sensitive locations. Unfortunately, existing work neglects partial visit orders and geographic features, which motivates us to consider partially ordered stops and circuitous path between two stops. In this work, we advance the state-of-the-art on Secure Semi-Constrained Navigation by allowing Multiple Spatial Restrictions (SCN-MSR), while improving navigation accuracy without sacrificing security. Based on the Divide-and-Conquer strategy, we design four novel navigation algorithms NLow, NMid, NHigh, and secure skimming. They enable an untrustworthy navigation server to search over an encrypted dataset to find the shortest path via k stops, subject to following orders of several stops and circumventing road obstacles. Next, we provide formal security analysis under the semi-honest adversary model. Experimental results demonstrate that Gaia achieves high geometric alignment with theoretical optimal paths and reduces navigation time by approximately 60% compared to the state-of-the-art Hermes, requiring only about 1.6 s to search over 2,200 road intersections with 5 stops and 3 partial orders.