Privacy-Preserving Shortest Distance Query for Dynamic Large-Scale Road Network

The road network plays an important role in guiding people's daily travel. In the road network, the shortest distance query is one of the most basic query operations. With the scale of the road network continuously expanding, people choose to outsource the road network to the cloud server in the form of an encrypted graph. To the best of authors' knowledge, the existing privacy-preserving shortest distance query schemes over large-scale encrypted graphs are all designed for the static graph. Nonetheless, the graph of road network is often updated over time. These static privacy-preserving shortest distance query schemes cannot work well in this practical application. In order to address this problem, we explore how to implement the privacy-preserving shortest distance query in an incremental large-scale road network. We use the 2-hop cover label index as the basic secure index structure, which can realize the shortest distance fast query. In order to update the 2-hop cover label index safely and efficiently, we combine a special adjacency index as an auxiliary index structure with homomorphic encryption to implement a dynamic incremental update algorithm for the encrypted graph. We prove that the proposed scheme achieves adaptive semantic security and verify its practicality through experiments.