Sonja Brangewitz
email: sonja.brangewitz@upb.de

Simon Hoof
email: simon.hoof@upb.de

Economic Aspects of Service Composition: Price Negotiations and Quality Investments ⋆

Keywords: Service Composition, Price Negotiations, Quality Investments, Nash Bargaining Solution, Differential Games

We analyse the economic interaction on the market for composed services. Typically, as providers of composed services, intermediaries interact on the sales side with users and on the procurement side with providers of single services. Thus, in how far a user request can be met often crucially depends on the prices and qualities of the different single services used in the composition. We study an intermediary who purchases two complementary single services and combines them. The prices paid to the service providers are determined by simultaneous multilateral Nash bargaining between the intermediary and the respective service provider. By using a function with constant elasticity of substitution (CES) to determine the quality of the composed service, we allow for complementary as well as substitutable degrees of the providers' service qualities. We investigate quality investments of service providers and the corresponding evolution of the single service quality within a differential game framework.

Introduction

Service composition in cloud computing or on-the-fly computing environments is not just technically challenging, but also offers interesting questions that arise from an economic perspective. Strategic decisions with respect to service quality and prices influence the interaction between users, providers of composed services (also referred to as intermediaries), and providers of single services. A composed service with complementary single services as inputs requires negotiations with different service providers interdependently about prices and qualities. However, the providers of single services strategically determine quality investments and thus the quality level to maximize their individual profits. Therefore, the intermediary selling the composed service has to pay the service providers accordingly to induce them to deliver the single services such that they fulfil the requirements to satisfy the users' demand. We propose a model that allows us to analyse the negotiations between the intermediary and the service providers and to investigate the evolution of service quality and the investments therein in a dynamic context using a differential game.

Literature

Formally, we combine models from cooperative bargaining theory and from noncooperative differential game theory to describe the interaction on the market for composed services. More precisely, for the price negotiations we use the well established Nash [START_REF] Nash | The bargaining problem[END_REF] bargaining solution. The use of multilateral Nash bargaining is inspired by the analysis in [START_REF] Guo | Multilateral bargaining and downstream competition[END_REF]. They investigate negotiations in vertical supply relationships between one manufacturer and two retailers and make use of the Nash bargaining solution to describe simultaneous and sequential price negotiations. In our model we add a dynamic variable by considering the demand of the end user and thus the negotiations depending on the qualities of the single services. We assume that simultaneous multilateral price negotiations take place at every instant in time. Using a differential game we investigate the dynamic evolution of the service quality. A comprehensive introduction into differential games is [START_REF] Dockner | Differential games in economics and management science[END_REF]. In particular, the evolution of service quality is modelled using the techniques for capital accumulation games [START_REF] Dockner | Differential games in economics and management science[END_REF]Chapter 9]. A similar game is also used to describe the evolution of quality in health care markets [START_REF] Brekke | Competition and quality in health care markets: A differential-game approach[END_REF]. A systematic overview of the literature on service composition in cloud computing environments can be found in [START_REF] Jula | Cloud computing service composition: A systematic literature review[END_REF]. Here, the intermediary is also referred to as a "cloud service broker". They describe the analysis of "dynamically contracting service providers" as one of the "most remarkable challenges" for the cloud computing service composition problem [START_REF] Jula | Cloud computing service composition: A systematic literature review[END_REF]Section 4.2,p. 3813]. A comprehensive survey on the pricing of cloud services is [START_REF] Al-Roomi | Cloud computing pricing models: A survey[END_REF]. Various pricing schemes and techniques are systematically presented and compared with respect to their advantages and disadvantages as well as fairness and implementation in practice. For cloud instance pricing, when jobs arrive sequentially following a specific stochastic process, two techniques such as fixed unit prices and spot markets have been explicitly investigated and compared in [START_REF] Abhishek | Fixed and market pricing for cloud services[END_REF]. The authors provide evidence that a fixed unit price seems to dominate a combination of both pricing models in terms of expected revenue. Different approaches and protocols for bargaining-based negotiations of service level agreements in cloud computing are surveyed in [7, Section 4.2.1, p. 51:12f]. In particular, an application of cooperative bargaining theory to web services for bilateral negotiations between a user and a service provider is [START_REF] Zheng | Applying bargaining game theory to web services negotiation[END_REF]. While the focus of these models is often primarily on the pricing or negotiation procedure, our model incorporates the interaction of different types of service providers that is required for trading composed services. A simple model describing the interaction between an intermediary and two service providers has already been analysed in [START_REF] Brangewitz | Contract design for composed services in a cloud computing environment[END_REF]. However, the model was only able to capture two different quality levels of the composed and single services and the dynamic analysis was by means of a repeated game. We extend this analysis here in the sense that the quality of a single service is a continuous state variable and the overall quality can range from complements to substitutes. This means that we include a parameter describing how the pure quality of a single service may or may not be compensated by the good quality of another single service. The investment decisions to change the quality level of the service providers are strategic. The differential game framework sets up a dynamic optimal control problem for each service provider and thus allows us to investigate the evolution of service quality over an infinite time horizon. Quality-dependent negotiations take place at every instant in time and are modelled by using cooperative bargaining theory.

Model

We study a market consisting of three types of market participants: users, intermediaries and service providers. An intermediary purchases single services and combines them, where the quality of the composed service depends on the qualities of the single services delivered by the service providers. Finally, the composed service is sold to the users. Here, we focus on the interaction between one intermediary as the seller of a composed service to the users and two service providers as the sellers of single services to the intermediary. Each of the service providers is assumed to produce one single service. These services are supposed to have complementary properties, i.e., the intermediary needs to bargain with both service providers and the overall quality depends on both single services. The economic interaction on the market for composed services is illustrated in Fig. 1. Time is indexed by t ∈ R + := [0, ∞). However, for ease of notation the time index is generally omitted. The quality of the composed service is a function of the single services' qualities

Θ(θ 1 , θ 2 ) := θ ρ 1 + θ ρ 2 1 ρ (1)
where θ i ∈ R + denotes the quality of the single service produced by provider i = 1, 2 and ρ ∈ (-∞, 1) is a measure of substitutability between the two single services. Technically, the quality of the composed service as in ( 1) is determined by a function with constant elasticity of substitution (CES) between the two single services. For the limit cases we get some special functions, namely

Θ (θ 1 , θ 2 ) =      min (θ 1 , θ 2 ) for ρ → -∞, θ 1 θ 2 for ρ → 0, θ 1 + θ 2 for ρ → 1.
(

) 2
For a given overall quality of the composed service Fig. 2(a) illustrates the special cases. That is, for ρ < 0 the service qualities are complementary while for ρ > 0 they are substitutes. 1The users' demand for the composed services is modelled by a demand function

D(Θ, P) :=    Θ(θ 1 , θ 2 ) P 2 if both services are provided 0 otherwise (3)
that describes the quantity the users are willing to purchase for a given price P ∈ R + and overall quality level Θ(•) of the composed service. In addition, the users' demand for a single service is supposed to be zero. These assumptions on the user's demand imply the following for the composition of services: Single services themselves are assumed to be complementary, i.e., both single services are needed to produce the composed service; while the qualities of the single services may be substitutable or complementary, i.e., quality differences between both single services may cancel out to a given extent in the composed service. The demand function is strictly decreasing in price and strictly increasing in quality. This means that at a given quality level, higher prices lead to a lower demand of composed services; and at a given price level, higher quality of the composed service increases the quantity demanded. The demand function is illustrated in Fig. 2(b) and is similar to the demand function analysed in the analytical example of [3, Appendix A].

In order to trade the single services the intermediary has to agree with each service provider on a price. We refer to this price as a transfer T i in the following. To model the negotiations between the intermediary and the service providers we make use of cooperative bargaining theory (see [START_REF] Nash | The bargaining problem[END_REF]). We look at the individual profits from trading the single services. The intermediary is not only concerned with costs T i , but must take into account the users' demand as well. The service provider on the other hand has revenues of T i , but in addition production costs for supplying the single service. The overall cost function for each service provider i captures production as well as investment costs

θ 2 θ 1 min(θ 1 , θ 2 ) θ 1 + θ 2 θ 1 θ 2 (a)
C i (θ i , I i , D) := 1 2 α i θ 2 i + β i I 2 i + γ i D(Θ, P) (4)
with α i , β i , γ i > 0 and for i = 1, 2. Here I i denotes the investment to improve the quality of service θ i , i.e., one unit of investment comes with quadratic costs. In addition, production costs are linear increasing to cover a given demand and quadratic in the supplied quality level. The intermediary must pay some transfer T i to each service provider to incentivise production. The profits of the three parties can now be stated as

Π(P, D, T 1 , T 2 ) := P • D(Θ, P) - 2 ∑ i=1 T i ( 5
)
π i (T i , C i ) := T i -C i (θ i , I i , D) (6)
where Π(•) is the profit of the intermediary, i.e., revenues from selling the composed service to the users minus transfers to the input suppliers. And π i (•), for i = 1, 2, denotes the profit of the service providers, i.e. transfers from providing the single service minus total costs. The individual transfer schedule is the result of a simultaneous negotiation between the intermediary and the two service providers.

To ensure that negotiations actually take place we must assume that revenues of the intermediary exceed the production costs, i.e., there exists some surplus to be divided among the three parties

P • D(Θ, P) > 2 ∑ i=1 C i (θ i , I i , P). ( 7
)
If this condition did not hold, the analysis of the economic interaction was trivial in the sense that there is no allocation of the surplus that induces nonnegative profits simultaneously for all negotiating parties and thus no trade would take place. Moreover, the profits of the negotiating parties shall be nonnegative, i.e.,

Π(P, D, T 1 , T 2 ) ≥ 0 and π i (T i , C i ) ≥ 0. (8)
Equation ( 8) is known to be the individual rationality or participation constraints.

In case of a disagreement the payoff is assumed to be zero. Hereby, we implicitly suppose that the disagreement with one service provider means that the composed service cannot be produced, since the single services are assumed to be complementary. This also implies that the profit of the intermediary cannot become positive when agreeing only with the other service provider as users do not demand single services. We use the well-known Nash bargaining solution to explicitly determine these transfers ( [START_REF] Nash | The bargaining problem[END_REF]). The Nash bargaining solution has the advantage that it is characterized by some specific axioms2 and leads to strictly positive profits of the intermediary as well as the service providers. Consider the negotiations between the intermediary and service provider i. The Nash bargaining solution then satisfies

T N i ∈ arg max T i Π(P, D, T i , T 3-i ) • π i (T i , C i ) s.t. (8) holds. (9)
Note that the Nash product for the negotiations with service provider i in [START_REF] Nash | The bargaining problem[END_REF] as well as the participation constraint in (8) depend on the outcome of the negotiations between the intermediary and the other service provider 3i. The complementarity of the single services is reflected by taking a zero disagreement payoff in case one of the negotiations fails. The resulting transfer is then readily given by

T N i (P, D, C i , T N 3-i ) = 1 2 P • D(Θ, P) + C i (θ i , I i , D) -T N 3-i (P, D, C 3-i , T N i ) . ( 10
)
For i = 1, 2 we have two equations in two unknowns T N i (•). Hence, we may explicitly solve for the transfer and obtain

T N i (P, D, C i , C 3-i ) = 1 3 [P • D(Θ, P) + 2C i (θ i , I i , P) -C 3-i (θ 3-i , I 3-i , P)] . ( 11
)
This means that the surplus that exists on the market for selling the composed service taking the service providers' costs into account is evenly split among the two service providers and the intermediary. Finally, the intermediary determines the sales price of the composed service. In every period the intermediary solves the following (static) program

P * = arg max P Π(P, D, T N 1 , T N 2 ) = 2(γ 1 + γ 2 ). ( 12
)
Note that P * is a datum determined by exogenous parameters, i.e., profits are given by

Π(P * , D, T N 1 , T N 2 ) = π i (T N i , C i ) = 1 3 P * • D(Θ, P * ) - 2 ∑ i=1 C i (θ i , I i , P * ) . ( 13
)
Since every party earns the same profit, we may stick to one symbol π. After substituting (3), ( 4) and ( 12) into (13) one arrives at

π(θ, I) = 1 6     θ ρ 1 + θ ρ 2 1 ρ 2 (γ 1 + γ 2 ) -α 1 θ 2 1 + α 2 θ 2 2 + β 1 I 2 1 + β 2 I 2 2     (14)
where θ = (θ 1 , θ 2 ) and I = (I 1 , I 2 ). Note that costs of service composition may be easily introduced into the model. As the surplus resulting from the composed service is always evenly distributed among the negotiating parties we may include costs of service composition directly into Equations ( 5) and [START_REF] Hani | Renegotiation in service level agreement management for a cloud-based system[END_REF].

For the dynamic analysis it is crucial to note that the bargaining process takes place in every period. Therefore, (14) holds at every point in time t ∈ R + . This reduces the entire profit path {π(θ(t), I(t)) : t ∈ R + } into an expression which solely depends on the respective quality and investment level in each period where θ i (t) : R + → R + and I i (t) : R + → R, respectively, are time-dependent functions. Next, we set up a differential game to investigate the dynamic interaction of both service providers and show how to determine the optimal investment decision and the associated path of the overall quality level.

Dynamics of Service Quality and Investments

In this section we analyse the service providers' incentives to invest into the quality of their single services. Each service provider i can govern the quality level over time by investing I i (control variable). This means the next periods' quality is given by the current investment minus a loss in quality that appears over time (depreciation). The law of motion for the state variable can be modelled by a differential equation

∀t ∈ R + : θi = I i -δθ i ( 15
)
where δ ∈ (0, 1] denotes depreciation of quality and we used the abbreviation θi (t) := dθ i dt (t). By introducing a depreciation of quality we assume that maintaining the service quality requires continuous investments. That is, I i denotes gross investment. Here, the depreciation rate of quality captures that a service provider has to continuously take care of the quality of his service. For software services this is by continuously adapting the software to technological changes in the runtime environments, dependencies with other services or security requirements, for example. In our theoretical analysis, the depreciation rate remains a parameter of the model and may range from almost no reduction of quality over time to a complete reduction, making the software without investments in the extreme case useless. Equation (15) links the current quality and the investments into quality of a service provider. Thus, the optimization problem of service provider i boils down to choose a stream of investment levels {I i (t) : t ∈ R + } as to maximize his discounted profits with respect to the flow constraints and some given initial quality level max

{I i (t)} ∞ 0 e -rt π(θ, I)dt s.t. θi = I i -δθ i and θ i (0) > 0 (16)
where r > 0 denotes the time preference rate. Future profits are discounted since we presume that economic agents are impatient, i.e., they rather prefer to earn profits today than tomorrow. 3Next, the best response of a service provider is determined. The dynamic optimization problem is solved by applying the maximum principle [5, Theorem 4.2]. We set up the current value Hamiltonians for each service provider i by

H i (θ, I, µ i ) = π(θ, I) + µ i (I i -δθ i ). ( 17
)
where µ i is the costate variable. The current value Hamiltonian measures current profits as well as future profits which arise by investing into the service quality. Note that each service provider faces an intertemporal trade-off when making an investment decision. Current investment instantly lowers profits due to investment costs, but also raises expectations of future gains from the investment due to an increase in the service quality. The costate variable is thus considered as a shadow price which translates gains of investment into current profits. Inserting the service provider's profit from ( 14), the 1. first order condition for optimal investment reads

∂H i ∂I i (θ, I, µ i ) = - β i 3 I i + µ i = 0 ⇐⇒ I i = 3 β i µ i . ( 18
)
The interpretation of ( 18) is straightforward: the larger the investment cost parameter given by β i , the smaller the investment and the larger future gains of an increase in quality measured by the shadow price µ i , the higher the investment. That is, current marginal costs of investment must be outweighed by future gains of current investment. The 2. first order condition gives the evolution of the costate over time

μi = µ i r - ∂H i ∂θ i (θ, I, µ i ) = µ i (r + δ) + α i θ i 3 - θ ρ-1 i θ ρ 1 + θ ρ 2 1-ρ ρ 12 (γ 1 + γ 2 ) . ( 19
)
Since we are rather interested in evaluating the dynamics in the (I i , θ i ) space, we may differentiate (18) over time yielding μi =

β i 3 İi (20)
and then combine it with (19) using ( 18) which gives us

İi = I i (δ + r) + α i β i θ i - θ ρ-1 i θ ρ 1 + θ ρ 2 1-ρ ρ 4β i (γ 1 + γ 2 ) . ( 21
)
Considering both service providers, we now have a four-dimensional system of differential equations which is denoted by D( θ, İ). The dynamic equilibrium or fixed point can be found solving D(0, 0) for I and θ and is given by

4 Ĩi = δ 4 (γ 1 + γ 2 ) ξ i 1 + ξ i ξ 3-i ρ 2-ρ 1-ρ ρ , ( 22
) θi = Ĩi δ ( 23
)
with ξ i := δβ i (δ + r) + α i and ξ 3-i := δβ 3-i (δ + r) + α 3-i for i = 1, 2. Note that for particular values of ρ we have

5 θi =        1 4(γ 1 + γ 2 ) • 1 ξ 1 + ξ 2 for ρ → -∞, 1 4(γ 1 + γ 2 ) • 1 ξ i for ρ → 1. ( 24
)
If the qualities of the single services are complementary, then service provider i also takes into account the cost parameters of 3i and both providers will supply their single service in the same quality. This feature essentially captures the Leontief characteristics of the quality for the composed service. No service provider has an incentive to invest into quality of the single service if the overall quality is solely determined by the other provider. The dynamic equilibrium is in fact identical for both service providers for ρ → -∞. While if qualities are perfect substitutes, a service provider is concerned only about his firm-specific quality and investment costs. In addition, we see that the long-run quality level is unambiguously increasing in all exogenous parameters. The economic interpretation is as follows: Since α i , β i and γ i are cost parameters for producing θ i , we will observe a low long-run quality level for high production costs. If δ is high, then we will observe a low θi , because quality depreciates rather rapidly over time. To maintain some specific quality level the service provider must make large gross investments Ĩi , which are costly. Finally, θi is decreasing in r.

That is, if the service provider is impatient and does not value future profits that much, he invests little and the long-run equilibrium is low as well.

The stability of the fixed point can be checked by evaluating the eigenvalues of the Jacobian matrix. It turns out that the eigenvalues are real and opposite in sign. That is, there are two positive and two negative eigenvalues, indicating that the system is saddle point stable. 6 There also exists a unique saddle path converging to the dynamic equilibrium.

Simulation

Since the problem is open loop 7 in nature, we are dealing with an initial value problem. That is, given θ i (0) we are concerned only with determining optimal initial investment decisions I i (0), for i = 1, 2. The system dynamics are then fully characterized by the four differential equations D( θ, İ). However, there are infinitely many possibilities to pick initial investment I i (0) ∈ R. To pin down the unique saddle path we make use of the 3. first order condition, namely the transversality condition

lim t→∞ e -rt µ i (t)θ i (t) = 0. ( 25
)
The transversality condition ensures that the system moves along the saddle path, because it rules out exploding paths which diverge from the dynamic equilibrium. Hence the transversality condition gives rise to a terminal condition. If investment is in steady state at some time instance t = t f , then it has to be stuck there forever, i.e., lim t f →∞ I i (t f ) = Ĩi for i = 1, 2. Now we are dealing with a 4D system of differential equations with two initial and two terminal conditions. We then use a numerical boundary value problem solver to simulate the system. To simulate the model we have to parametrize it. We used the following parameters throughout θ

1 (0) = θ 2 (0) = 3, δ = 1, r = 0.05, α 1 , β 1 , γ 1 = 0.1 and α 2 , β 2 , γ 2 = 0.2.
We vary ρ ∈ {-5, 0.9} to emphasize the main feature of the model. That is, what the optimal quality level of a single service is if the overall quality of the composed service is either complementary or substitutable. The respective steady states are given by ( 23) and read ρ = 0.9 : θ1 = Ĩ1 = 4. If the services are substitutable (ρ = 0.9), then cost parameters drive the longrun equilibrium. Here the cost advantage of service provider 1 yields a higher investment and thus also a higher quality in the dynamic equilibrium. On the other hand, if services are complementary (ρ = -5), the cost advantage nearly vanishes and both service providers adjust quality towards some similar level. Figure 3 displays the respective time paths θ i (t) and I i (t) over a time horizon of five periods t ∈ [0, 5]. Consider the case ρ = 0.9 (cf. Fig. 3(a)). Firm 1 invests slightly more than the long-run equilibrium level and thus increases quality over time θ1 > 0. Service provider 2 on the other hand invests less and thus the quality decreases. Note that the time paths of quality steadily diverge from the common origin θ 1 (0) = θ 2 (0). Consider the case ρ = -5 (cf. Fig. 3(b)). Even though the cost parameters did not change, the dynamics fundamentally differ with respect to the first case. Here the shape of the time path is congruent for both service providers. Service provider 1 now adjusts the quality towards the less efficient provider 2, i.e., both service providers decrease quality over time and reach some "close" equilibria due to the complementarity of the services. Now service provider 1 has no incentive to produce a high quality service, since the overall quality is strongly determined by the lower quality.

Conclusion

We introduced a model with an intermediary producing a composed service using two single services to investigate the dynamic interaction on the market for composed services. While considering in principal a composed service with two complementary single services as inputs, our analysis is valid for different assumptions on how the quality of the composed service is actually determined from the single services' qualities. Price negotiations have been modelled cooperatively by simultaneously applying the Nash bargaining solution in negotiations between the intermediary and each single service provider. We have shown that the surplus that is generated from producing and selling the composed service to a user is evenly divided among the intermediary and the two service providers. The dynamic evolution of quality and the investments therein have been analysed using a differential game with an open loop strategy profile. We find that there exists a unique saddle point for the quality and respective investment level. That is, the equilibrium is generally unstable, but reachable on the unique saddle path. We pin down the saddle path by applying a boundary value problem solver. Depending on the quality substitutability the dynamics fundamentally differ for fixed, but asymmetric cost parameters. That is, cost advantages are of minor interest if the overall quality heavily depends on both services. This means we observe that there is a crucial impact of how quality differences between single services may or may not be compensated when the quality of the composed service is determined. Beyond our analysis here, several extensions of the model are possible. First of all, we did not explicitly fix a negotiation protocol. In fact, existing approaches and protocols implementing the Nash bargaining solution may be easily incorporated into the model without changing our observations. Surely the impact of competition between several intermediaries producing composed services and the use of more complex models of service composition are worth further investigation in future work. For instance, typically different alternative single services may be available for a composed service. Thus, besides complementary also substitutable single services may be considered. Competition between service providers may as well have an effect on the bargaining power of the intermediary. In addition, the comparison of different pricing models in an additional direction for further research.

A Technical Appendix

A.1 Fixed Point

In this section we derive the unique fixed point of D( θ, İ) denoted by θ, Ĩ . Instead of solving İ1 = İ2 = θ1 = θ2 = 0 simultaneously, we express the equilibrium investment level by means of the quality. Setting (15) equal to zero yields Ĩiδ θi = 0 =⇒ Ĩi = θi δ for i = 1, 2.

(28)

We now solve the remaining equations for θ1 and θ2 . Inserting (28) into (21) yields

θi δ δ + r + α i β i δ - θρ-1 i θρ 1 + θρ 2 1-ρ ρ 4β i (γ 1 + γ 2 ) = 0. ( 29
)
Rearranging gives us θ2-ρ i (β i δ(δ + r)

+ α i ) = θρ 1 + θρ 2 1-ρ ρ 4 (γ 1 + γ 2 ) . ( 30
)
Note that the right-hand side of (30) is identical for both providers, i.e, symmetric in the variables γ 1 and γ 2 as well as in θ1 and θ2 . Thus, we know that θ2-ρ

i ξ i = θ2-ρ 3-i ξ 3-i ( 31
)
where we defined ξ i := δβ i (δ + r) + α i for i = 1, 2. This yields a relationship between the two quality levels θ3-i = ξ i ξ 3-i 1 2-ρ θi =: φ i θi .

(32)

Now, we plug (32) into (30) and obtain θ2-ρ

i ξ i = θρ i + φ i θi ρ 1-ρ ρ 4 (γ 1 + γ 2 ) . ( 33
)
Solving according to θi yields

θi = 1 + φ ρ i 1-ρ ρ 4 (γ 1 + γ 2 ) ξ i . (34)

A.2 Stability

The stability of the fixed point can be checked by evaluating the eigenvalues {ω n : n = 1, 2, 3, 4} of the Jacobian matrix. We obtain

J D =             ∂ İ1 ∂I 1 ∂ İ1 ∂I 2 ∂ İ1 ∂θ 1 ∂ İ1 ∂θ 2 ∂ İ2 ∂I 1 ∂ İ2 ∂I 2 ∂ İ2 ∂θ 1 ∂ İ2 ∂θ 2 ∂ θ1 ∂I 1 ∂ θ1 ∂I 2 ∂ θ1 ∂θ 1 ∂ θ1 ∂θ 2 ∂ θ2 ∂I 1 ∂ θ2 ∂I 2 ∂ θ2 ∂θ 1 ∂ θ2 ∂θ 2             =     ε 11 0 ε 13 ε 14 0 ε 22 ε 23 ε 24 ε 31 0 ε 33 0 0 ε 42 0 ε 44     (35) with ε 11 = ε 22 = δ + r, ε 31 = ε 42 = 1, ε 33 = ε 44 = -δ, ( 36
)
ε 13 = α 1 β 1 + 1 -ρ 4β 1 (γ 1 + γ 2 ) θ ρ-2 1 θ ρ 2 θ ρ 1 + θ ρ 2 1 ρ -2 , ( 37
)
ε 24 = α 2 β 2 + 1 -ρ 4β 2 (γ 1 + γ 2 ) θ ρ-2 2 θ ρ 1 θ ρ 1 + θ ρ 2 1 ρ -2 , ( 38
)
ε 14 = - 1 -ρ 4β 1 (γ 1 + γ 2 ) (θ 1 θ 2 ) ρ-1 θ ρ 1 + θ ρ 2 1 ρ -2 , ( 39
)
ε 23 = - 1 -ρ 4β 2 (γ 1 + γ 2 ) (θ 1 θ 2 ) ρ-1 θ ρ 1 + θ ρ 2 1 ρ -2 . ( 40
)
The eigenvalues are

ω 1,

Fig. 1 .

 1 Fig. 1. Market Interaction

DFig. 2 .

 2 Fig. 2. Quality and demand of the composed service

  3 and θ2 = Ĩ2 = 2.3 (26) ρ = -5 : θ1 = Ĩ1 = 1.3 and θ2 = Ĩ2 = 1.2 (27)

  Complementary services ρ = -5Note: Quality and investment levels over five time periods t ∈ [0, 5] for varying quality substitutability ρ ∈ {-5.0, 0.9}. Service provider 1 is indicated by solid red and provider 2 by dashed blue lines.

Fig. 3 .

 3 Fig. 3. Solution Paths

  2 = 1 2 ε 11 + ε 33 ± (ε 11ε 33 ) 2 + 4ε 13 = 22 + ε 44 ± (ε 22ε 44 ) 2 + 4ε 24 = 1 2 r ± (r + 2δ) 2 + 4ε 24 .Since ε 13 > 0 and ε 24 > 0 we must have |r| < | (r + 2δ) 2 + 4ε 13 | and |r| < | (r + 2δ) 2 + 4ε 24 |. Hence two eigenvalues are positive and the remaining two are negative ω 1,3 > 0 > ω 2,4 respectively. The system is thus said to be saddle point stable.

			1 2	r ± (r + 2δ) 2 + 4ε 13
				(41)
	ω 3,4 =	1 2	ε (42)

Note that the elasticity of substitution can be denoted by σ = 1 1-ρ . We may observe σ → {0, 1, ∞} for ρ → {-∞, 0, 1}.

See[START_REF] Nash | The bargaining problem[END_REF] for further details.

From a technical point of view we must assume that r > 0, because otherwise the payoff integral may not converge.

Further details on the derivation are presented in Appendix A.1.

At the discontinuity point ρ = 0, where the quality of the composed good switches from complementary to substitutable, one can show that the left-and right-hand side limits differ with lim ρ→0 -θi = 0 and lim ρ→0 + θi = ∞.

derivation can be found in Appendix A.2.

Actually, here the cooperative as well as the open and closed loop solution coincide. Since profits are split evenly among the market participants they try to maximize the overall profit, which is basically the definition of a cooperative mood of play. In addition, the game is somehow linear-quadratic (LQ). That is, the law of motions are linear and the payoffs are quadratic with respect to the control and state variable. LQ games are known to have the same solution for open and closed loop strategies [5, Section 7.1].

⋆ This work was partially supported by the German Research Foundation (DFG) within the Collaborative Research Center "On-The-Fly Computing" (SFB 901). We thank Claus-Jochen Haake for constructive suggestions and comments.


Somchart Fugkeaw
email: somchart@satolab.itc.u-tokyo.ac.jp

Hiroyuki Sato

Updating Policies in CP-ABE-based Access Control: An Optimized and Secure Service

Policy update management is one of the key problems in the ciphertext policy-attribute-based encryption (CP-ABE) supporting access control in data outsourcing scenario. The problem is that the policy is tightly coupled with the encryption itself. Hence, if the policy is updated, the data owner needs to reencrypt files and sends them back to the cloud. This incurs overheads including computation, communication, and maintenance cost at data owner side. The computation and communication overheads are even more costly if there are frequent changes of access control elements such as users, attributes and access rules. In this paper, we extend the capability of our access control scheme: C-CP-ARBE to be capable to support secure and flexible policy updating in data outsourcing environment. We develop a policy updating algorithm and propose a very lightweight proxy re-encryption (VL-PRE) technique to enable policies to be dynamically and effectively updated in the cloud. Finally, we demonstrate the efficiency and performance of our proposed scheme through our evaluation and implementation.

Introduction

To consider adopting a cloud solution for storing large scales of highly value data, security and privacy are of paramount importance. Existing research works and cloud applications generally deploy encryption techniques and applicable access control model to satisfy the security requirement.

Access Control is among the most effective solutions for full-fledged network security control. Data access control for outsourced data should not only support the security but it should also provide a flexible and efficient management of the policy enforced over a large number of users as well as the optimized cost for handling the change of access control elements such as users, attributes, access policies. Importantly, the access control policy must be up-to-date to support the right and effective control and enforcement. In addition, access control supporting collaborative accesses across the data sources outsourced at the cloud servers is very important.

Attribute-based encryption (ABE) [START_REF] Goyal | Attribute-Based Encryption for Fine-grained Access Control of Encrypted Data[END_REF] is regarded as an effective solution for formulating a lightweight access control to outsourced data and unknown decrypting parties. To date, several works apply ciphertext attribute-based encryption (CP-ABE) [START_REF] Wan | HASBE: A Hierarchical Attribute-Based Solution for Flexible and Scalable Access Control in Cloud Computing[END_REF][START_REF] Yang | Enabling efficient access control with dynamic policy updating for big data in the cloud[END_REF][START_REF] Li | Scalable and Secure Sharing of Personal Health Records in Cloud Computing using Attribute-based Encryption[END_REF][START_REF] Yang | Expressive, Efficient, and Revocable Data Access Control for Multi-Authority Cloud Storage[END_REF][START_REF] Fugkeaw | Achieving privacy and security in multi-owner data outsourcing[END_REF] for the access control solutions and generally concentrate on minimizing key management cost, reducing computing cost of interaction between data owner and outsourced data storage, improving scalability and efficient revocation. However, these works have not addressed the policy evolution or policy updating problem in their proposed models.

In fact, policy updating is one of the critical administrative tasks to control the most up-to-date access policy enforcement. The policy update in CP-ABE renders the cost of policy update operation, cost of file re-encryption and communication cost for loading the file back to the cloud. All of these costs are usually occurred at data owner's side.

Therefore, in addition to the fine-grained and scalable access control model supporting data outsourced in the cloud, optimizing the policy update is also another grand challenge. For the operational point of view, the issues including correctness, security, and accountability of the subsequent update of policy are the requirements to be provided by CP-ABE policy updating scheme. These requirements are described as follows.

• Correctness: An updated policy must be syntactically correct and the policy updating must support any types of CP-ABE policy boolean. In addition, users who hold the keys containing a set of attributes satisfying the policy are able to decrypt the data encrypted by an updated policy. • Security: A policy must be updated by the data owner or authorized administrator only in the secure manner and a new policy should not introduce problems for the existing access control. • Accountability: All policy updating events must be traceable for auditing.

The remainder of the paper is organized as follows. Section 2 discusses related works. Section 3 presents detail of our proposed approach. Section 4 describes the policy updating method and presents concept of our proxy re-encryption scheme. Section 5 gives the evaluation and implementation detail. Finally, the conclusion and future work are depicted in Section 6.

Related Work

Ciphertext Policy Attribute Based Encryption (CP-ABE) was originally proposed in [START_REF] Bethencourt | Ciphertext-policy Attribute-based Encryption[END_REF]. In CP-ABE, each user is given a set of attributes, which is embedded into the user's secret key, and a public key is defined for each user attribute. The ciphertext is associated with the access policy structure in which the encryptor can define the access policy by her own control. Users are able to decrypt a ciphertext if their attributes satisfy the ciphertext access structure.

However, policy update in ABE scheme has attracted less attention by existing research works. In [START_REF] Sahai | Dynamic credentials and ciphertext delegation for attributebased encryption[END_REF], the authors introduced a ciphertext delegation method to update the policy of ciphertext in attribute-based access control. Their method aimed at solving user revocation based on a re-encryption delegation technique to protect newly encrypted data. Nevertheless, the performance on updating the ciphertext over the complex access policy was not examined by the authors.

Recently, K. Yang et al. [START_REF] Yang | Enabling efficient access control with dynamic policy updating for big data in the cloud[END_REF][START_REF] Yang | Secure and Verifiable Policy Update Outsourcing for Big Data Access Control in the Cloud[END_REF] proposed a method to outsource a policy updating to the cloud server. They proposed policy updating algorithms for adding and removing attributes in the AND, OR, and threshold gate of LSSS policy. The proposed scheme is to update ciphertext in order to avoid file re-encryption. Cost for ciphertext update is also linear to the number of attributes updated over the access structure. Besides, the authors have not discussed how updated polices are maintained and how the security and accountability are supported when there is the policy update.

Proxy-based Re-encryption (PRE) was initially introduced by Mambo and Okamoto [START_REF] Mambo | Proxy cryptosystems: Delegation of the power to decrypt ciphertexts[END_REF]. They proposed a technique that uses a concept of delegator to perform re-encryption of the ciphertext sent by the originator. In this scheme, the delegator learns neither the decryption keys nor original plaintext. Later, Ateniese et al. [START_REF] Ateniese | Improved Proxy Re-encryption Schemes with Applications to Secure Distributed Storage[END_REF] introduced a proxy re-encryption scheme that improves security in preventing collusion attack over the bilinear map. They implemented the PRE to show its efficiency in a few PRE scenarios. This approach becomes adopted by several PREbased scheme.

In 2014, K. Liang et al. [START_REF] Liang | An Efficient Cloud-based Revocable Identity-Based Proxy Re-encryption Scheme for Public Clouds Data Sharing[END_REF] proposed a cloud-based revocable identity-based proxy re-encryption (CB-IB-PRE) scheme to support user revocation in the cloud data sharing systems. Hereafter, several works [ e.g., 10, 14 ,17, 20] have adopted PRE to optimize the revocation overhead, specifically the re-encryption cost in attributebased access control.

In [START_REF] Lai | Adaptable Ciphertext-Policy Attribute-based Encryption[END_REF], the authors introduced adaptable CP-ABE scheme to handle policy changes in CP-ABE encryption for data outsourced in cloud computing. In this scheme, a trapdoor is generated from the central authority and it is used to transform a ciphertext under one access policy into ciphertexts under any other access policies. With this scheme, a data owner outsources ciphertext re-encryption task to the proxy and the proxy can not learn the content from the plaintext encrypted. However, the trapdoor generation is still the computation burden that the authority has to compute every time of all policy update events.

In [START_REF] Kawai | Outsourcing the Re-encryption Key Generation: Flexible Ciphertext-Policy Attribute-Based Proxy Re-encryption[END_REF], Yukata Kawai proposed a flexible CP-ABE proxy re-encryption scheme by combining key randomized and encrypted methodology and adaptive CP-ABE. The proposed scheme focuses on reducing the computation cost at client side by outsourcing the re-encryption key generation to cloud server. The universal reencryption key (urk) is proposed to be used together with the decryption key (Sk s ) for generating the re-encryption key. The decryption key is concealed by randomized parameters and sent to the cloud for computing the re-encryption key. Importantly, Kawai's approach is the first attempt dealing with the outsourcing concept of reencryption key generation in PRE setting. However, the author does not provide the performance evaluation to demonstrate the efficiency of the proposed scheme.

However, the proposed schemes [START_REF] Lai | Adaptable Ciphertext-Policy Attribute-based Encryption[END_REF][START_REF] Kawai | Outsourcing the Re-encryption Key Generation: Flexible Ciphertext-Policy Attribute-Based Proxy Re-encryption[END_REF] only provide the security function while the implementation result and performance have not been provided. Hence, the efficiency of the proposed CP-ABE proxy re-encryption in handling the policy changes cannot be inferred.

In [START_REF] Fugkeaw | Embeding Lightweight Proxy Re-Encryption for Efficient Attribute Revocation in Cloud Computing[END_REF], Fugkeaw and Sato proposed PRE scheme that fully outsources reencryption key generation to the proxy; the computation cost at data owner is minimized. However, if there are frequent revocation or policy update cases, the reencryption key needs to be re-generated in every cases and data owners require to prepare and submit data package to the proxy for computing the re-encryption key.

To the best of our knowledge, existing normal PRE schemes are not practical for policy updating in large-scale data outsourcing environment where the access control elements are changed frequently. This is because cost for re-encryption key generation is unpredictable at the data owner side. However, offloading too much computation cost to a proxy may introduce the delay for re-encryption task and thus cause efficiency problem. Besides, this strategy is also not advisable for the cloud model that the cloud provider charges the fee based on CPU usage. Thus optimizing both setup cost at data owner side and re-encryption cost at cloud side is a real challenge. Unfortunately, this computation optimization aspect has not been addressed by the existing PRE schemes. In this paper, we entail the practical solutions for handling policy evolution in the evolvable cloud environment with the consideration on computation and communication cost reduction in both data owner and cloud side.

Background

C-CP-ARBE Model

In this section, we give basic system definitions of our proposed access control called Collaborative-Ciphertext Policy-Attribute Role-based Encryption (C-CP-ARBE). The proposed access control model integrates role-based access control (RBAC) model into the CP-ABE. The model thus accommodates the benefits of RBAC feature with the attribute-based attribute encryption. RBAC provides more scalable management over a number of attributes [START_REF] Liang | An Efficient Cloud-based Revocable Identity-Based Proxy Re-encryption Scheme for Public Clouds Data Sharing[END_REF]. Here, a set of attributes in CP-ABE is assigned to the specific roles and the privileges are included to compliment the expressiveness of access control mechanism. Definition 1 and Definition 2 show the complete set of our access control elements and access control policy (ACP).

Definition 1: User (U), Role (R), Attributes (attr), and Permission (P)

• User (U) is a subject who requests to access (read or write) the data outsourced by the data owner in the cloud. Each user is assigned the set of attributes with respect to his/her role by the attribute authority. • Attributes(Attr) are a set of attributes used to characterize the user and associated to the particular attribute "role". A set of attributes is issued by attribute authority(AA). • Role (R) is a super set of attribute where users and respective attributes are assigned to. • Permission(P) is an action or privilege having value read (r) and write (w).

Definition 2: Access Control Policy (ACP)

ACP is a tree-based structure. Let ACP T is a tree represent the access structure in C-CP-ARBE. Each non-leaf node of the ACP tree represents the Role node and threshold gate where the Role node is a parent of threshold gate node. The threshold gate rule is the same as access tree of CP-ABE. We denote the parent of the children node x in the tree by parent(x). Thus, the parent of leaf node x is the pair of {Role node, threshold gate}. The function attr(x) is defined only x is in a leaf node of the tree. To provide a fine-grained access control, we introduce special attribute "privilege" as an extended leaf (EL) node of the ACP T in order to identify the read or write privilege of the role. Figure 1 illustrates a sample access control policy used to enforce access rules to hospital staffs and patients in accessing disease diagnostic data. Figure 1 illustrates a sample access control policy used to enforce access rules to restrict the access of hospital staff and patients to the healthcare data. As seen from the figure, hospital staffs, hospital executives, and a specific group of medical doctor from another hospital is allowed to access the disease diagnostic data.

The policy is administered by the host hospital and it is able to be updated by authorized administrator. In reality, such a policy can be changed anytime. For example, the senior nurse may be allowed to access the diagnosis file for preparing the summarized report. In this case, the data owner needs to update the above policy tree by adding role "nurse" and its attributes with the logical rules specifying the authorized access to the diagnosis file. In addition to updating the policy, the file encrypted by the before-updated policy needs to be retrieved from the cloud and it will be decrypted and re-encrypted with a new policy. Then, it will be uploaded back to the cloud. This is a cumbersome task especially when there is a large amount of data as well as the high chance of policy changes. We will discuss how the policy change is securely and efficiently managed in section 4.

C-CP-ARBE Constructs

Our proposed cryptographic process of C-CP-ARBE scheme is a kind of Multi-Authority CP-ABE (MA-CP-ABE). We use attribute authority identification (a id ) to identify the authority who issues the attributes to users. Each user who is issued the attributes by the attribute authority is identified with uid.aid. Basically, bilinear map is a major construct in our user key generation protocol.

Definition 3: Bilinear Map [7]

Let G 1 and G 2 be two multiplicative cyclic groups of prime order p and e be a bilinear map, e : G 1 ×G 1 →G 2 . Let g be a generator of G 1 . Let H: {0,1}* → G 1 be a hash function that is modeled in a random oracle. The bilinear map e has the following properties: 1. Bilinearity: for all u, v ∈G 1 and a, b ∈ Z p , e(u a , v b ) = e(u, v) ab 2. Non-degeneracy: e(g, g) ≠1.

The following table presents the notations and its description used in our proposed algorithms. Here, we present our four major cryptographic algorithms including AA setup, user key generation, encryption, and decryption.

AuthoritySetUp

Attribute Authority Setup (AA k where each AA is identified with a id ) Each AA k (k ∈ set of all authority S A ).

Let S (a K ) be a set of attributes issued and managed by the authority AA k . The AA setup (AA k ) chooses two random numbers , ∈ .

Then the Public Key (or PK aid )= G 1 , g, h = , = / , e( , ) ; and the Secret Key (or SK aid ) is ( , ).

2. UserKeyGen(S uid,aid , SK aid , Cert uid ) EDK uid,aid , RDK aid . The KeyGen algorithm takes continuous two steps as follows:

(1) the algorithm takes input as set of attributes S uid,aid , attribute authority's secret key SK aid , then it returns the set of user decryption keys UDK.

(2) a UDK is encrypted with the global public key of the user Cert uid and outputs an encrypted decryption key EDK uid,aid . In addition to the UDK generated, the system will also produce the root decryption key RDK aid for further use in reencryption key generation. It contains the data owner's ID attribute and digital signature attribute of the data owner. Thus, the RDK aid is very small and it can be used to decrypt the files they created because these two attributes are bounded in the ACP as default attributes. RDK aid is also encrypted by the data owner's key.

3. Enc(PK aid , [SS, GRP], M, ACP, Cert uid ) SCT. The encryption algorithm performs two continuous steps as follows:

(1) Inner layer: the algorithm takes as inputs authority public key PK aid , access control policy ACP, and data M. Then it returns a ciphertext CT. (2) Outer Layer: the algorithm takes group role parameter GRP which is randomly generated from a set of user members (i.e. Users' IDs) of all roles. GRP is used as a key together with AES algorithm to generate the session key referred as a secret seal SS. The SS is used to encrypt the ciphertext CT. Then, the algorithm returns sealed ciphertext SCT. Finally, a SS is encrypted with user's public key Cert uid , and stored in the cloud server.

4. Decrypt(PK aid , SCT, GSK uid , EDK uid ,) M. The decryption algorithm performs two continuous steps as follows:

(1) Decrypt the secret seal SS. The algorithm takes user's global secret key GSK uid and then obtains the session key to decrypt the SCT and gets the CT.

(2) Decrypt the encrypted decryption key (EDK uid ). The algorithm takes user's global secret key GSK uid and then obtains the user decryption key UDK. Then, if the set of attribute S satisfies the ACP structure, the algorithm returns the original M.

Policy Updating Method

To complete the policy updating process, two tasks including policy updating and file re-encryption are required. To this end, we propose a policy updating algorithm and a proxy re-encryption technique called a very lightweight PRE (VL-PRE) to efficiently support the required tasks respectively.

Flexible and Secure Policy Update Management

Outsourcing policy update to the cloud enhances the service availability and reduces computing costs at data owner side.

In typical cloud-based access control systems, if there is a change to the policy, data owners apply a new policy to re-encrypt the files at their local side and send them back to the cloud server. Accordingly, policy update introduces the communication, computation, and maintenance cost at data owners.

Therefore, a flexible and secure policy update should be provided to allow data owners or administrators to manage the attributes (add, update, delete) in polices stored in a cloud server in a practical manner. We develop policy updating algorithm to support access policy updating in the cloud. This reduces computation and communication cost and allows the data owners to update the policy anytime and anywhere. The policy updating undertakes the updating operations including add, update, and delete of the attributes contained in the policy together the syntax checking. For the syntax checking, the algorithm checks the possible operands taken on the attribute type and attribute value. This guarantees that the updated policy is syntactically correct. In our scheme, after the policy updating is done, the proxy will return false else if (policy.contain ("and" | "or" using in attribute)) return false else if(!policy.contain(operator is 'and' , 'or' , 'of' , '>' , '<' , '>=' , '<=' , '=' only)) return false else if(policy.contain(threshold gate operator as 'K of (P1, P2, ... PN)' && K is negative integer)) return false else return true automatically take the updated policy to re-encrypt all files encrypted by the beforeupdated policy.

Very Lightweight Proxy Re-Encryption (VL-PRE)

VL-PRE is an extended PRE model that is specifically designed to deliver a very lightweight PRE operation in supporting attribute revocation or policy update in CP-ABE based access control. The process of VL-PRE is divided into three phases: Generate re-encryption key, Update re-encryption key, and Renew re-encryption key. Generally, the proposed three-phase PRE is triggered when there is a case of attribute revocation or policy update. Basically, the proxy transforms ciphertext CT k1 to CT k2 with a re-encryption key RK( rk s1 s2 ) where RK is generated by a proxy server.

Phase 1: Generate re-encryption key:

For the initial phase, it consists of Pre-process, ReKeyGen and ReEnc algorithms which are described as follows. , and Expire_time. First, the SS is used to decrypt the sealed ciphertext (SCT) and the original ciphertext (CT) is derived. The Expire_time is used to indicate the validity of re-encryption key rk s2 . Hence, if the key expires, the owner needs to initiate re-key generation with a new random R vn .

Then, the algorithm outputs a re-encryption key rk s2 (M′, ACP′) that can be used to transform a ciphertext under (M, ACP) to another ciphertext under (M′, ACP′).

• ReEnc(param; rk s2 (M′, ACP′) , CMR function , CT(M, ACP))

CT k2 : The algorithm takes input param, a re-encryption key rk s2 (M′, ACP′) , CombineMatchRemove function CMR, and an original CT(M, ACP). It outputs a re-encrypted ciphertext CT ′ (M′, ACP′). According to the element of rk s2 , we embed the CombineMatchRemove (CMR) function to support the re-encryption process as follows:

(1) Combine pieces of R applied in leaf nodes of a new .

(2) Match R between R vn (RDK aid ) and .

(3) Remove R from R vn (RDK aid ).

Then, the RDK aid is automatically used to decrypt the old ciphertext and the algorithm applies a new ACP′ to re-encrypt the data. Finally, the proxy takes SS to encrypt a new Ciphertext (CT k2 ).

Phase 2: Update re-encryption key:

There are two algorithms for updating re-encryption key.

UpdateACP(R vn ,ACP vn+1 )

! " Data owner applies current random number R vn to encrypt the updated ACP, and the # is obtained and sent to the proxy.

UpdateReEncKey(rk s2,vn ,

! "

) rk s2,vn+1

The proxy runs the algorithm by taking the updated ACP, # to update the current version of re-encryption key, rk s2,vn . The new rk s2,vn+1 is used to re-encrypt the existing ciphertext.

The algorithms help to reduce both computation and communication overhead at both data owner side and proxy since the RDK needs not to be encrypted every time and the information (only the updated ACP) sent out to the proxy is small. Besides, the proxy does not need to fully compute a new re-encryption key upon policy update, it only updates the key instead.

Phase 3: Renew re-encryption key

In this phase, if the current re-encryption key rk s2,vn expires, the algorithms in phase 1 will be run.

Here, the owner needs to initiate re-key generation with a new set of random seeds R vn+1 and updated ACP. Then, re-encryption key generation and ciphertext reencryption are performed by the proxy.

However, re-encryption key renewal is not required to perform instantly when the key expires, it will be executed when there is the next policy update.

Security Model

Our C-CP-ARBE is secure under the random oracle model in the following security game.

Initialization.

Adversary A outputs a challenge access policy ACP C to Challenger C.

2. Setup. C runs CreateAttributeAuthority algorithm and gives a public keys PK to the adversary A. For corrupted authorities S′ A, the challenger sends both the public keys and secret keys to adversary.



In the security point of view of VL-PRE, we use random encryption to secure reencryption key component while our core access control enforcement is based on CP-ABE. The detailed security proof is as presented in the original CP-ABE [START_REF] Bethencourt | Ciphertext-policy Attribute-based Encryption[END_REF].

Policy Update Evaluation

We analyze and evaluate our policy update scheme based on the correctness, accountability, and security requirement.

Correctness: An updated policy must be syntactically correct and users who hold the keys containing a set of attributes satisfying the policy are able to decrypt the data encrypted by an updated policy.

Proof: The syntax of the updating is validated through the CP-ABE tree structure. Hence, attributes updated to AND, OR, K out of N is done at the policy structure. The policy checking for the update is controlled by our policy updating algorithm. The algorithm verifies the syntax of the threshold gates to ensure the correctness of grammar of tree-based model. Also, if the policy is updated with valid attributes (issued trusted AA with PK x.aid ) the users who hold sufficient attributes satisfying a new policy are able to decrypt the file encrypted by a new policy. This correctness is guaranteed by CP-ABE model.

Security: A policy must be updated by the data owner or authorized administrator only in the secure manner and a new policy should not introduce problems for the existing access control.

Proof:

To enable the policies to be securely stored and managed in cloud, we make use a simple CP-ABE tree policy to encrypt the ACP. The policy encryption is simply formed by a set of identity attributes of the data owners and authorized users. Hence, only data owners and authorized users are allowed to access the policy and can use the policy to encrypt the data. Here, the data owner can selectively delegate the policy update function to the users. In addition, our scheme requires data owner's digital signature for executing and committing the update.

Accountability: All policy updating events must be traceable. Proof: When the policy is updated, event log keeps the details of update including login users, update time, and update operations. In addition, the system requires digital signing of the authorized data owner or administrator to commit the update.

Evaluation

Comparison of Policy Update Cost

We analytically compare policy update features and update cost between the C-CP-ARBE, K. Yang et al. scheme [START_REF] Yang | Enabling efficient access control with dynamic policy updating for big data in the cloud[END_REF], and J. Lai et al. scheme [START_REF] Lai | Adaptable Ciphertext-Policy Attribute-based Encryption[END_REF]. 1) O(1) t c = the total number of attributes in the updated ciphertext From Table 2, according to K. Yang et al. scheme, data owner has to update key generation and to update the ciphertext to complete the policy updating process. For the ciphertext update, the data owner needs to compute ciphertext components for new attributes. The entire computation cost is subject to the number of attributes and the type of update operations (i.e. OR, AND) over the access structure. In J. Lai et al. scheme, PRE concept is used to convert the existing ciphertext according to the updated policy. In this scheme, the trapdoor or re-encryption key is generated at key generation authority or at data owner side. This limits the operation with the dependability on the availability of the authority or data owner. In contrast, we delegate the major cost of re-encryption key generation and file re-encryption to the delegated proxy in the cloud.

Our scheme has no limitation for update operations and number attributes involving in the policy. The computation cost for re-encryption is O(1) as the re-encryption is performed once to complete the policy update. In addition, our scheme allows policies to be securely stored in the cloud. This enables flexible and efficient policy management in data outsourcing scenario.

Performance Evaluation

In our experiments, we implement the application service using PHP and Java language which are run on the Apache Sever. The service is run on Intel Xeon, E 562 processor 2.40 GHz. with Ubuntu Linux. We use the Pairing-Based Cryptography library version 0.5.12 to simulate the cryptographic constructs of those two compared schemes. Our core cryptographic library is extended developed from the CP-ABE programming library provided in [18]. On the client (data owner) end, a simulation was run on MacBook Pro Intel Core i5 Dual-core, 2.7GHz.

In the experiment setting, we simulate KeyUpdate and CiphertextUpdate algorithms for K. Yang et al. scheme, while Trapdoor generation and policy update based on PRE are simulated for Lai, J. et al. scheme. For our C-CP-ARBE scheme, the time used for executing policy updating algorithm and processing the VL-PRE are used to measure the total cost of policy update.

To demonstrate the performance improvement, we compare total time used for policy updating and re-encryption between these three approaches. We simulate the policy updating protocols of K. Yang et al. scheme by simulating the key update generation and ciphertext update while J. Lai et al. scheme and our C-CP-ARBE use the PRE strategy. To measure the performance, we vary the number of attributes updated in the given access policy. The access policy contains up to 120 attributes and it is used to encrypt 2-MB file. Then, we measure the total time for the policy update and file re-encryption or ciphertext update used by these three schemes. computation at data owner side is significantly reduced. With our scheme, the data owner only updates at her own machine, while the policy and the subsequent costs (re-encryption key generation and ciphertext re-encryption) are fully outsourced to the delegated proxy. With a small re-encryption key size and key update strategy of VL-PRE, the processing workload performed by the proxy at cloud is also optimized. In J. Lai et al. scheme, even though the PRE is used to transform the ciphertext, the data owner still needs to compute the trapdoor and update the policy before the proxy performs the re-encryption task. Obviously, both C-CP-ARBE and J. Lai et al. scheme do not get significant impact from the number of attributes changed or the operations used in the policy. In contrast, with the ciphertext update strategy of K. Yang et al. scheme, it is very practical to support a small number of updated attributes. However, when the number of updated attributes increases, the processing time sharply increases.

Conclusion

In this paper, we have presented a privacy-preserving CP-ABE based access control model with the capability of policy change management in the data outsourcing scenario. Our core access control policy contains roles, attributes, and privileges logically modeled in a tree-based structure. We introduce our proposed policy updating algorithm and VL-PRE to securely and economically support policy evolution in cloud data access control. VL-PRE uses a small package of re-encryption key generation and relies on key updates strategy instead of key generations. Therefore, it outperforms existing PRE schemes. Finally, we conduct the experiments to evaluate the performance of our proposed policy update scheme. The results reveal that our proposed scheme is efficient and promising for real deployment in supporting policy update for data outsourcing scenario.

For future work, we will conduct larger scale of experiments in real cloud environment and measure the scalability of the proposed system in serving concurrent updates of multiple policies.

Fig. 1 .

 1 Fig. 1. Access control policy of disease diagnosis file

Fig. 2 .Fig. 3 .

 23 Fig. 2. Policy updating algorithm

3 .

 3 Query Phase1: (a) Private key extraction: C runs UserKeyGen on the attribute set S (S uid,aid ) of the corrupted AA and returns UDK to A. (b) Re-encryption key extraction oracle O rk (S, ACP C ): With attribute set S, and an access control policy ACP C , C returns reKeyGen(param; SS, R vn (RDK aid ), (ACP CRvn )) rk s2,vn (M′, ACP′) . to A, where rk s2,vn is a generated reencryption key and (S, SK aid ) UDK. (c) RE-encryption oracle O rk (S, ACP C , CT (M, ACP) ): With the input an attribute set S, an access control policy ACP C , and an original ciphertext CT (M, ACP) , C returns rk s2 (M′, ACP′) ,CT (M, ACP) ) CT R (M′, ACP′) , where reKeyGen(param, SS, R vn (RDK aid ), (ACP' R )) rk s2 (M′, ACP′) , (S, SK aid ) UDK and S|= ACP. (d) Original ciphertext decryption oracle O d2 (S, CT (M, ACP) ). With the input an attribute set S and an original ciphertext CT (M, ACP) ,C returns Decrypt(S, UDK, CT (M, ACP) ) M to A, where (S, SK aid ) UDK and S|= ACP. (e) Re-encrypted ciphertext decryption oracle O d2 (S′, CT R (M′, ACP′) ). With the input an attribute set S' and a re-encrypted ciphertext CT R (M′, ACP′) , C returns Decrypt(S′, UDK′, CT R (M′, ACP′) ) M, where (S', SK aid ) UDK′ and S′|= ACP′. Note that if the ciphertexts queried to oracles O re , O d2 , and O d1 are invalid, C simply outputs a | . 1. Challenge. A outputs two equal length messages M 0 and M 1 to C. C returns CT * (M * ,ACP * ) = Enc(ACP * , M b ) to A, where b ∈{0,1}. 2. Query Phase II: A performs as it did in Phase 1. Guess. A submits a guess bit b′ ∈{0,1}. If b′ = b, A wins. The advantage of A in this game is defined as Pr[b′ = b | μ= 0]= % .

Fig. 4 .

 4 Fig. 4. Comparison of policy update cost As of the Figure 4, compared with K. Yang et al. scheme and J. Lai et al. scheme, our C-CP-ARBE fully outsources the PRE process to the proxy. Thus, the

Table 1 .

 1 Notations used in the C-CP-ARBE Notation Description S uid.aidSet of all attributes issued to user uid and managed by authority aid.

	SK aid	a secret key which belongs to authority aid.
	PK aid	Public key which belongs to authority aid.
	GSK uid	A global secret key of a user uid. GSK is a private key issued by the
		certification authority CA.
	Cert uid	A public key certificate containing user's public key issued by a certi-
		fication authority CA.
	UDK uid.aid	User Decryption key issued by authority aid
	EDK uid.aid	EDK is an encrypted form of a UDK which is encrypted by a user
		public key.
	GRP	Group role parameter is a seed numbers computed from a set of user
		members of the roles.
	SS	Secret seal is a symmetric key created from the AES algorithm togeth-
		er with the GRP.
	ACP	An access control policy used to encrypt the data files.
	SCT	A sealed ciphertext is a ciphertext encrypted with the SS

  1. Pre-process: Data owner (1) chooses random seeds and generates secure random number R and applies random number R vn (tagged with the current version number vn) to encrypt the root decryption key RDK aid generated since the key generation phase. (2) applies R vn to append the attributes in the leaf node of the The algorithm takes input param, secret seal SS, root decryption key encrypted by the Random R vn , R vn (RDK aid ), a new access policy embedded with Random R vn ,

	updated version of access control policy	, and gets the	. Then, data
	owner submits encrypted RDK aid and	as parts of re-encryption key to the
	cloud proxy.
	2. ReKeyGen (param; SS, R vn (RDK aid ), (	), ExpireTime)	rk s2 (M′, ACP′) .