The impact of social cloud reputation and structure on rational computation

Abstract

Rational computation means secure multi-party computation in the presence of rational parties, who care about maximizing their utility. Here the notion of utility denotes payoffs when parties take certain actions in the computation. Therefore rational parties may carefully choose their actions before they interact with others. Traditionally, the main tasks of rational computation is to encourage parties to exchange information with their opponents, even if they do not trust each other. Exchanging information is similar to the action of cooperation towards the view of game theory. Therefore, measures should be taken to encourage parties to cooperate with others in rational computation. In this paper, we assume that rational parties who participate in the computation protocol form a social cloud. Parties in the social cloud may interact within several rounds and in each round, some desirable properties such as reputation may be generated. Parties who have good reputation means they are likely to cooperate with others. The structure of social cloud is not static. Instead, it evolutes when parties complete one round of computation. We mainly discuss the impact of social cloud structure on rational computation. Simulation results show that when the community structure reach to a proper value, parties are more likely to cooperate in the computation protocol. In addition, rational parties can gain optimal utilities.

Keywords

Social cloud reputation community structure Nash equilibrium rational computation

1. Introduction

Social cloud presents relationships among a group of individuals, where they interact for certain purposes. Furthermore, social cloud plays a fundamental part as a medium spreading information, ideas etc. Meanwhile the spreading information affects the behaviours of members in the network. That is, individuals in social cloud are likely to be influenced by decisions of their friends or colleagues. Some research works show that the influences relate to the structure of social cloud. Individuals in the cloud may be divided into several groups and they are more likely to be influenced by individual within the same group. Therefore, we should care more about the influence inside the group other than outside the group. If one social cloud has different group divisions, we regard that the social cloud has different structures. In this paper, we mainly discuss the structure evolution of social clouds and its impact on rational computation protocols.

Rational computation protocols allow rational parties to participate in computation protocols. Recall that in traditional computation protocols, there are altogether four kinds of parties:

Honest parties always honestly follow the protocol.

Semi-honest adversary properly follows the protocol except to keep a record of all its intermediate computations.

Malicious adversary may arbitrarily deviate from the specified program of a two-party protocol.

Covert adversary who may arbitrarily deviate from the protocol specification in an attempt to cheat, but do not wish to be “caught” doing so.

Recently the notion of rational adversary is put forward to reason why parties have incentives to deviate from the protocol. Rational parties behave like neither semi-honest parties nor malicious parties. Instead they choose whether to deviate from the protocol according to their utilities. That is, if deviation may bring a higher utility than following the protocol, then they will deviate from the protocol, and vice versa. Rational parties are a bit like covert adversaries while the latter ones have incentives to cheat without considering their utility. Since parties will inevitably have some profit motives in realities, rational parties can better characterize the incentives for parties in many commercial, political and social settings [9,11].

1.1. Related works

Marks presents the notion of social clouds [8] by means of OpenSocial [30]. Pezzi [31] constructs a social cloud which can develop self-organizing and resilient communities without architectural details. A dynamic social is formed in [7] in order to leverage trust relationships among users. Examples include myExperiment [32] for biologists and nanoHub [21] for the nanoscience community. These systems may coordinate research communities. Social cloud is not similar to P2P network [12,23,24,33]. The reason lies in that the former is based on the encoded relationships. However the latter follows a group-based cloud model other than the completely decentralized model. Social cloud can be also used to support scientific collaboration, such as SETI@home [22] and Folding@home [6] etc. Chard and Caton [7] discuss the problem of measuring social compliance by using reputation in social cloud. Wang et al. [34] relate social cloud and rational computation protocol without considering clouds scenario. They also consider reputation in the utility definition to boost cooperation [35]. However, reputation in [35] is only an assumption there lacking practical application background. In this paper we combine previous results about reputation in order to find incentives for rational parties to cooperate under a practical application background. That is, reputation is a tangible factor derived from social cloud [10].

Game theory can also be used in secret sharing schemes, where rational parties only want to maximize their utilities [2,18,20,28]. Rational secret sharing schemes can be viewed as a kind of rational secure multi-party computation. Ong et al. [29] construct a secret sharing scheme in the presence of an honest minority and a rational majority parties. Lysyanskaya and Triandopoulos [27] study rational secure multi-party computation in the presence of rational parties and malicious adversaries. In [19,25,26], strong physical communications such as physical envelopes and ballot boxes are used to achieve Nash equilibrium or other stronger equilibriums. Recently, Garay et al. [15] discuss the incentives in rational cryptographic protocols by modeling them as a game, which consists of an protocol designer and external attacker. They think the attacker’s incentives is affected by costly corruption.

1.2. Motivations and contributions

In rational computation protocols, parties mainly choose to exchange their information with others according to their utilities. That is, they choose to cooperate with others towards the view of game theory. The decisions for rational parties’ action depend on their utilities. Traditionally, the utility is defined similar to prisoner’s dilemma (PD). However, it is well known that in one shot PD game, cooperation is not dominated strategy for both parties. Therefore, most previous works encourage them to cooperate by repeatedly interacting with each other just like repeated PD game. On the other hand, parties in social cloud form reputation when they repeatedly interact with each other. Furthermore, parties are willing to cooperate with those who have high reputation. If reputation on the basis of social cloud is introduced into rational computation, then parties have incentives to cooperate with each other instead of non-cooperation. Motivated by this, reputation is considered as an important part in rational computation by adding it into the utility definition. We also reconstruct the hybrid protocol in the presence of rational parties with new utility definition. We have done similar works in [35], where rational parties are independent and not belong to any network. Here we revisit this problem in a social cloud scenario on account of the following reasons.

Rational parties are not isolate in rational computation, instead they may belong to a social cloud, where they have a good reputation of cooperating with others or bad reputation of not cooperating. Reputation is considered as an ingredient of utility.

In [35], reputation is equal to the trust value between two parties and it dynamically updates according to their interactions. When parties belong to a social cloud, they may interact with other parities and accumulate their reputation even if he does not interact with the other party in rational computation. This is convenient especially for new comers in rational computation since they can evaluate the reputation coming from the social cloud.

As the reputation dynamically updates in each round, they should compute it continually, which burdens the computation complexity for parties. Here, we can delegate the social cloud to complete this task. That is, when parties need the value of reputation, they only inquire the social cloud and get back a global reputation about this party. The global reputation can prevent parties from cheating locally for a temporary high reputation. In other words, when reputation only derives from the interactions between parties in rational computation, parties therein may pretend to cooperate in order to gain a high reputation. However, when reputation derives from the interactions in social cloud, parties have no incentives to pretend to cooperate since it is not profitable.

In this paper, trust denotes one party’s belief in another capability to cooperate on the basis of its own direct experiences. Reputation denotes one party’s belief in another capability to cooperate on the basis of other parties’ recommendations in the whole network. Although trust and reputation is different with respect to their development, they both evaluate a party’s capability to cooperate. In rational computation, reputation is often used to implement fairness and improve the efficiency for the protocols [1,3,4,34].

Before presenting the hybrid protocol, we first represent the new utility definition. Traditional utility definition is formulated according to that of PD game, which is based on selfishness and exclusivity. Under such utility definition, both parties have no incentives to cooperate since cooperation is a dominated strategy for them. However, mutual cooperation may bring higher utility than mutual fink just like the results in PD game. New utility definition must be introduced to boost mutual cooperation. Therefore, we add reputation as the third part in utility definition. The computation of reputation is completed in the social cloud which greatly releases the computation word for the rational parties. Furthermore, we prove that given proper parameters, mutual cooperation is Nash equilibrium in rational computation. Note that this conclusion solves the problem that no parties will cooperate in rational computation since mutual cooperation is not Nash equilibrium.

Given the utility definition, the hybrid protocol is described as follows. The first stage is the same as that of [1,17]. We modify the second stage such that it adapts to the addition of social cloud. Assume that two parties in rational computation come from the social cloud and their reputation is computed on the social cloud. They compute the utility utilizing the reputation derived from the social cloud before they decide to send shares to his opponent at the beginning of each round in the second stage. In previous works, multiple exchanging rounds are available such that rational parties do not know whether they will obtain enough shares to retrieve the output. The basic idea of multiple rounds lies in two points. One point is that rational parties want to get the output according to the selfishness assumption. So they have incentives to cooperate in each stage for early aborting will lead them to a random output. The other point is that rational parties should abort at the right round, where he can retrieve the output while his opponent cannot, if he wants to reach to the exclusivity assumption. The abortion is possible for parties but with a small probability for the number of rounds is too large to guess the right round with a high probability. Parties compute their expected utility in the second stage, so the utility multiply by a small probability can be neglect when parties successfully guess the right round. Thus parties have no incentives to early abort. Multiple rounds can effectively prevent parties from deviating and achieving desirable result. However, things become different when parties possess reputation. Reputation change the way parties participate in the second stage. Since reputation is one part of the utility, no parties have incentives to deviate from it for mutual cooperation is Nash equilibrium according to Lemma 1. That is, each party will send his share to his opponent at the beginning of each round of the second stage. Now that parties have incentives to exchange their shares in each round, the multiple rounds in the second stage to prevent parties from prematurely abort failed to serve its purpose. That is, there is no need setting a right round in the second stage. Therefore, the hybrid protocol for rational computation should adjust a bit to adapt this change since it seems that multiple rounds are redundant.

For simplicity, the main contributions of this paper are concluded in the following way.

We bridge social cloud and rational computation by utilizing the reputation property. New utility definition are modified adding reputation as an important part such that mutual cooperation is Nash equilibrium on the basis of social cloud. To the best of our knowledge, it is the first time that rational computation is discussed under the background of social cloud. Reputation assigns sufficient justification for parties to cooperate with each other, which is essential to achieve desirable security goals in rational computation.

We introduce dynamic mechanism to boost cooperation in social cloud and find that its structure has impact on action selection for rational parties. We choose Zachary network as an example to further study the optimal structure for social cloud. Simulation results show that the structure of evolution network is related to cooperation level. There exits an optimal structure for a social cloud such that most rational parties have incentives to cooperate.

We propose an efficient rational computation protocol using the above conclusions. The most distinction of our hybrid protocol is that both parties can successfully exchange shares within only one round since mutual cooperation is Nash equilibrium. Note that multiple rounds are necessary in previous works, which decrease the round complexity of the protocol.

1.3. Organization

The rest of paper is organized as follows. Section 2 presents some preliminaries such as the construction of social cloud, the notions of trust and reputation, the definitions of utility and Nash equilibrium. In Section 3 we present the revolution of trust and reputation on social cloud. We also describe the architecture of rational computation and interactions based on social cloud, where parties form their reputation. Then we redefine the utilities considering the effect of greediness except selfishness and exclusivity. Furthermore, we also simulate the social cloud structure on the base of Zachary network and results show that the evolution network can well boost cooperation for parties in the social cloud. Section 4 presents the construction of rational computation protocol based on the theoretical and simulation results such that rational parties have enough incentives to cooperate in the protocol. Section 5 concludes this paper and presents some directions of future works.

2. Preliminaries

2.1. Utility and Nash equilibrium

In the following sections, we only discuss rational computation in the presence of two parties. Let $Γ (P, A, U)$ denote a protocol, where $P = {P_{1}, P_{2}}$ is the set of parties who want to compute function f, $A = A_{1} \times A_{2}$ and $U = {u_{1}, u_{2}}$ . Here, $A_{i} = {Cooperate (C), Fink (F)}$ is a strategy set of party $P_{b}$ , $b \in {1, 2}$ in the following sections, where C denotes that a party participates in the protocol by sending his shares to his opponent F denotes that a party does not participate in the protocol by not sending shares. An outcome of the protocol is a tuple of actions $O = (a_{1}, a_{2}) \in A$ , where $a_{b} \in A_{b}$ . Let $u_{b} (O) : A_{1} \times A_{2} \mapsto R$ be the utility of party $P_{b}$ with the outcome $O \in A$ , $δ_{b} (O) \in {0, 1}$ be a bit denoting whether $P_{b}$ learns the output of the function. Specifically, $δ_{b} (O) = 1$ means that $P_{b}$ learns the output of the function; otherwise, $P_{b}$ does not. Let $num (O) = \sum_{b} δ_{b} (O)$ denote the number of parties who learn the output of the function. For example, $num (O) = 0$ when no parties learn the output of the function, $num (O) = 1$ when either party learns the output of the function and $num (O) = 2$ when both parties learn the output of the function. The utility definitions in most works follow the assumptions of [18].

Selfishness: If $δ_{b} (O) > δ_{b} (O^{'})$ , then $u_{b} (O) > u_{b} (O^{'})$ .

Exclusivity: If $δ_{b} (O) = δ_{b} (O^{'})$ and $num (O) < num (O^{'})$ , then $u_{b} (O) > u_{b} (O^{'})$ .

Note that $O^{'}$ denotes an outcome other than O. Selfishness means that parties want to learn the output of the function. Exclusivity means that the fewer other parties who learn the output of the function, the better for him. The two assumptions will confine the actions for rational parties. Parties should participate in the protocol to get the output of the function according to the selfishness assumption. However, finally they would not participate in the protocol for fear that others will get the output of the function according to the exclusivity assumption. The dilemma exists for rational parties in the rational computation just as that for users in PD game. Therefore, we may borrow the strategies in PD game to solve this problem such that rational parties have incentives to participate in the protocol.

A strategy $σ_{b}$ for $P_{b}$ is a distribution on actions in $A_{b}$ . Following the definitions in game theory, $\vec{σ} \overset{def}{=} (σ_{1}, σ_{2})$ is a strategy vector, where $P_{b}$ adopts strategy $σ_{b}$ . Let $u_{b} (\vec{σ})$ be the expected utility of $P_{b}$ given all parties following the strategy vector $\vec{σ}$ . $(σ_{b}^{'}, {\vec{σ}}_{- b})$ ( $- b \in {1, 2}$ and $- b \neq b$ ) is a strategy vector, where $P_{b}$ adopts $σ_{b}^{'}$ while $P_{- b}$ obeys the specified strategies assigned by $\vec{σ}$ . Note that the strategies in $σ_{b}$ are mixed strategies and the strategies in O are pure strategies. In the following sections, if not specified, we only discuss pure strategies.

Definition 1.
A strategy $\vec{σ}$ induces a Nash equilibrium if for every party $P_{b}$ and any strategy $σ_{b}^{'}$ , it holds that $u_{b} (σ_{b}^{'}, {\vec{σ}}_{- b}) ⩽ u_{b} (\vec{σ}) .$

If $u_{b} (σ_{b}^{'}, {\vec{σ}}_{- b}) < u_{b} (\vec{σ})$ suffices, the strategy $\vec{σ}$ induces a strict Nash equilibrium. A (strict) Nash equilibrium guarantees that no one gains any advantages by deviating from the equilibrium as long as other parties follow it. The function of (strict) Nash equilibrium is to guarantee parties to follow the protocol.
2.2. Social cloud

Social cloud is a scalable computing model, which dynamically share resources among friends in a network. Here we rehearsal the definition of social cloud coming from [7].

A social cloud is a resource and service sharing framework utilizing relationships established between members of a social cloud.

In this paper, we assume that two distrustful rational parties will complete a computation. Those rational parties, denoted as $P_{i}$ and $P_{j}$ , exchange their shares in the social cloud. If $P_{i}$ cooperates with $P_{j}$ and sends his shares to $P_{j}$ , we regarded that $P_{i}$ provides certain service to $P_{j}$ , and vice versa. In rational computation, the process of resource exchanging is symmetric in that shares are randomly generated in the first stage $ShareGen$ . Normally, social clouds regarded the social cloud groups as dynamic Virtual Organizations (VOs) [14]. There are lots of groups and sharing policies among parties in VOs. Furthermore reputation is defined on the basis of the sharing policies. For instance, in this paper, cooperation with others can increase the value of reputation; otherwise decrease the value. A social cloud model is shown in Fig. 1. Zachary network is a classical problem in social cloud, which presents the relationship of university Karate clubs. Wayne Zachary constructs the network according to the internal and external relationships of club members [36]. In this network, club members relate with each other. Although two members such as 1 and 32 belong to different Karate clubs, they still have relations in the whole network. When parties in a social cloud want to share or exchange files with others, they may tend to interact with parties in the same club, while it does not imply that parties in different club have no chance to interact like 1 and 32 in Fig. 1. This may depend on party’s trust and reputation.

Fig. 1.

The social cloud of Zachary network. (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/JHS-150519.)

3. New utility based on social cloud settings

3.1. The evolution of social cloud structure based on reputation

In this paper, we assume that two rational parties are also users in Facebook. Figure 2 describes the architecture of rational computation based on social cloud. Alice and Bob are two users in the Facebook, meanwhile they are also two rational parties who will participate in a computation protocol. The Facebook will initialize their reputation and send the values to social cloud in step (1). Then social cloud updates the reputation of Alice and Bob according to their actions in the social cloud in step (2). Alice and Bob request the reputation values from Facebook and it return the values to them in steps (3) and (4). They then decide whether to participate in the protocol after they compute the utilities in step (5). Finally, the social cloud records their actions, updates the reputation values and send the values to Facebook in step (6).

Fig. 2.

The architecture of rational computation based on social cloud. (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/JHS-150519.)

The interactions between two rational parties in one round of rational computation are presented in Fig. 3.

Before two parties (without loss of generality Alice and Bob) want to execute rational computation protocols, Facebook initializes their trust and reputation and sends them to the social cloud.

The social cloud updates the trust and reputation according to users’ behaviors in the social could. Note that the trust models can be any one in [13] and the reputation is defined as mentioned in Section 1.

Alice and Bob request to the trust (if they are neighbors) or reputation (if they are not neighbors) from the Facebook platform.

Facebook responds with parties’ respective trust or reputation to them.

Both parties compute their utility using these received values and decide whether to cooperate with the other party.

Meanwhile these decisions are observed by the social cloud, which records the actions and updates trust and reputation values. Finally the social cloud sends the updated values to Facebook in case for future request.

This is the end of one round of rational computation. In fact there are several rounds in the whole rational computation protocol just like repeat PD games.

Fig. 3.

The interactions of rational computation based on social cloud.

3.2. New utility definition

Since parties in social cloud have the property of reputation, previous utility assumptions: selfishness and exclusivity cannot well describe the affect of reputation on utility. Therefore, new assumption reflecting reputation must be considered. In this paper, new definition of utility consists of three assumptions. Equations (1)–(3) give the expression of each assumption, respectively. Let $R_{- b}^{b} {(t)}^{O} \in (- 1, 1)$ denote the reputation of $P_{b}$ received from the social cloud with the outcome $O \in A$ in the tth round. Let $τ_{b} (o) = R_{- b}^{b} {(t)}^{o} - R_{- b}^{b} {(t - 1)}^{o}$ denote the increment of reputation. In other words, parties gain positive reputation if they cooperate and negative reputation if they fink. $\begin{array}{rclr} Greediness: \frac{| τ_{b} (o) |}{τ_{b} (o)}, & (1) \\ Selfishness: δ_{b} (o), & (2) \\ Exclusivity: \frac{1}{num (o) + 1} . & (3) \end{array}$

Considering the above factors of each assumption, the extended utility definition under new assumptions is: $u_{b} (O) = ρ_{1} \cdot \frac{| τ_{b} (O) |}{τ_{b} (O)} + ρ_{2} \cdot δ_{b} (O) + \frac{ρ_{3}}{num (O) + 1} .$ (4)

Note that the updating rules of reputations and the new utility definition are common knowledge for all rational parties. For two rational parties, the new utilities with the outcomes are defined as follows:

$(C, C)$ : $(τ_{b} > 0, δ_{b} = 1, num (O) = 2)$ then ${NU}^{+} = u_{b}^{(C, C)} (O) = ρ_{1} + ρ_{2} + \frac{ρ_{3}}{3}$ .

$(C, F)$ : $(τ_{b} > 0, δ_{b} = 0, num (O) = 1)$ then $NU = u_{b}^{(C, F)} (O) = ρ_{1} + \frac{ρ_{3}}{2}$ .

$(F, C)$ : $(τ_{b} < 0, δ_{b} = 1, num (O) = 1)$ then ${NU}^{-} = u_{b}^{(F, C)} (O) = - ρ_{1} + ρ_{2} + \frac{ρ_{3}}{2}$ .

$(F, F)$ : $(τ_{b} < 0, δ_{b} = 0, num (O) = 0)$ then ${NU}^{- -} = u_{b}^{(F, F)} (O) = - ρ_{1} + ρ_{3}$ .

The utility matrix of two rational parties under the new utility definition is given in Table 1.

Table 1

The utility between two pure rational parties

$P_{i}$	$P_{j}$

	$Cooperate (C)$	$Fink (F)$
$Cooperate (C)$	$({NU}^{+}, {NU}^{+})$	$(NU, {NU}^{-})$
$Fink (F)$	$({NU}^{-}, NU)$	$({NU}^{- -}, {NU}^{- -})$

Lemma 1.

Given $4 ρ_{1} > 2 ρ_{2} > ρ_{3} > 0$ , $(C, C)$ is a strict Nash equilibrium for rational parties.

Proof.

The utilities with the corresponding outcomes are: $\begin{array}{rcl} {NU}^{+} = ρ_{1} + ρ_{2} + \frac{ρ_{3}}{3}, NU = ρ_{1} + \frac{ρ_{3}}{2}, \\ {NU}^{-} = - ρ_{1} + ρ_{2} + \frac{ρ_{3}}{2}, {NU}^{- -} = - ρ_{1} + ρ_{3} . \end{array}$

The main target is ${NU}^{+} > NU > {NU}^{-} > {NU}^{- -}$ .

If it suffices ${NU}^{+} > NU$ , then we have $ρ_{2} - \frac{ρ_{3}}{6} > 0$ .

If it suffices $NU > {NU}^{-}$ , then we have $2 ρ_{1} - ρ_{2} > 0$ .

If it suffices ${NU}^{-} > {NU}^{- -}$ , then we have $ρ_{2} - \frac{ρ_{3}}{2} > 0$ .

Therefore, if

ρ_{2} - \frac{ρ_{3}}{2} > 0

and

2 ρ_{1} - ρ_{2} > 0

suffice, then we have

{NU}^{+} > NU > {NU}^{-} > {NU}^{- -}

. That is, given

4 ρ_{1} > 2 ρ_{2} ⩾ ρ_{3} > 0

, it holds that

{NU}^{+} > NU > {NU}^{-} > {NU}^{- -}

. Note that

ρ_{1}

ρ_{2}

ρ_{3}

are positive.

Then we prove that $\vec{σ} = (C, C)$ is strict Nash equilibrium. If the first party (denoted as $P_{b}$ ) and the second party (denoted as $P_{- b}$ ) both follow Nash equilibrium, the strategy profile is $\vec{σ}$ . $P_{b}$ will obtain utility ${NU}^{+}$ in this case. Suppose $P_{b}$ deviates from Nash equilibrium and $P_{- b}$ still abide by the action in Nash equilibrium, the strategy profile turns out to be $\vec{σ^{'}} = (F, C)$ . $P_{b}$ will obtain utility ${NU}^{-}$ in this case. Given $4 ρ_{1} > ρ_{3}$ , it suffices that $u_{b} (\vec{σ}) > u_{b} (\vec{σ^{'}})$ for ${NU}^{+} > {NU}^{-}$ . That is, $P_{b}$ will get an inferior utility if he deviates from Nash equilibrium. Therefore, $P_{b}$ has no incentives to deviate. $P_{- b}$ has no incentives to deviates from Nash equilibrium for the same reason.

So, parties have no incentives to deviate and $\vec{σ} = (C, C)$ is a strict Nash equilibrium for two rational parties. □

3.3. Simulation the structure evolution

Lots of measures are taken in order to make parties cooperate in protocols, such as punishments mechanism, awards mechanism etc. In this paper, we introduce dynamic mechanism to boost cooperation in social clouds. The basic idea is to utilize the results of repeated PD game, where parties may take certain retaliatory measures to avoid their opponents taking the action of defect in PD game. The most simple retaliatory measures is tit-for-tat (TFT) strategy, where parties always adopt the action which is adopted by their opponent. For example, if $P_{i}$ adopts cooperate while $P_{j}$ adopts defect in the current round of repeated PD game, $P_{i}$ will adopt the action of defect in the next round according to TFT strategy. Previous research works show that TFT can effectively prevent the spread of defect and maintain a high cooperation level in social clouds.

Furthermore, we find that the cooperation level is related to the structure of social clouds. That is, parties belong to the same group are more likely to adopt the same action. Therefore, it is necessary to study the impact of community structure to the cooperation level in social clouds. The notion of community structure is similar to community in real life. The social network is divided into several groups. Nodes in the same group have close connection, while have sparse connections with nodes outside the group. Traditionally, there are various methods to divide the social network, such as agglomerative method, divisive method etc. Each method consists of lots of algorithms. In this paper, we choose the Newman algorithm to define the community of the social network and analyze the impact on cooperation level.

Newman et al. introduce a standard value Q to measure the quality community structure. Q is defined as follows. Define a symmetric matrix $e = (e_{i j})$ with $k \times k$ dimension. $e_{i j}$ denotes the ratio of one edge to all edges. Let $Tre = \sum_{i} e_{i j}$ be sum of diagonal elements and $a_{i} = \sum_{i} e_{i j}$ be sum of each column (line) elements. Then the standard value Q can defined as: $Q = \sum_{i} (e_{i j} - a_{i}^{2}) = Tre - ∥ e^{2} ∥,$ where $∥ x ∥$ denotes sum of elements in the matrix. The maximum of Q is 1. The larger the value of Q the clearer the community structure is.

Figure 4 denotes the value of Q and its corresponding tree view in the initial stage. In Fig. 4, it is shown that Q is optimal when community number is 3. That is, parties has clear community structure in this case and are more likely to cooperate. In this paper, we optimize the community structure algorithm by using TFT strategy and present the simulation results in Fig. 5, where n denotes the iteration rounds among parties. Q is optimal when the community number is 3 in Fig. 5(a) and 2 in Fig. 5(b). When the network is divided into 2 community, parties there are more likely to cooperate than the community number is 2. The network after n rounds of iteration is shown in Fig. 6. The community structure is more evident in Fig. 6(b) than in Fig. 6(a).

Fig. 4.

The value of Q and tree view in the initial stage. (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/JHS-150519.)

Fig. 5.

The value of Q and tree view after n rounds of iteration. (a) $n = 100$ ; (b) $n = 500$ . (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/JHS-150519.)

Fig. 6.

The evolution networks. (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/JHS-150519.)

4. The construction of rational computation

In previous works, the adversary may be semi-honest or malicious. However, security under semi-honest adversary is considered as a weak one. While security under malicious adversary is too strict to fit for the reality protocols. Therefore covert adversary is put forwards to model more realistic adversaries. The efficiency of protocols in the presence of covert adversary is between semi-honest adversary and malicious adversary. In this paper, we consider a more realistic kind of parties – rational parties , who are more adapt to economic or political scenarios. That is, if the strategy can maximize his utility then they will adopt it; otherwise they will not adopt it. Computational protocols in the presence of rational parties can achieve many desirable properties like fairness in computation.

In this paper, the rational computation in the presence of rational parties under social clouds is a hybrid protocol $Π^{ShareGen}$ , consisting of two stages. The first stage is the functionality ShareGen and the second stage is a real share–exchange protocol. The first stage is the same to [17], we will re-describe it for completeness.

The second stage is a protocol Π consisting of four phases: initial phase, exchange phase, cheat phase and output phase. The protocol Π is much like the actual protocol in [5]. Here, we use secret sharing schemes as building blocks and achieve informational security in the presence of rational covert adversaries (Ref. [16], Section 7.6).

The first stage functionality ShareGen:

Inputs: ShareGen takes as input values $x_{i}$ from $P_{i}$ , $i, j \in {1, 2}$ . If either input is of no vail, then ShareGen returns ⊥ to parties.

Computation: Compute $f (x_{i}, x_{j})$ and randomly choose shares $s_{i}$ and $s_{j}$ such that $s_{i} \oplus s_{j} = f (x_{i}, x_{j})$ .

Outputs: Send $s_{j}$ to $P_{i}$ and $s_{i}$ to $P_{j}$ .

The second stage protocol Π:

Initial phase: Parties run functionality ShareGen using their specific inputs. $P_{i}$ receives $s_{j}$ and $P_{j}$ receives $s_{i}$ .

Utility computation phase: Before parties take actions to exchange shares with his opponents, they first request Facebook for his opponent’ trust or reputation according to their relationship. For example, to judge whether they are neighbours. Then they compute their utility.

Exchange phase: Parties exchange their shares according to the utility and they also affected by the community structure of the social clouds.

Reputation updating phase: The social clouds update their reputation according to their behaviors, and send trust or reputation values back to Facebook for future use.

Output phase: At the end of the protocol, each party determines his outputs.

Rational parties form and update their reputation in social clouds. Furthermore, their utilities are based on their reputation. That is, a good reputation may bring higher utilities. Therefore, parties have incentives to cooperate in the protocol to gain a good reputation. According to the above ideas, rational parties in our protocol will finally get their outputs.

5. Conclusions

This paper considers the impact of reputation and structure of social clouds on rational computation protocols in social clouds settings. In this paper, we first present the new definition of reputation and evolution of reputation in social clouds and then add reputation as a new part in the utility. Furthermore, we also find that the community structure also has impact on the cooperation level in rational computation. We assume that two rational parties belong to a social cloud and the value of reputation is not only affected by the interactions with the other party in rational computation but also by the interaction with other parties in the social cloud. Previous works only consider the reputation between two parties in rational computation. In this paper, we also consider reputation and structure of social clouds. Finally, we consider a more general setting for both parties. Future works need to stress on more complex scenarios such as the reputation among multiple parties, where parties may collude to forge high reputation. Furthermore, new utility definitions should be explore based on other games like store chain game etc.

Footnotes

Acknowledgements

This work is partially supported by National Natural Science Foundation of China (No. 61202475), Outstanding Young Scientists Foundation Grant of Shandong Province (No. BS2014DX016), PhD Programs Foundation of Ludong University (No. LY2015033), Fujian Provincial Key Laboratory of Network Security and Cryptology Research Fund (Fujian Normal University) (No. 15004).

References

[1]

Asharov,

Canetti and

Hazay, Towards a game theoretic view of secure computation, in: EUROCRYPT 2011,

K.G.

Paterson, ed., Springer, Tallinn, Estonia, 2011, pp. 426–445.

[2]

Asharov and

Lindell, Utility dependence in correct and fair rational secret sharing, in: CRYPTO 2009, Springer, Heidelberg, 2009, pp. 559–576.

[3]

Asharov,

Lindell and

Zarosim, Fair and efficient secure multiparty computation with reputation systems, in: Advances in Cryptology – ASIACRYPT 2013, Springer, Heidelberg, 2013, pp. 201–220.

[4]

Asharov and

Orlandi, Calling out cheaters: Covert security with public verifiability, in: ASIACRYPT 2012, Springer, 2012, pp. 681–698.

[5]

Aumann and

Lindell, Security against covert adversaries: Efficient protocols for realistic adversaries, Journal of Cryptology 23(2) (2010), 281–343.

[6]

Beberg,

Ensign,

Jayachandran,

Khaliq and

Pande, Folding@home: Lessons from eight years of volunteer distributed computing, in: Parallel Distributed Processing (IPDPS 2009), IEEE, 2009, pp. 1–8.

[7]

Chard and

Caton, Social cloud computing: A vision for socially motivated resource sharing, IEEE Transactions on Services Computing 5(4) (2012), 551–563.

[8]

Chard,

Caton,

Rana and

Bubendorfer, Social cloud: Cloud computing in social networks, in: 3rd International Conference on Cloud Computing (CLOUD’10), IEEE Computer Society, Washington, DC, USA, 2010, pp. 99–106.

[9]

Chen,

Li,

Ma,

Tang and

Lou, New algorithms for secure outsourcing of modular exponentiations, in: Computer Security – ESORICS 2012, Springer, 2012, pp. 541–556.

10.

[10]

Chen,

Li and

Susilo, Efficient fair conditional payments for outsourcing computations, IEEE Transactions on Information Forensics and Security 7(6) (2012), 1687–1694.

11.

[11]

Chen,

Wu,

Zhang,

Tian,

Wei,

Lee,

Lee and

Kim, New receipt-free voting scheme using double-trapdoor commitment, Information Sciences 181(8) (2011), 1493–1502.

12.

[12]

Cox and

Noble, Samsara: Honor among thieves in peer-to-peer storage, SIGOPS Operating Systems Review 37 (2003), 120–132.

13.

[13]

Firdhous,

Ghazali and

Hassan, Trust management in cloud computing: A critical review, International Journal on Advances in ICT for Emerging Regions 4(2) (2011), 24–36.

14.

[14]

Foster,

Kesselman and

Tuecke, The anatomy of the grid: Enabling scalable virtual organizations, International Journal of High Performance Computing Applications 15(3) (2001), 200–222.

15.

[15]

Garay,

Katz,

Maurer,

Tackmann and

Zikas, Rational protocol design: Cryptography against incentive-driven adversaries, in: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2013, pp. 648–657.

16.

[16]

Goldreich, Foundations of Cryptography: Volume 2, Cambridge Univ. Press, 2004.

17.

[17]

Groce and

Katz, Fair computation with rational players, in: EUROCRYPT 2012, Springer, 2012, pp. 81–98.

18.

[18]

Halpern and

Teague, Rational secret sharing and multiparty computation: Extended abstract, in: STOC’04: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, ACM, New York, NY, USA, 2004, pp. 623–632.

19.

[19]

Izmalkov,

Micali and

Lepinski, Rational secure computation and ideal mechanism design, in: 46th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, Los Alamitos, 2005, pp. 585–595.

20.

[20]

Katz, Bridging game theory and cryptography: Recent results and future directions, in: 5th Theory of Cryptography Conference TCC 2008, Springer, 2008, pp. 251–272.

21.

[21]

Klimeck,

McLennan,

S.P.

Brophy,

G.B.

AdamsIII and

M.S.

Lundstrom, Nanohub.org: Advancing education and research in nanotechnology, Computing in Science and Engineering 10 (2008), 17–23.

22.

[22]

Korpela,

Werthimer,

Anderson,

Cobb and

Lebofsky, SETI@HOME – Massively distributed computing for SETI, Computing in Science and Engineering 3 (2001), 78–83.

23.

[23]

Lakshman and

Malik, Cassandra: Structured storage system on a P2P network, in: 28th ACM Symposium Principles of Distributed Computing (PODC’09), ACM, New York, NY, USA, 2009, pp. 5–5.

24.

[24]

Lakshman and

Malik, Cassandra: A decentralized structured storage system, ACM SIGOPS Operating Systems Review 44(2) (2010), 35–40.

25.

[25]

Lepinski,

Micali,

Peikert and

Shelat, Completely fair SFE and coalition-safe cheap talk, in: 23rd ACM Symposium Annual on Principles of Distributed Computing, ACM, New York, NY, USA, 2004, pp. 1–10.

26.

[26]

Lepinski,

Micali,

Peikert and

Shelat, Collusion-free protocols, in: 37th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, NY, USA, 2005, pp. 543–552.

27.

[27]

Lysyanskaya and

Triandopoulos, Rationality and adversarial behavior in multi-party computation, in: CRYPTO 2006,

Dwork, ed., Springer, Heidelberg, 2006, pp. 180–197.

28.

[28]

Nojoumian,

Stinson and

Gringer, Unconditional secure social secret sharing scheme, IET Information Security 4(4) (2010), 202–211. (Special Issue: Multi-Agent and Distributed Information Security.)

29.

[29]

S.J.

Ong,

D.C.

Parkes,

Rosen and

Vadhan, Fairness with an honest minority and a rational majority, in: 6th Theory of Cryptography Conference, Springer, 2009, pp. 36–53.

30.

[30]OpenSocial and Gadgets Specification Group, OpenSocial specification v0.9, 2009, available at: http://www.opensocial.org/Technical-Resources/opensocial-spec-v09/OpenSocial-Specification.html.

31.

[31]

Pezzi, Information technology tools for a transition economy, 2009, available at: http://www.socialcloud.net/papers/ITtools.pdf.

32.

[32]

D.D.

Roure,

Goble and

Stevens, The design and realisation of the myExperiment virtual research environment for social sharing of workflows, Future Generation Computer Systems 25(5) (2012), 561–567.

33.

[33]

Rowstron and

Druschel, Storage management and caching in past, a large-scale, persistent peer-to-peer storage utility, SIGOPS Operating Systems Review 35 (2001), 188–201.

34.

[34]

Wang,

Liu,

Wang and

Xu, Social rational secure multi-party computation, Concurrency and Computation: Practice and Experience 26(5) (2013), 1076–1083.

35.

[35]

Wang,

Liu and

Xu, New rational parties relying on reputation, 2013, available at: http://onlinelibrary.wiley.com/doi/10.1002/sec.844/abstract.

36.

[36]

W.W.

Zachary, An information flow model for conflict and fission in small groups, Journal of Anthropological Research 33 (1977), 452–473.