Open Access

ARTICLE

Road Distance Computation Using Homomorphic Encryption in Road Networks

by Haining Yu¹, Lailai Yin^1,*, Hongli Zhang¹, Dongyang Zhan^1,2, Jiaxing Qu³, Guangyao Zhang⁴

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. https://doi.org/10.32604/cmc.2021.019462

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

Abstract

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.

---

Keywords

---