Computers, Materials & Continua DOI:10.32604/cmc.2021.019462 | |

Article |

Road Distance Computation Using Homomorphic Encryption in Road Networks

1School of Cyberspace Science, Harbin Institute of Technology, Harbin, 150001, China

2The Ohio State University, Columbus, 43202, USA

3Heilongjiang Province Cyberspace Research Center, Harbin, 150001, China

4National Internet Emergency Response Center, Harbin, 150001, China

*Corresponding Author: Lailai Yin. Email: yinlailai163@163.com

Received: 14 April 2021; Accepted: 26 May 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: Road network; road distance; homomorphic encryption

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, e.g., Partially Homomorphic Encryption (PHE), Somewhat Homomorphic Encryption (SHE), Yao’s garbled circuits (GCs). Shen et al. [1] proposed a graph encryption scheme based on symmetric-key primitives and SHE, which enables approximate constrained shortest distance queries. Meng et al. [2] presented three schemes based on distance oracle and structured encryption for approximate shortest distance queries. Wang et al. [3] proposed a secure Graph DataBase (SecGDB) encryption scheme based on PHE and Yao's GCs, which supports exact shortest distance/path queries. Wu et al. [4] proposed an efficient cryptographic protocol for fully-private navigation based on compressing the next-hop routing matrices, symmetric Private Information Retrieval (PIR) and Yao's GCs. However, existing schemes are not efficient enough to compute large-scale shortest distances in real time.

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 [5] is a popular PHE scheme, which relies on the decisional composite residuosity assumption. We briefly summarize it as follows for better understanding and description of our plan.

• Key Generation:

• Encryption:

• Decryption:

Paillier cryptosystem has properties of additive homomorphism and the mixed multiplication homomorphism: for any

FV scheme [6] is a widely used SHE scheme which can support a finite number of both multiplications and additions on data in the cipher domain. Mathematically, FV scheme depends on a hard computation problem named as Ring Learning with Errors (RLWE) problem. Set

• Key Generation:

• Encryption:

• Decryption:

• Homomorphic Addition:

• Homomorphic Multiplication:

Express

In this section, we propose two different methods to compute road distance in ciphertext domain.

3.1 Approximate Road Distance Computation with PHE

3.1.1 Road Network Set Embedding

By using Road Network Set Embedding (RNSE) technique [7], the planar road network can be converted into a high-dimensional space, in which we can convert the complex calculation of the shortest road distance into a simple calculation supported through existing encryption primitives.

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

3.1.2 Encrypted Approximate Road Distance Computation Using Paillier Cryptosystem

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

3.2 Exact Road Distance Computation with SHE

3.2.1 Road Network Hypercube Embedding

The m-dimensional hypercube

Related definitions are as follows.

• The interior face

• An even(odd ) face means a face with even(odd ) edges. Let

• A cut

• An alternating cut refers to a cut which alternates on the odd faces. In other words, if the cut turns left (resp. right) on an odd face, then it turns right (resp. left) on the following odd face. We can view an alternating cut as a line which passes through the graph and intersects only the selected edges.

The embedded road network

• Starting with e, we move in both directions, take opposite edge on even face and end when we meet the first odd face in both directions.

• 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 m-dimensional boolean vector, where m is the total number of alternating cuts. At last,

The computational complexity of hypercube embedding is

Let

where

Given

3.2.2 Encrypted Exact Road Distance Computation Using FV Scheme

For locations

Using the homomorphic property of FV Scheme, the encrypted

Then, the encrypted

When the length of m is long, the computation overhead of above basic distance computation method is heavy, since it is inefficient to encrypt/decrypt coordinate bit-by-bit. To reduce computation overhead, we propose an optimized approach with ciphertext packing to compute the shortest road distance efficiently. We now describe the details of two packed ciphertext constructions for the coordinates

For the coordinate

where

Given the coordinate

where

Encrypted

then we have

where

then we have

The constant term in Eq. (21) equals the Hamming weight of

then we have

The inner product of two coordinates

Based on Eq. (9), we can use three packed ciphertexts (18), (20) and (22) to calculate the encrypted

Based on Eq. (10) and (24), the ciphertext of the distance between location

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 (https://www.cs.utah.edu/~lifeifei/SpatialDataset.htm). Following the assumptions made in [7], we need to delete some trivial edges and insert virtual vertices on edges with fixing the unit distance. For PHE, we use the Paillier cryptosystem library (https://acsc.cs.utexas.edu/libpaillier). For the modified Paillier cryptosystem, we set N and g to 1024 bits and 160 bits, respectively. For SHE, we use FV scheme built on FV-NFLlib (https://github.com/CryptoExperts/FV-NFLlib), and the degree of polynomials in FV scheme n is set to 2048. All our experiments are conducted and executed on a PC running Ubuntu 18.04 LTS, with an Intel i7 processor at 3.4GHZ and 16GB RAM.

We evaluate the accuracy and the efficiency of our proposed road distance approaches in a k-Nearest Neighbors (kNN) query application [12,13]. We first generate some locations on the edges of the road networks in a random fashion. Then, one location is randomly picked as the starting location, from which all road distances to other locations are computed by using our approaches. Finally, the closest location is selected as the nearest neighbor. Fig. 2 depicts the accuracy of kNN query by using Euclidean distance, approximate road distance (dimension

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 [14], differential privacy [15–17] or Private Information Retrieval (PIR) [18] to guarantee privacy for the client or the server. However, these approaches suffer from limited privacy, performance or scalability. There is also a vast literature on privacy-preserving shortest distance computation in structured encryption [19] or graph encryption, which focuses on protecting graph data when outsourced to third-party servers or on the cloud [20–22]. The most famous class of structured encryption schemes are searchable symmetric encryption (SSE) schemes [23]. Generally speaking, SSE schemes usually encrypt indexes or search trees for the purpose of efficiently searching on encrypted data. Another line of work executing graph algorithms over encrypted graphs is to develop data-oblivious algorithms [24] or data structures [25]. In these solutions, the graph data is stored in an Oblivious RAM (ORAM) [26] or an oblivious data structure on the server. The client can compute the shortest distances on the server without leaking its access patterns. Also relevant are the works based on SMC, such as Yao’s GCs and ORAM. The generic solution is to construct a GC that contains the entire graph structure for a shortest-path algorithm and apply Yao’s protocol. However, above approaches are often prohibitively expensive and impractical for city-scale road networks [27,28]. For instance, the GC-based approach by Carter et al. [29,30] requires several minutes to compute a single shortest path in a road network with just 100 vertices. Another generic approach combining GCs and ORAM requires communication overhead on the order of GB and run-times ranging from tens of minutes to several hours for a single computation on a network with 1024 vertices. Recently, some schemes are proposed to support computation over large-scale encrypted graphs. Shen et al. [1] proposed a graph encryption scheme based on symmetric-key primitives and SHE, which enables approximate constrained shortest distance queries. Meng et al. [2] presented three schemes based on distance oracle and structured encryption for approximate shortest distance queries. Above two schemes provide an estimate on the shortest distance, along with sacrificing accuracy. Wang et al. [3] proposed a secure Graph Data Base (SecGDB) encryption scheme based on PHE and Yao's GCs, which supports exact shortest distance/path queries. Wu et al. [4] proposed an efficient cryptographic protocol for fully-private navigation based on compressing the next-hop routing matrices, symmetric Private Information Retrieval (PIR) and Yao's GCs, which requires about 1.5 s and less than 100 KB of bandwidth for each hop in city-scale road network. Compared with existing schemes, our two road distance computation approaches are more efficient to compute large-scale shortest distances in real time.

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.

Funding Statement: This work was partially supported by National Natural Science Foundation of China (Grant Nos. 61601146, 61732022), National Key R&D Program of China (Grant No. 2016QY05X1000).

Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.

1. M. Shen, B. Ma, L. Zhu, R. Mijumbi and X. Du, “Cloud-based approximate constrained shortest distance queries over encrypted graphs with privacy protection,” IEEE Transactions on Information Forensics and Security, vol. 13, no. 4, pp. 940–953, 2018. [Google Scholar]

2. X. Meng, S. Kamara, K. Nissim and G. Kollios, “GRECS: Graph encryption for approximate shortest distance queries,” in 22nd ACM SIGSAC Conf. on Computer and Communications Security, Denver, Colorado, USA, pp. 504–517, 2015. [Google Scholar]

3. Q. Wang, K. Ren, M. Du, Q. Li and A. Mohaisen, “SecGDB: Graph encryption for exact shortest distance queries with efficient updates,” in 21st Int. Conf. on Financial Cryptography and Data Security, Sliema, Malta, pp. 79–97, 2017. [Google Scholar]

4. D. J. Wu, J. Zimmerman, J. Planul and J. C. Mitchell, “Privacy-preserving shortest path computation,” in 23rd Annual Network and Distributed System Security Sym., NDSS 2016, San Diego, California, USA, 2016. [Google Scholar]

5. P. Paillier, “Public-key cryptosystems based on composite degree residuosity classes,” in Int. Conf. on the Theory and Applications of Cryptographic Techniques, Prague, Czech Republic, pp. 223–238, 1999. [Google Scholar]

6. J. Fan and F. Vercauteren, “Somewhat practical fully homomorphic encryption,” IACR Cryptology ePrint Archive, vol. 2012, pp. 144, 2012. [Google Scholar]

7. S. Gupta, S. Kopparty and C. Ravishankar, “Roads, codes, and spatiotemporal queries,” in 23rd ACM SIGMOD-SIGACT-SIGART Sym. on Principles of Database Systems, Paris, France, pp. 115–124, 2004. [Google Scholar]

8. H. Yu, X. Jia, H. Zhang, X. Yu and J. Shu, “PSRide: Privacy-preserving shared ride matching for online ride hailing systems,” IEEE Transactions on Dependable and Secure Computing, vol. 18, no. 3, pp. 1425–1440, 2019. [Google Scholar]

9. H. Yu, J. Shu, X. Jia, H. Zhang, X. Yu et al., “Lightweight and privacy-preserving ride matching over road networks in online ride hailing systems,” IEEE Transactions on Vehicular Technology, vol. 68, no. 11, pp. 10418–10428, 2019. [Google Scholar]

10. H. Yu, H. Zhang, X. Yu, X. Du and M. Guizani, “PGRide: Privacy-preserving group ridesharing matching in online ride hailing services,” IEEE Internet of Things Journal, vol. 8, no. 7, pp. 5722–5735, 2020. [Google Scholar]

11. H. Yu, X. Jia, H. Zhang and J. Shu, “Efficient and privacy-preserving ride matching using exact road distance in online ride hailing services,” IEEE Transactions on Services Computing, 2020. https://doi.org/10.1109/TSC.2020.3022875. [Google Scholar]

12. C. Shahabi, M. R. Kolahdouzan and M. Sharifzadeh, “A road network embedding technique for k-nearest neighbor search in moving object databases,” GeoInformatica, vol. 7, no. 3, pp. 255–273, 2003. [Google Scholar]

13. A. Bachir, I. M. Almanjahie and M. K. Attouch, “The k nearest neighbors estimator of the m-regression in functional statistics,” Computers, Materials & Continua, vol. 65, no. 3, pp. 2049–2064, 2020. [Google Scholar]

14. J. Gao, J. X. Yu, R. Jin, J. Zhou, T. Wang et al., “Neighborhood privacy protected shortest distance computing in cloud,” in 2011 ACM SIGMOD Int. Conf. on Management of Data, Athens, Greece, pp. 409–420, 2011. [Google Scholar]

15. A. Sealfon, “Shortest paths and distances with differential privacy,” in 35th ACM SIGMOD-SIGACT-SIGAI Sym. on Principles of Database Systems, San Francisco, California, USA, pp. 29–41, 2016. [Google Scholar]

16. H. Chen, S. Li and Z. Zhang, “A differential privacy based (k-ψ)-anonymity method for trajectory data publishing,” Computers, Materials & Continua, vol. 65, no. 3, pp. 2665–2685, 2020. [Google Scholar]

17. W. Han, M. Cheng, M. Lei, H. Xu, Y. Yang et al., “Privacy protection algorithm for the internet of vehicles based on local differential privacy and game model,” Computers, Materials & Continua, vol. 64, no. 2, pp. 1025–1038, 2020. [Google Scholar]

18. Y. Xi, L. Schwiebert and W. Shi, “Privacy preserving shortest path routing with an application to navigation,” Pervasive and Mobile Computing, vol. 13, pp. 142–149, 2014. [Google Scholar]

19. M. Chase and S. Kamara, “Structured encryption and controlled disclosure,” in Int. Conf. on the Theory and Application of Cryptology and Information Security, Singapore, pp. 577–594, 2010. [Google Scholar]

20. J. Qiu, Z. Tian, C. Du, Q. Zuo, S. Su et al., “A survey on access control in the age of internet of things,” IEEE Internet of Things Journal, vol. 7, no. 6, pp. 4682–4696, 2020. [Google Scholar]

21. L. Jiang and Z. Fu, “Privacy-preserving genetic algorithm outsourcing in cloud computing,” Journal of Cyber Security, vol. 2, no. 1, pp. 49–61, 2020. [Google Scholar]

22. X. Liu, J. Zhang, X. Li, S. Zhou, S. Zhou et al., “A block compressed sensing for images selective encryption in cloud,” Journal of Cyber Security, vol. 1, no. 1, pp. 29–41, 2019. [Google Scholar]

23. F. Hahn and F. Kerschbaum, “Searchable encryption with secure and efficient updates,” in 2014 ACM SIGSAC Conf. on Computer and Communications Security, Scottsdale, Arizona, USA, 310–320, 2014. [Google Scholar]

24. M. Blanton, A. Steele and M. Alisagari, “Data-oblivious graph algorithms for secure computation and outsourcing,” in 8th ACM SIGSAC Sym. on Information, Computer and Communications Security, Hangzhou, China, pp. 207–218, 2013. [Google Scholar]

25. M. Keller and P. Scholl, “Efficient, oblivious data structures for MPC,” in Proc. of Int. Conf. on the Theory and Application of Cryptology and Information Security, Berlin, Germany, pp. 506–525, 2014. [Google Scholar]

26. E. Stefanov, M. Van Dijk, E. Shi, C. Fletcher, L. Ren et al., “Path ORAM: An extremely simple oblivious ram protocol,” in 2013 ACM SIGSAC Conf. on Computer & Communications Security, Berlin, Germany, pp. 299–310, 2013. [Google Scholar]

27. S. Su, Z. Tian, S. Liang, S. Li, S. Du et al., “A reputation management scheme for efficient malicious vehicle identification over 5G networks,” IEEE Wireless Communications, vol. 27, no. 3, pp. 46–52, 2020. [Google Scholar]

28. Z. Tian, X. Gao, S. Su and J. Qiu, “Vcash: A novel reputation framework for identifying denial of traffic service in internet of connected vehicles,” IEEE Internet of Things Journal, vol. 7, no. 5, pp. 3901–3909, 2020. [Google Scholar]

29. H. Carter, B. Mood, P. Traynor and K. Butler, “Secure outsourced garbled circuit evaluation for mobile devices,” in 22nd USENIX Conf. on Security, Washington D.C., USA, pp. 289–304, 2013. [Google Scholar]

30. M. Shen, B. Ma, L. Zhu, R. Mijumbi, X. Du et al., “Cloud-based approximate constrained shortest distance queries over encrypted graphs with privacy protection,” IEEE Transactions on Information Forensics and Security, vol. 13, no. 4, pp. 940–953, 2018. [Google Scholar]

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. |