Ling Chen

Ting Yu

Rada Chirkova
email: rychirko@ncsu.edu

Privacy-Preserving Two-Party Skyline Queries over Horizontally Partitioned Data

Skyline queries are an important type of multi-criteria analysis with diverse applications in practice (e.g., personalized services and intelligent transport systems). In this paper, we study how to answer skyline queries efficiently and in a privacy-preserving way when the data are sensitive and distributedly owned by multiple parties. We adopt the classical honest-but-curious attack model, and design a suite of efficient protocols for skyline queries over horizontally partitioned data. We analyze in detail the efficiency of each of the proposed protocols as well as their privacy guarantees.

Introduction

Given a set of multi-dimensional vectors, a skyline query [START_REF] Borzsony | The skyline operator[END_REF] is to find all the vectors that are not dominated by any other vector. Skyline queries are widely used in multi-criteria decision making applications, for example, personalized services, intelligent transport systems, location-based services and urban planning.

In this paper, we study how to answer skyline queries over sensitive data distributedly owned by multiple parties who do not fully trust each other. Similar to many past efforts on other data analysis tasks [START_REF] Wahab | Darm: A privacy-preserving approach for distributed association rules mining on horizontally-partitioned data[END_REF][START_REF] Miyaji | Privacy-preserving data mining: A game-theoretic approach[END_REF][START_REF] Vaidya | Privacy-preserving top-k queries[END_REF][START_REF] Vaidya | Privacy-preserving naive bayes classification[END_REF], by adopting a secure multi-party computation setting, our goal is to design efficient and privacy-preserving distributed protocols to enable multiple data owners to collaboratively compute skyline queries without revealing their private inputs. Due to space limit, we focus on horizontally partitioned data where similar information about different individuals is collected in different organizations.

Our approach for privacy-preserving skyline queries over horizontally partitioned data utilizes some existing secure protocols for basic operations, such as secure comparison protocols [START_REF] Cachin | Efficient private bidding and auctions with an oblivious third party[END_REF][START_REF] Yao | Protocols for secure computations[END_REF], secure vector dominance protocols [START_REF] Atallah | Secure multi-party computational geometry[END_REF][START_REF] Ibrahim | Two-party private vector dominance: The all-or-nothing deal[END_REF][START_REF] Yuan | Secure computation of the vector dominance problem[END_REF], secure permutation protocols [START_REF] Du | Protocols for secure remote database access with approximate matching[END_REF], secure equality-testing protocols [START_REF] Fagin | Comparing information without leaking it[END_REF][START_REF] Naor | Oblivious transfer and polynomial evaluation[END_REF], and secure multi-to-sum protocols [START_REF] Naor | Oblivious transfer and polynomial evaluation[END_REF][START_REF] Naor | Efficient oblivious transfer protocols[END_REF]. To securely compute skyline queries, the secure protocol needs to address two problems: (1) how to securely determine whether a vector in one party dominates a vector in the other party? (2) how to securely apply the protocol of (1) to the set of vector pairs formed by pairing a vector V 1 in one party A with each vector in the other party B, with the goal of determining whether V 1 is dominated by any vector in party B or not. To address these two problems, straightforward compositions of such basic building blocks would not offer viable solutions. For example, existing techniques propose secure protocols to perform vector dominance checking, but they cannot be applied directly to address the first problem. The reason is that vector dominance requires each dimensional value in a vector V 1 to be strictly better than the corresponding dimensional value in another vector V 2 , while the dominance used in skyline queries (referred to as skyline dominance) allows some dimensional values but not all values in V 1 to be equal to the corresponding dimensional values in V 2 . Further, to address the second problem, simply invoking the protocol for the first problem for each pair of vectors when answering skyline queries would unnecessarily reveal sensitive intermediate results, i.e., V 1 is dominated or not dominated by certain vector in the other party.

To address these challenges, we propose three secure protocols. The major novelty of our protocols lies in the following aspects. First, to address the first problem, we propose a novel protocol, enhanced vector dominance protocol (EVDP). Our insight is that for two d-dimensional vectors V 1 and V 2 that are not equal in every dimension, we can obtain the same dominance results for vector dominance and skyline dominance if we improve every value in V 1 by a fixed value. Therefore, EVDP improves every value in V 1 by a fixed value to obtain V ′ 1 , and applies a vector dominance protocol over V ′ 1 and V 2 to securely obtain the skyline dominance results of V 1 and V 2 . Second, built upon EVDP, we propose three 1-to-N skyline dominance protocols (HP.1,HP.2, and HP.3) to address the second problem. These protocols determine whether a vector in one party is dominated by any of the N vectors in the other party. By applying these protocols on every vector in each party, we can securely compute the final skyline results without disclosing non-skyline results.

These three proposed protocols provide different levels of protection of the intermediate computation results with different communication and computation costs. HP.1 applies EVDP to determine whether a vector V a in party A is dominated by any of the n vectors V b1 , . . . , V bn in party B, and terminates whenever a dominance is found or when all vectors in party B are compared with. To prevent the disclosure of which vector in party B dominates V a , HP.1 also employs the secure permutation protocol to permute the order of the vectors in party B. However, such protocol still discloses the intermediate results about at least how many vectors in B do not dominate V a . To prevent such disclosure, HP.2 and HP.3 improve over HP.1 with different additional costs. HP.2 requires O(d • 2 n ) invocations of the multi-to-sum protocol, while HP.3 requires O(d • n) invocations of the multi-to-sum protocol for d-dimensional vectors and O(n) invocations of the secure comparison protocol. When n is relatively small, HP.2 and HP.3 have comparable costs, and HP.3 is preferred when n becomes larger.

Skyline Queries

Skyline queries are an important class of preference queries supporting multicriteria decision making. A skyline query over a d-dimensional data set S returns a subset of S containing d-dimensional vectors that are not dominated by any other vector in S. We assume the existence of a total order relationship on each dimension, and refer to the dominance relationship in skyline queries as skyline dominance:

Definition 1 (Skyline Dominance). Given two vectors V 1 = (a 1 , . . . , a d ) and V 2 = (b 1 , . . . , b d ), if for i = 1, . . . , d, a i b i and ∃j, a j ≻ b j , we say that V 1 ≻ s V 2 ,
where ≻ s denotes skyline dominance, denotes better than or equal to, and ≻ denotes better than.

Consider the following example of skyline queries. Assume that a user wants to book a hotel for a conference with the goals of inexpensive price and short distance to the conference venue. Consider four hotels A ($200, 5 miles), B ($150, 2 miles), C ($120, 3 miles), and D ($150, 1 mile). Hotel C is clearly a better candidate than A because C is cheaper and closer to the venue. Therefore, we say that C dominates A. Also, D dominates B since D is as expensive as B but is closer to the venue. However, C does not dominate B since B is closer than C to the venue. Therefore, the skyline results are {C, D}.

In a straightforward approach for skyline queries, such as Block-Nested-Loops [START_REF] Borzsony | The skyline operator[END_REF], a skyline vector needs to be compared against all other vectors to ensure that no other vectors dominate it. Without loss of generality, we assume that the domain of each dimension is I (the integer domain) and the larger the better, i.e., a bigger value dominates a smaller value. Each dimension can be encoded with l bits, and its value ranges from 0 to 2 l -1.

Horizontally Partitioned Data

We formally define skyline queries over the vectors distributed in two parties, i.e., horizontally partitioned data (HPD): Definition 2 (Skyline Queries over HPD). Party A has m vectors V a = (V a,1 , . . . , V a,m ) and party B has n vectors V b = (V b,1 , . . . , V b,n ). Vectors in both parties have the same d skyline attributes. A skyline query over HPD returns a set of vectors

{V i |V i ∈ V a ∪ V b , ∄V j ∈ V a ∪ V b , s.t. V j ≻ s V i }.
To compute skyline queries over HPD, a straightforward approach is to create a list of all the vectors from two parties and compute skyline vectors over the list of the vectors. A more efficient approach is to compute skyline vectors first in each party (referred to as local skyline vectors) and then compute global skyline vectors from the local skyline vectors, since local non-skyline vectors are guaranteed not to be global skyline vectors.

Application Scenario. A state fellowship is looking for high school student candidates that have high GPA, high SAT score and high ACT score. Since the candidates are distributed over different high schools within a state, secure skyline queries over the data across different schools are required. The scores of those students that are not selected for the fellowship should not be revealed. To securely select the candidates, high schools can perform privacy-preserving skyline queries with GPA, SAT and ACT scores as the skyline attributes.

Threat Model

We consider the semi-honest adversarial model, where both parties are honest but curious. Each party knows only its own vectors. The final skyline results are known to both parties. Given a secure protocol that computes the final skyline results, both parties strictly follow the protocol specifications but are willing to learn any information leaked during execution in order to compromise privacy.

Secure Multi-Party Computation Building Blocks

Secure multi-party computation (SMC) [START_REF] Goldreich | How to play any mental game[END_REF][START_REF] Yao | Protocols for secure computations[END_REF] is a framework that allows multiple parties to perform rich data analytics over their private data without revealing any information other than the output [START_REF] Amirbekyan | A new efficient privacy-preserving scalar product protocol[END_REF][START_REF] Atallah | Secure multi-party computational geometry[END_REF][START_REF] Yuan | Secure computation of the vector dominance problem[END_REF][START_REF] Laur | From oblivious aes to efficient and secure database join in the multiparty setting[END_REF]. We next present some basic SMC protocols that we use in our proposed protocols.

Secure Comparison Protocol. Secure comparison is an important problem in cryptography and its solution serves as a primitive operation in many SMC problems. The goal of this problem is to solve the inequality between two numbers a and b, i.e., whether a ≥ b, without revealing the actual values of a and b. Cachin [START_REF] Cachin | Efficient private bidding and auctions with an oblivious third party[END_REF] proposed a scheme where a semi-trusted third party provides a means for two bidders to determine whose bid is higher in zero knowledge. This scheme assumes that two bidders do not collude with each other. The communication complexity of Cachin's scheme is linear.

Secure Permutation Protocol. A secure permutation protocol is to permute the values in a vector without revealing the values of the vector and the permutation. A typical scenario is that party A has a vector V A = (a 1 , . . . , a d ) and party B has a private permutation π and a random vector R = (r 1 , . . . , r d ). A secure two-party permutation protocol enables party A to obtain π(V A + R) without party A learning π or R; Party B also should not learn about V A . Existing research [START_REF] Du | Protocols for secure remote database access with approximate matching[END_REF] introduces a representative secure protocol based on a homomorphic public key system. The working mechanism is as follows: firstly, party A generates a key pair for a homomorphic public key system and sends the public key to party B. Using the public key, party A then encrypts V A and sends the result

E(V A ) to party B. Party B computes E(V A ) • E(R) = E(V A + R),
permutes E(V A +R) using π, and then sends the result π(E(V A +R)) to party A. Party A decrypts π(E(V A + R)) by the private key and gets

D(π(E(V A + R))) = π(D(E(V A + R))) = π(V A + R).
Secure Equality-Testing Protocol. An equality-testing protocol is to determine the equality between two numbers without revealing the values of two numbers. A typical solution is to apply a commutative encryption scheme to achieve secure equality testing [START_REF] Fagin | Comparing information without leaking it[END_REF][START_REF] Naor | Oblivious transfer and polynomial evaluation[END_REF].

Secure Vector Dominance Protocol. Suppose party A has a vector V A = (a 1 , . . . , a d ) and party B has a vector V B = (b 1 , . . . , b d ). One existing protocol [START_REF] Atallah | Secure multi-party computational geometry[END_REF][START_REF] Ibrahim | Two-party private vector dominance: The all-or-nothing deal[END_REF][START_REF] Yuan | Secure computation of the vector dominance problem[END_REF] is as follows: first, party A and party B use an input disguise method to get a randomized input:

V ′ A = (a ′ 1 , . . . , a ′ 4d ) and V ′ B = (b ′ 1 , . . . , b ′ 4d
). Such a disguise makes sure that for values in V ′ A and V ′ B , there will be the same number of

a ′ i > b ′ i situations as that of a ′ i < b ′ i situations. Let Z = (1, . . . , 1, 0, . . . , 0)
, where the first 2d values are all 1 (indicating a ′ i > b ′ i ) and the remaining 2d values are all 0. Second, party B generates a random permutation π and a random vector R.

Party A computes V ′′ A = π(V ′ A + R) using the secure permutation protocol while party B computes V ′′ B = π(V ′ B + R) and Z ′ = π(Z).
Third, party A and party B use a secure comparison protocol, such as Yao's Millionaire protocol, to compare V ′′ Ai and V ′′ Bi where i = 1, . . . , 4d. Party A holds all the comparison results, U = (u 1 , . . . , u 4d ). If V ′′ Ai > V ′′ Bi , where i = 1, . . . , 4d, u i = 1, otherwise, u i = 0. Fourth, party A and party B use a secure equality-testing protocol to compare U with

Z ′ . If U = Z ′ , indicating a ′ i > b ′ i for i = 1, . . . , 2d, then V A dominates V B . Otherwise, V A does not dominate V B .
Secure Multi-to-Sum Protocol. The multi-to-sum protocol [START_REF] Naor | Oblivious transfer and polynomial evaluation[END_REF][START_REF] Naor | Efficient oblivious transfer protocols[END_REF] is to convert the multiplicative sharing of a secret s to the additive sharing of s. Assume there is a secret s over a ring R and s = a • b = x + y. P air(a, b) is called the multiplicative sharing of s. P air(x, y) is called the additive sharing of s. Initially, party A holds a while party B holds b such that a • b = s. After executing the multi-to-sum protocol, party A holds x and party B holds y such that x + y = s, with no information leaked to any of them about s or the multiplicative sharing a and b.

4 Privacy-preserving Skyline Queries

Enhanced Vector Dominance Protocol (EVDP)

Existing work proposes a secure vector dominance protocol (VDP) that securely computes the vector dominance of two d-dimensional vectors, but the definition of vector dominance is more strict than skyline dominance.

Definition 3 (Vector Dominance). Given two vectors

V 1 = (a 1 , . . . , a d ) and V 2 = (b 1 , . . . , b d ), if for all i = 1, . . . , d, a i ≻ b i , then we say that V 1 ≻ v V 2 ,
where ≻ v denotes vector dominance and ≻ denotes better than.

Table 1 illustrates the differences between vector dominance and skyline dominance using 2-dimensional vectors. As we can see from the second column ((2, 1) ≻ (1, 1)), vector dominance and skyline dominance return different values when (1) every value in V a is not worse than the corresponding value in V b and at least one value in V a is better than the corresponding value in V b and (2) at least one and at most d -1 values in V a are the same as the corresponding values in V b . Due to such differences, we cannot directly apply secure vector dominance protocols to answer skyline queries.

To address this problem, we propose an enhanced vector dominance protocol (EVDP), which adapts VDP to support skyline dominance. EVDP accepts as input two vectors V a = (a 1 , . . . , a d ) and

V bi = (b i,1 , . . . , b i,d ), and improves V bi in every dimension to obtain V ′ bi : V ′ bi = V bi + (1, . . . , 1) = (b i,1 + 1, . . . , b i,d + 1)
. By performing VDP on V ′ bi instead of V bi , EVDP obtains the same dominance results as skyline dominance except when V ai and V bi are exactly the same, as shown in the first column in Table 1. In other words, if we assume that V bi and Table 1: Differences between Vector Dominance and Skyline Dominance

Input: Va, V b (1, 1) ≻ (1, 1) (2, 1) ≻ (1, 1) (2, 2) ≻ (1, 1) (2, 0) ≻ (1, 1) Vector Dominance F F T F Skyline Dominance F T T F Enhanced Vector Dominance T T T F
V a are not the same in every attribute (referred to as the inequality assumption), then the results of EVDP is the same as skyline dominance's.

Checking the inequality assumption allows both parties to know that they have a set of common vectors. We next analyze how such disclosure can be used to infer side information about the other party. First, if a vector V 1 in party A and a vector V 2 in party B are equal, there exists no vector in either party dominating V 1 or V 2 , and V 1 and V 2 must belong to the final skyline results, which are known to both parties. Such disclosure cannot help a party infer the values of the remaining vectors in another party. Second, ideally, even if party A sees a vector of its local skyline results V 1 is in the final results, it should not know whether party B has the same vector. Thus, knowing the existence of V 2 can be used by A to infer that the local skyline results of party B do not contain the vectors that can be dominated by V 2 . However, such disclosure cannot be directly used by A to infer the complete data distribution of B's vectors.

To securely test the inequality assumption, we adopt equality-testing protocol, which leverages homomorphic encryption to securely identify from two parities all the vectors that have the same attribute values. For these identified vectors, we can safely output them as the final skyline results. Also, since these vectors do not dominate any other vector V ′ in the local skyline results (otherwise V ′ would not appear in the local skyline results), we can safely exclude them from the skyline dominance testing against the remaining vectors.

For computing the final skyline results from the remaining vectors, we propose three secure protocols based on EVDP.

1-to-N Skyline Dominance

As discussed earlier, a straightforward protocol that applies EVDP on each pair of vectors in both parties discloses significant intermediate results. To prevent such disclosure, we define 1-to-N skyline dominance as the primitive operation in privacy-preserving skyline queries over HPD.

Definition 4 (1-to-N Skyline Dominance). Party A has one vector V a = (a 1 , . . . , a d ) and party B has

n vectors V b1 = (b 1,1 , . . . , b 1,d ),. . . ,V bn = (b n,1 , . . . , b n,d ). 1-to-N skyline dominance returns false if ∄V bi s.t. V bi ≻ s V a ; otherwise, returns true.
Based on this definition, we propose three secure horizontal 1-to-N skyline dominance protocols, referred to as HP.1, HP.2, and HP.3, which securely compute skyline dominance between a vector V a in Party A and n vectors in party B. To obtain the final skyline results, these protocols are applied m + n times on each vector in parties A and B. One party can easily learn the number of vectors in the local skyline results in the other party (i.e., m or n) during the computation. To prevent the disclosure of m and n, both parties can generate random number of dummy vectors that are guaranteed to be pruned in the computation of final skyline results. The dummy vectors can be generated by randomly selecting outof-domain values. For example, when each element in a vector is in the range [0, 1000), the dummy vectors can be generated within the range (-∞, 0). We next present the details of the three protocols.

Secure Horizontal 1-to-N Skyline Dominance Protocol (HP.1)

To determine whether V a is dominated by any of the n vectors from party B (1-to-N Skyline Dominance), HP.1 first pairs V a with each of the vectors in party B and gets pairs of vectors (V a , V b1 ), . . . , (V a , V bn ). The steps of HP.1 are shown in Algorithm 1. To securely compute skyline queries over HPD, HP.1 prevents two types of disclosure: (1) for each pair (V a , V bi ), which values and how many values in V bi dominate the corresponding values in V a (Steps 1-4); (2) which vector in {V b1 , . . . , V bn } dominates V a (Steps 5-6).

In Step 1, party B prepares each of its vectors for EVDP by increasing the values in the vectors.

Steps 2-4 include input disguise, secure permutation and secure comparison, which are adapted from VDP. In Step 2, both parties A and B disguise their vectors to prevent the disclosure of how many values in V a are better than the values in V bi . We adopt the disguise algorithm based on [START_REF] Atallah | Secure multi-party computational geometry[END_REF]: given party A's vector V a = (a 1 , . . . , a d ), it generates a 4d-dimension vector

V ′ a = (a ′ 1 , . . . , a ′ 4d ), such that a ′ 1 = 2a 1 , . . ., a ′ d = 2a d , (1)
a ′ d+1 = 2a 1 + 1, . . ., a ′ 2d = 2a d + 1, (2)
a ′ 2d+1 = -2a 1 , . . ., a ′ 3d = -2a d , (3)
a ′ 3d+1 = -(2a 1 + 1), . . ., a ′ 4d = -(2a d + 1). (4)
Given party B's vector V bi = (b i,1 , . . . , b i,d ), it generates a 4d-dimension vector

V ′ bi = (b ′ i,1 , b ′ i,2 , . . . , b ′ i,4d ), such that b ′ i,1 = 2b i,1 + 1, . . ., b ′ i,d = 2b i,d + 1, (5) b
′ i,d+1 = 2b i,1 , . . ., b ′ i,2d = 2b i,d , (6) b
′ i,2d+1 = -(2b i,1 + 1), . . ., b ′ i,3d = -(2b i,d + 1), (7) b
′ i,3d+1 = -2b i,1 , . . ., b ′ i,4d = -2b i,d . (8)
This disguise scheme has the following interesting property: for a pair (V ′ a , V ′ bi ), there will be the same number of a ′ j > b ′ i,j situations as that of a ′ j < b ′ i,j situations when a j = b i,j or a j > b i,j or a j < b i,j . Thus, we cannot infer how many values in V 1 are greater than the values in V 2 by simply counting the number of "1"s in the comparison vector [START_REF] Atallah | Secure multi-party computational geometry[END_REF]. Also, we can see that when the d-dimensional vector V ′ a dominates V ′ bi , the comparison vector must be a 4ddimensional vector where the first 2d attribute values are all "1" and the remaining 2d attribute values are all "0". Thus, we construct Z = (1, . . . ,

1 2d , 0, . . . , 0 2d ) in
Step 2, which is used to determine whether V a is dominated by V bi by comparing the permuted Z with the comparison vector noted as U in HP.1 (Step 6).

In Step 3, HP.1 uses the secure permutation protocol to prevent B from learning the order of the vectors used to perform skyline dominance checking with V a . Party A generates n random permutations and n random vectors. These permutations and random vectors are used to permute the disguised vectors V ′ a , V ′ bi and Z. We use n random permutations instead of one to prevent adversaries from guessing the data distribution of the skyline attribute values.

In Step 4, for the ith pair (V ′′ a,i ,V ′′ bi ), party B applies a secure comparison protocol to obtain comparison results U i , where U i = (u i,1 , . . . , u i,4d ), u i,j = 1 if b ′′ i,j > a ′′ i,j , and u i,j = 0 if b ′′ i,j ≤ a ′′ i,j for j = 1, . . . , 4d. If we simply run a secure equality testing protocol for each pair of Z ′ i in Z and U i in U, we will disclose the intermediate results about whether V a is dominated by V bi or not.

To prevent disclosure of the intermediate results, HP.1 applies a secure permutation protocol on Z and U (Step 5). Party A generates a new random permutation π n+1 to obtains Z ′ , and party B obtains U ′ by using π n+1 . Then Z ′ is compared with U ′ by using a secure equality testing protocol: the testing terminates if there is any U ′ i = Z ′′ i or none can be found. Example. Assume that Party A has V a = (1, 1), and Party B has three vectors: V b1 = (3, 1), V b2 = (2, 2), and V b3 = (4, 0). After Step 1, we have V b1 = (4, 2), V b2 = (3, 3), and V b3 = (5, 1). We then perform input disguise (Step 2): Party A has V ′ a = (2, 2, 3, 3, -2, -2, -3, -3) and Z, and Party B has V ′ b2 = (7, 7, 6, 6, -7, -7, -6, -6). We omit the detailed transformations of V ′ b1 and V ′ b3 due to space limitations. In Step 3, assume that R 2 = (1, 1, 1, 1, 1, 1, 1, 1) and π 2 simply switches the first 4d values with the last 4d values: Party A has V ′′ a,2 = (-1, -1, -2, -2, 3, 3, 4, 4) and Z ′ 2 = (0, 0, 0, 0, 1, 1, 1, 1), and Party B has V ′′ b2 = (-6, -6, -5, -5, 8, 8, 7, 7). In Step 4, by applying secure comparison on V ′′ a,2 and V ′′ b2 , Party B obtains U 2 = (0, 0, 0, 0, 1, 1, 1, 1). In Step

U ′ = (U ′ 2 , U ′ 1 , U ′
3 ) (note that Party B does not know the order of items in U ′ ). In Step 6, Z ′′ 2 and U ′ 2 are first compared and since they are equal, we know that V a is at least dominated by V b2 .

Communication and Computation Cost. HP.1's communication cost includes the costs for applying the secure permutation protocol, the secure comparison protocol, and the secure equality testing protocol.

For a vector in party A(B), HP.1 needs to apply n + 1 (m + 1) times of the secure permutation protocol. We assume each dimension in a vector is an integer that can be encoded with l bits, and its value ranges from 0 to 2 l -1. The communication cost of applying one secure permutation protocol is O(d • l) as it uses the homomorphic public key system. As HP.1 is applied m times for vectors in party A and n times for vectors in party B, the cost of the secure permutation protocol is O(n • m • d • l). The computation cost of secure permutation depends on the adopted protocol. A representative protocol (see Section 3) requires O(1) encryption/decryption, O(1) modular multiplication to obtain E(V A )•E(R), and O(1) application of the permutation π, whose cost is O(d) for permuting values in a vector.

for i = 1 to n do V b i = Improve(V b i ) 2: Input disguise: Party A : V ′ a = Disguise(Va), Z = (1, . . . , 1 2d , 0, . . . , 0 2d ) Party B : for i = 1 to n do V ′ b i = Disguise(V b i ) 3: Secure permutation: Party A : for i = 1 to n do Generate πi and Ri, V ′′ a,i = πi(V ′ a + Ri), Z ′ i = πi(Z) Z = (Z ′ 1 , . . . , Z ′ n ) Party B : for i = 1 to n do V ′′ b i = SecurePermutation(πi,V ′ b i ,Ri) * 4: Secure comparison: Party B : for i = 1 to n do Ui = SecureComparison(V ′′ a,i ,V ′′ b i ) U = (U1, . . . , Un) 5: Secure permutation: Party A : Generate πn+1 for i = 1 to n do Generate R ′ i , Z ′′ i = Z ′ i + R ′ i Z ′ = πn+1(Z ′′ 1 , . . . , Z ′′ n ), R = (R ′ 1 , . . . , R ′ n ) Party B : U ′ = SecurePermutation(πn+1,U,R) 6: Secure equality testing: for i = 1 to n do if SecureEqualityTest(U ′ i , Z ′′ i ) then return true return false
The secure comparison protocol is applied to compare corresponding attribute values in two vectors, and thus we need to apply at most n•4d times of the secure comparison protocol. According to Cachin [START_REF] Cachin | Efficient private bidding and auctions with an oblivious third party[END_REF], the communication cost of Cachin's protocol to compare input numbers is O(l). By applying n + m times of HP.1, the communication cost of the secure comparisons is

O((n + m) • d • l).
The computation cost of one secure comparison includes the costs of one generation of the garbled circuits and one evaluation of the garbled circuits, which also includes the adopted oblivious transfer protocols and encryption/decryption of the values for the gates in the circuits [START_REF] Cachin | Efficient private bidding and auctions with an oblivious third party[END_REF][START_REF] Huang | Faster secure two-party computation using garbled circuits[END_REF][START_REF] Yao | Protocols for secure computations[END_REF]. Latest works on garbled circuits show that 16K-bit integer comparison can be computed within 0.5s [START_REF] Holzer | Secure two-party computations in ansi c[END_REF][START_REF] Liu | Oblivm: A programming framework for secure computation[END_REF].

The secure equality testing protocol uses the homomorphic public key system. Thus, the communication cost of the adapted equality testing protocol for evaluating the inequality assumption and the equality testing for determining the skyline dominance are both O((n + m)

• d • l). The computation cost is O(n + m) invocations of encryption and O(n • m • d) of comparisons to identify the equal encrypted vectors.
Security Analysis. In HP.1, Steps 1-4 protect the comparison results of a pair (V a ,V bi ). In Step 1, the result is computed locally in party B and no information is disclosed. The input disguise in Step 2 makes sure that if a j > b i,j , we will have a

′ j > b ′ i,j , a ′ d+j > b ′ i,d+j , a ′ 2d+j < b ′ i,2d+j
, and a ′ 3d+j < b ′ i,3d+j , preventing the disclosure of the comparison results in Step 4. In Step 3, party A generates the permutations and the random vectors, and thus after permutation party B loses track of the order of the values in the vectors. Party A does not know the values of U i and is not aware of the comparison results.

Steps 5-6 protect the comparison results of the pairs (V a ,V bi ), . . . , (V a ,V bn ). In Step 5, party A generates the permutation π n+1 and the random vector R, and thus after permutation party B loses track of the order of the vectors in U. On the other hand, party A knows the order of the vectors V ′′ a,i , (i = 1, . . . , n) after the permutation. However, since all the V ′′ a,i come from V a , party A cannot infer more information from the order other than what party A originally knows.

However, step 6 could disclose the intermediate results of at least how many vectors in party B do not dominate V a . In Step 6, parties A and B runs secure equality testing until a pair (V a , V bi ) is found to be equal. If such a pair is not found, then V a is not dominated by any vector in party B and no intermediate information is disclosed. But if such a pair is found in the ith secure equality testing, then both parties know that at least i-1 vectors in party B do not dominate V a in party A.

Enhanced Secure Horizontal 1-to-N Skyline Dominance Protocol (HP.2)

To prevent the disclosure in HP.1, i.e., V a in party A is not dominated by at least i -1 vectors in party B, we propose an enhanced secure horizontal 1-to-N skyline dominance protocol (referred to as HP.2), which replaces the secure equality testing (Step 6 in Algorithm 1) with a secure protocol to compute a product of the polynomials:

n i=1 (Z ′′ i -U ′ i ). If there exists i such that Z ′′ i = U ′ i ,
the product is 0, i.e., V a in party A is dominated by at least one vector in party B and V a is not a vector in the final skyline results.

2: Secure compute n i=1 (Z ′′ i -U ′ i ): n i=1 (Z ′′ i -U ′ i ) = n i=1 (Z ′′ i ) + n-1 i=1 (Z ′′ i ) • (-U ′ n ) + . . . + Z ′′ 1 • n i=2 (-U ′ i ) 2 n -2 multiplicative sharings:M S 1 ,...,M S 2 n -2 + n i=1 (-U ′ i ) Party A : for i = 1 to 2 n -2 do Xa i = MultitoSum(M Si) Az = n i=1 (Z ′′ i ) + 2 n -2 i=1 Xa i Party B : for i = 1 to 2 n -2 do X b i = MultitoSum(M Si) Bz = n i=1 (-U ′ i ) + 2 n -2 i=1 X b i 3: Equality testing: if Az + Bz = 0 then return true else return false
Secure evaluation of the product of polynomials can be achieved by leveraging the existing secure multi-to-sum protocol. The steps of the algorithm is shown in Algorithm 2. We first perform the polynomial expansion and obtain a sum of 2 n products. Each product can be converted from the multiplicative sharing to the additive sharing by the secure multi-to-sum protocol. Each party sums all the additive sharing together. Then each party shares the sum and securely computes the final product value of

n i=1 (Z ′′ i -U ′ i ).
If it is equal to 0, there must be at least one factor, i.e., (Z ′′ i -U ′ i ), being 0, indicating that V a in party A is dominated.

Let us walk through the process of polynomial expansion by an example where n = 2. Party A holds

Z ′ = (Z ′′ 1 , Z ′′ 2 ) while party B holds U ′ = (U ′ 1 , U ′ 2 ).
By polynomial expansion,

2 i=1 (Z ′′ i -U ′ i ) = Z ′′ 1 • Z ′′ 2 -Z ′′ 1 • U ′ 2 -U ′ 1 • Z ′′ 2 + U ′ 1 • U ′ 2 .
Party A holds the multiplicative value of

Z ′′ 1 •Z ′′ 2 while party B holds the value of U ′ 1 • U ′ 2 .
We use the secure multi-to-sum protocol to obtain the additive sharing X a and X b such that

X a + X b = Z ′′ 1 • U ′ 2
, where X a is held by party A and X b is held by party B. We do the same for U ′ 1 • Z ′′ 2 with Y a is held by party A and Y b is held by party B. Therefore, party A holds the sum

A = Z ′′ 1 • Z ′′ 2 + X a + Y a and party B holds the sum B = U ′ 1 • U ′ 2 + X b + Y b .
Then we adopt the secure sum protocol to obtain = A + B . If = 0, V a is dominated. Communication and Computation Cost. HP.2 includes the private permutation protocol, the secure comparison protocol, and the secure equality testing protocol. The analyses of these three protocols are the same as those in HP.1 except that HP.2 replaces Step 6 of HP.1 with the secure evaluation of the prod-

uct n i=1 (Z ′′ i -U ′ i ).
After the polynomial expansion, this product of polynomials is expanded into 2 n items. Among them, there are d • (2 n -2) items requiring the multi-to-sum protocol to securely convert the multiplicative sharing to the additive sharing.

To compute the final skyline results, HP.2 is applied m + n times. For party A, it requires m • d • (2 n -2) invocations of the multi-to-sum protocol. For party B, it requires n•d•(2 m -2) invocations of the multi-to-sum protocol. In total, the complexity is

O(m • d • (2 n -2) + n • d • (2 m -2)
) invocations of the multi-to-sum protocol. Even though the cost of the multi-to-sum protocol is O(l) invocations of OT 1 2 oblivious transfer of strings whose cost is O(l) [START_REF] Naor | Oblivious transfer and polynomial evaluation[END_REF][START_REF] Naor | Efficient oblivious transfer protocols[END_REF], the exponential invocations of the multi-to-sum protocol are expensive.

Security Analysis. HP.2 provides strong security guarantee. Compared with

HP.1, in Step 6 of HP.2, the evaluation of = n i=1 (Z ′′ i -U ′ i
) is protected by the secure multi-to-sum protocol. If is 0, both parties know that V a is dominated by at least one vector of B. But they cannot infer which vectors in B dominate V a . If is not 0, both parties know that V a is not dominated by any vector of B, and thus V a becomes a vector in the final skyline results. (Z ′′ i -U ′ i ) in HP.2 with the secure computation of

(Z ′′ i -U ′ i ) 2 . Since (Z ′′ i -U ′ i )
2 are all greater than or equal to 0, if the min value of (Z ′′ i -U ′ i ) 2 is 0, V a in party A is dominated; otherwise, V a is not dominated. We next discuss the three new steps of HP.3 in Algorithm 3.

In Step 2, each of (

Z ′′ i -U ′ i ) 2 is expanded into a polynomial, i.e., (Z ′′ i -U ′ i ) 2 = (Z ′′ i ) 2 -2 • Z ′′ i • U ′ i + (U ′ i ) 2
, where 2 • Z ′′ i • U ′ i can be converted to the additive sharing using the multi-to-sum protocol and then party A holds X ai and party B holds X bi . Then each of (Z ′′ i -U ′ i ) 2 can be transformed into the additive sharing where party A holds A i = (Z ′′ i ) 2 + X ai and party B holds B i = (U ′ i ) 2 + X bi . Therefore, party A holds A = (A 1 , . . . , A n ) and party B holds B = (B 1 , . . . , B n ).

In Step 3, we securely find the min value of A i + B i using n -1 times of secure comparisons. For example, we test whether

A 1 + B 1 < A 2 + B 2 , i.e., A 1 -A 2 < B 2 -B 1 . If A 1 + B 1 < A 2 + B 2 ,
we keep the pair (A 1 , B 1 ) to compare with the next pair (A 3 , B 3 ). It requires n -1 times of secure comparisons to find the min value A z + B z .

In Step 4, both parties reveal the values of A z and B z , whose sum is minimum among all, and compute A z + B z , and then test whether the min sum value is equal to 0 or not. If it is 0, V a in party A is dominated. Otherwise, V a is a global skyline vector. into the additive sharing. For Step 3, it requires O(n) invocations of the secure comparisons to securely identify the pair of (A z , B z ). For Step 4, there is no secure protocol applied and the cost can be ignored. Thus, HP.3 reduces the cost of HP.2 from the exponential invocations of the multi-to-sum protocol to the linear invocations of the multi-to-sum protocol plus the linear invocations of the secure comparison protocol. Security Analysis.

2: (Z

′′ i -U ′ i ) 2 computation: Party A : for i = 1 to n do Xa i = MultitoSum(Z ′′ i , U ′ i ) Ai = (Z ′′ i ) 2 + Xa i Party B : for i = 1 to n do X b i = MultitoSum(Z ′′ i , U ′ i ) Bi = (U ′ i ) 2 + X b i 3
Step 1 of HP.3 is the same as Steps 1-5 of HP.1, and thus protects the comparison results of the pairs (V a , V bi ). Steps 2-3 protect the information of how many vectors in party B may dominate V a . The multi-to-sum protocol in Step 2 makes sure that both parties cannot know the sum values of each pair (A i , B i ) while searching for the min sum A z + B z . Assume that after Step 3, both parties know that the ith pair produces the min sum (A z , B z ). Party B does not know the order of vectors as Step 5 in HP.1 (Algorithm 1) permutes the order. Hence, party B cannot infer which vector produces the value B z . For party A, all vectors are derived from V a and thus no more information can be inferred by party A regarding which vector in party B contributes to the value B z .

In Step 4, both parties reveal the values of (A z , B z ) to compute the minimum sum. If A z + B z = 0, both parties learn that V a is dominated. Party A can learn such result from the output as well. Party B can learn what vectors in A are global skyline vectors from the output and V a is not among the global skyline vectors. But B does not know the values of V a , and thus cannot know which vector in A is pruned. In addition, with dummy vectors included in the local skyline results of both parties, knowing that V a is pruned cannot be used by each party to learn the exact number of the pruned vectors. If A z + B z = 0, both parties can learn V a is not dominated and is a vector in the final skyline results, which can be learned from the output anyway. Since A generates the permutations, A knows the order of vectors in B and the ith vector of B is selected for (A z , B z ). However, A does not know the values of any vector from B and such information cannot be combined with B z to infer the value of V bz . For B, since the permutation π n+1 is generated by A, B does not know which vector of B is selected for (A z , B z ), and A z cannot be used by B to infer the value of V a .

Extension to N -Parties

All the proposed protocols (HP.1,HP.2, and HP.3) can be extended to support the secure communication and computation of N parties (N > 2) : (1) for party P 1 from N parties, apply the protocols on P 1 and every other N -1 parties, and only output the results of P 1 if the results are not dominated by any vector in the other N -1 parties; (2) P 2 first selects only the vectors that are not dominated by the results output by P 1 , then runs the protocols with every other N -2 parties, and outputs the results of P 2 ; (3) repeat (2) for the remaining parties.

Related Work

Yao [START_REF] Yao | Protocols for secure computations[END_REF] first proposed the two-party comparison problem (Yao's millionaire protocol) and developed a provably secure solution. Ben-Or et al. [START_REF] Ben-Or | Completeness theorems for noncryptographic fault-tolerant distributed computation[END_REF] and Chaum [START_REF] Chaum | Multiparty unconditionally secure protocols[END_REF] then proposed secure protocols for computing addition and multiplication (XOR and AND). More recently, the advances in the theory of secure multi-party computations [START_REF] Cachin | Efficient private bidding and auctions with an oblivious third party[END_REF][START_REF] Gordon | Complete fairness in secure twoparty computation[END_REF][START_REF] Harnik | Completeness in two-party secure computation: A computational view[END_REF] proved that any multi-party function can be computed securely with certain amount of computation cost.

With these primitives, finding an efficient and practical solution for a specific problem is still not trivial. A line of research has focused on developing efficient secure multi-party communication protocols for specific functions. There exists research work on more generic primitives such as set operations [START_REF] Blanton | Private and oblivious set and multiset operations[END_REF][START_REF] Michael | Efficient private matching and set intersection[END_REF], top-k queries [START_REF] Vaidya | Privacy-preserving top-k queries[END_REF]. More recent work also focuses on secure protocols for vector dominance [START_REF] Ibrahim | Two-party private vector dominance: The all-or-nothing deal[END_REF][START_REF] Yuan | Secure computation of the vector dominance problem[END_REF]. These protocols focus on finding more efficient solutions to specific problems, which can provide building blocks for more complex applications, such as the problem of skyline queries that our work focuses on.

Another important line of research focuses on creating frameworks and specialized programming languages to implement and run secure multi-party computation protocols. The early approaches include FairplayMP [START_REF] Ben-David | Fairplaymp: A system for secure multi-party computation[END_REF], Sharemind [START_REF] Bogdanov | Sharemind: A framework for fast privacypreserving computations[END_REF], and SEPIA [START_REF] Burkhart | Sepia: Privacy-preserving aggregation of multi-domain network events and statistics[END_REF], which implement generic MPC frameworks that support a similar set of primitives, such as addition, multiplication, comparisons and equality testing. These frameworks either provide specialized programming languages to facilitate the security programming, or allow users to program using standard programming languages and library calls. With the advances of research on garbled circuits [START_REF] Huang | Faster secure two-party computation using garbled circuits[END_REF][START_REF] Bellare | Efficient garbling from a fixedkey blockcipher[END_REF], more efficient framework, ObliVM [START_REF] Liu | Oblivm: A programming framework for secure computation[END_REF], has been built to make secure computations easier and faster. This framework provides a domain-specific language designed for compiling programs into efficient oblivious representations suitable for secure computations. It also provides MapReduce abstractions that facilitate the parallelization of the compiled program.

Unlike this line of research work that focuses on building efficient generic secure computation frameworks, our work focuses on designing efficient secure protocols that minimize the costs of communication and computation while preserve the privacy of the data in multiple participating parties.

Conclusion

Skyline queries are an important type of multi-criteria analysis with diverse applications in practice. In this paper, we adopt the classical honest-but-curious attack model and present a suite of efficient protocols for skyline queries to answer skyline queries in a privacy-preserving way when the data is sensitive and distributedly owned by multiple parties. The secure protocols for horizontally partitioned data take 1-to-N skyline dominance as the primitive secure operation to prevent the revelation of intermediate results. We analyze in detail the efficiency of each protocol and its privacy guarantee.

Algorithm 1

 1 Secure 1-to-N Skyline Dominance Protocol (HP.1) Input: Party A has one vector Va = (a1, . . . , a d ) and party B has n vectors V b 1 = (b1,1, . . . , b 1,d ),. . . ,V bn = (bn,1, . . . , b n,d ). Output: Whether Va is dominated by any of the n vectors in party B or not. 1: EVDP preparation: Party B :

Algorithm 2

 2 Enhanced Secure 1-to-N Skyline Dominance Protocol (HP.2) Input: Party A has one vector Va = (a1,1, . . . , a 1,d ) and party B has n vectors V b 1 = (b1,1, . . . , b 1,d ),. . . ,V bn = (bn,1, . . . , b n,d ). Output: Whether Va is dominated by any of the n vectors in party B or not. 1: Steps 1 -5 from HP.1.

4. 5 3 )

 53 Alternative Enhanced Secure Horizontal 1-to-N Skyline Dominance Protocol (HP.As discussed above, the use of polynomial expansion in HP.2 incurs exponential communication and computation costs. To reduce the cost, we further propose a more efficient protocol HP.3. The insight of HP.3 is to replace the secure evaluation of the product n i=1

Algorithm 3

 3 Alternative Enhanced Secure 1-to-N Skyline Dominance Protocol (HP.3) Input: Party A has one vector Va = (a1,1, . . . , a 1,d ) and party B has n vectors V b 1 = (b1,1, . . . , b 1,d ),. . . ,V bn = (bn,1, . . . , b n,d ). Output: Whether Va is dominated by any of the n vectors in party B or not. 1: Steps 1 -5 from HP.1.

:

  Min value identification: Party A : Az = A1 Party B : Bz = B1 for i = 2 to n do if SecureGreaterThan(Az -Ai, Bi -Bz) then Party A : Az = Ai Party B : Bz = Bi 4: Equality testing: if Az + Bz = 0 then return true else return false Communication and Computation Cost. The analysis of Step 1 in Algorithm 3 is the same as HP.1. For Step 2, it requires O(d • n) invocations of the multi-to-sum protocol to securely convert the multiplicative sharing Z ′′ i • U ′ i

* Using the secure permutation protocol, party B getsV ′′ b i = πi(V ′ b i + Ri).


Vassilios Vassilakis
email: vasileios.vasilakis@uwl.ac.uk

Emmanouil Panaousis
email: e.panaousis@brighton.ac.uk

Haralambos Mouratidis
email: h.mouratidis@brighton.ac.uk

Security Challenges of Small Cell as a Service in Virtualized Mobile Edge Computing Environments

Keywords: Security, small cell as a service, network functions virtualization, mobile edge computing, 5G

Research on next-generation 5G wireless networks is currently attracting a lot of attention in both academia and industry. While 5G development and standardization activities are still at their early stage, it is widely acknowledged that 5G systems are going to extensively rely on dense small cell deployments, which would exploit infrastructure and network functions virtualization (NFV), and push the network intelligence towards network edges by embracing the concept of mobile edge computing (MEC). As security will be a fundamental enabling factor of small cell as a service (SCaaS) in 5G networks, we present the most prominent threats and vulnerabilities against a broad range of targets. As far as the related work is concerned, to the best of our knowledge, this paper is the first to investigate security challenges at the intersection of SCaaS, NFV, and MEC. It is also the first paper that proposes a set of criteria to facilitate a clear and effective taxonomy of security challenges of main elements of 5G networks. Our analysis can serve as a staring point towards the development of appropriate 5G security solutions. These will have crucial effect on legal and regulatory frameworks as well as on decisions of businesses, governments, and end-users.

Introduction

Rapid advances in the industry of handheld devices and mobile applications has fuelled the penetration of interactive and ubiquitous web-based services into almost every aspect of our lives. At the same time, users expect almost zero-delay and infinite-capacity experience. However, current 4G technologies reveal their inherent limitations, as discussed in [START_REF] Boccardi | Five disruptive technology directions for 5G[END_REF]. This is true, for both human-to-human and machine-to-machine (M2M) communications [START_REF] Andreev | Understanding the IoT connectivity landscape: A contemporary M2M radio technology roadmap[END_REF][START_REF] Vardakas | Performance analysis of M2M communication networks for QoS-differentiated smart grid applications[END_REF]. Both will require radically different architectural design, network protocols, and business models. To achieve that, researchers are working towards the next-generation 5G wireless networks aiming to offer high-speed and personalized services to both humans and machines, when and where needed [START_REF] Patel | 5G: Future mobile technology -vision 2020[END_REF].

To support highly dense areas where a vast number of users want to access the network infrastructure, deployment of small cells (SCs) is envisioned. These can co-operate with traditional macro cells, to provide high levels of user experience [START_REF] Andrews | Seven ways that HetNets are a cellular paradigm shift[END_REF][START_REF] Osseiran | Scenarios for 5G mobile and wireless communications: The vision of the METIS project[END_REF]. SCs will play a significant role in 5G networks, which are expected to be highly heterogeneous. That is, future 5G networks will comprise a variety of collocated resources, such as indoor and outdoor SCs, macro cell sites, and WiFi access points. Another driving force in 5G will be the advances in hardware virtualization technologies, which can facilitate the realization of the small cell as a service (SCaaS) concept [START_REF] Trakas | A novel learning mechanism for traffic offloading with small cell as a service[END_REF].

The primary benefit that comes with SCaaS is that independent actors own and lease their cellular infrastructure to multiple mobile network operators (MNOs); therefore SCaaS provides a natural multi-tenant support, by allowing each MNO to be a tenant of the infrastructure and getting a "slice" of the physical SC infrastructure [START_REF] Giannoulakis | System architecture and aspects of SESAME: Small cEllS coordinAtion for Multi-tenancy and Edge services[END_REF]. This is not the only advantage that SCaaS can offer to 5G. We can leverage SCaaS to provide high-speed, low-latency communications, and to offload the mobile core network traffic and computation to the network edge, giving life to the concept of mobile edge computing (MEC) and fog computing, which has recently attained attention [START_REF] Soldani | A 5G infrastructure for anything-as-a-service[END_REF][START_REF] Vaquero | Finding your way in the fog: Towards a comprehensive definition of fog computing[END_REF][START_REF] Roman | A survey and analysis of security threats and challenges[END_REF].

Finally, another important technology of 5G is network function virtualization (NFV), which: decouples network functions from their physical location; offers flexible function migration; and distributes functions across different network components [START_REF] Han | Network function virtualization: Challenges and opportunities for innovations[END_REF][START_REF] Yu | Network function virtualization in the multi-tenant cloud[END_REF]. It is worth mentioning that NFV can be further enhanced with the concept of software-defined networking (SDN) decoupling the control plane from the data plane [START_REF] Ameigeiras | Link-level access cloud architecture design based on SDN for 5G networks[END_REF][START_REF] Sun | Integrating network function virtualization with SDR and SDN for 4G/5G networks[END_REF].

Although 5G network technologies are still taking shape, and standardization activities are still ongoing, it is expected that SCaaS, MEC, NFV, and SDN are going to be integral parts of 5G networks. For example, the recently started EU 5G-PPP project SESAME (Small cEllS coordinAtion for Multi-tenancy and Edge services) aims to provide solutions in the field [START_REF] Ec H | Small sElls coordinAtion for Multi-tenancy and Edge services (SESAME) Project[END_REF]. Another, EU 5G-PPP project called 5G-ENSURE aims at defining the security architecture and developing security enablers for 5G [START_REF] Ec H | 5G-ENSURE[END_REF].

Contribution

In order to investigate the security challenges of 5G networks, one must look into the security issues of its elements and their interaction. In this paper, we identify the security threats and vulnerabilities of SCaaS, NFV, and MEC, as a first step towards a more comprehensive 5G security analysis that we intend to undertake in future work. Our analysis is focused on SC infrastructure, whose security is a very crucial issue because SCs are expected to support both MNOs and end-users, who cannot tolerate financial losses or data privacy violations, and therefore they seek the highest possible security guarantees. Having a comprehensive view and taxonomy of security threats and vulnerabilities in SCs, is prerequisite for architecting optimal security solutions.

State-of-the-art

The state-of-the-art within the field of 5G security is in its infancy. Mantas et al. [START_REF] Mantas | Security for 5G Communications. Fundamentals of 5G Mobile Netw[END_REF] investigated some of the potential threats and attacks against the main components of 5G systems. The authors mainly focus on security issues related to the user equipment, and although they briefly go beyond that, they do not present security issues that open up as a result of SCaaS, NFV, and MEC. Apart from this, they lack a clear list of criteria that facilitate the creation of a taxonomy of threats and vulnerabilities. In an even less depth, in terms of threats and vulnerabilities investigation, Fang et al. [START_REF] Fang | Unified security architecture research for 5G wireless system[END_REF] propose a high level security framework for 5G networks, without paying particular attention in the technologies we consider in our paper, here.

Within the realm of physical layer security for 5G networks, Yang et al. [START_REF] Yang | Safeguarding 5G wireless communication networks using physical layer security[END_REF] investigate the security challenges that open up when considering the technologies of heterogeneous networks, massive multiple-input multiple-output (MIMO), and millimeter wave, which are likely to be important parts of 5G networks. Furthermore, Duan and Wang [START_REF] Duan | Authentication handover and privacy protection in 5G Het-Nets using software-defined networking[END_REF] investigated the security challenges, focusing mainly on authentication handover and privacy protection in 5G. The contribution of these papers is not directly comparable to ours, here, and we only referred to them for completeness.

Outline

This paper is structured as follows. In Section 2, we describe a generic, high-level architecture for SCaaS. We also present our assumptions regarding the SCaaS security and the adversarial model. Section 3 discusses the security challenges of SCaaS and reveals major security threats that arise due to (i) network resources and functions being virtualized, (ii) the adoption of MEC, and (iii) the incorporation of NFV and SDN concepts. We also present a set of criteria to facilitate the taxonomy of security challenges and discuss their mutual dependencies. Finally, Section 4 concludes this paper by summarizing its contributions and presenting our plans for future work.

Prerequisites

System Architecture

Our considered high-level system architecture for SCaaS is in line with [START_REF] Vassilakis | A softwaredefined architecture for next-generation cellular networks[END_REF] and has been illustrated in Fig. 1. The main elements of this architecture include: infrastructure virtualization; NFV; SDN, and MEC. According to the SC infrastructure virtualization principle, the physical SC is sliced into a number of virtual SCs (VSCs). To enable MEC services, each VSC is equipped with a MEC server, which has the ability to communicate with the Cloud and to execute some of the functions that are traditionally hosted in the Cloud. Furthermore, multiple MEC servers can be clustered to provide enhanced services in the form of a light data centre (Light DC) and managed by the virtual resources manager Fig. 1. High-level system architecture for Small Cell as a Service.

(VRM). Each VSC also accommodates a number of virtual network functions (VNFs) and it is managed by the SCaaS Orchestrator via an SDN agent. Above the management layer there is the service layer, in which multiple tenants (i.e., MNOs) are accommodated.

The network service layer accommodates MNOs who are benefited from having on-demand access to SC resources without owing the physical infrastructure. MNOs communicate with the SCaaS Orchestrator, located in the management layer, who orchestrates the allocation of virtual resources to MNOs. The SCaaS Orchestrator closely collaborates with the VRM, which is responsible for the management of virtual resources of MEC servers in the physical infrastructure layer. The control of VSCs is performed via SDN agents using some appropriate SDN protocol, such as the MobileFlow [START_REF] Pentikousis | Mobileflow: Toward software-defined mobile networks[END_REF]. Finally, various network functions, such as firewalling and deep packet inspection (DPI), are virtualized using the NFV technology and managed by the VNF Manager. A specific realization of the architecture of Fig. 1 could be, for example, the SESAME architecture [START_REF] Ec H | Small sElls coordinAtion for Multi-tenancy and Edge services (SESAME) Project[END_REF], [START_REF] Fajardo | Introducing mobile edge computing capabilities through distributed 5G cloud enabled small cells[END_REF]. However, in this work we intentionally keep our considered system architecture as generic as possible in order to accommodate a wide range of implementation choices of the SCaaS concept.

Security Assumptions

To identify the security challenges of the investigated system architecture, we first introduce our security assumptions, regarding the baseline security of the system. One of main assumptions is the physical security of SC infrastructure and hardware integrity. More specifically, we assume that hardware tampering is prevented by appropriate security controls deployed by the SC infrastructure owner [START_REF] Skorobogatov | Physical attacks and tamper resistance. Introduction to Hardware Security and Trust[END_REF], and that the Cloud provider has ensured the physical security of the Cloud infrastructure and of the data centres (e.g., according to the recommendations from the Cloud Security Alliance [START_REF]Cloud Security Alliance, Security Guidance for Critical Areas of Focus in Cloud Computing V2[END_REF]). The existence of physical attacks will be considered in our future works. Note that due to space limitations, in this paper, we do not consider attacks that are initiated from the Cloud side. Instead, we focus on attacks originated either from user equipment (UE) or from the SC infrastructure itself (e.g., from a malicious tenant or a compromised system component). Besides, modern literature has investigated Cloud-originated attacks and identified the main Cloud security challenges [START_REF] Subashini | A survey on security issues in service delivery models of cloud computing[END_REF][START_REF] Ryan | Cloud computing security: The scientific challenge, and a survey of solutions[END_REF]; developed adequate security solutions [START_REF] Zissis | Addressing cloud computing security issues[END_REF]; and proposed methods for Cloud provider selection based on security and privacy requirements [START_REF] Mouratidis | A framework to support selection of cloud providers based on security and privacy requirements[END_REF].

Adversarial Model

Our analysis adopts the widely-used Dolev-Yao adversarial model [START_REF] Dolev | On the security of public key protocols[END_REF]. According to this model, the cellular network is represented as a set of abstract entities that exchange messages and the adversary is capable of overhearing, intercepting, and synthesizing any message and they are only limited by the constraints of the deployed cryptographic methods. For example, the adversary neither is able to forge the message authentication code (MAC) nor has the means to obtain the plaintext of encrypted messages.

Apart from the above, we enrich the adversarial model by considering compromised nodes. The adversary per se could be a legitimate tenant interacting with network entities by using valid credentials and having privileged access to virtualized resources. Yet the adversary might run any management application in their VSC or specify various policies within its virtual domain, which is defined as a cluster of VSCs allocated to the same tenant.

Security Challenges

In this section we discuss the security challenges that emerge from the adoption of the SCaaS concept, using as a reference the architecture of Fig. 1. We adopt the widely-used threat taxonomy proposed in [START_REF] Papp | Embedded systems security: Threats, vulnerabilities, and attack taxonomy[END_REF] and identify the security challenges that arise due to specific architectural characteristics and interaction of various components and layers of SCaaS. The different security challenges can be classified according to five categories.

-Precondition: What are the necessary conditions to be met before the adversary is able to launch the attack? For example, if the attack requires a particular service running on the victim side, the existence of an open interface is a precondition; another case is when the adversary has some particular access rights. -Vulnerability: What are the vulnerabilities of the system components or the network interfaces, which can be exploited by the adversary? For example, some components could be implemented in software with flaws or non-adequate cryptographic mechanisms could be in place [START_REF] Mihaljevic | Generic cryptographic weakness of k-normal Boolean functions in certain stream ciphers and cryptanalysis of grain-128[END_REF]. -Target: Which components or interfaces are the potential attack targets?

Other considerations include the communication layer the adversary targets and whether he aims to compromise the control or the data plane or both. -Method: What are the various attack methods, tools and techniques that the adversary might use? In the same category we examine whether the adversary follows an active (e.g., replay attack) or passive strategy (e.g., passive reconnaissance). -Effect: What is the impact of a successful attack on the victimized system component or network interface? Impact might be, for instance, unavailability of some services, financial costs, and leakage of sensitive data.

Below, we identify specific security challenges for each of the aforementioned five categories.

Precondition

Regarding precondition, the following types of requirements might be valid for the adversary.

Specific configuration: In some cases, to launch an attack against a component, the adversary requires that this component has specific exploitable configuration or runs a specific software. For example, a precondition for a denialof-service (DoS) attack [START_REF] Gobbo | A denial of service attack to GSM networks via attach procedure[END_REF][START_REF] Merlo | A denial of service attack to UMTS networks using SIM-less devices[END_REF] can be specific configuration of the VRM with regard to the allocation of resources to tenants. Yet, some flaws in the resource allocation algorithm can allow the adversary to prevent a tenant from accessing its portion of virtual resources. Also, other types of DoS attacks may exploit the broadband nature of the wireless medium. For example, malicious interference at the physical layer, even using off-the-shelf hardware, can cause packet collisions at the media access control (MAC) layer [START_REF] Fragkiadakis | Denial-of-service attacks in wireless networks using off-the-shelf hardware[END_REF].

Ubiquitous connectivity: If a network component or function can be accessed via the public Internet, this may be exploited by a remote adversary. The adversary will require a way of discovering the vulnerable component and sending messages via control or data plane. By moving the network intelligence to the network edge, as with the Light DC, a pool of MEC servers is usually available for UEs to be connected via the Internet using conventional methods. Also, the physical location and distributed or centralised nature of the SCaaS Orchestrator could be an important factor influencing its security. For example, one way to realise the SCaaS Orchestrator is as a distributed function with its instances located across multiple SCs (e.g., in the form of a VNF). In such case, if public Internet is used to remotely configure various SCaaS policies, this can be exploited by the adversary.

Privileged access:

The adversary has privileged access to some parts of the network components or functions. The privileged access can be either at the administrator level or at the user level. For example, the adversary may be a legitimate UE receiving service from its MNO, with the latter being a legitimate tenant of the SC network infrastructure. Also, the emerging bring your own device (BYOD) trend in modern enterprises, constitutes many conventional security solutions incapable of protecting the private network [START_REF] Armando | Bring your own device, securely[END_REF]. For example, a Trojan horse that infected an employee's device, can bypass the security of the corporate firewall.

Vulnerabilitiy

SDN controller weaknesses: Some vulnerabilities are caused by flaws in software and programming errors. This may lead, for example, to control flow attacks [START_REF] Davi | MoCFI: A framework to mitigate control-flow attacks on smartphones[END_REF] and buffer overflow attacks [START_REF] Wang | Research of defense scheme against buffer overflow attack in embedded system[END_REF]. This issue is particularly important in the context of next-generation wireless networks, where the trend is to implement the control plane in software and to virtualize network functions [START_REF] Wang | SoftNet: A software defined decentralized mobile network architecture toward 5G[END_REF][START_REF] Vassilakis | On the security of software-defined next-generation cellular networks[END_REF] Flaws of NFV platforms: The virtualised environment itself could introduce many potential security problems [START_REF] Kotsovinos | Virtualization: Blessing or curse?[END_REF]. In particular, flaws of the virtualisation platform in place, may constitute the guest operating system (OS) vulnerable to side-channel attacks. For example, weak isolation between host and guest OSs may lead to a side-channel attack based on cache leakage [START_REF] Barthe | Cache-leakage resilient OS isolation in an idealized model of virtualization[END_REF].

Cloud based management: Some vulnerabilities stem from the Cloud based management nature of certain network components. The Cloud based interface used for configuration and updates could be used as a potential attack channel.

Weak access control and authentication: Use of weak or default passwords could be easily exploited by an adversary and should be avoided. Also, some components may have hard-coded passwords, which can be exploited by the adversary towards the establishment of backdoor access; stealthy or not.

Weak cryptographic mechanisms: Weaknesses or improper use of cryptographic mechanisms may lead to security breaches in authentication processes and data confidentiality. Also, the generation of cryptographic keys shouldn't rely on weak random number generators. Other security problems may arise due to communication protocols that use weak cryptographic primitives. Hence, it should be ensured that the cryptographic security controls are in place [START_REF] Bhargavan | Implementing TLS with verified cryptographic security[END_REF]. This is to say that any adopted public-key scheme that enables the encryption of the communications among SC, UE, and the Cloud, should be sufficiently secure.

Target

Physical small cell infrastructure: Attacks on the specific piece of hardware that is used in the cellular network [START_REF] Rostami | Hardware security: Threat models and metrics[END_REF]. For example the physical SC infrastructure can be a target of hardware attacks. While it is a common practice for the users to authenticate themselves to mobile devices before using them, the devices usually do not do the same to users. This means that there is a risk for the authentication secret to be revealed to a non-authenticated device. Hence, an attacker may try to obtain the secret, by replacing the device with a malicious one [START_REF] Findling | Towards device-to-user authentication: Protecting against phishing hardware by ensuring mobile device authenticity using vibration patterns[END_REF].

NFV-based management system: Some attacks initiated inside virtualised environments may aim at taking control of the Hypervisor [START_REF] Perez-Botero | Characterizing hypervisor vulnerabilities in cloud computing servers[END_REF]. Also, the SCaaS Orchestrator is an attractive attack target due to being in the '"middle" of the system model architecture, as well as other components of the management layer, such as the VNF Manager. Finally, impersonation by the adversary of one of the VNFs or the MEC server when communicating with the management layer could be a potential threat.

VM-hosted operating system: Both host and guest OS may be targeted [START_REF] Suzaki | Memory deduplication as a threat to the guest OS[END_REF], and to alleviate the impact of such an attack, adequate isolation must be enforced between guest virtual machines (VMs), as well as between the host and guest VMs. The adversary could attempt to break the isolation by exploiting, e.g., some flaws of the virtualisation platform in use [START_REF] Hoesing | Virtualization security assessment[END_REF].

Mobility management entity: In some cases, the attack does not target a specific layer in the system architecture, but it rather aims to take control of a specific network entity, either physical or virtual, such as the mobility management entity (MME). Protecting against such kind of attacks will be even more difficult when a distributed MME is introduced in 5G networks [START_REF] Giust | Distributed mobility management for future 5G networks: Overview and analysis of existing approaches[END_REF].

MEC-based application: A certain application that runs, for instance, on a MEC server is a potential attack target. This does not affect only the SC that hosts the compromised MEC server. Due to clustering of MEC servers into the Light DC, as discussed in Section 2, and their communication with the Cloud, a compromised MEC server can be used as a door to attack other network entities and components. Also, the adversary may attempt to attack the network service isolation. This may result in the violations of limits for virtual resources or unauthorized use of other tenants' resources. We assume that the adversary can attempt to impersonate another tenant or another network entity. Also, it may attempt to decrypt the intercepted messages.

MobileFlow protocol : A usual attack target is the protocol used for communication, management or control purposes, such as the MobileFlow protocol [START_REF] Pentikousis | Mobileflow: Toward software-defined mobile networks[END_REF]. For example, the southbound and northbound interfaces, shown in Fig. 1, are potential attack targets when attempting to hijack the communication of the SCaaS Orchestrator with VSCs and MNOs. Also, the communication within the SC infrastructure could be targeted; for example, between the management and the physical infrastructure layer. This may enable an adversary to alter the network policies and create attack channels. In particular, possible attack targets are (i) communication of the VNF Manager with VNFs in a SC; and (ii) communication of the VRM with MEC servers. Hence, the adversary may try to alter or disable legitimate policies and cause attacks such as DoS and privilege escalation or to violate the privacy of other tenants data.

Method

Reverse engineering: The adversary collects and analyses sensitive information about the network and its functionality. She may also try to decompile the soft- ware to retrieve the source code. This may enable the adversary to identify vulnerabilities in the software or network interfaces. In some cases, the adversary may exploit weaknesses in the implemented access control mechanisms and exploit a device through normal usage, i.e., as a legitimate user. Other reverseengineering techniques may target users' sensitive personal information. For example, the increasing popularity of mobile crowdsourcing and mobile sensing projects [START_REF] Chen | When crowdsourcing meets mobile sensing: A social network perspective[END_REF] may enable an attacker to exploit various personal data such as the user location, mobility patterns or web browsing habits [START_REF] Han | Mobile cloud sensing, big data, and 5G networks make an intelligent and smart world[END_REF].

SDN controller hijacking: By exploiting the SDN controller implementation weaknesses, the adversary tries to divert the control flows to a controlled device [START_REF] Goktas | Out of control: Overcoming control-flow integrity[END_REF]. Then the captured messages can be discarded preventing the data plane entities from proper operation. In a more advanced case, the captured messages may be manipulated with a special purpose code and sent into the network.

VNF/VM infection: The adversary infects a virtual network component, such as a VM or a VNF, with a malicious code. In this way, an unwanted and potentially harmful functionality can be added to the affected system and can modify its behaviour. The future trends in network softwarization and programmability [START_REF] Nikaein | Network store: exploring slicing in future 5G networks[END_REF][START_REF] Chin | Emerging technologies and research challenges for 5G wireless networks[END_REF] make this attack method particularly important. Furthermore, in a typical virtualised environment, guest VMs are expected to run in complete isolation. This means that a VM is not able to interact with the host and other VMs nor is able to monitor or control them in any way. This isolation is typically enforced by the Hypervisor. However, such virtualised environments may be vulnerable to the so-called VM escape attack [START_REF] Luo | Virtualization security for cloud computing service[END_REF], which is a process of breaking out the aforementioned VM isolation. This can be achieved for example by installing malware on the Hypervisor [START_REF] Oyama | Detecting malware signatures in a thin hypervisor[END_REF].

Crafted packets and data: The adversary can attack communication and control protocols by injecting crafted packets or crafted input data. These actions may exploit, for example, the parsing vulnerabilities of protocol implementations [START_REF] Hu | File parsing vulnerability detection with symbolic execution[END_REF].

Replay attack : The adversary captures packets or packet fragments and replays them at appropriate times aiming to cause protocol failures or other types of disruption and confusion.

Eavesdropping: The adversary observes messages exchanged between various network components or functions. In this way, sensitive information can be obtained, especially if this information is weakly protected by cryptographic mechanisms or not protected at all.

Effect

VM/VNF privilege escalation: The adversary, who has already some level of limited access privilege (e.g., to a VM or a VNF), manages to gain more privilege. This may have very serious negative effects for SDN-based mobile networks [START_REF] Chen | Software-defined mobile networks security[END_REF] as well as for the emerging Internet of things (IoT) technologies [START_REF] Roy | IoT enablers and their security and privacy issues[END_REF].

Denial of service: A potential outcome of attacks can be DoS leading to switched off or malfunctioning SC, or unavailable MEC servers. Also, a DoS attack against the SCaaS Orchestrator can cause service disruption and data loss. Yet, in a multi-tenant environment, security implications that may arise due weak isolation between tenants may allow adversaries to compromise more than one tenants upon compromising one of the other tenants. Furthermore, a DoS attack may be launched from within the SC [START_REF] Roman | A survey and analysis of security threats and challenges[END_REF].

Tenant data integrity violation: Some data or code, including various configuration settings and security policies, can be altered. This is a particularly important issue in a virtualised multi-tenant environment. It must be taken into account that some tenants could be malicious. Hence, adequate data isolation for different tenants must be ensured. This could be done, for example at the database level or at the hardware level.

Tenant confidentiality violation: In some cases sensitive information of a tenant may be leaked and made available to the adversary or to a malicious tenant.

Degraded level of SCaaS protection: A possible effect can be the degradation of SCaaS infrastructure protection. This can be achieved, for example, by altering the security policies or switching to weaker cryptographic mechanisms.

Illegitimate access to SC/MEC resources: The adversary gains illegitimate access to the SC resources (physical or virtual) or MEC environment. Given the increasing trend of outsourcing data and applications, an adequate security solution must ensure that only authorised entities gain access. Also, the insider threat should be considered and appropriate mechanisms must be put in place for preventing service providers form misusing tenants' data.

In Fig. 2, we show, in the form of a directed graph, an example of possible dependencies of these categories. For instance, to cause DoS, the adversary could select VM/VNF infection as an attack method. To achieve that, malware could be injected in the management system (e.g., to the VRM or the VNF Manager in Fig. 1), a VM-hosted OS, or a MEC-based application (i.e., by compromising a MEC server), which constitute the potential attack targets. To target, e.g., the VM-hosted OS, the adversary could possibly exploit the SDN controller weaknesses or flaws of NFV platforms, and take advantage of any privileged access rights.

Conclusion

In this paper, we have identified the most important security challenges of SCaaS in virtualized environments of 5G networks. We envision that novel technologies, such as NFV, SDN, and MEC will be adopted in the future and will play an important role in the SCaaS realization. We have summarized the main security challenges that (i) open up with these technologies and (ii) arise due to the interoperability among them, which enables SCaaS. We have highlighted the necessary conditions for the adversary to be able to launch an attack; the vulnerabilities of various system components and network interfaces that can be exploited by the adversary; potential targets of attacks, such as management systems and applications; various methods and techniques that can be used by the adversary; and finally, the impact of the attacks on an SCaaS provider and its tenants. In future work, we intend to study and evaluate prominent security solutions developed for protecting virtualized SC networks and systems per se, focusing on NFV, SDN, and MEC. This security assessment will use this paper, here, as a basis.

Fig. 2 .

 2 Fig. 2. Dependencies among security challenges of Small Cell as a Service in virtualised MEC environments.

Acknowledgements. The present work has been performed in the scope of the SESAME ("Small cEllS coordinAtion for Multi-tenancy and Edge services") European Research Project and has been supported by the Commission of the European Communities (5G-PPP/H2020, Grant Agreement No. 671596 ).