EP-GSPR: An Efficient Privacy-Preserving Graph Shortest Path Retrieval Scheme
Chenbin Zhao, Ruifeng Zhu, Jing Chen, Ruiying Du, Kun He, Jianting Ning, Yang Xiang · IEEE Transactions on Mobile Computing · 2025
The continuous development of mobile terminal applications, online maps, and other navigation services have become widely used, simultaneously giving rise to significant security risks. To address the issues of privacy leakage and low efficiency in traditional graph shortest path retrieval schemes, an efficient privacy-preserving graph shortest path retrieval scheme is proposed, called EP-GSPR. Specifically, this scheme addresses the privacy security problems in the existing graph shortest path retrieval solutions by ensuring the bilateral privacy protection of the user's query location and the database privacy of the cloud server. Throughout the retrieval process, the cloud server cannot obtain the user's location information, and the user cannot access any database information other than the retrieval results. To overcome the performance bottlenecks in existing schemes, a progressive iterative retrieval framework is designed as the fundamental modular, called Pirf, achieving sub-linear retrieval costs and low storage overhead on the cloud server side. Finally, the security analyses demonstrate the EP-GSPR scheme achieves the bilateral privacy-preserving in terms of user and server sides. The comprehensive experiment evaluations also state the efficiency and practicality of the proposed scheme