ESPADE: An Efficient and Semantically Secure Shortest Path Discovery for Outsourced Location-Based Services

Abstract

With the rapid growth of smart devices and technological advancements in tracking geospatial data, the demand for Location-Based Services (LBS) is facing a constant rise in several domains, including military, healthcare and transportation. It is a natural step to migrate LBS to a cloud environment to achieve on-demand scalability and increased resiliency. Nonetheless, outsourcing sensitive location data to a third-party cloud provider raises a host of privacy concerns as the data owners have reduced visibility and control over the outsourced data. In this paper, we consider outsourced LBS where users want to retrieve map directions without disclosing their location information. Specifically, our paper aims to address the following problem: Given a user’s location s, a target destination t, and a graph G stored in a cloud, can users retrieve the shortest path route from s to t in a privacy-preserving manner? Although there exist a few solutions to this problem, they are either inefficient or insecure. For example, existing solutions either leak intermediate results to untrusted cloud providers or incur significant costs on the end-user. To address this gap, we propose an efficient and secure solution based on homomorphic encryption properties combined with a novel data aggregation technique. We formally show that our solution achieves semantic security guarantees under the semi-honest model. Additionally, we provide complexity analysis and experimental results to demonstrate that the proposed protocol is significantly more efficient than the current state-of-the-art techniques.

1. Introduction

Due to the advent of the Internet of Things (IoT), a wide range of smart devices (e.g., tablets and smartphones) are being used to boost businesses across several industries, including healthcare [1,2], manufacturing [3], and military [4]. The number of applications that provide services using geo-locations has also increased in recent years [5]. Specifically, the proliferation of smart devices is the driving force for the growth of Location-Based Services (LBS). LBS applications and platforms allow users to access relevant and updated information about their surroundings based on their real-time geo-location information. For example, navigation, gaming, advertising, and tracking are some domains that effectively leverage LBS [6].

Although the LBS feature renders dynamic user experience and enhances the way businesses can operate and interact with their customers, many such applications sacrifice user security for increased availability and performance [7]. For example, addressing the inherent privacy issues in LBS remains a critical challenge for many service providers [8,9]. In general, a user should disclose his/her location data for the LBS provider to make accurate recommendations. This enables LBS providers to continuously track the user’s personal information, such as their home address, travel plans, lifestyle, etc. Due to growing privacy concerns, users may not want to disclose their location information to LBS providers, but they may still want to get benefits from such applications. Additionally, the evolution of real-time LBS queries emphasizes the need for LBS providers to provide on-demand services. That is, LBS providers often require huge computational and storage resources to manage graph data and process location-aware queries. As a result, it is costly and challenging for LBS providers to manage on-premise infrastructure for delivering services. A natural solution to this problem is to adopt cloud computing technology [10] for efficient processing of LBS queries with on-demand scalability and increased resiliency [11]. The LBS provider can delegate their computational operations in addition to their data to the cloud. Nonetheless, the privacy issues mentioned above become even more challenging under an outsourced environment as the cloud service providers are remote and not trusted servers. A common approach to address the confidentiality of the location data is to encrypt it before being outsourced to a cloud. However, processing over encrypted data is not straightforward as the cloud cannot see the underlying data, thus affecting the quality of LBS. Therefore, we emphasize that there is a strong need to develop privacy-preserving technologies (e.g., [12,13]) that can equilibrate privacy and quality of LBS applications in a cloud environment.

In this paper, we focus on the Single-Source Single-Destination (SSSD) shortest path query, which is one of the commonly used LBS features, under an outsourced cloud environment. For example, consider finding the shortest path to the military base in a mission-critical search-and-rescue operation. To achieve data confidentiality, we assume that the geospatial data are represented as a graph and are encrypted before being outsourced to a cloud. Specifically, given an encrypted graph G stored in a cloud, the goal is to find the shortest path from the source to a destination in a privacy-preserving manner. In the literature, this problem is commonly referred to as Privacy-Preserving Shortest Path over Encrypted Graph (PSPEG) [14]. We emphasize that any solution to the PSPEG problem needs to address the following three privacy objectives:

• Privacy Objective 1 (PO1): User’s input information (i.e., source and destination locations) should not be revealed to the cloud service providers and any other users.
• Privacy Objective 2 (PO2): The contents of graph G should never be revealed to the cloud service providers and unauthorized users.
• Privacy Objective 3 (PO3): The shortest path information should be revealed only to the query issuer.

Existing PSPEG solutions (e.g., [14,15,16]) either do not meet all the above privacy objectives or are not very efficient. Therefore, the primary goal of this paper is to develop a solution that is both secure and efficient. Specifically, we address two research questions: (i) Investigate ways for the data owner to securely and efficiently outsource his/her graph data as well as the shortest path query processing task to a cloud. (ii) Study methods for the query issuer to efficiently retrieve the shortest path results from the cloud without compromising his/her location privacy. To address the above two questions, we adopt the Paillier cryptosystem [17] due to its efficiency and inherent additive homomorphic properties over encrypted data. The cloud server can directly operate on encrypted data to execute the steps involved in the shortest path-discovery process. Along this direction, we propose an Efficient and Semantically Secure Shortest Path Discovery over Encrypted Graph Data (ESPADE) protocol under a cloud environment. The proposed ESPADE protocol meets all of the three privacy objectives mentioned above and provides semantic security [18] under the semi-honest model of Secure Multi-party Computation (SMC) [19]. The main idea behind our protocol is to split the graph data into grids, apply homomorphic encryption operations using a novel data aggregation technique, and execute the shortest path discovery process in an iterative process. The underlying steps involved in ESPADE are based on the well-known Dijkstra’s algorithm [20]; thus, ensuring the correctness. Our performance analysis shows that ESPADE is more secure and efficient compared to the existing PSPEG protocols. It is worth noting that our solution can be incorporated into critical outsourced LBS applications (e.g., military rescue operations) where the secure computation of single-source single-destination shortest path queries is a fundamental task in the graph mining process.

Main Contributions

The existing solutions to the PSPEG problem are either insecure (e.g., leak intermediate results to the cloud providers) or not very efficient. Our proposed ESPADE protocol is both secure and efficient over existing solutions. The main contributions of this paper are summarized below:

• Semantic Security: ESPADE meets all three privacy objectives mentioned earlier. That is, the contents of the outsourced graph G and the user’s input query are never revealed to the cloud service providers and any unauthorized users. This is because our solution is designed to achieve semantic security under the semi-honest model of SMC. We refer the reader to Section 6.1 for more details.
• Efficiency: Our protocol is significantly efficient (in terms of both computation and communication-wise) compared to existing solutions. It is worth noting that the majority of expensive computations in ESPADE are performed by cloud providers, thus minimizing the costs on the end-user.
• Correctness: The steps involved in ESPADE are similar to the ones in the standard Dijkstra’s algorithm. The only difference is that the underlying operations are performed either over encrypted or randomized data. For any given G and shortest path query Q, the shortest path returned by our protocol is the same as the one that would be returned by executing Dijkstra’s algorithm on $\{G,Q\}$.
• Flexibility: Upon outsourcing the graph data to the cloud, the data owner does not have to participate in any other operations. Specifically, the end-users can issue SSSD queries directly to the cloud and the majority of the query processing task is done by the cloud providers, which suffices in the main purpose of outsourcing in the first place.

The remainder of this paper is organized as follows: Section 2 discusses our system model. In Section 3, we touch upon more closely related work to ours. Section 4 presents the background information. Section 5 discusses the proposed ESPADE protocol in detail along with a running example. We present the security proofs and the comparative performance analysis of ESPADE with experimental results in Section 6, and conclude the paper with future work in Section 7.

2. Problem Model

In our problem setting, we consider three types of entities: (i) Alice (ii) Federated Cloud and (iii) Bob. The proposed system model along with the information flow among different entities is shown in Figure 1. Next, we discuss the role of each of these entities.

• Alice: We assume that Alice (data owner) holds sensitive geospatial data represented as a graph $G=\{V,E,W\}$, where $V=\{v_1,\dots ,v_n\}$ denotes the set of vertices, E denotes the edges connecting those vertices associated with weights W. In our model, we consider that G is an undirected weighted graph represented as an $\alpha \times \alpha$ grid matrix (refer to Section 5 for more details). For example, consider a graph used by Google Maps where G represents a road network. Here each vertex in V will correspond to a given point on the road network, and each edge E will correspond to the road segment that connects any two points on the road network. In this case, weight can be the distance between junctions or traffic flow.
• Federated Cloud: Without loss of generality, let Alice outsource G (in encrypted format) to a Federated Cloud (FC) environment consisting of two cloud services providers $C_1$ and $C_2$. We assume that $C_1$ and $C_2$ are semi-honest and do not collude. This is a realistic model as it is being used in several existing works (e.g., in [21,22,23,24]). This is because most of the cloud service providers are well-known IT organizations and it is highly unlikely that any two cloud service providers will collude as it may damage their reputation and can adversely affect their revenues.
• Bob: The end-user Bob issues SSSD shortest path queries to FC. $C_1$ and $C_2$ will collaboratively compute the shortest path from source s to t, and return the path to Bob.

Under the above problem setting, we formally define the proposed ESPADE protocol as follows:

$$\mathrm{ESPADE}(G,\langle s,t\rangle )\to \mathrm{SP}(s,t)$$

(1)

where G is known only to Alice and is outsourced (after proper randomization) to FC. $\langle s,t\rangle$ denote the source and destination locations, respectively, known only to Bob. At the end of the ESPADE protocol, the shortest path route, denoted by SP$(s,t)$, should be revealed only to Bob.

Briefly, our model involves the following main steps: (1) $C_2$ initially generates a public-private key pair $(pk,sk)$ based on the Paillier cryptosystem [17] and distributes the public key $pk$ to Alice, $C_1$ and Bob, (2) Alice randomly splits her graph data G in a systematic way and outsources them to $C_1$ and $C_2$, (3) Bob randomly splits his shortest path query information and forwards them to FC, (4) $C_1$ and $C_2$ involve secure computations to collaboratively extract the shortest path information, and (5) FC sends the randomized sub-graph data to Bob, who then aggregates and extracts the shortest path information based on Dijkstra’s algorithm.

3. Related Work

In this section, we discuss the existing methods for privacy-preserving shortest path (PPSP) computation. We also demonstrate the limitations of the existing solutions.

3.1. Privacy-Preserving Shortest Path over Plaintext Data

In this sub-section, we briefly touch upon existing privacy-preserving shortest path solutions in which the graph data stored on the server-side are in a non-encrypted format.

3.1.1. Obfuscation Methods

In obfuscation methods [25], Bob does not send his query directly to the LBS provider. For example, in [26], Bob computes a set of dummy locations and obfuscates his source location s with the fake locations. Similarly, he obfuscates the destination location t with many fake locations. Suppose S and T denote the obfuscated source and destination locations, respectively. Bob forwards $(S,T)$ to the LBS provider. Upon receiving, the LBS provider computes the shortest path from every location in S to every location in T, based on G resulting in $\left|S\right|\ast \left|T\right|$ paths which are forwarded to Bob. Finally, Bob retains the shortest path that corresponds to the original source-destination location pair. It is worth noting that any PPSP solution based on the obfuscation method is not secure as it will reveal substantial information about the query to the LBS provider. For example, LBS knows that the original source (or destination) location is one among the many locations in the set S (or T). Additionally, obfuscation-based methods assume that outsourced data (i.e., G in our case) are known to the LBS provider, whereas in our problem setting the contents of G are hidden from both cloud service providers.

3.1.2. Private Information Retrieval (PIR) Methods

In PIR [27], the server is assumed to hold a database of items and the end-user wants to retrieve the $ith$ item from the database in an oblivious manner. Computational PIR [28] is one kind of PIR which can work with a single server and utilizes cryptographic techniques to ensure the privacy of the query from a computationally bounded server. Existing PIR-based solutions to PPSP assume that the outsourced graph database is not privacy-sensitive and is known to the LBS provider. For example, Mouratidis and Yiu [29] proposed a hardware-aided PIR-based solution to PPSP that relies on a tamper-resistant secure co-processor installed at the server-side. However, such schemes require decrypting the data in a secure area at the cloud and perform the computation on decrypted data; thus, they do not protect data access patterns from the server [30].

In this paper, we assume that the graph data are sensitive and thus the above schemes are not applicable to our problem domain, especially for outsourced environments where the outsourced data are in an encrypted format and has to be protected even from the cloud service providers.

3.2. PPSP over Encrypted Graph Data

In the past decade, various techniques for location-based query processing over outsourced encrypted data have been proposed [14,15,16,31,32]. However, there exist only a few solutions to the PPSP problem over encrypted graph data. Blanton et al. [15] proposed a data-oblivious algorithm for the SSSD shortest path problem on protected information. First, their algorithm is well-suited only for dense graphs. Second, their framework is based on the $(k,n)$ threshold linear secret sharing scheme that requires at least three parties whereas our framework utilizes a more practical two-cloud model.

Zhang et al. [16] proposed a shortest path computing framework based on homomorphic encryption and secure multi-party computation. However, their protocols assume that only the edge-weight information was encrypted; and thus, their solution reveals the vertex information to the cloud server. Additionally, they utilized 1-out-of-n oblivious transfer cryptographic primitive, which can be prohibitively expensive and their solution requires the participation of the data owner during the shortest path computation, whereas in our protocol the data owner does not participate in any operations after the data outsourcing step.

Samanthula et al. [14] proposed two PPSP solutions over encrypted graph data, referred as PSPEG${}_1$ and PSPEG${}_2$, under different cloud settings. First, PSPEG${}_1$ utilizes a single cloud service provider whereas PSPEG${}_2$ uses a two-cloud model similar to ours. However, both of these protocols incur significant computation and communication costs on Alice and Bob. Furthermore, there is no provable way to quantify the security guarantees of these two protocols as they did not provide any security proofs. In Section 6, we formally show that our proposed ESPADE protocol is more efficient and secure compared to both PSPEG${}_1$ and PSPEG${}_2$. Specifically, the proposed ESPADE protocol utilizes a data aggregation technique under encryption to boost the performance of each iteration in the shortest path discovery process whereas PSPEG${}_1$ and PSPEG${}_2$ incur significant costs (computation, communication, and round) on the cloud providers and the end-user. We refer the reader to Section 6 for a detailed analysis on the secure guarantees of ESPADE and its comparison with existing work.

4. Preliminaries

In this section, we discuss basic concepts and core algorithms that are utilized in ESPADE as background knowledge. First, we present the main steps involved in the Dijkstra’s algorithm. Then, we discuss the importance of homomorphic encryption in outsourced environments along with the properties of Paillier Cryptosystem, which are crucial to perform certain operations over encrypted data in our proposed protocol. Finally, we discuss the two-party secure multiplication (SM) protocol over encrypted data, which is used as a building block in ESPADE. Some common notations utilized in this paper are shown in

Table 1. Common Notations.

Notation	Description
SSSD-SP	Single-source single-destination shortest path
ESPADE	Efficient and semantically secure shortest path discovery over encrypted graph data
FC	A federated cloud environment consisting of two cloud service providers $C_1$ and $C_2$
G	A weighted graph consisting of $V=\{v_1\dots ,v_n\}$ vertices with E edges and W weights
n	The total number of grids G is divided into
$v_{i,j}$	jth vertex in grid location i
$v_{i,j}^k$	kth neighbor of vertex $v_{i,j}$
$w_{i,j}^k$	Weight between the two vertices: $v_{i,j}$ and $v_{i,j}^k$
$(s,t)$	Source and destination locations
$SP(s,t)$	Shortest path from s to t based on G
$(pk,sk)$	A pair of public-private key pair generated based on Paillier cryptosystem
Epk	Paillier’s Encryption function with public key $pk$
Dsk	Paillier’s Decryption function with private key $sk$
$r{\in }_R{\mathbb{Z}}_N$	A random number chosen uniformly in the group ${\mathbb{Z}}_N$

.

4.1. The Dijkstra’s Algorithm

There exist several algorithms to find the single-source shortest path for a weighted graph $G=\{V,E,W\}$, such as Dijkstra’s and Bellman–Ford algorithms. In this paper, we focus on Dijkstra’s algorithm as it is one of the most commonly used algorithms for non-negative weighted graphs. In general, most of the location-based services, such as map directions, deal with non-negative weighted graphs. For brevity, in this paper, we restrict our discussion to non-negative weighted graphs. Given a weighted graph G, Dijkstra’s algorithm can be used to compute the shortest path from a given source (s) to the destination (t), denoted by SP$(s,t)$. Let us consider a graph G with the following elements:

∘

Vertices denoted by u or v;

∘

Each edge that connects two vertices $(u,v)$ has weights associated with it, denoted by $w_{u,v}$.

For a given $(s,t)$ pair, the algorithm will traverse neighboring vertices in G, finding the shortest path by adding edge weights and replacing the current shortest path if a lower total distance is found. The main steps involved in Dijkstra’s algorithm are discussed below.

A. Initialization

∘

The current vertex $cv$ is marked as source s;

∘

Each vertex in G is initially marked as unvisited;

∘

All vertices are assigned with ∞ as the distance from s, while for s itself the distance is assigned as 0. That is, $dist\left(v\right)=\infty$, $\forall v\in V\wedge v\ne s$;

∘

SP$(s,t)=\left\{\right\}$.

B. Iterative Process

∘

Step 1: For the current vertex $cv$, consider all unvisited vertices that are directly connected to $cv$. Let us denote this set by L.

∘

Step 2: For each vertex $u\in L$, calculate its new distance from the source as $dis{t}^{\prime }\left(u\right)=dist\left(cv\right)+w_{u,cv}$. If $dis{t}^{\prime }\left(u\right)\le dist\left(u\right)$, then update vertex $u^{\prime }$s distance as $dis{t}^{\prime }\left(u\right)$. Otherwise, it is unchanged.

∘

Step 3: Mark $cv$ as visited and update $\mathrm{SP}(s,t)$ as $\mathrm{SP}(s,t)\parallel cv$. If $cv=t$, then terminate and return $\mathrm{SP}(s,t)$ as the output. Otherwise, select the vertex $m\in L$, which has the smallest distance, set $cv$ to m, and proceed to Step 1.

4.2. Homomorphic Encryption and Paillier Cryptosystem

Homomorphic Encryption (HE) provides a way to process the information in an encrypted format and produce the same results as if the operations were performed over plaintext data [33]. In outsourced environments, HE enables untrusted servers to directly perform operations over encrypted data while maintaining the confidentiality of the data. Existing HE schemes are broadly categorized into Fully Homomorphic Encryption (FHE) and Partially Homomorphic Encryption (PHE) schemes. On one hand, FHE supports multiple types of operations (i.e., addition and multiplication) over encrypted data, but the existing FHE schemes are very expensive and not practical. On the other hand, PHE schemes support only one type of operation, either addition or multiplication, over encrypted data.

The Paillier cryptosystem [17] is an asymmetric PHE scheme that can support an arbitrary number of addition operations over encrypted data and whose security relies on the hardness of integer factorization. Let $E_{pk}$ denote the Paillier’s encryption function, where the public key $pk$ consists of $(N,g)$. Here N denotes the RSA modulurats and g denotes the geneor from group ${\mathbb{Z}}_N^{\ast }$. The encryption of a message m under Paillier’s scheme is given by, $E_{pk}\left(m\right)=(g^m\ast r^N)mod{N}^2$, where $r{\in }_R{\mathbb{Z}}_N$. For any two given messages, $m_1,m_2\in {\mathbb{Z}}_N$, the following properties of Paillier’s encryption function always hold:

∘

Additive Homomorphism: The output of multiplying the ciphertexts of $m_1$ and $m_2$ is equivalent to the encryption of $m_1+m_{2}modN$. That is,

$$E_{pk}\left(m_1\right)\ast E_{pk}\left(m_2\right)=E_{pk}(m_1+m_{2}modN)$$

∘

Partial Multiplication: Given a constant $b\in {\mathbb{Z}}_N$, rising the ciphertext of $m_1$ to the power of b is equivalent to the encryption of $b\ast m_1$. That is,

$$E_{pk}{\left(m_1\right)}^b=E_{pk}(b\ast m_1)$$

∘

Semantic Security: Paillier’s encryption function is a probabilistic scheme meaning that encryptions of the same message will result in different ciphertexts. Therefore, given a set of ciphertexts, an adversary cannot deduce any information about the underlying plaintexts. That is, ciphertexts are indistinguishable from one another; thus, the scheme exhibits the semantic security property [18].

In this paper, we adopt Paillier’s scheme as the underlying encryption scheme due to its security guarantees, homomorphic properties, and possible optimizations (refer to Section 6.2.2 for more details).

4.3. Secure Multiplication (SM)

As mentioned above, Paillier’s encryption scheme allows parties to locally perform addition operations over encrypted data. However, multiplication over encrypted data cannot be done locally and it requires the help of the party holding the corresponding private-key. Without loss of generality, suppose $C_1$ holds private data $\langle E_{pk}\left(a\right),E_{pk}\left(b\right)\rangle$ and $C_2$ holds the corresponding Paillier’s private-key $sk$. We assume that a and b are not known to $C_1$ and $C_2$. Under this setting, the goal of Secure Multiplication (SM) [34] is to enable $C_1$ and $C_2$ to jointly compute $E_{pk}(a\ast b)$. The output of the SM protocol—i.e., $E_{pk}(a\ast b)$, should be known only to $C_1$. During the execution of SM, the contents of a, b, and $(a\ast b)$ should not be revealed to $C_1$ and $C_2$.

The main steps involved in the SM protocol [34] are highlighted in Algorithm 1. Initially, $C_1$ generates two random numbers $r_a,r_b{\in }_R{\mathbb{Z}}_N$, and uses them to randomize the encrypted inputs. That is, $C_1$ computes $A=E_{pk}(a+r_a)$ and $B=E_{pk}(b+r_b)$ using the additive homomorphic properties of Paillier’s scheme and forwards these values to $C_2$. Upon receiving, $C_2$ decrypts $(A,B)$ to get $(a^{\prime },b^{\prime })$, respectively. Then, it multiplies $a^{\prime }$ and $b^{\prime }$ whose equation can be expanded as follows:

$$a^{\prime }\ast b^{\prime }=(a+r_a)\ast (b+r_b)=a\ast b+a\ast r_b+b\ast r_a+r_a\ast r_b$$

At this point, $C_2$ knows that $p=a^{\prime }\ast b^{\prime }$, which it encrypts under $pk$ and sends the resulting encrypted value P to $C_1$. Finally, $C_1$ performs homomorphic operations on P locally and removes the randomized factors (i.e., $a\ast r_b,b\ast r_a$ and $r_a\ast r_b$) under encryption to get $E_{pk}(a\ast b)$ as the final output.

Algorithm 1 SM$(E_{pk}\left(a\right),E_{pk}\left(b\right))\to E_{pk}(a\ast b)$

Require:  $C_1$ holds $\langle E_{pk}\left(a\right),E_{pk}\left(b\right)\rangle$ and $C_2$ holds $sk$. a and b are not known to $C_1$ and $C_2$    1: $C_1$:    (a). Pick two random numbers $r_a,r_b\in {\mathbb{Z}}_N$    (b). $A\leftarrow E_{pk}\left(a\right)\ast E_{pk}\left(r_a\right)$    (c). $B\leftarrow E_{pk}\left(b\right)\ast E_{pk}\left(r_b\right)$    (d). Send $A,B$ to $C_2$  2: $C_2$:    (a). Receive A and B from $C_1$    (b). $a^{\prime }\leftarrow D_{sk}\left(A\right)$;  $b^{\prime }\leftarrow D_{sk}\left(B\right)$    (c). $p\leftarrow a^{\prime }\ast b^{\prime }modN$    (d). $P\leftarrow E_{pk}\left(p\right)$    (e). Send P to $C_1$  3: $C_1$:    (a). Receive P from $C_2$    (b). $y\leftarrow P\ast E_{pk}{\left(a\right)}^{N-r_b}$    (c). $y^{\prime }\leftarrow y\ast E_{pk}{\left(b\right)}^{N-r_a}$    (d). $E_{pk}(a\ast b)\leftarrow y^{\prime }\ast E_{pk}{(r_a\ast r_b)}^{N-1}$

Example 1.

Suppose $a=59$ and $b=58$. For simplicity, let $r_a=1$ and $r_b=3$. Assume that $C_1$ holds $\langle E_{pk}\left(59\right),E_{pk}\left(58\right)\rangle$. Various intermediate results computed during the execution of SM protocol are as follows. Initially, $C_1$ computes $A=E_{pk}\left(a\right)\ast E_{pk}\left(r_a\right)=E_{pk}\left(60\right)$, $B=E_{pk}\left(b\right)\ast E_{pk}\left(r_b\right)=E_{pk}\left(61\right)$ and sends them to $C_2$. Then, $C_2$ decrypts and multiplies them to get $p=3660$. After this, $C_2$ encrypts p to get $P=E_{pk}\left(3660\right)$ and sends it to $C_1$. Upon receiving P, $C_1$ computes $y=E_{pk}(3660-a\ast r_b)=E_{pk}\left(3483\right)$, and $y^{\prime }=y\ast E_{pk}(-b\ast r_a)=E_{pk}\left(3425\right)$. Finally, $P_1$ computes $E_{pk}(a\ast b)=y^{\prime }\ast E_{pk}(-r_a\ast r_b)=E_{pk}\left(3422\right)$.

5. The Proposed ESPADE Protocol

In this section, we present our ESPADE protocol in detail. As mentioned in Section 2, our proposed protocol consists of three parties: Alice, Federated Cloud, and Bob. ESPADE is constructed based on the Paillier cryptosystem and by utilizing the SM primitive as a building block. For the rest of this paper, we explicitly make the following assumptions:

• Alice’s geospatial data are represented as a weighted graph G with V vertices and W weights. The contents of G are sensitive and thus need to be kept confidential from cloud service providers and unauthorized parties. We assume that each vertex in G is associated with a unique identification number—for example, denoting the combination of latitude and longitude information.
• $C_2$ generates the public-private key pair $(pk,sk)$ based on the Paillier’s scheme and securely distributes $pk$ to Alice, $C_1$, and Bob. We assume that there exist secure communication channels (e.g., SSL) between each pair of parties participating in our protocol.
• Similar to existing work [14,15,16], we assume that all the participating parties in our protocol are semi-honest [19]. The semi-honest model is a practical security model, due to the following reasons. First, building protocols under the semi-honest model is an important first step for constructing protocols under stronger security models (e.g., against covert and malicious adversaries). Second, protocols under the semi-honest model are typically considered to be quite efficient, which may not be the case for other adversarial models. Third, protocols that are proven to be secure under the semi-honest model can prevent inadvertent leakage of information among participating parties. Finally, it is highly unlikely that the well-established cloud service providers (e.g., Amazon and Microsoft) would deviate from the prescribed protocol and collude, as this would damage their reputation and consumer trust. Therefore, we believe that the semi-honest model is a practical security model for our problem domain.

The goal of ESPADE is to securely outsource G to FC and execute Bob’s shortest path query $(s,t)$ in a privacy-preserving manner. The proposed ESPADE protocol consists of the following two stages:

∘

Stage 1—Secure Outsourcing of Graph G (SOG): In this stage, Alice transforms her graph data G into a proper $\alpha \times \alpha$ grid matrix. During this process, Alice relies on our data aggregation technique to intelligently capture the information in each grid. After this transformation, Alice outsources the aggregated graph information to the federated cloud environment using the randomization approach. At the end of this stage, only $C_1$ knows the encrypted graph data.

∘

Stage 2—Secure Retrieval of Shortest Path (SRSP): In this stage, Bob securely sends his shortest path query $Q=\langle s,t\rangle$ to FC. Then, $C_1$ and $C_2$ jointly involve secure computations to retrieve the shortest path in an iterative process, based on Dijkstra’s algorithm. At the end of this stage, only Bob knows the shortest path from s to t.

The main steps involved in the proposed ESPADE protocol are given in Algorithm 2. Next, we explain each of the two stages of ESPADE in detail.

Algorithm 2 ESPADE($G,\langle s,t\rangle$) → SP($s,t)$

Require:  Alice holds private graph G; $C_2$ holds private key $sk$; Bob holds the shortest path query $\langle s,t\rangle$    (Note: parameters $pk$, ℓ, m, and n are public)   {Stage1—Secure Outsourcing of Graph} 1: Alice:   (a). for$1\le i\le n$do:     ∘ Compute $M_i$ from G, m, and ℓ     ∘ Compute aggregated grid information $T_i$ from $M_i$     ∘ Split $T_{i,j}$: $T_{i,j}^1=T_{i,j}+r_{i,j}modN$ and $T_{i,j}^2=N-r_{i,j}$, for $1\le j\le 3m+1$   (b). Send $T^1$ to $C_1$ and $T^2$ to $C_2$ 2: $C_2$:   (a). Receive $T^2$ from Alice   (b). $F_{i,j}\leftarrow E_{pk}\left(T_{i,j}^2\right)$, for $1\le i\le n$ and $1\le j\le 3m+1$   (c). Send F to $C_1$ 3: $C_1$:   (a). Receive $T^1$ from Alice and F from $C_2$   (b). $G_{i,j}^{\prime }\leftarrow E_{pk}\left(T_{i,j}^1\right)\ast F_{i,j}mod{N}^2$, $1\le i\le n$ and $1\le j\le 3m+1$   {Stage2—Secure Retrieval of Shortest Path} 4: SRSP$(G^{\prime },\langle s,t\rangle )$

5.1. Secure Outsourcing of Graph G (SOG)

During Stage 1, Alice first divides her graph G into $\alpha \times \alpha$ square grids (for example, 1 mile by 1 mile). Let n denote the total number of grids in G and $g_v$ denote the grid ID in which a vertex v resides. Each grid is represented by the set of vertices that reside inside the grid, their neighbors, and the associated weights. Alice represents each piece of grid information as a matrix where each row corresponds to a vertex in that grid. Suppose ℓ denotes the maximum number of unique vertices in each grid and m denotes the maximum of 1-hop neighbors, a vertex in G can have. Upon dividing the graph G into n grids, Alice constructs the matrix $M_i$ for each grid, for $1\le i\le n$. Each row in $M_i$ corresponds to a particular vertex in grid i and its m neighboring vertex information. Specifically, for grid i, the number of unique vertices are denoted by $v_{i,1},\dots ,v_{i,\ell }$. For each vertex $v_{i,j}$ in grid i, Alice stores 3m entries, such that each entry consists of the neighboring vertex, its associated edge weight, and the grid ID of the neighboring vertex, where $1\le j\le m$. As an example, for vertex $v_{i,j}$, Alice stores $\langle v_{i,j}^1,w_{i,j}^1,g_{v_{i,j}^1}\rangle ,\dots ,\langle v_{i,j}^m,w_{i,j}^m,g_{v_{i,j}^m}\rangle$. In this case, $v_{i,j}^1,\dots ,v_{i,j}^m$ and $w_{i,j}^1,\dots ,w_{i,j}^m$ denote the neighboring vertices of $v_{i,j}$ and the corresponding edge weights, respectively, for $1\le j\le m$. Additionally, $g_{v_{i,j}^1}$ denotes the Grid ID of vertex $v_{i,j}^1$. A sample snapshot of the grid information captured in $M_i$ is shown below.

$$M_i=\left[\begin{array}{cccc}{v}_{i,1}& \langle v_{i,1}^1,w_{i,1}^1,g_{v_{i,1}^1}\rangle & \dots & \langle v_{i,1}^m,w_{i,1}^m,g_{v_{i,1}^m}\rangle \\ v_{i,2}& \langle v_{i,2}^1,w_{i,2}^1,g_{v_{i,2}^1}\rangle & \dots & \langle v_{i,2}^m,w_{i,2}^m,g_{v_{i,2}^m}\rangle \\ ⋮& ⋮& ⋮& ⋮\\ v_{i,\ell }& \langle v_{i,\ell }^1,w_{i,\ell }^1,g_{v_{i,\ell }^1}\rangle & \dots & \langle v_{i,\ell }^m,w_{i,\ell }^m,g_{v_{i,\ell }^m}\rangle \end{array}\right]$$

For security reasons, we assume that all the matrices constructed from G are of the same size; that is, $\ell \times m$. However, if a grid has less than ℓ vertices, Alice can add dummy entries. Similarly, if a vertex has less than m neighbors, she can insert dummy values.

Upon creating all the matrices, we propose that Alice adopts the following data aggregation technique to reduce its outsourcing costs, as well as later query processing costs for the end-users. Alice transforms matrix $H_i$ into a vector $T_i$ of size $3m+1$ by concatenating the column-wise entries in $M_i$. That is, the first entry of $T_i$ is computed as $\langle v_{i,1}\parallel v_{i,2},\dots ,\parallel v_{i,\ell }\rangle$, the second entry as $\langle v_{i,1}^1\parallel v_{i,2}^1,\dots ,\parallel v_{i,\ell }^1\rangle$, and so on. After transforming all the matrices into vectors, Alice needs to outsource $T_i$’s to FC in an encrypted format. However, for large values of $n,m$ and ℓ, it would be expensive for Alice to encrypt $T_i$, for $1\le i\le n$. Therefore, we propose the following approach for Alice to outsource $T_{i,j}$. Alice selects a random number $r_{i,j}$ and splits $T_{i,j}$ into two random shares: $T_{i,j}^1=T_{i,j}+r_{i,j}modN$ and $T_{i,j}^2=N-r_{i,j}$. It is worth noting that $T_{i,j}=T_{i,j}^1+T_{i,j}^{2}modN$ always holds, for $1\le i\le n$ and $1\le j\le 3m+1$. Then, Alice outsources $T_{i,j}^1$ and $T_{i,j}^2$ to $C_1$ and $C_2$, respectively. Upon receiving $T_{i,j}^2$, $C_2$ computes $E_{pk}\left(T_{i,j}^2\right)$ and forwards it to $C_1$. Finally, $C_1$ computes $E_{pk}\left(T_{i,j}^1\right)\ast E_{pk}\left(T_{i,j}^2\right)mod{N}^2$ which is equivalent to $E_{pk}(T_{i,j}^1+T_{i,j}^2)=E_{pk}\left(T_{i,j}\right)$. We denote the final encrypted dataset by $G^{\prime }$, which is known only to $C_1$.

5.2. Secure Retrieval of Shortest Path (SRSP)

Following from Stage 1, $C_1$ has encrypted graph dataset $G^{\prime }$. During Stage 2, Bob with private input $\langle s,t\rangle$, $C_1$ with private input $G^{\prime }$ and $C_2$ with private key $sk$ wants to jointly find the shortest path from s to t in a privacy-preserving manner. At the end of Stage 2, SP$(s,t)$ should be known only to Bob.

The main steps involved in Stage 2 of ESPADE are shown in Algorithm 3. Next, we discuss the steps of Stage 2 in detail below:

• To start with, Bob creates a graph $G_s$ that initially contains no values except his starting point s. The goal of Bob is to expand $G_s$ by retrieving graph data from FC in an iterative manner until he has sufficient graph data to construct SP$(s,t)$. First, he computes the grid location (e.g., using his GPS) in which his source location s resides, denoted by $cg$. He also sets the current vertex $cv$ to s. Now, Bob wants to request $cg$’s grid data from FC so that he can expand $G_s$ without revealing any information about $cg$ to $C_1$ and $C_2$. A trivial approach here is for Bob to encrypt $cg$ and forward it to $C_1$, but this would require exponentiation module $N^2$ operations, which are expensive. To avoid this, Bob splits $cg$ into two random shares $c{g}_1$ and $c{g}_2$, such that $c{g}_1=cg+rmodN$ and $c{g}_2=N-r$, where $r{\in }_R{\mathbb{Z}}_N$. Bob sends $c{g}_1$ and $c{g}_2$ to $C_1$ and $C_2$, respectively.
• Upon receiving $c{g}_2$, $C_2$ encrypts it under $pk$ and forwards $E_{pk}\left(c{g}_2\right)$ to $C_1$.
• After receiving $c{g}_1$ from Alice and $E_{pk}\left(c{g}_2\right)$ from $C_2$, $C_1$ computes $E_{pk}\left(cg\right)$ by performing homomorphic operations, as $E_{pk}\left(c{g}_1\right)\ast E_{pk}\left(c{g}_2\right)mod{N}^2$. Then, it obliviously checks which grid’s information Bob is requesting. To achieve this, $C_1$ computes ${\Delta }_i=E_{pk}\left(cg\right)\ast E_{pk}{\left(i\right)}^{N-1}mod{N}^2$. The idea behind this operation is to subtract Bob’s requesting grid ID $cg$ from all grid IDs under encryption. The observation here is that exactly one of the values of $\Delta$ is an encryption of 0. $C_1$ randomizes $\Delta$ by computing $X_i={\Delta }_i^{r_i}mod{N}^2$, where $r_i{\in }_R{\mathbb{Z}}_N$. Then, $C_1$ randomly permutes $Y\leftarrow \pi \left(X\right)$ and sends Y to $C_2$. Here $\pi$ is a random permutation function known only to $C_1$.
• Upon receiving Y, $C_2$ decrypts it component-wise using the private key $sk$ resulting in a new vector Z. It is worth noting that only one of the entries in Z is 0. Now, $C_2$ generates a new encrypted vector P based on whether the value of $Z_i$ is 0 or not. Specifically, it generates P as follows and sends it to $C_1$:

  $$P_i=\left\{\begin{array}{cc}{E}_{pk}\left(1\right)\hfill & \mathrm{if}{Z}_i=0\hfill \\ E_{pk}\left(0\right)\hfill & \mathrm{otherwise}\hfill \end{array}\right.$$

  Algorithm 3 SRSP$(G^{\prime },\langle s,t\rangle )$

  Require:  Bob holds SSSD query $\langle s,t\rangle$; $C_1$ holds $G^{\prime }$ and $C_2$ holds the private key $sk$    1: Bob:    (a). $G_s\leftarrow \langle s\rangle$ and $cv\leftarrow s$    (b). Compute the current grid ID $cg$ of $cv$    (c). Compute two random shares of $cg$ as $c{g}_1\leftarrow cg+rmodN$ and $c{g}_2\leftarrow N-r$, where $r{\in }_R{Z}_N$    (d). Send $c{g}_1$ to $C_1$ and $c{g}_2$ to $C_2$  2: $C_2$:    (a). Receive $c{g}_2$ from Bob    (b). Compute and send $E_{pk}\left(c{g}_2\right)$ to $C_1$  3: $C_1$:    (a). Receive $c{g}_1$ from Bob and $E_{pk}\left(c{g}_2\right)$ from $C_2$    (b). $E_{pk}\left(cg\right)\leftarrow E_{pk}\left(c{g}_1\right)\ast E_{pk}\left(c{g}_2\right)mod{N}^2$    (c). for$1\le i\le n$do:     ∘ ${\Delta }_i\leftarrow E_{pk}\left(cg\right)\ast E_{pk}{\left(i\right)}^{N-1}mod{N}^2$     ∘ $X_i$ = ${\Delta }_i^{r_i}$ mod $N^2$,where $r_i{\in }_R{\mathbb{Z}}_N$    (d). $Y\leftarrow \pi \left(X\right)$; Send Y to $C_2$  4: $C_2$:    (a). Receive Y from $C_1$    (b). for$1\le i\le n$do:     ∘ $Z_i=D_{sk}\left(Y\right)$     ∘ if$Z_i=0$then    $P_i$=$E_{pk}\left(1\right)$ else    $P_i$=$E_{pk}\left(0\right)$    (c). Send P to $C_1$  5: $C_1:$    (a). $Q\leftarrow {\pi }^{-1}\left(P\right)$    (b). for$1\le i\le n$do:     ∘ ${\Phi }_{i,j}\leftarrow \mathrm{SM}(Q_i,G_{i,j}^{\prime })$, for $1\le j\le 3m+1$ {SM requires participation of both $C_1$ and $C_2$}    (c). for$1\le j\le 3m+1$do     ∘ ${\Lambda }_j\leftarrow {\prod }_{i=1}^n{\Phi }_{i,j}mod{N}^2$     ∘ Compute ${\Lambda }_j^{\prime }\leftarrow {\Lambda }_j\ast E_{pk}\left(r_j\right)$ mod $N^2$, where $r{\in }_R{Z}_N$.     ∘ ${\lambda }_{1,j}\leftarrow N-r_j$    (d). Send ${\lambda }_1$ to Bob and ${\Lambda }^{\prime }$ to $C_2$  6: $C_2$:    (a). ${\lambda }_{2,j}\leftarrow D_{sk}\left({\Lambda }_j^{\prime }\right)$ for $1\le j\le 3m+1$    (b). Send ${\lambda }_2$ to Bob  7: Bob:    (a). Receive ${\lambda }_1$ from $C_1$ and ${\lambda }_2$ from $C_2$    (b). ${\lambda }_j\leftarrow {\lambda }_{1,j}+{\lambda }_{2,j}modN$, for $1\le j\le 3m+1$    (c). Update $G_s$ based on ${\lambda }_j$ and execute Dijkstra’s algorithm    (d). ift is marked as visited then    return SP$(s,t)$ else    Identify the new neighboring vertex $cv$ and proceed to step 1(b)

• $C_1$ performs inverse permutation on P to get $Q={\pi }^{-1}\left(P\right)$. It is worth noting that $Q_i$ equals $E_{pk}\left(1\right)$ if $i=cg$, and $Q_i=E_{pk}\left(0\right)$ otherwise. After this, $C_1$ with private input $\langle Q,G^{\prime }\rangle$ and $C_2$ with private key $sk$ are involved in a set of secure multiplication operations. Specifically, $C_1$ with input $\langle Q_i,G_{i,j}^{\prime }\rangle$ and $C_2$ jointly execute SM$(Q_i,G_{i,j}^{\prime })$, for $1\le i\le n$ and $1\le j\le 3m+1$. Suppose $\Phi$ denotes the output of SM. Since Q consists of $E_{pk}\left(1\right)$ only for Bob’s current grid $cg$, secure multiplication will result in $\Phi$ to store the aggregated grid information of $cg$. For $i\ne cg$, every other entry in $G_i^{\prime }$ is multiplied by $E_{pk}\left(0\right)$; thus, the result will be encryptions of 0’s for all other grids. Note that the output of SM—that is ${\Phi }_{i,j}$—is known only to $C_1$, for $1\le i\le n$ and $1\le j\le 3m+1$. Next, $C_1$ aggregates all the SM results column-wise locally. That is, $C_1$ computes ${\Lambda }_j\leftarrow {\prod }_{i=1}^n{\Phi }_{i,j}mod{N}^2$. The important observation here is that $\Lambda$ contains the entire grid data in which $cg$ resides. At this point, $C_1$ needs to somehow send the current grid data to Bob. In order to alleviate the overload on Bob, $C_1$ utilizes the randomization approach. That is, $C_1$ selects random numbers $r_j{\in }_R{\mathbb{Z}}_N$ and adds it to $\Lambda$ using additive homomorphic properties by computing ${\Lambda }_j^{\prime }\leftarrow {\Lambda }_j\ast E_{pk}\left(r_j\right)mod{N}^2$. Additionally, $C_1$ computes ${\lambda }_{1,j}=N-r_j$. Now, $C_1$ sends ${\lambda }_{1,j}$ to Bob and ${\Lambda }_j^{\prime }$ to $C_2$, for $1\le j\le 3m+1$.
• After receiving the encrypted randomized vector ${\Lambda }^{\prime }$, $C_2$ decrypts it component-wise using $sk$ to get ${\lambda }_{2,j}$, for $1\le j\le 3m+1$. Then, $C_2$ sends ${\lambda }_2$ to Bob. Due to the randomization by $C_1$, it is worth noting that the decrypted values in this step do not reveal any information to $C_2$.
• Finally, upon receiving ${\lambda }_1$ and ${\lambda }_2$ from $C_1$ and $C_2$, Bob adds them component-wise to get ${\lambda }_j\leftarrow {\lambda }_{1,j}+{\lambda }_{2,j}modN$, for $1\le j\le 3m+1$ which consists of $cg$’s grid data. Bob will then update $G_s$ based on this new grid information and executes the Dijkstra’s algorithm to determine the shortest path marking each vertex with minimum distance as visited. If Bob’s destination t is in this subgraph and marked as visited, Bob can calculate the shortest distance from s to t locally, and thus terminates the protocol by returning SP$(s,t)$. Otherwise, Bob identifies the new vertex $nv$ for which the grid information is missing and sets it as the new current vertex $cv$. Then, the algorithm is repeated (i.e., go to step 1(b) of Algorithm 3) with an updated $cv$ as input to the next iteration.

Example 2.

In this example, we consider a sample weighted graph G (refer to Figure 2) and illustrate various intermediate steps during the execution of ESPADE. Here G consists of 16 vertices, denoted from A to P, and it is split into four evenly distributed square grids. The four grid cells are denoted by $M_1,\dots ,M_4$. Without the loss of generality, suppose Bob wants to retrieve the shortest path from A to P using ESPADE. Various intermediate results along with the shortest path discovery process in each iteration are shown in Figure 3. For brevity, we only show the steps involved during Stage 2 of ESPADE.

•

Iteration 1: Initially, Bob sets his current vertex $cv$ to A. In this case, the current grid ID of $cv$ is 1 since $cv$ resides in $M_1$. That is, Bob sets $cg=1$. Bob randomly splits his $cg$ information and sends them to $C_1$ and $C_2$, separately. At the end of the first iteration, Bob receives all the vertex and associated edge weight information of $M_1$. He updates his sub-graph $G_s$ (refer to Figure 3a) and executes Dijkstra’s algorithm. After marking C as visited, Bob makes I the current vertex.

•

Iteration 2: Bob updates the current grid ID $cg$ value to 3, as vertex I resides in $M_3$. $cg$ is passed as input to the second iteration. At the end of the second iteration, Bob expands $G_s$ as shown in Figure 3b.

∘

Similarly, Bob retrieves $M_2$ and $M_4$ information in iterations 3 and 4, respectively. Refer to Figure 3c,d. At the end, Bob finds out that SP$(A,P)=\{A,C,D,G,M,P\}$.

6. Performance Analysis of ESPADE

In this section, we present the security and performance analysis of the ESPADE protocol. First, we formally show that ESPADE is secure under the semi-honest model of SMC. Then, we discuss the complexity costs of our protocol and provide a comparative analysis with two existing solutions including experimental results.

6.1. Security Analysis under the Semi-Honest Model

As mentioned earlier, we assume that all the parties participating in our protocol are semi-honest as it is the commonly used adversarial model. Under the semi-honest model, parties follow the prescribed steps of the protocol, but they are free to deduce any meaningful information about the inputs based on the messages they see during the execution of the protocol. In this paper, we adopt the following security definition that is commonly used for the semi-honest model [19,35]:

Definition 1.

Suppose P be a party participating in a protocol π with input a and output b. Assume that ${\Pi }_{P,real}\left(\pi \right)$ denotes the P’s execution image of π. In general, an execution image of P consists of all the inputs, outputs, and the intermediate messages it sees during the execution of the protocol. Let ${\Pi }_{P,sim}\left(\pi \right)$ denote the P’s simulated image based on π and $\langle a,b\rangle$. Then, π is secure if the (real) execution image of P is computationally indistinguishable from its simulated image.

6.1.1. Proof of Security for Stage 1

During Stage 1, the execution image of $C_2$ is given by ${\Pi }_{C_2,real}\left(\mathrm{ESPADE}\right)=\{\langle T_{i,j}^2,F_{i,j}\rangle ,\mathrm{for}1\le i\le n\wedge 1\le j\le 3m+1$}. Here $T_{i,j}^2$ is the encrypted value received from Alice at step 2(a) of Algorithm 2. Additionally, $F_{i,j}$ is a random number derived upon decrypting $T_{i,j}^2$. Without loss of generality, let the simulated image of $C_2$ be given as ${\Pi }_{C_2,sim}\left(\mathrm{ESPADE}\right)=\{\langle a_{i,j},a_{i,j}^{\prime }\rangle ,\mathrm{for}1\le i\le n\wedge 1\le j\le 3m+1$}, where $a_{i,j}$ and $a_{i,j}^{\prime }$ are randomly chosen from ${\mathbb{Z}}_{N^2}$ and ${\mathbb{Z}}_N$, respectively. Since the encryption function of Paillier’s scheme is semantically secure, it is guaranteed that $T_{i,j}^2$ will be a random number in ${\mathbb{Z}}_{N^2}$. Thus, $T_{i,j}^2$ is indistinguishable from $a_{i,j}$. Similarly, $F_{i,j}$ is distinguishable from $a_{i,j}^{\prime }$. As a result, ${\Pi }_{C_2,sim}\left(\mathrm{ESPADE}\right)$ is computationally indistinguishable from ${\Pi }_{C_2,real}\left(\mathrm{ESPADE}\right)$, which implies that $C_2$ does not learn anything during the execution of Stage 1.

On the other hand, the execution image of $C_1$ in Stage 1 is given by ${\Pi }_{C_1,real}\left(\mathrm{ESPADE}\right)=\left\{T^2\right\}$, where $T^2$ is an encrypted matrix sent by $C_2$ (at step 2(c) of Algorithm 2). Let the simulated image of $C_1$ be ${\Pi }_{C_1,sim}\left(\mathrm{ESPADE}\right)=\left\{B\right\}$, where the values of $B_{i,j}$ are randomly selected from ${\mathbb{Z}}_{N^2}$. Since $E_{pk}$ is a semantically secure encryption function, it guarantees that ciphertexts $T_{i,j}^2$ are randomly distributed in ${\mathbb{Z}}_{N^2}$. This shows that $T_{i,j}$ is computationally indistinguishable from $B_{i,j}$; thus, ${\Pi }_{C_1,sim}\left(\mathrm{ESPADE}\right)$ is computationally indistinguishable from ${\Pi }_{C_1,real}\left(\mathrm{ESPADE}\right)$. Therefore, $C_1$ cannot deduce any information about G in Stage 1.

6.1.2. Proof of Security for Stage 2

In this sub-section, we formally prove that Stage 2 of ESPADE is secure as per Definition 1. Without the loss of generality, we consider the messages exchanged between $C_1$ and $C_2$ in a single iteration. We emphasize that similar analyses can be carried out for other iterations.

During Stage 2, the execution image of $C_2$ is given by,

$${\Pi }_{C_2,real}\left(\mathrm{ESPADE}\right)=\{cg2,\langle Y,Z\rangle ,\langle {\Lambda }^{\prime },{\gamma }_2\rangle \}$$

where $c{g}_2$ is a randomized value sent by Bob (at step 1(d) of Algorithm 3). Additionally, Y is an encrypted vector sent by $C_1$ at step 3(d) and Z is the resulting decrypted vector, such that exactly one of the entries is 0 and all others values are random numbers in ${\mathbb{Z}}_N$. Similarly, ${\Lambda }^{\prime }$ is the encrypted randomized vector sent by $C_1$ at step 5(d) and ${\gamma }_2$ is the resulting decrypted vector. Without loss of generality, let the simulated image of $C_2$ be given by,

$${\Pi }_{C_2,sim}\left(\mathrm{ESPADE}\right)=\{h,\langle I,J\rangle ,\langle K,L\rangle \}$$

Here h denotes a random number generated from ${\mathbb{Z}}_N$. I denotes a vector of size $3m+1$ whose elements are randomly selected from ${\mathbb{Z}}_{N^2}$ whereas vector J is randomly generated such that only one of the entries is 0 and the remaining entries are random numbers in ${\mathbb{Z}}_N$. Similarly, K and L denote vectors of size $3m+1$ whose elements are randomly selected from ${\mathbb{Z}}_{N^2}$ and ${\mathbb{Z}}_N$, respectively. Since $c{g}_2$ and h are both random numbers from ${\mathbb{Z}}_{N^2}$, it is evident that they are computationally indistinguishable. Since $E_{pk}$ generates ciphertexts that are uniformly random in ${\mathbb{Z}}_{N^2}$, we conclude that I and K are computationally indistinguishable from Y and ${\Lambda }^{\prime }$, respectively. Plus, J is computationally indistinguishable from Z as they both have exactly one of the entries as 0 and remain as random numbers in ${\mathbb{Z}}_N$. Furthermore, L and ${\gamma }_2$ are vectors consisting of random numbers chosen from ${\mathbb{Z}}_N$; thus, they are computationally indistinguishable. Based on the above results, it is implied that $C_2$ cannot deduce any information about G and Bob’s query during Stage 2.

Similarly, according to Algorithm 3, we can show that $C_1$’s execution image can be simulated from random numbers. The important observation here is that all the messages received by $C_1$ (from Bob and $C_2$) are either in an encrypted format or are randomized numbers distributed in ${\mathbb{Z}}_N$. Therefore, no information is revealed to $C_1$.

Following from Algorithm 2, we emphasize that ESPADE is constructed by sequentially combining the two stages. As shown above, Stages 1 and 2 are secure under the semi-honest model. Additionally, it is worth noting that the output of Stage 1 (which is in encrypted format) is passed as an input to Stage 2. Therefore, by Composition Theorem [35], we can conclude that ESPADE is secure under the semi-honest adversary model. That is, ESPADE ensures that neither the contents of G nor the shortest path query is revealed to $C_1$ and $C_2$. Therefore, our proposed protocol meets all the three privacy objectives (i.e., PO1, PO2, and PO3), described in Section 1.

6.2. Complexity Analysis

In this sub-section, we analyze the computation, communication and round complexities of the proposed ESPADE protocol.

Table 2. Complexity Results: Computation, Communication and Round Costs for different parties in ESPADE.

	Online Computation	Communication (in bits)	Round
Alice (one-time)	$(6m+2)\ast n$ additions	$2n\ast (3m+1)\ast logN$	-
Bob	$O\left(mn\right)$ additions	$O(nlogN)$	$O\left(n\right)$
Federated Cloud	$O(m{n}^{2}logN)$ multiplications	$O(m{n}^{2}logN)$	$O\left(n\right)$

shows the complexity costs incurred for various participating parties during the execution of our protocol.

6.2.1. Computation Costs

In our problem setting, we explicitly assume that the value of generator g is set to $N+1$ which helps us to optimize the Paillier encryption function without affecting the underlying security guarantees. Specifically, when $g=N+1$, Paillier’s encryption function can be reduced to $E_{pk}\left(m\right)=(1+m\ast N)\ast r^{N}mod{N}^2$, for any message $m\in {\mathbb{Z}}_N$. Additionally, it is worth noting that the computation of $r^{N}mod{N}^2$ can be done offline, since it is independent of the message to be encrypted. As a result, the actual online computation cost of Paillier encryption is two multiplications (under modulo $N^2$). We refer the reader to [36] for detailed security analysis on this setting. Following from the above optimizations, we only consider the online computation costs during our complexity analyses of ESPADE.

First, during step1(a) of Stage 1, the computation cost of Alice is bounded by $(6m+2)\ast n$ addition operations. Note that Alice does not participate in any other operations after outsourcing the data to FC. It is evident that Alice’s computation costs are negligible as it is a one-time cost. Similarly, the computation cost of Bob mainly depends on steps 1 and 7 in Algorithm 3. In each iteration, Bob needs to perform $O\left(m\right)$ additions. Since the number of iterations is bounded by $O\left(n\right)$, the total computation cost of Bob in ESPADE is bounded by $O\left(nm\right)$ additions (which is low compared to the overall computation cost of the protocol as shown below).

Next, we discuss the computation costs incurred on the federated cloud. During Stage 1, at step 2(b) of Algorithm 2, $C_2$ is involved in $n\ast (3m+1)$ encryption operations, which is equivalent to $2n\ast (3m+1)$ multiplication operations. Here n denotes the total number grids and m denotes the maximum number of 1-hop neighbors, a vertex can have in G. Additionally, at step 3(b), $C_1$ performs $n\ast (3m+1)$ multiplications. Combining these results, the total computation cost of FC in Stage 1 is bounded by $O\left(m{n}^2\right)$ multiplications.

During Stage 2, the computation cost of FC mainly depends on steps 3, 4, and 5 of Algorithm 3. For steps 3 and 5, $C_1$ needs to perform $(nlogN)$ and $(mnlogN)$ multiplications, respectively. For step 4, $C_2$ is involved in $logN$ multiplications. Therefore, the total computation cost of FC in stage 2 is bounded by $O(mnlogN)$ multiplications. Putting everything together, the total computation cost of FC (i.e., the combined computation costs of $C_1$ and $C_2$) in ESPADE is bounded by $O(m{n}^{2}logN)$ multiplications.

6.2.2. Communication and Round Complexity

One the one hand, for Alice, the communication cost depends on step 1(c) of Algorithm 2, where it sends out two matrices $T^1$ and $T^2$ to FC. The size of these matrices is $n\times (3m+1)$. Since each entry in these matrices is a random number chosen from ${\mathbb{Z}}_N$, the total size of each matrix is $n\ast (3m+1)\ast logN$ bits. Therefore, the total communication cost of Alice is $(2n\ast (3m+1)\ast logN)$ bits. On the other hand, in each iteration of Stage 2, Bob splits the $cg$ value into two random shares and forwards them to FC. This results in $2logN$ bits of communication. Since the number of total iterations is bounded by $O\left(n\right)$, the total communication cost of Bob is bounded by $O(nlogN)$ bits. On the other hand, the total communication cost of FC is bounded by $O(m{n}^{2}logN)$ bits.

The number of communication rounds between Bob and FC is bounded by $O\left(n\right)$. Furthermore, the number of communication rounds between $C_1$ and $C_2$ is bounded by $O\left(n\right)$. Therefore, the round complexity of ESPADE is bounded by $O\left(n\right)$.

6.3. Performance Comparison with Existing Work

In this sub-section, we compare the performance of ESPADE with two closely related works, namely PSPEG${}_1$ and PSPEG${}_2$ [14]. The performance comparison results are shown in

Table 3. Performance comparison of ESPADE with PSPEG${}_1$ and PSPEG${}_2$.

$\mathbf{Features}$	PSPEG${}_1$	PSPEG${}_2$	ESPADE
Cloud Model	Single-Cloud	Two-Cloud	Two-Cloud
Shortest-Path Accuracy	✓	✓	✓
Proof of Security	✗	✗	✓
Data Outsourcing Cost	$O(\ell mnlogN)$ mul.	$O\left(m\right|V|logN)$ mul.	$\mathit{O}\left(\mathit{mn}\right)$ add.
Bob’s Computation Cost	$O(n^{2}log{N}^{\prime })$ mul.	$O\left(\right|V|log|V\left|\right)$ add.	$\mathit{O}\left(\mathit{mn}\right)$ add.
Total Computation Cost	$O(m{n}^{2}log{N}^{\prime })$ mul.	$O\left(m\right|V{|}^{2}logN)$ mul.	$\mathit{O}({\mathit{mn}}^{\mathbf{2}}log\mathit{N})$ mul.
Total Communication Cost	$O(m{n}^{2}log{N}^{\prime })$ bits	$O\left(m\right|V{|}^{2}logN)$ bits	$\mathit{O}({\mathit{mn}}^{\mathbf{2}}log\mathit{N})$ bits
Total Round Complexity	$\mathit{O}\left(\mathit{n}\right)$	$O\left(\right|V\left|\right)$	$\mathit{O}\left(\mathit{n}\right)$

.

On the one hand, PSPEG${}_1$ is based on a single-cloud architecture whereas PSPEG${}_2$ and ESPADE adopt a two-cloud federated model. Additionally, we observe that PSPEG${}_1$, PSPEG${}_2$ and ESPADE always produce correct results as the underlying operations in all the three protocols are constructed based on Dijkstra’s algorithm. On the other hand, the security guarantees of PSPEG${}_1$ and PSPEG${}_2$ are unclear as no formal proofs were provided to demonstrate the confidentiality of the outsourced data, privacy of the user’s shortest path query and the protection of access patterns. In our case, as we formally showed in Section 6.1, ESPADE is semantically secure under the semi-honest model; thus, it meets all the three privacy criteria. Additionally, it is worth noting that ESPADE hides data access patterns due to the underlying random permutation operations.

We observe that PSPEG${}_1$ is very inefficient in terms of computation and communication complexities. Specifically, since PSEPG${}_1$ utilizes a single-cloud model, it incurs significant costs on the data owner Alice and the end-user Bob. For the data outsourcing step, the computation costs of Alice in PSPEG${}_1$ and PSPEG${}_2$ are bounded by $O(\ell mnlogN)$ and $O\left(m\right|V|logN)$ multiplications, respectively, where n denotes the number of grids and $\left|V\right|$ denotes the number of vertices in G. Unlike PSEPG${}_1$ and PSEPG${}_2$, our proposed ESPADE protocol utilizes a random splitting approach during the data outsourcing step, which incurs low costs on Alice. In particular, the computation cost of Alice is bounded by $O\left(mn\right)$ additions. It is clear that the computation cost of Alice is significantly less in ESPADE in comparison with PSEPG${}_1$ and PSEPG${}_2$.

For PSEPG${}_1$, the computation cost of Bob is bounded by $O(n^{2}log{N}^{\prime })$ multiplications, where $N^{\prime }$ denotes the RSA moduli, such that $N^2<N^{\prime }$. In PSPEG${}_2$, this computation burden is alleviated to a certain extent by pushing some expensive computations from Bob’s side to the second cloud. Nonetheless, the computation cost incurred on bob is bounded by $O\left(\right|V|log|V\left|\right)$ which is still high even for moderate-sized graphs ($\left|V\right|\approx 10,000$). In ESPADE, the computation cost of Bob is bounded by $O\left(mn\right)$ additions. It is worth noting that, with the effective combination of homomorphic encryption properties and our secure data aggregation technique, ESPADE significantly improves the computation cost of Bob. As shown in Table 3, ESPADE incurs overall less computation and communication costs compared to PSEPG${}_1$ and PSEPG${}_2$, especially for $n<\left|V\right|$. Furthermore, the round complexities of PSEPG${}_1$ and ESPADE are bounded by $O\left(n\right)$, whereas for PSEPG${}_2$ it is bounded by $O\left(\right|V\left|\right)$.

6.4. Experimental Results

In this sub-section, we demonstrate the superiority of ESPADE over PSPEG${}_1$ and PSPEG${}_2$ through empirical analysis. All three protocols were implemented in Java using the BigInteger Class to handle arbitrary-precision arithmetic operations, and experiments were conducted on a Intel^® Core™ i7 3.1 GHz PC running macOS 10.13.6 High Sierra with 16GB memory. The Paillier encryption key size is set to 1024 bits (i.e., the size of N in bits is 1024) and all the results presented are average values over five executions.

In our experiments, randomly generated datasets were used. For $\ell =20,m=20,n=100,\left|V\right|=5000$, the running time for Alice in PSPEG${}_1$ and PSPEG${}_2$ are 4.11 and 6.81 min, respectively, whereas the running time for Alice in ESPADE is 21 milliseconds. Note that Alice needs to perform expensive exponentiation operations to encrypt the matrix data in PSPEG${}_1$ and PSPEG${}_2$, whereas in ESPADE Alice simply involves in modulo addition operations. Additionally, the running time for Bob in PSPEG${}_1$ and PSPEG${}_2$ are 1.02 min and 121 milliseconds, respectively. The running time for Bob in ESPADE is 7 milliseconds. The above results clearly justify our performance analysis in Section 6.3 and show that ESPADE is significantly more efficient, by several orders of magnitude, than PSPEG${}_1$ and PSPEG${}_2$.

In summary, by using the proposed data aggregation approach in ESPADE, Alice can securely outsource her graph data and effectively delegate the shortest path query processing task to Federated Cloud (FC). Furthermore, the costs incurred on Bob during Stage 2 of ESPADE are minimal. Based on the above discussions, we conclude that ESPADE significantly offers improved performance in computation and communication load over PSPEG${}_1$ and PSPEG${}_2$, and at the same time, offering a higher level of security protection.

7. Conclusions

Existing research shows that location-based services violate user’s privacy and the issue becomes even more challenging when such applications are pushed to remote and non-trusted cloud servers. In this paper, we addressed the single-source single-destination shortest path query processing problem in outsourced LBS. Specifically, we proposed an efficient and semantically secure shortest path discovery protocol for encrypted graph data outsourced to a federated cloud environment. At the core of our proposed ESPADE protocol, we utilized homomorphic encryption combined with a novel data aggregation technique to enable the cloud service providers to operate over encrypted aggregated data in a privacy-preserving manner. We formally showed that our protocol is secure under the semi-honest model and also hides access patterns. Additionally, we discussed the complexity analysis of ESPADE and demonstrated that it is more efficient and secure compared to PSPEG${}_1$ and PSPEG${}_2$. Our experimental results show that ESPADE is significantly faster than the existing solutions.

Improving the performance of ESPADE further largely depends on minimizing the amount of data sent from the federated cloud to Bob. Additionally, improving the performance of the secure multiplication protocol is another important step to improve the overall efficiency of ESPADE. For future work, we will investigate better data aggregation and pruning techniques to enhance the secure retrieval of the shortest path (Stage 2) process in ESPADE. We will also extend our research to other graph mining tasks, such as minimum spanning tree and breadth-first search, over encrypted graph data. Another direction for future work is to extend the ESPADE protocol into a secure protocol under other adversarial models (e.g., covert and malicious models).