Schemes for multi-party trust computation are presented. The schemes do not make use of a Trusted Authority. The schemes are more ein a completely distributed manner, where each user calculates its trust value privately and independently. Given a community C and its members (users) U1,…,Un, we present computationally secure schemes for trust computation. The first scheme, Accumulated Protocol AP computes the average trust attributed to a specific user, Ut following a trust evaluation request initiated by a user Un. The exact trust values of each queried user are not disclosed to Un. The next scheme, Weighted Accumulated Protocol WAP generates the average weighted trust in a specific user Ut taking into consideration the unrevealed trust that Un has in each user participating in the trust evaluation process. The Public Key Encryption Protocol PKEP outputs a set of the exact trust values given by the users without linking the user that contributed a specific trust value to the trust this user contributed. The obtained vector of trust values assists in removing outliers. Given the set of trust values, the outliers that provide extremely low or high trust values can be removed from the trust evaluation process. We extend our schemes to the case when the initiator, Un, can be compromised by the adversary, and we introduce the Multiple Private Keys and the Weighted protocols (MPKP and MPWP) for computing average unweighted and weighted trust, respectively. Moreover, the Csed Protocol (CEBP) extends the PKEBP in this case. The computation of all our algorithms requires the transmission of O(n) (possibly large) messages.
The online version of this article (doi:10.1186/2196-064X-1-8) contains supplementary material, which is available to authorized users.
Competing interests
The authors declare that they have no competing interests.
Authors’ contributions
All authors read and approved the final manuscript.
Our contribution
The purpose of this paper is to introduce new schemes for decentralized reputation systems. These schemes do not make use of a Trusted Authority to compute the trust in a particular user that is attributed by a community of users. Our objective is to compute trust while preserving user privacy.
We present new efficient schemes for calculating the trust in a specific user by a group of community members upon the request of an initiator. The trust computation is provided in a completely distributed manner, where each user calculates its trust value privately. The user privacy is preserved in a computationally secure manner. The notions of privacy and privately computed trust, are determined in the sense that given an output average trust in a certain user, it is computationally infeasible to reveal the exact trust values in this user, given by community users. We assume a community of users C={U1, U2,…,Un}. Let Un be an initiator. The goal of Un is to get an assessment of the trust in a certain user, Ut by a group consisting of U1, U2,…,Un−1 users from C. The AP calculates the average trust (or the sum of trust levels) in the user Ut (Section ‘Accumulated protocol AP’). The AP protocol is based on a computationally secure homomorphic cryptosystem, e.g., the Paillier cryptosystem [1], which provides a homomorphic encryption of the secure trust levels T1,…,Tn−1 calculated by each user U1, U2,…,Un−1 from C. The AP satisfies the features of the Additive Reputation System [2] and does not take into consideration subjective trust values in the queried users U1, U2,…,Un−1. A decentralized reputation system is defined as additive/non additive [2] if feedback collection, combination, and propagation are implemented in a decentralized way, and if a combination of feedbacks provided by agents is calculated in an additive/non additive manner, respectively. The WAP carries out a non additive trust computation (Section ‘Weighted accumulated protocol WAP’). It outputs the weighted average trust which is based on the trust given by the initiator Un in each C member participating in the feedback. The WAP is an enhanced version of the AP protocol. The AP and WAP protocols cope with a curious adversary and are restricted to the case of an uncompromised initiator, Un. The MPKP and MPWP protocols, introduced in Section ‘Multiple Private Keys Protocol MPKP’, use additional communication to relax the condition that the initiator Un is uncompromised and provide average unweighted and weighted privately computed trust, respectively.
Advertisement
Compared with the recent results in [2] and [3], our schemes have several advantages.
The Private Trust scheme is resistant against either curious or semi-malicious users
The AP and WAP protocols preserve user privacy in a computationally secure manner. Our protocols cope with any number of curious but honest adversarial users. Moreover, the PKEBP (Section ‘Protocols for removal of outliers’) is resistant against semi-malicious users that return false trust values. The PKEBP supports the removal of outliers. The general case, when the initiator, Un, can be compromised by the adversary, is addressed by the MPKP, MPWP and CEBP (Sections ‘Protocols for removal of outliers’ and ‘Multiple Private Keys Protocol MPKP’) protocols. Unlike our model, [2] suggests protocols that are resistant against curious agents who only try to collude in order to reveal private trust information. Moreover, the reputation computation in some of the algorithms in [3] contains a random parameter that reveals information about the reputation range of the queried users.
Low communicational overhead
The proposed schemes require only O(n) size messages to be sent, while the protocols of [2] and [3] require O(n3) communication messages.
No limitations on the number of curious users
The computational security of the proposed schemes does not depend on the number of curious users in the community. Moreover, privacy is preserved regardless of the size of the coalition of curious users. Note that the number of the curious users should be no greater than half of the community users in the model presented in [2].
Advertisement
Background and literature review
The use of homomorphic cryptosystems in general Multiparty Computation (MPC) models is presented in [4]. In [4] it is demonstrated that, given keys for any sufficiently efficient homomorphic cryptosystem, general MPC protocols for n players can be devised such that they are secure against an active adversary who corrupts any minority group of the players. The problem stated and solved in [4] is as follows: given the encryptions of two numbers, say a and b (where each player knows only its input), compute securely an encryption of c=ab. The correctness of the result is verified. The total number of bits sent is O(nkC), where k is a security parameter and C is the size of a Boolean circuit computing the function that should be securely evaluated. An earlier scheme proposed in [5] with the same complexity was only secure for passive adversaries. Earlier protocols had complexity that was at least quadratic in n. Threshold homomorphic encryption is used to achieve the linear communication complexity in [4]. The schemes proposed in [4, 6], and [7] are based on public key infrastructure and use Zero Knowledge proofs (ZKP) as building blocks. When compared to [4, 6], and [7] our schemes privately compute the average unweighted (additive) and weighted (non additive) characteristics, respectively, without using relatively hard-to-implement techniques such as ZKP.
Independently, (though slightly later than [8, 9]), linear communication MPC was presented in [10]. A perfectly secure MPC protocol with linear communication complexity was proposed in [11]. Our model presented herein, (with a semi-honest but curious adversary) copes with at most compromised users that supply arbitrary trust values, while [11] copes (in an information theoretic manner) with up to compromised users (even totally malicious users) with a similar communication overhead, O(n3·ln3). Here, l denotes the total message length.
Following [8, 9], privacy preserving protocols were investigated in [12] and [13]. Protocols for efficient multi-party sum computation (in the semi-honest adversarial model) are proposed in [12] and [13]. The derived protocols are augmented (by applying Zero Knowledge Proofs of plaintext equality and set membership) to handle malicious adversary. The simulation results demonstrate the efficiency of the designed methods. Compared with our results, the most powerful and efficient StR protocol of [12] and [13] is based on a completely connected network topology where each network user is directly connected to all other users. In addition, the schemes of [12] and [13] can be applied in the Additive Reputation Systems, while our schemes are designed also for the Non-Additive Reputation System.
Homomorphic ElGamal encryption is used in [6] as part of a scheme for multi-party private web search with untrusted partners (users). The scheme is based on multi-party computation that protects the privacy of the users with regards to the web search engine and any number of dishonest internal users. The number of sent messages is linear in the number of users (each of the n users sends 4n−4 messages). In order to obtain a secure permutation (of N elements), switches of the Optimized Arbitrary Size Benes network (OAS-Benes) are distributed among a group of n users, and the honest users control at least a large function S(N) of the switches of the OAS-Benes. The proposed MPC protocol is based on the homomorphic threshold n-out of-n ElGamal encryption. Nevertheless, unlike our model, a MPC protocol is based on the computationally expensive honest-verifier ZKP protocol, and the Benez permutation network.
The efficient scheme for the secure two-party computation for “asymmetric settings” in which one of the devices (smart card, mobile device, etc.) is strictly computationally weaker than the other, is introduced in [7]. The workload for one of the parties is minimized in the presented scheme. The proposed protocol satisfies one-round complexity (i.e., a single message is sent in each direction assuming trusted setup).The proposed protocol performs only two-party secure computations, while the number of participants is not bounded in our schemes. Moreover, computationally expensive, Non Interactive Zero-Knowledge Proof techniques, and “extractable hash functions” are used in the scheme of [7].
A number of systematic approaches and corresponding architectures for creating reliable trust and reputation systems have been recently proposed in [14‐18]. The main scope of these papers is the definitions of variety of settings for decentralized trust and reputation systems. A probabilistic approach for constructing computational models of trust and reputation, is presented in [17], where trust and reputation are studied in the scope of various social and scientific disciplines.
The computation models for the reputation systems of [16] support user anonymity by generating a pseudonym for any user, therefore, concealing user identity. In contrast to [16], the main challenge of our approach is to preserve the user anonymity in the computation process of the trust.
One of the common problems stated and discussed in [18] is that most existing reputation systems lack the ability to differentiate dishonest from honest feedback and, therefore, are vulnerable to malicious cooperations of users (peers in P2P systems) who provide dishonest feedback. The dishonest feedback is effectively filtered out in [18] by introducing the factor of feedback similarity between a user (pair) in the collusive group, and a user (peer) outside the group. We propose a different approach for the removal of dishonest users (outliers) by estimating the range of the correct trust values [19].
Two other works that are related to our scheme appear in [2] and [3]. In [2] several privacy and anonymity preserving protocols are suggested for an Additive Reputation System.
The authors state that supporting perfect privacy in decentralized reputation systems is impossible. Nevertheless, they present alternative probabilistic schemes for preserving privacy. A probabilistic “witness selection” method is proposed in [2] in order to reduce the risk of selecting dishonest witnesses. Two schemes are proposed. The first scheme is very efficient in terms of communication overhead, but this scheme is vulnerable to collusion of even two witnesses. The second scheme is more resistant toward curious users, but still is vulnerable to collusion. It is based on a secret splitting scheme. This scheme provides a secure protocol based on the verifiable secret sharing scheme [20] derived from Shamir’s secret sharing scheme [21]. The number of dishonest users is heavily restricted and must be no more than , where n is the number of contributing users. The communication overhead of this scheme is rather high and requires O(n3) messages.
An enhanced model for reputation computation that extends the results of [2] is introduced in [3]. The main enhancement of [2] is that a non additive (weighted) trust and reputation can be computed privately. Three algorithms for computing non additive reputation are proposed in [3]. The algorithms have various degrees of privacy and different levels of protection against adversarial users. These schemes are computationally secure regardless of the number of dishonest users.
The paper [22] (published later than [8, 9]), proposes the distributed Malicious-k-shares protocol, which extends the results of [2] and [3] in the sense that a high majority of users (agents) can find k, k<<n sufficiently trustworthy agents in a set of n−1 users-feedback providers. This protocol is based on homomorphic encryption and Non-Interactive Zero-Knowledge proofs. The Malicious k-shares protocol is applicable in the Additive Reputation System only, while our schemes privately compute also the weighted trust. The techniques, used for removal of outliers, is based on Non-Zero Knowledge Proofs of set-membership and plain-text equality, while the proof preserves that a certain share lies in the correct interval. The proposed protocol requires the exchange of O(n+ log N) messages (where n and N are the number of users in the protocol and environment, respectively), while we use a more computationally effective techniques for removal of outliers exchanging only O(n) messages.
We propose new efficient trust computation schemes that can replace any of the above schemes. Our schemes enable the initiator to compute unweighted (additive) and weighted (non additive) trust with low communication complexity of O(n) (large) messages.
Table 1 summarizes the approaches proposed in this paper, computations that they perform, resistance to the different types of attacks and the crypto building blocks that are used.
Table 1
Summary of the Presented Approaches
Protocol
Computation
Adversarial model
Crypto building blocks
AP
Average trust
Honest but curious
Homomorphic (of Paillier)
WAP
Weighted average trust
Honest but curious
Homomorphic (of Paillier)
PKEBP
Vector of exact trust;
Semi-malicious
Any public key encryption
removal of outliers
(restricted)
CEBP
Vector of exact trust;
Semi-malicious
Commutative (Polhig-Hellman),
removal outliers
(non restricted)
ElGamal
This paper extends the schemes of [9] by introducing the MPKP and MPWP protocols that compute average unweighted and weighted trust in the general case, even when the initiator Un can be compromised by the adversary. The proofs of correctness of the proposed protocols extend the presentations of [9] and [8].
Paper organization
The formal system description appears in Section ‘Research design and methodology’. The computationally resistant (against curious but honest adversary) private trust protocol, AP, is introduced in Section ‘Results and discussion’ (Subsection “Accumulated protocol AP”). The enhanced version of AP, WAP, is presented in Section ‘Results and discussion’ (Subsection “Weighted accumulated protocol WAP”). The (resistant against semi-malicious users) PKEBP and CEBP and the scheme for removing outliers are presented in Section ‘Results and discussion’ (Subsection “Protocols for removal of outliers”). The generalized MPKP protocol and the weighted MPWP protocol are introduced in Section ‘Results and discussion’ (Subsection “Multiple Private Keys Protocol MPKP”). Conclusions appear in Section ‘Conclusions’.
Research design and methodology
The purpose of this paper is to generate new schemes for private trust computation within a community. The contribution of our work is as follows: (a) the trust computation is performed in a completely distributed manner without involving a Trusted Authority. (b) the trust in a particular user within the community is computed privately. The privacy of trust values, held by the community users is preserved subject to standard cryptographic assumptions, when the adversary is computationally bounded. (c) The proposed protocols are resistant to a curious but honest poly-bounded k-listening adversary, Ad[23]. Such an adversary Ad may do the following: Ad may trace all the network links in the system and Ad may compromise up to k users, k< n. We require that an adversary Ad, compromising an intermediate node can only learn the node’s trust values and an adversary Ad, compromising the initiator Un can learn the output of the protocol, namely the average trust. We distinguish between two categories of adversaries: honest but curious adversaries, and semi-malicious adversaries [2]. An honest but curious k-listening adversary follows the protocol by providing correct input. Nevertheless, it might try to learn trust values in different ways, including collusion with, at most, k compromised users. While an honest but curious adversary does not try to modify the correct output of the protocol, a semi-malicious adversary may provide dishonest input in order to bias the average trust value.
Let C=U1,…,Un be a community of users such that each pair of users is connected via an authenticated channel. Assume that the purpose of a user Un from C is to get the unweighted or weighted average trust in a specific user, Ut, evaluated by the community of users. Denote by Ti, i=1.. n, the trust of user Ui in Ut, and by and the unweighted and weighted average trust in Ut, respectively. Here wi=1,2,…,10 is the subjective trust of the initiator Un in Ui in the form of an integer that facilitates our secure computation. In the subsequent work we always assume that wi is an integer in this range. Denote by Mt the message sent by Un to the first member of the community, C.
Our definitions of computational indistinguishability, simulation and private computation follow the definitions of [24]. Informally speaking, two probability ensembles are computationally indistinguishable if no polynomial time, probabilistic algorithm can decide with non-negligible probability if a given input is drawn from the first or the second ensemble. A distributed protocol computes a function fprivately if an adversary cannot obtain any information on the input and output of other parties, beyond what is implicit in the adversary’s own input and output. The way to prove that a protocol is private is to show that there exists a polynomial time, probabilistic simulator that receives as input the same input and output as an adversary and generates a string that is computationally indistinguishable from the whole view of the adversary, including every message that the adversary received in the protocol. Intuitively, the existence of a simulator implies that the adversary learns nothing from the execution of the protocol except its input and output.
Methods
The main tool we use in our schemes is public-key, homomorphic encryption. In such an encryption scheme there is a modulus, M, and an efficiently computable function ϕ that maps a pair of encrypted values (EK(x),EK(y)), where 0≤x,y<M, to a single encrypted element ϕ(EK(x),EK(y))=EK(x+y mod M). In many homomorphic encryption systems the function ϕ is multiplication modulo some integer N. Given a natural number, c, and an encryption, EK(x), it is possible to compute EK(c·x mod M), without knowing the private key. Set β=EK(1) and let the binary representation of c be c=ckck−1…c0. Go over the bits ck,…,c0 in descending order. If cj=0, set β=ϕ(β,β) and if cj=1, set β=ϕ(ϕ(β,β),EK(x)). If ϕ is modular multiplication, this algorithm is identical to standard modular exponentiation.
There are quite a few examples of homomorphic encryption schemes known in the cryptographic literature, including [1, 25‐28]. There are also systems that allow both addition and multiplication of two encrypted plaintexts, e.g., [29] where only a single multiplication is possible for a pair of ciphertexts, and [30]. All of these examples of homomorphic cryptosystems are currently assumed to be semantically secure [26].
Results and discussion
Accumulated protocol AP
The AP protocol may be based on any homomorphic encryption scheme such that the modulus N satisfies . We illustrate the protocol by using the semantically secure Paillier cryptosystem [1]. This cryptosystem possesses a homomorphic property and is based on the Decisional Composite Residuosity assumption. Let p and q be large prime numbers, and N=pq. Let g be some element of . Note that the base, g, should be chosen properly by checking whether gcd(L(gλmodN2),N)=1, where λ=lcm(p−1,q−1), and the L function is defined as . The public key is the (N,g) pair, while the (p,q) pair is the secret private key. The ciphertext, c, for the plaintext message m<N is generated by the sender as c=gmrN mod N2, where r<N is a randomly chosen number. The decryption is performed as at the destination. Our schemes are based on the homomorphic property of the Paillier cryptosystem. Namely, the multiplication of two encrypted plaintexts m1 and m2 is decrypted as the sum m1+m2 mod N of the plaintexts. Thus, E(m1)·E(m2)≡E(m1+m2 mod m) mod N2 and . The AP protocol is described in Algorithm 1.
Assume that the initiator, Un, has generated a pair of its public and private keys as described above, and it has shared its public key with each community user. Then, Un initializes to 1 the single entry trust message Mt and sends it to the first U1 user (lines 1–3). Upon receiving the message, Mt, each node, Ui, encrypts its trust in Ut as . Here, Ti is a secret trust level in Ut and ri is a randomly generated number. The output is accumulated in the accumulated variable A multiplying its current value by the new encrypted Ui−th trust E(Ti) from the i−th entry as A=A·(E(Ti)). Then Ui sends the updated Mt message to the next user, Ui+1. This procedure is repeated until all trust values are accumulated in A (lines 4–9). The final Mt message received by the initiator, Un is . As a result, the Un user decrypts the value accumulated in the M message as the sum of trusts . Thus, the average trust is (Algorithm 1, lines 10–12). Proposition 1 proves that AP is a computationally private protocol to compute the trust of a community in Ut.
Proposition1
Assume that an honest but curious adversary corrupts at most k users out of a community of n users, k<n. Then, AP privately computes Tavr, the average trust in user Ut.
Proof
In order to prove the proposition, we have to prove that for every adversary there exists a simulator that given only the adversary’s input and output, generates a string that is computationally indistinguishable from the adversary’s view in AP. Let denote the set of users that the adversary controls. Let denote the combined view of all users in I. includes the input, , of all users in I, and a sequence of messages received by users in I. A simulator cannot generate the exact sequence , since it does not have the input of uncorrupted users. Instead, the simulator chooses a random value αj for any user Uj∉I, from the distribution of trust values, D. The simulator denotes and computes E(αj) for j=1,…,n−1. The simulator now computes: . Hence, a simulator replaces by .
Assume, in contradiction, that there exists an algorithm DIS that distinguishes between the encryption of partial sums of the correct trust values and the values randomly produced by a simulator. We construct an algorithm, B, that distinguishes between the two sequences E(T1),⋯ E(Tn−1) and E(α1),⋯,E(αk), contradicting the semantic security property of E. The input to algorithm B is a sequence of values E(x1),⋯ E(xn−1) and it attempts to determine whether the values x1,…,xn−1 are equal to the values T1,…,Tn−1 that the users provide, or is a sequence of random values chosen from the distribution D. The algorithm B computes for every ℓ=1,…,k
and provides the encryption of partial sums as input to DIS. B returns as output the same output as DIS. Since the input of DIS is if and only if the input of B is E(T1),…E(Tn−1), we find that B distinguishes between its two possible input distributions with the same probability that DIS distinguishes between its input distributions. □
AP uses O(n) messages each of length O(n).
Weighted accumulated protocol WAP
The Weighted Accumulated WAP protocol, in addition to the AP protocol, generates the weighted average trust in a specific user, Ut, by the users in the community. The WAP protocol is based on an anonymous communications protocol proposed in [31] and on the homomorphic cryptosystem, e.g., Paillier cryptosystem [1]. It is described in Algorithm 2.
The initiator, Un, generates n−1 weights w1,…,wn−1. Each wi value reflects the subjective trust level in user Ui. Un initializes the accumulated variable, A, to 1, encrypts each wi value by means of, e.g., the Paillier cryptosystem [1] as , composes a Trust Vector TV= [ E(w1).. E(wn−1)] and sends the message Mt=(TV,A) to U1. Here, as in the AP case, p, q are large prime numbers which compose the Paillier cryptosystem, N=(p−1)(q−1), and g and h are properly chosen parameters of the Paillier cryptosystem. rn,i is a random degree of h chosen by Un for each Ui from C. Note that the AP protocol is a private case of the WAP protocol where all weights wi are equal to 1.
As in the AP case, the Mt message is received by the community users in the prescribed order. Each Ui user encrypts its weighted trust in Ut as and accumulates it in the accumulated variable A (lines 6–10). Note that multiplying by the random encryption of zero ensures semantic security of the WAP protocol since the user’s output cannot be distinguished from a simulated random string. As a result, the initiator, Un, receives the Mt message and decrypts the value accumulated in A as the weighted sum of trust . Therefore, the average trust is equal to . Proposition 2 proves the privacy of the weighted average trust in the Ut user by the community users in a computationally secure manner.
Proposition2
Assume that an honest but curious adversary corrupts at most k users out of a community of n users, k<n. Then, WAP privately computes wTavr, the average weighted trust in user Ut.
Proof
The proof is similar to the proof of Proposition 1. View of adversary includes the input of compromised users , trust vector TV, and the accumulated variable, A. Each compromised user from I receives and .
A simulator for the adversary simulates as follows. The simulator input is the same as the input of the compromised users. A simulator chooses at random v1,…,vn according to a distribution, W, of weights, and according to a distribution, D, of trust values. Here . Due to the semantic security of the homomorphic cryptosystem, the encrypted random values E(v1),…,E(vn) are indistinguishable from the encrypted correct weights .
The randomization of any Ui−th user output is performed by multiplying its secret by the random encryption of a zero string . Given E(w), the two values E(w)T and E(u), where u is chosen at random from the distribution of wT, can be distinguished since T is chosen from a small domain of trust values. Given E(w), the values are distributed identically to an encryption E(w)T=E(wT mod N). Based on the semantic security of the homomorphic cryptosystem, E(u) and E(wT) cannot be distinguished even given E(w). □
WAP uses O(n) messages each of length O(n).
Protocols for removal of outliers
The protocols for outliers removal are introduced in this section. The Public Key Encryption Based Protocol PKEBP produces a vector of the exact trust values. As a result, the initiator, Un, can evaluate the correct trust range by removing the outliers that provide extremely high or low trust feedback. PKEBP preserves user privacy in a case where the adversary cannot corrupt the initiator and several users at the same time.
The generalized Commutative Encryption Based Protocol (CEBP) relaxes this limitation and privately computes the exact trust values contributed by each community user, even in the case when an adversary can corrupt the initiator and several users at the same time.
Public Key Encryption Based Protocol PKEBP
Denote the encryption algorithm used in this scheme by E and the decryption algorithm by D. Un generates a pair (k,s) of public-private keys. Then Un publishes its decryption public key k, while the private decryption key s is kept secret.
The Public Key Encryption Based Protocol PKEBP is performed in two rounds (Algorithm 3, Figure 1). At the initialization stage Un initializes the n−1-entry vector TV[ 1.. n−1] and sends it to the community of users in the prescribed order in the Mt=(TV[ 1.. n−1]) message (Algorithm 3, lines 1–2 and Figure 1, Round 1).
Figure 1
Public Key Encryption Based ProtocolPKEBP.
×
In the first round, on reception of Mt each user, Ui, encrypts its trust, Ti, by k in the corresponding TV[ i]′s entry as E(Ti), and sends the updated message Mt to the next user (Algorithm 3, lines 3–7).
The second round of the PKEBP protocol is performed when the updated TV[ 1.. n−1] vector returns from Un−1 to the user U1 (see Algorithm 3, lines 8–11 and Figure 1, Round 2). Note that the TV vector does not visit the initiator Un after execution of the first round. Each user, Ui, performs a random permutation of its i−th entry with a randomly chosen ij−th entry during the second round. After that, the newly updated Mt vector-message is sent to the next Ui+1 user (Algorithm 3, lines 8–11).
The result of round 1 is a sequence of encrypted elements (E(T1),…,E(Tn−1)) while the result of round 2 is a sequence . The multi-set T1, …,Tn−1 is identical to the multi-set . The sequence T1,…,Tn−1 is permuted to by a permutation π, which is computed in a distributed manner by all community members (Algorithm 3, line 10). Thus, by applying the decryption procedure, all encrypted trust values T1,…,Tn−1 are revealed (Algorithm 3, lines 12–13). Moreover, the random permutation π performed at the second round preserves the unlinkability of user identities.
Proposition 3 proves the privacy of the PKEBP protocol.
Proposition3
PKEBP performs computationally secure computation of exact private trust values assuming that an adversary cannot corrupt the initiator and several users at the same time.
Proof sketch
Case 1:Un∉I. We argue that PKEBP is private by showing that an adversary that controls a set of compromised users does not learn any information on the trust values of other users. We achieve that by showing a simulator that, given the input of compromised users, can simulate the messages that these users receive as part of the protocol. Therefore, protocol messages do not give users in I any information on users outside of I. Assume that the set I of compromised users includes k members , while the uncompromised users are . The view of users in I includes the input of compromised users and trust vectors TV. Each compromised user from I receives the TV vector with partially permuted entries.
A simulator for the adversary simulates this view as follows. The simulator input is the same as the input of compromised users and it contains the trust values of the compromised users and the set of their permuted indexes . The simulator chooses a random value, , for any user Uℓ∉I from the distribution D of trust values. The simulator sets αℓ=Tℓ and computes E(αj) for ℓ=k+1,…,n. Due to the semantic security of the homomorphic cryptosystem [24, 32], the simulator cannot distinguish between the encryption of the correct trust values and the encryption of simulated random variables, E(αj), of uncompromised users, Uj, chosen from the distribution, D, of trust values.
Case 2: {Un}=I. In this case, the view of Un consists of the TV with the randomly permuted entries. TV includes the sequence of the randomly permuted exact trust values, decrypted by the secret key, s. We prove the privacy of PKEBP by showing a simulator that, given a PKEBP output sequence of the exact trust values, can simulate the TV as Un receives it as a part of the protocol. A simulator for the compromised Un simulates this view as follows. The simulator input is the multi-set T1,…,Tn of the exact trust values that have been decrypted by public key, s. The simulator chooses a random permutation and permutes the received values. Due to the random permutation, π, performed by each community user, the simulator cannot distinguish between the simulated sequence and the correct output of the PKEBP.
As a result, given a multi-set of the exact trust values, Un cannot link these values to the users that contributed them. □
PKEBP uses O(n) messages each of length O(n).
Generating the average trust level in the presence of semi-malicious users is based on the algorithm suggested in [19]. Let us define by U, the multi-set of non corrupted users which provide correct feedback, and by V, the multi-set of all users participating in the trust computation process. According to [19] the following requirement must be satisfied in our model: |V−U|≤J and |V|≥2J for a certain J value. Then the range of the correct trust values, range(U), contains the subset reduceJ(V) of V. Here reduceJ(V) is received from the V multi-set of all (correct and extremely low/high) trust values, by deleting the J smallest and J largest values, respectively.
If an adversary can corrupt the initiator and several users at the same time, a different protocol is required. The generalized Commutative Encryption Based Protocol CEBP is presented in the next subsection.
Commutative Encryption Based Protocol CEBP
The CEBP we propose, uses commutative encryption as a building block. An encryption scheme is commutative if a ciphertext that is encrypted by several keys can be decrypted regardless of the order of decryption keys. Formally, denote the encryption algorithm by E and the decryption algorithm by D. The encryption scheme is commutative if for every plaintext message m and every two keys k1,k2 if then (note that for any encryption scheme . One possible candidate for a commutative encryption scheme is the Pohlig-Hellman scheme [33].
The basic idea of CEBP is for each user to encrypt all the trust values and then decrypt and permute them at the same time so that an adversary cannot associate decrypted trust values with the users that published their encryption. The CEBP protocol is executed in three rounds (Algorithm 4). Each round passes sequentially from the first user Un to the last Un−1.
The first round begins with the initiator, Un choosing and publishing a public key. Every other user selects a symmetric key for a commutative encryption scheme. All the users encrypt their trust values both with their keys and with the public key of Un. Encryption with the initiator’s public key prevents an adversary that does not control the initiator, Un, from obtaining the multi-set of trust values. After the first round, for every i=1,…,n−1, the i-th entry in the trust vector, TV, includes the trust value of Ui encrypted by both the public key of Un and the symmetric key of Ui.
In the second round each user encrypts all entries in TV entries in such a way that at the end of the second round the i-th entry is the trust value of Ui encrypted by the keys of U1,U2,…,Un. Finally, in the third round, for every i=1,…,n−1, Ui decrypts every entry using its own symmetric key and randomly permutes the entries of TV. At the end of round 3 the trust vector contains all the trust values, encrypted by the public key of Un and permuted. By decrypting all the entries in TV, Un obtains the vector of all trust values.
We use El-Gamal encryption [34] as the initiator’s public key scheme. The symmetric scheme for users U1,…,Un−1 is Pohlig-Hellman. Both the Pohlig-Hellman and the El-Gamal schemes are implemented over the same group, which is defined as follows. Let p be a large prime, such that p−1 has a large prime factor, q. Let be an element of order q in . In a Pohlig-Hellman scheme, the key is a pair such that ab≡1 mod (p−1). A plaintext is encrypted by c≡ma mod p and a ciphertext is decrypted by m≡cb mod p. In an El-Gamal scheme, the private key is a∈{0,…,q−1}, the public key is ga mod p and a plaintext is encrypted by the pair (gb mod p,gab·m mod p). We refer to the two parts of an El-Gamal encryption as two components.
By using Pohlig-Hellman and El-Gamal encryption schemes over the same group we ensure that the security of CEBP can be reduced to the hardness of the Decisional Diffie-Hellman (DDH) problem [35]. The DDH problem is to distinguish between the two ensembles (gx mod p,gy mod p,gz mod p) and (gx mod p,gy mod p,gxy mod p). The hardness assumption of DDH is that no probabilistic, polynomial time algorithm can distinguish between these two probability ensembles with non-negligible probability.
The details of the protocol follow.
The initiator begins round 1 (lines 1–9) by choosing parameters for El-Gamal encryption and distributes its public key . Every other user Ui (i=1,…,n−1) chooses four random and independent pairs of Pohlig-Hellman keys , , , . Ui uses the El-Gamal public key to encrypt its trust value, Ti. The result is , where Ui chooses ki randomly in the range 0,…,q−1. Ui proceeds to encrypt the El-Gamal encryption of Ti with its Pohlig-Hellman keys. Each of the two components of the El-Gamal encryption is encrypted by one distinct Pohlig-Hellman key. The result is
Ui completes the round by publishing this value in TV[ i]. We think of TV[ i] as having two components, TV[ i,1] and TV[ i,2]. Ui stores in TV[ i,1] and stores in TV[ i,2].
In round 2, every user, Ui, i=1,…,n−1 makes sure that every entry in TV[ ] is encrypted with all four of its Pohlig-Hellman encryption keys (where two of the keys are used to encrypt the left component and two are used to encrypt the right component). Thus, Ui encrypts TV[ i] with and and encrypts TV[ j] for any j≠i with , and . After the second round the entry TV[ i] holds the value:
In round 3, the users both decrypt and permute all the values. Each user decrypts all values using both its pairs of Pohlig-Hellman keys (lines 20–27) and then randomly permutes the resulting vector of values. Due to the commutative property of the scheme, the initiator, Un, holds all the trust values at the end of round 3. However, the random permutation each user applies to the encrypted values in round 3 ensures that even if only a pair of users is not compromised, the decrypted trust values are randomly permuted in relation to their associated users.
Proposition 4
Assume that the DDH problem is hard and assume that an honest but curious adversary corrupts at most k users out of a community of n users, k≤n. If the trust values of all the users are in the sub-group generated by g, then, CEBP privately computes the set of all trust values of community users.
Proof sketch
If the adversary controls at least n−1 users, including the initiator, then the protocol is trivially private, since the output reveals the exact trust values of every user, and thus any protocol does not add information. If the adversary does not control the initiator then the protocol is private because all trust values are encrypted by the initiator’s public key throughout the protocol. Since the El-Gamal encryption scheme is semantically secure, given the hardness of DDH problem, it is easy to argue privacy.
Therefore, the most interesting case is when k≤n−2 and the adversary controls the initiator. To prove privacy we define a simulator that is given the adversary’s input and output (which includes the set of trust values) and simulates the adversary’s view of protocol messages.
Each message in our protocol consists of the trust vector TV. Each entry in this vector is a pair of elements in . Thus, the whole view of the adversary can be written as e1,…,em, where for every i=1,…,m. The value of m is at most O(n2) because the number of elements in TV is 2(n−1) and the adversary receives a message with TV in it at most n−2 times for each of the three rounds.
Note that each element ei is obtained by raising g to a power ηi that depends on the input and random coin tosses of each participant. The simulator generates a simulated view f1,…,fm as follows. If ηi is determined by the input and coin tosses of the adversary, then the simulator who has access to this input and coin tosses sets fi=ei. However, if ηi is generated at least partially by an uncorrupted node then the simulator independently chooses a random element ζi∈{0,…,q−1} and sets .
To prove that the simulator’s view is computationally indistinguishable from the real-world view, we construct a series of hybrid ensembles H0,…,Hm, such that H0 is the real world view e1,…,em and for every i=1,…,m we define Hi=△f1,…,fi,ei+1,…,fm. Essentially, Hm is the view of the simulator.
We can show that for every i, if Hi can be computationally distinguished from Hi+1 then the DDH assumption is false. Since we assume that DDH is a hard problem we have that Hi and Hi+1 are computationally indistinguishable and since m is of polynomial size in n, we have that H0 is indistinguishable from Hm, completing the proof. □
The protocol requires O(n) messages, each of length O(n) and the computation complexity for each participant in the scheme is O(n).
Multiple Private Keys Protocol MPKP
The AP and WAP protocols introduced in the previous sections carry out private trust computation assuming that the initiator Un is not compromised and does not share its private key with other users. In the rest of this work assume that any community user, including Un, may be compromised by a poly-bounded k-listening curious adversary.
The generalized Multiple Private Keys Protocol MPKP copes with this problem and outputs the average trust. The idea of the MPKP protocol is as follows. During the initialization stage the Un user initializes all entries of trust vector, TV, and accumulated vector, AV, to 1, sets the accumulated variable A to 1, and sends the Mt=(TV,AV,A) message to the first community user U1 as in the previous protocols. During the first round of the MPKP protocol execution each user, Ui, randomly fragments its secret trust, Ti, to a sum of n−1 shares, encrypts the corresponding share by the public key of each Uj, j=1.. n−1 user and accumulates its encrypted shares (multiplying each of them with the corresponding entries) in the accumulated vector, AV. After execution of the first round, the updated AV vector does not return to the initiator Un. The AV vector visits each community user, while each Ui opens the i−th entry (that is encrypted by Ui−th public key) revealing a sum of decrypted shares, encrypts this sum by the public key of the initiator Un, accumulates this sum in the accumulated variable,A, and deletes the i−th entry of the AV vector.
A detailed description of the MPKP protocol follows. Assume that each community user, Ui, i=1.. n−1 generates its personal pair of private and public keys. Denote by Ei and Di the encryption and decryption algorithms produced by Ui. The private key, , is kept secret, while the public key, , is shared with all other users U1,…,Ui−1, Ui+1…Un. As in the previous schemes, the cryptosystem must be homomorphic. An additional requirement is that the homomorphism modulus, m, must be identical for all users. One possibility is to use the Benaloh cryptosystem [28, 36] for which many different key pairs are possible for every homomorphism modulus. The system works as follows. Select two large primes, p,q, such that: N=△pq, m|p−1, and , which implies that m is odd. The density of such primes along appropriate arithmetic sequences is large enough to ensure efficient generation of multiple p,q (see [36] for details). Select such that yϕ(N)/m≢1 mod N. The public key is (N,y), and encryption of is performed by choosing a random and sending yMum mod N. In order to decrypt, the holder of the secret key computes at a preprocessing stage TM=△yMϕ(N)/m mod N for every . It should be noted that m is small enough such that m exponentiations can be performed. Decryption of z is performed by computing zϕ(N)/n mod N and finding the unique TM to which it is equal.
The MPKP is performed in two rounds (Algorithm 5). The initialization procedure is shown in lines 1–4. The first round is the accumulation round, where all users share their secret trust Ti values with other users. Upon reception of a message, Mt, each user, Ui, proceeds as follows: (a) Ui chooses uniformly at random such that ; (b) Ui encrypts each by the public key of the Uj user and multiplies it by the current value stored in j−th entry of AV. As a result, the output AV vector contains the accumulated product in each j−th entry (lines 5–12).
In the second round, on reception of message Mt, each user, Ui, decrypts the Mt message and decrypts the corresponding i−th entry by its private key, , computes the sum, encrypts it by the Un′s public key, , as , accumulates this sum in the accumulated variable, A, deletes the i−th entry and sends the updated TV vector to the next Ui+1 user. Note that the partial sum that Ui decrypts reveals no information about correct trust values. As a result of the second round the initiator Un receives (lines 13–19). Un decrypts , and computes the sum of trusts as . Actually, the average trust Tavr is equal to (lines 20–22). Proposition 4 states the privacy of the MPKP protocol. The communication complexity of the MPKP protocol is O(n) messages, each of length O(n).
Proposition 5
MPKP performs computationally secure computation of the exact private trust values in the Additive Reputation System. No restriction is imposed on the initiator Un.
The last introduced protocol is the MPWP for the weighted average trust computation. The idea of the MPWP is as follows. During the initialization stage the Un user generates a vector, TV, such that each i−th entry contains the Ui−th weight wi encrypted by the Un−th public key. Un sends TV and a (n−1)×(n−1) matrix, SM, with all entries initialized to 1 to the first community user, U1, as in the previous protocols. During the first round of the MPWP execution each Ui computes its encrypted weight in the power of its secret trust , multiplies it by a randomly chosen number (bias) zi, and accumulates the product in the accumulated entry (by multiplying the entry by the obtained result). In addition, Ui fragments its bias, zi, into n−1 shares, encrypts each j−th share by the public key of Uj, and inserts it in the j−th location of i−th matrix row. At the end of the first round Un decrypts the total biased weighted trust. The total random bias is removed during the second round of the MPWP execution when each Uj decrypts the entries of j−th matrix column, encrypts the sum of these values by the public key of the initiator, accumulates it in an accumulation variable, A, and deletes the j−th column.
The details follow. The initiator, Un, starts the first round by generating the encryption of the n−1 entries trust vector, TV= [ En(w1).. En(wn−1)]. Note, that each weight wi is encrypted by the Un−th public key, . In addition, Un initializes to 1 each entry of the (n−1)×(n−1) matrix of shares SM. The message sent by Un to the community users is M=(TV,SM). Upon the TV vector reception each Ui user proceeds as follows: (a) Ui computes . Here zi is a randomly generated by Ui number that provides the secret bias. (b) Ui accumulates its encrypted weighted trust in the accumulated variable A by setting . After that, the i−th entry of TV is deleted. (c) Ui shares zi in the i−th row of the SM shares matrix as . At the end of the first round Un receives the TV[ ] entry that is equal to the biased product , encrypted by its public key, and the updated shares matrix SM while . Actually, the decryption procedure applied on the TV[] vector outputs the decrypted sum . A second round is performed in order to subtract the random bias from the correct weighted average trust wTavr. The second round of the MPWP is identical to the corresponding round of the MPKP. Upon reception of the SM matrix each user, Ui, decrypts the corresponding i−th column , encrypted by all community users by Ui−th public key, . Each Ui, i=1.. n−1 computes the sum of the partial shares , encrypts it by the Un−th public key, , and accumulates it in the accumulated variable A. After that, i−thSM′s column SM[ ][ i] is deleted. As a result of the second round, the initiator, Un, receives the accumulated variable, . The encrypted bias, BT, is decrypted as .
Finally, the weighted average trust wTavr is equal to wTavr=TV−A. The private trust computation carried out by the MPKP and the MPWP protocols is preserved in the computationally secure manner due to the following reasons:
(a)
Each community user, Ui, fragments its trust, Ti, randomly into n−1 shares (Algorithm 5, lines 6–8).
(b)
Each encrypted by Ui by the Uj−th public key, , shared with each Uj,j=1,…,n−1 user and accumulated in the TV vector, reveals no information about the exact Ti value to Uj (lines 9–14).
(c)
The decryption performed by each Ui,i=1,…,n−1 by its private key, , at the second round, outputs the sum of the partial shares, of all community users. In essence, the value reveals no information about the secret trust values T1,…,Ti−1, Ti+1,…,Tn−1.
(d)
The encryption of the partial shares sum performed by each Ui with the initiator Un public key and accumulated in A, can be decrypted by Un only.
(e)
Assume a coalition of at most k<n curious adversarial users, possibly including the initiator Un. Then the exact trust values revealed by the coalition, are the coalition members trust only. The privacy of the uncorrupted users is preserved by the homomorphic encryption scheme which generates for each user its secret private key, and by the random fragmentation of the secret trust.
In MPWP, O(n) messages of length O(n2) are sent.
Conclusions
We derived a number of schemes for the private computation of trust in a given user by a community of users. Trust computation is performed in a fully distributed manner without involving a Trusted Authority. The proposed AP and WAP protocols are computationally secure, under the assumption of an uncompromised initiator, Un. The AP and WAP protocols compute the average unweighted and weighted trust, respectively. The generalized MPKP and MPWP protocols relax the assumption that Un is non-compromised. They carry out the private unweighted and weighted trust computation, respectively, without limitations imposed on Un. The number of messages sent in the proposed protocols is O(n) (large) messages.
The PKEBP and CEBP for the removal of outliers are presented as well.The protocols, introduced and analyzed in this paper, may be efficiently applied in the fully distributed environment without any trusted authority. Compared with other models, our schemes privately compute trust values with low communication overhead of O(n) (large) messages in the simplified ring network topology. The schemes may be applied to complete topology systems when all network users are connected by direct links. The schemes may be attractive in the case when sending the linear number (O(n)) of large messages is better than sending a substantially larger number (O(n3)) of possibly smaller messages. Moreover, the outliers removal (performed by the CEBP protocol) may be efficiently performed by the computationally restricted users when there are no resources for generating computationally expensive Interactive and Non Interactive Zero Knowledge Proofs. The schemes proposed in this paper are not restricted to trust computation. They may be extended to other models that compute privately sensitive information with only O(n) messages.
In a case where the trust is represented by several values rather then a single value, one can apply our techniques to each such value independently.
Acknowledgments
Supported by Deutsche Telekom Laboratories at Ben-Gurion University of the Negev, Israel, Rita Altura Trust Chair in Computer Sciences, ICT Programme of the European Union under contract number FP7-215270 (FRONTS), Lynne and William Frankel Center for Computer Sciences, and the internal research program of the Sami Shamoon College of Engineering. The paper is a full version of two extended abstracts each describing a different part of the results [8, 9].
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Competing interests
The authors declare that they have no competing interests.
Authors’ contributions
All authors read and approved the final manuscript.
