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.
Nowadays, road networks have been widely used in many application domains for sciences and engineering, such as closeness testing in spatial social networks, route planning, ride hailing or navigation in road networks, etc. For example, online ride hailing services such as Uber and DiDi employ large road networks with millions or even billions of vertices and edges in their operation. A well-maintained road network computation system plays a significant role. It not only reduces the cost of transportation, both in terms of money and time, but also improves the quality of upper services.
The shortest road distance computation has been considered as one of the most fundamental operations of road networks computation and has a wide range of applications. There are many efficient shortest distance (path) algorithms, such as Dijkstra's algorithm and Bellman Ford's Algorithm. In some application scenarios, the shortest road distance must be computed in encryption form to avoid privacy leaks. As an example, an online ride hailing service enables a rider to find the closest driver to offer ride service. To enjoy this service, both riders and drivers have to update their locations to the online ride hailing service provider, while the service provider computes the shortest road distances from the rider to all drivers, and select the closest driver. But the service providers are not always honest, they may track users or infer their profiles for economic advantage. To alleviate this privacy concerns, the riders and the driver submit their encrypted locations, and the service provider can compute the encrypted road distance over received ciphertexts. However, it is not a trivial problem to compute shortest road distance in ciphertext domain. Some schemes have been presented in the literature to compute shortest road distance in a secure manner, which make use of cryptographic primitives to encrypt the road network itself or the corresponding pre-generated index,
To tackle the practical limitations of the state-of-the-art, we propose two secure road distance computation approaches, which can compute road distance over encrypted data efficiently. We summarize main contributions as:
We propose an efficient approximate road distance computation approach over encrypted data, by using PHE and road network set embedding. Our approach only needs several additive homomorphic operations to compute an encrypted approximate road distance. We propose an efficient exact road distance computation approach over encrypted data, by using SHE and road network hypercube embedding. Our approach only needs several additive and multiplicative homomorphic operations over packed ciphertexts to compute an encrypted exact road distance. We implement our approximate road distance computation approach using Paillier Cryptosystem and exact road distance computation approach using FV scheme. Their performance is evaluated on the real city-scale road network. Evaluation results show that they achieve high accuracy, and keep efficient.
The remainder of this paper is structured as follows. In Section 2, we briefly introduce necessary preliminaries. In Section 3, we propose two road distance computation approaches over encrypted data. In Section 4, we evaluate their performance. Finally, we review the related literature and summarize the paper.
Partially homomorphic encryption (PHE) allows to carry out operations over ciphertexts. Paillier cryptosystem [
Paillier cryptosystem has properties of additive homomorphism and the mixed multiplication homomorphism: for any
FV scheme [ Decryption:
Express
In this section, we propose two different methods to compute road distance in ciphertext domain.
By using Road Network Set Embedding (RNSE) technique [
We model the road network as a weighted planar graph
where
Based on the above definition, the coordinate of a node
Then we can use
For the coordinate of a position
where
Without losing generality, let the embedded road network have
where
Suppose that the road network is represented by
The coordinates
The encrypted approximate road distance between
1) Compute the ciphertext vector
Note that
2) Because Paillier cryptosystem has a plaintext space much larger than the upper limit of the road distance, several ciphertexts can be packed into one ciphertext using ciphertext packing technology, which can improve the efficiency. In the Paillier cryptosystem, assuming that
After performing a decryption operation, we can get the packed plaintext
3) The approximate road distance between
The
Related definitions are as follows.
The An A cut An
The embedded road network Starting with Next, we turn right on one odd face and left on the other (we can obtain more alternating cuts by changing the selection of odd face). Proceeding in both directions, we alternate at all odd faces and end up with reaching the outer face. Clearly, the coordinate is an
The computational complexity of hypercube embedding is
Vertex | Label |
---|---|
00000000000000 | |
11111100000000 | |
11111111001100 | |
11111111111100 | |
11111101111110 | |
11010001111111 | |
01000001111111 | |
00000000110000 | |
11111100110000 | |
11111100111100 |
Let
where
Given
For locations
Using the homomorphic property of FV Scheme, the encrypted
Then, the encrypted
When the length of
For the coordinate
where
Given the coordinate
where
Encrypted
then we have
where
then we have
The constant term in
then we have
The inner product of two coordinates
Based on
Based on
where we have
It needs only three multiplicative homomorphisms operations and four subtractive/additive homomorphisms operations for the calculation of the shortest road distance over two locations.
Our experiments are performed on the real road network of California, which consists of 21048 vertices and 21693 edges (
We evaluate the accuracy and the efficiency of our proposed road distance approaches in a k-Nearest Neighbors (kNN) query application [
Numerous protocols have been proposed for private shortest road distance computation in different applications, such as kNN query and navigation. For (yet related) privacy issues of distance computation, some approaches utilize structural anonymization [
In this paper, we proposed 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. According to the evaluation over a real city-scale road network, we have verified that our approaches are accurate and efficient.