Open Access


Road Distance Computation Using Homomorphic Encryption in Road Networks

Haining Yu1, Lailai Yin1,*, Hongli Zhang1, Dongyang Zhan1,2, Jiaxing Qu3, Guangyao Zhang4
1 School of Cyberspace Science, Harbin Institute of Technology, Harbin, 150001, China
2 The Ohio State University, Columbus, 43202, USA
3 Heilongjiang Province Cyberspace Research Center, Harbin, 150001, China
4 National Internet Emergency Response Center, Harbin, 150001, China
* Corresponding Author: Lailai Yin. Email:

Computers, Materials & Continua 2021, 69(3), 3445-3458.

Received 14 April 2021; Accepted 26 May 2021; Issue published 24 August 2021


Road networks have been used in a wide range of applications to reduces the cost of transportation and improve the quality of related services. The shortest road distance computation has been considered as one of the most fundamental operations of road networks computation. To alleviate privacy concerns about location privacy leaks during road distance computation, it is desirable to have a secure and efficient road distance computation approach. In this paper, we propose two secure road distance computation approaches, which can compute road distance over encrypted data efficiently. An approximate road distance computation approach is designed by using Partially Homomorphic Encryption and road network set embedding. An exact road distance computation is built by using Somewhat Homomorphic Encryption and road network hypercube embedding. We implement our two road distance computation approaches, and evaluate them on the real city-scale road network. Evaluation results show that our approaches are accurate and efficient.


Road network; road distance; homomorphic encryption

Cite This Article

H. Yu, L. Yin, H. Zhang, D. Zhan, J. Qu et al., "Road distance computation using homomorphic encryption in road networks," Computers, Materials & Continua, vol. 69, no.3, pp. 3445–3458, 2021.

This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • 1045


  • 798


  • 0


Share Link

WeChat scan