# Outsourcing Hierarchical Threshold Secret Sharing Scheme Based on Reputation

Authors: En Zhang; Jun-Zhe Zhu; Gong-Li Li; Jian Chang; Yu Li
Journal: Security and Communication Networks
 (2019)

---

## Abstract

Secret sharing is a basic tool in modern communication, which protects privacy and provides information security. Among the secret sharing schemes, fairness is a vital and desirable property. To achieve fairness, the existing secret sharing schemes either require a trusted third party or the execution of a multiround protocol, which are impractical. Moreover, the classic scheme requires expensive computing in the secret verification phase. In this work, we provide an outsourcing hierarchical threshold secret sharing (HTSS) protocol based on reputation. In the scheme, participants from different levels can fairly reconstruct the secret, and the protocol only needs to run for one round. A cloud service provider (CSP) uses powerful computing resources to help participants complete homomorphic encryption and complex verification operations, and the CSP cannot be aware of any valuable information. The participants can obtain the secret with a small number of operations. To avoid collusion, we suppose that participants have their own reputation value, and they are punished or rewarded according to their behavior. The reputation value of a participant who deviates from the protocol will decrease; therefore, the participant will choose a cooperative strategy to obtain better payoffs. Lastly, our scheme is proved to be secure, and experiments indicate that our scheme is feasible and efficient.


---

## Body

## 1. Introduction

Secret sharing is an important cryptographic primitive and has a widespread application in secure multiparty computation, image encryption, and attribute-based encryption. Secret sharing, an idea proposed by Shamir [1] and Blakley [2], allows a dealer to distribute different shares among a set of participants. The method guarantees any authorized subsets of t or more participants can reconstruct the secret. However, it is hard to guarantee that the dealer and participants are absolutely honest. To address this problem, verifiable secret sharing (VSS) schemes [3–5] guarantee additionally any cheating behavior can be detected, which can check the validity of shares. Subsequently, a series of protocols [6–9] is studied sharing multiple secrets at a time. In these schemes, participants only need to submit a pseudoshare rather than a real share to recover multiple secrets. Secret sharing has become an important research topic, and a large quantity of studies have been proposed. A multistage secret sharing scheme was introduced by Pilaram and Eghlidos [10], which was based on Lattice and could resist quantum attacks. Zhang et al. [11] presented an outsourcing secret sharing scheme based on homomorphic encryption, but the scheme could not effectively resist collusion. Recently, secret sharing has stronger privacy requirements. Although information about shares is leaked, the adversary still has no access to information about secret. Fehr and Yuan [12] constructed a robust secret sharing scheme with security against a rushing adversary. Benhamouda et al. studied leakage resilience of the MPC protocol [13]. A nonmalleable scheme concerning secret sharing was presented by Goyal and Kumar [14]. The scheme can resist adversary of someone who arbitrarily tampers with shares. Later, Goyal and Kumar [15] proposed nonmalleable secret sharing schemes for more general access structures.In real life, everyone is not exactly equal in status or privileges. It would be an endless task to cite such living examples. For example, in a research and development department of a company, the shares of the private key of confidential files may be distributed among employees. Some are accountants, and some are department managers. The company’s policy requires 3 employees to be in attendance at the same time to open confidential files, but at least one of them must be a department manager. Such a setting requires a special secret sharing method. Therefore, the concept of HTSS was proposed. Tassa [16] introduced the structure of HTSS. In the scheme, a secret is shared among participants that are divided into different levels. Only participants who meet a certain level can reconstruct the secret. If the specific level is not met, the participants learn nothing about the secret. Later, Traverso et al. [17] proposed an HTSS scheme that supports verifiability and dynamics, which can add, remove, and renew shares. Recently, Mohamed and Arockia [18] introduced an HTSS scheme for color images. Bhattacharjee et al. [19] presented a hierarchical image scheme for bandwidth efficient transmission and offered a great degree of robustness in compressed sensing.In the classic secret sharing scheme, fairness is a desirable property that guarantees each participant can gain the secret simultaneously. For the purpose of the goal, Tompa and Woll [20] firstly introduced a fair reconstruction scheme. The main idea of the scheme is to hide the real secret value, and the cheater has to guess the secret location. However, it is impractical for all participants to release their shares synchronously. A novel fair threshold scheme was presented by Tian et al. [21]. In the work, the real secret value was hidden in the sequence for the sake of decreasing the probability of the cheater achieving a successful guess. Combining the approach with game theory, Halpern and Teague [22] introduced a rational cryptographic protocol. In the rational scheme, the participants are rational players whose behavior aims are to maximize their profit. To achieve fairness, existing schemes require either a trusted third party or the execution of a multiround protocol, which are impractical.The reputation system plays a key role in the online community, such as auction markets, trusted content delivery, and e-commerce. By publicizing the reputation value, participants can choose trusted peers with whom to cooperate. Reputation systems can effectively combat selfish, dishonest, and malicious behavior. Xiong and Liu [23] presented a detailed explanation. Combining with reputation systems, Zhang et al. [24] proposed a PSI protocol against social rational participants in which the parties who defect the PSI protocol will be penalized. Nojoumian and Stinson [25] introduced a socio-rational protocol. In this paper, participants are invited to execute an unknown number of protocols based on their reputation. Recently, a series of works were proposed. Litos and Zindros [26] created a reputation network in which the reputation value is quantifiable and expressed in monetary terms. Clark et al. [27] presented a dynamic, privacy-preserving decentralized reputation system.At present, the vast amount of data stored in the cloud has led to explosive growth in the data volume. People are entering the era of big data, and everything will be digitized. According to the statistics of the Millet cloud storage service, the number of customers at the end of 2015 reached 97 million, with 46.5 billion photos and 504 million videos. It is estimated that by 2020, the global data volume will reach 44 ZB. At the same time, cloud outsourcing computing is also very common. More and more devices with poor computing power such as smart phones, pads, and sensors can outsource computing to a CSP with powerful computing power so that users can enjoy unlimited computing resources. However, in the face of outsourcing computing, users are reluctant to disclose their personal sensitive data. Therefore, we need to find a practical approach to implement an HTSS scheme.


### 1.1. Our Contribution

We provide an outsourcing HTSS protocol based on reputation, as is demonstrated in Figure1. In this protocol, secret shares are distributed to different levels of participants. The participants can obtain the secret fairly with a small quantity of operations. Expensive computing is outsourced to a CSP, and the CSP can gain nothing about the secret. Moreover, the reputation system can effectively prevent participants from colluding with the server. Compared with previous schemes, our scheme has the following advantages:(1)
The participants are not required to always be online, which avoids multiple interactions between the participants and the server.(2)
The protocol could accurately check the malicious behavior of the participants or the server.(3)
Expensive computing is outsourced to a CSP. With the CSP’s computing power, the CSP can execute homomorphic encryption and complex verification operations, and the server can gain nothing about the secret.(4)
Through a combination with the reputation system, we design a social game model for the hierarchical secret sharing scheme, which can resist collusion between the participant and the server. Assuming that participants have their own reputation value, they are punished or rewarded according to their behavior. Moreover, all participants are rational players whose behavior aims are to maximize their profit. The reputation value of a participant deviating from the protocol will decrease. In our model, a participant who chooses a cooperative strategy can obtain better payoffs. Therefore, each participant will honestly abide by the protocol.Figure 1
Outsourcing the hierarchical secret sharing scheme based on reputation.We formally describe preliminaries in Section2. We construct an outsourcing HTSS scheme based on reputation in Section 3. We indicate the security of the scheme in Section 4 and compare our scheme with previous schemes in Section 5. Finally, the conclusion of our paper is presented in Section 6.


## 1.1. Our Contribution

We provide an outsourcing HTSS protocol based on reputation, as is demonstrated in Figure1. In this protocol, secret shares are distributed to different levels of participants. The participants can obtain the secret fairly with a small quantity of operations. Expensive computing is outsourced to a CSP, and the CSP can gain nothing about the secret. Moreover, the reputation system can effectively prevent participants from colluding with the server. Compared with previous schemes, our scheme has the following advantages:(1)
The participants are not required to always be online, which avoids multiple interactions between the participants and the server.(2)
The protocol could accurately check the malicious behavior of the participants or the server.(3)
Expensive computing is outsourced to a CSP. With the CSP’s computing power, the CSP can execute homomorphic encryption and complex verification operations, and the server can gain nothing about the secret.(4)
Through a combination with the reputation system, we design a social game model for the hierarchical secret sharing scheme, which can resist collusion between the participant and the server. Assuming that participants have their own reputation value, they are punished or rewarded according to their behavior. Moreover, all participants are rational players whose behavior aims are to maximize their profit. The reputation value of a participant deviating from the protocol will decrease. In our model, a participant who chooses a cooperative strategy can obtain better payoffs. Therefore, each participant will honestly abide by the protocol.Figure 1
Outsourcing the hierarchical secret sharing scheme based on reputation.We formally describe preliminaries in Section2. We construct an outsourcing HTSS scheme based on reputation in Section 3. We indicate the security of the scheme in Section 4 and compare our scheme with previous schemes in Section 5. Finally, the conclusion of our paper is presented in Section 6.


## 2. Preliminary

### 2.1. Secret Sharing Homomorphisms

Benaloh [28] described the homomorphic property of secret sharing. For example, consider two secrets k1 and k2, which are shared by polynomials φx and ϕx. If we add the shares fi=φi+ϕi,1≤i≤n, each of fi can be viewed as a subshare of secret k1+k2. Suppose that K is defined as the secret domain, and Σ is defined as the share domain. A set of functions FI:Σt⟶K can be determined, where I⊆1,2,…,n and I=t. Given any set of t values ki1,…,kit, the following equation can define the secret k:(1)k=FIki1,…,kit,forI=i1,…,it.Definition 1.
Suppose⊕ and ⊗ are two operations on the secret domain K and share domain Σ, respectively. There are(2)k=FIki1,…,kit,k′=FIki1′,…,kit′,then,(3)k⊕k′=FIki1⊗ki1′,…,kit⊗kit′.
From the above definition, Shamir’s polynomial is+,+-homomorphic, which implies that the sum of the shares is equivalent to shares of the sum.


### 2.2. Tassa’st,n Hierarchical Threshold Scheme

In HTSS, a set of participantsP=P1,…,Pn are split into multiple levels U0,U1,…,Um, where U0 is the highest level and Um is the lowest level. For all 0≤i<j≤m, there is P=∪i=0mUi, where Ui∩Uj=∅. Supposing that nh is the number of participants associated with level Uh, we can obtain n=P=∑h=0mnh. Then, we define a threshold th associated with level Uh, for h=0,…,m, which satisfies 0<t0<…<tm. In addition, we set t=thh=0m, t=tm, and t−1=0. Therefore, the t,n hierarchical access structure Γ is described as follows:(4)Γ=A⊂P:A∩⋃j=0iUj≥ti,∀i∈0,1,…,m.Next, we describe in detail how the Birkhoff interpolation reconstructs the secret.The Birkhoff interpolation problem is to find a polynomialFx=∑r=0t−1arxr∈ℝt−1x that satisfies the equalities Fi=σi,j, where Fji is the j-th derivative of Fx at position i. Suppose that an authorized subset R∈Γ⊂P can reconstruct the secret. E associated with R is a matrix with binary entries. If there is participant pi,j with share σi,j, then the entry ei,j is set to “1”. In addition, we set φ=1,x,…,xt=ω0,ω1,…,ωt−1 and define ωrj as the j-th derivative of ωr. The matrix AE,X,φ can be expressed as follows:(5)AE,X,φ=ω0j1i1ω1j1i1⋯ωt−1j1i1ω0j2i2ω1j2i2⋯ωt−1j2i2⋮⋮⋮⋮ω0jrirω1jrir⋯ωt−1jrir,wherer=0,…,t−1.The polynomialFx can be reconstructed:(6)Fx=∑r=0t−1AE,X,φrAE,X,φxr,in which we can obtain AE,X,φr by replacing the r+1-th column with the shares σi,j in the lexicographic order.Definition 2.
LetM be a message space, Σ be a share space, and Γ be an access structure where th is the threshold associated with level Uh. Suppose that the pair i,j is the identity of participant pi,j∈Uh. Then, an HTSS scheme contains the share phase and reconstruction phase.Share Phase. A dealer outputs n shares σi,j∈∑ that is distributed to participant pi,j∈Uh.Reconstruction Phase. An authorized subset R of t participants, which satisfies R∈Γ, can reconstruct the secret k∈M using Birkhoff interpolation.


### 2.3. Social Game Model of Secret Sharing

Reputation systems can provide an incentive for honest behavior and help people decide who is trustworthy. Several reputation systems have been deployed in practical applications, such as encouraging compliance with e-commerce contracts. Next, we briefly review the related concepts and methods in [25].Definition 3.
LetTijp be the trust value assigned by participant Pj to Pi during period p. Let Ti:ℕ⟼ℝ be the trust function computing the reputation of Pi:(7)Tip=1n−1∑j≠iTijp,where−1≤Tip≤+1andTi0=0.
The monotonically increasing functionμx and the monotonically decreasing function μ′x are used to update reputation values recursively, that is, computing Tip by Tip−1. If participant Pi has a choice of cooperating during period p, then Tip=Tip−1+μx. If participant Pi has a choice of defecting during period p, then Tip=Tip−1−μ′x.
Subsequently, we review the payoff assumption. Letuia be Pi’s payoff by considering future action, let μi′a be Pi’s payoff by considering current action, let lia∈0,1 define whether the participant is aware of secret during period p, and define numa=∑lia. The generalized payoff assumptions of social games are as follows:(A)lia=lia′andTia′p>Tia′p⟹uia>uia′(B)lia>lia′⟹uia>uia′(C)lia=lia′and numa<numa′⟹uia>uia′Remark 1.
A, B, and C have impact factorsρ1, ρ2, and ρ3, respectively, where ρ1≫ρ2≥ρ3.
Let(8)ωia=32−Tiap.
We can obtain the current payoffui′a and the future payoff uia as follows:(9)ui′a=ρ2lia+ρ3lianuma+1,uia=ρ1Tiap−Tiap−1Tiap−Tiap−1×ωia+ui′a.


## 2.1. Secret Sharing Homomorphisms

Benaloh [28] described the homomorphic property of secret sharing. For example, consider two secrets k1 and k2, which are shared by polynomials φx and ϕx. If we add the shares fi=φi+ϕi,1≤i≤n, each of fi can be viewed as a subshare of secret k1+k2. Suppose that K is defined as the secret domain, and Σ is defined as the share domain. A set of functions FI:Σt⟶K can be determined, where I⊆1,2,…,n and I=t. Given any set of t values ki1,…,kit, the following equation can define the secret k:(1)k=FIki1,…,kit,forI=i1,…,it.Definition 1.
Suppose⊕ and ⊗ are two operations on the secret domain K and share domain Σ, respectively. There are(2)k=FIki1,…,kit,k′=FIki1′,…,kit′,then,(3)k⊕k′=FIki1⊗ki1′,…,kit⊗kit′.
From the above definition, Shamir’s polynomial is+,+-homomorphic, which implies that the sum of the shares is equivalent to shares of the sum.


## 2.2. Tassa’st,n Hierarchical Threshold Scheme

In HTSS, a set of participantsP=P1,…,Pn are split into multiple levels U0,U1,…,Um, where U0 is the highest level and Um is the lowest level. For all 0≤i<j≤m, there is P=∪i=0mUi, where Ui∩Uj=∅. Supposing that nh is the number of participants associated with level Uh, we can obtain n=P=∑h=0mnh. Then, we define a threshold th associated with level Uh, for h=0,…,m, which satisfies 0<t0<…<tm. In addition, we set t=thh=0m, t=tm, and t−1=0. Therefore, the t,n hierarchical access structure Γ is described as follows:(4)Γ=A⊂P:A∩⋃j=0iUj≥ti,∀i∈0,1,…,m.Next, we describe in detail how the Birkhoff interpolation reconstructs the secret.The Birkhoff interpolation problem is to find a polynomialFx=∑r=0t−1arxr∈ℝt−1x that satisfies the equalities Fi=σi,j, where Fji is the j-th derivative of Fx at position i. Suppose that an authorized subset R∈Γ⊂P can reconstruct the secret. E associated with R is a matrix with binary entries. If there is participant pi,j with share σi,j, then the entry ei,j is set to “1”. In addition, we set φ=1,x,…,xt=ω0,ω1,…,ωt−1 and define ωrj as the j-th derivative of ωr. The matrix AE,X,φ can be expressed as follows:(5)AE,X,φ=ω0j1i1ω1j1i1⋯ωt−1j1i1ω0j2i2ω1j2i2⋯ωt−1j2i2⋮⋮⋮⋮ω0jrirω1jrir⋯ωt−1jrir,wherer=0,…,t−1.The polynomialFx can be reconstructed:(6)Fx=∑r=0t−1AE,X,φrAE,X,φxr,in which we can obtain AE,X,φr by replacing the r+1-th column with the shares σi,j in the lexicographic order.Definition 2.
LetM be a message space, Σ be a share space, and Γ be an access structure where th is the threshold associated with level Uh. Suppose that the pair i,j is the identity of participant pi,j∈Uh. Then, an HTSS scheme contains the share phase and reconstruction phase.Share Phase. A dealer outputs n shares σi,j∈∑ that is distributed to participant pi,j∈Uh.Reconstruction Phase. An authorized subset R of t participants, which satisfies R∈Γ, can reconstruct the secret k∈M using Birkhoff interpolation.


## 2.3. Social Game Model of Secret Sharing

Reputation systems can provide an incentive for honest behavior and help people decide who is trustworthy. Several reputation systems have been deployed in practical applications, such as encouraging compliance with e-commerce contracts. Next, we briefly review the related concepts and methods in [25].Definition 3.
LetTijp be the trust value assigned by participant Pj to Pi during period p. Let Ti:ℕ⟼ℝ be the trust function computing the reputation of Pi:(7)Tip=1n−1∑j≠iTijp,where−1≤Tip≤+1andTi0=0.
The monotonically increasing functionμx and the monotonically decreasing function μ′x are used to update reputation values recursively, that is, computing Tip by Tip−1. If participant Pi has a choice of cooperating during period p, then Tip=Tip−1+μx. If participant Pi has a choice of defecting during period p, then Tip=Tip−1−μ′x.
Subsequently, we review the payoff assumption. Letuia be Pi’s payoff by considering future action, let μi′a be Pi’s payoff by considering current action, let lia∈0,1 define whether the participant is aware of secret during period p, and define numa=∑lia. The generalized payoff assumptions of social games are as follows:(A)lia=lia′andTia′p>Tia′p⟹uia>uia′(B)lia>lia′⟹uia>uia′(C)lia=lia′and numa<numa′⟹uia>uia′Remark 1.
A, B, and C have impact factorsρ1, ρ2, and ρ3, respectively, where ρ1≫ρ2≥ρ3.
Let(8)ωia=32−Tiap.
We can obtain the current payoffui′a and the future payoff uia as follows:(9)ui′a=ρ2lia+ρ3lianuma+1,uia=ρ1Tiap−Tiap−1Tiap−Tiap−1×ωia+ui′a.


## 3. The HTSS Scheme Based on Reputation

In this section, combining an outsourcing computation and the reputation system, we propose a novel outsourcing HTSS protocol based on reputation. In the protocol,t or more parties from different levels can recover the secret. The scheme contains five phases: an initialization phase, a secret distribution phase, an outsourcing phase, a reconstruction phase, and a reputation update phase. We formally defined some parameters during the initialization phase. In the secret distribution phase, a dealer distributes encrypted shares and broadcasts verification information and participants receive a random value and encrypted shares. Then, the participants send shares to a CSP, and the CSP returns the results to the participants where the CSP cannot be aware of any valuable information about the secret. Next, the participants can obtain the secret fairly in the reconstruction phase. Finally, we can update the participant’s reputation value. To avoid collusion, participants have their own reputation value and they are punished or rewarded according to their behavior. For example, if a participant wants to collude with the CSP and sends a collusion invitation to the CSP, then we can penalize the participant according to the reputation system.


### 3.1. Initialization Phase

Letp and q, such as q∣p−1, be two large primes, g be a generator of the q-th order subgroup Fq of Fp∗, and Hx be a collision-resistant hash function.A secretk is shared among n-parties, and a set of parties denoted by P=P1,…,Pn are split into multiple levels U0,U1,…,Um. nh is the number of participants associated with level Uh, and th is the threshold associated with level Uh, for h=0,…,m. The pair i,j is the identity of participant pi,j∈Uh, for i=1,…,nh, j=th−1, and t−1=0.


### 3.2. Secret Distribution Phase

The trusted dealer distributes shares by performing the following stages:Step 1. The dealer randomly chooses t−1 coefficients a1,…,at−1∈Fq and generates a polynomial with t−1 degree:(10)fx=∑r=0t−1aixrmodq,where a0 is a secret value, i.e., k=a0. The corresponding shares are σi,j=fji, where fji is the j-th derivative of the polynomial fx at position i.Step 2. The dealer randomly chooses t−1 coefficients a1′,…,at′∈Fq and generates a polynomial with t−1 degree:(11)f′x=∑r=0t−1ai′xrmodq,where a0′ distributed to all participants is a random value. The corresponding shares are σi,j′=f′ji.Step 3. According to the +,+-homomorphic property, the sum of the shares is equivalent to the shares of the sum, and the dealer performs the following operation:(12)ξi,j=σi,j⊗σ′i,j=fji⊗f′ji.Step 4. The dealer distributes ξi,j,Ha0 to participant pi,j∈Uh, for i=1,…,nh, j=th−1, and h=0,…,m.Step 5. The dealer broadcasts verification information:(13)cr=gar⊗ar′modp,r=0,…,t−1.


### 3.3. Outsourcing Phase

Suppose thatt or more participants from different levels commit their shares, and then they will perform the following stages:Step 1. An authorized subset of t participants sent ξi,j,cr to the CSP.Step 2. According to following equation, the CSP checks whether ξi,j,cr is correct:(14)gξi,j≡∏r=jt−1crr!/r−j!ir−j=gfjimodp,where r=0,…,t−1. The CSP performs Step 3 if the above equation is held; otherwise, the protocol is terminated and the deception of participant pi,j will be disclosed.Step 3. The CSP uses Birkhoff interpolation to reconstruct fx with ξi,j:(15)fx=∑r=0t−1AE,X,φrAE,X,φxr.According to the above equation, the CSP can learnk′=F0=k⊕a0′ and send k′ to t participants.


### 3.4. Reconstruction Phase

Each participant can obtain the secret with a small amount of computation according to the following steps:Step 1. The participant can obtain the secret k by k=k′⊕a0′.Step 2. The participant can verify secret k according to the following equation:(16)Ha0=Hk.If the equation is true, CSP’s calculation is correct; otherwise, it is wrong.


### 3.5. Reputation Update Phase

The reputation value updates as follows:Case 1.
IfPk1≤k≤n+1 sends a collusion to Pj≠k1≤k≤n+1 and Pj has a choice of colluding with Pk, then the colluder earns ρ4, where ρ1≫ρ2≥ρ3≥ρ4 and Pn+1=CSP.Case 2.
IfPj has a choice of not to collude with Pk and broadcasts his malicious behavior, then Pj’s reputation value will increase. In contrast, Pk’s reputation value will decrease.Case 3.
If each participant has a choice of cooperating, then the reputation value will increase; otherwise, the reputation value will decrease.


## 3.1. Initialization Phase

Letp and q, such as q∣p−1, be two large primes, g be a generator of the q-th order subgroup Fq of Fp∗, and Hx be a collision-resistant hash function.A secretk is shared among n-parties, and a set of parties denoted by P=P1,…,Pn are split into multiple levels U0,U1,…,Um. nh is the number of participants associated with level Uh, and th is the threshold associated with level Uh, for h=0,…,m. The pair i,j is the identity of participant pi,j∈Uh, for i=1,…,nh, j=th−1, and t−1=0.


## 3.2. Secret Distribution Phase

The trusted dealer distributes shares by performing the following stages:Step 1. The dealer randomly chooses t−1 coefficients a1,…,at−1∈Fq and generates a polynomial with t−1 degree:(10)fx=∑r=0t−1aixrmodq,where a0 is a secret value, i.e., k=a0. The corresponding shares are σi,j=fji, where fji is the j-th derivative of the polynomial fx at position i.Step 2. The dealer randomly chooses t−1 coefficients a1′,…,at′∈Fq and generates a polynomial with t−1 degree:(11)f′x=∑r=0t−1ai′xrmodq,where a0′ distributed to all participants is a random value. The corresponding shares are σi,j′=f′ji.Step 3. According to the +,+-homomorphic property, the sum of the shares is equivalent to the shares of the sum, and the dealer performs the following operation:(12)ξi,j=σi,j⊗σ′i,j=fji⊗f′ji.Step 4. The dealer distributes ξi,j,Ha0 to participant pi,j∈Uh, for i=1,…,nh, j=th−1, and h=0,…,m.Step 5. The dealer broadcasts verification information:(13)cr=gar⊗ar′modp,r=0,…,t−1.


## 3.3. Outsourcing Phase

Suppose thatt or more participants from different levels commit their shares, and then they will perform the following stages:Step 1. An authorized subset of t participants sent ξi,j,cr to the CSP.Step 2. According to following equation, the CSP checks whether ξi,j,cr is correct:(14)gξi,j≡∏r=jt−1crr!/r−j!ir−j=gfjimodp,where r=0,…,t−1. The CSP performs Step 3 if the above equation is held; otherwise, the protocol is terminated and the deception of participant pi,j will be disclosed.Step 3. The CSP uses Birkhoff interpolation to reconstruct fx with ξi,j:(15)fx=∑r=0t−1AE,X,φrAE,X,φxr.According to the above equation, the CSP can learnk′=F0=k⊕a0′ and send k′ to t participants.


## 3.4. Reconstruction Phase

Each participant can obtain the secret with a small amount of computation according to the following steps:Step 1. The participant can obtain the secret k by k=k′⊕a0′.Step 2. The participant can verify secret k according to the following equation:(16)Ha0=Hk.If the equation is true, CSP’s calculation is correct; otherwise, it is wrong.


## 3.5. Reputation Update Phase

The reputation value updates as follows:Case 1.
IfPk1≤k≤n+1 sends a collusion to Pj≠k1≤k≤n+1 and Pj has a choice of colluding with Pk, then the colluder earns ρ4, where ρ1≫ρ2≥ρ3≥ρ4 and Pn+1=CSP.Case 2.
IfPj has a choice of not to collude with Pk and broadcasts his malicious behavior, then Pj’s reputation value will increase. In contrast, Pk’s reputation value will decrease.Case 3.
If each participant has a choice of cooperating, then the reputation value will increase; otherwise, the reputation value will decrease.


## 4. Security Analysis

In the section, we give the analysis of the protocol.Theorem 1.
The outsourcing HTSS scheme is secure and anyt−1 or fewer participants get nothing about the secret.Proof.
(a) Anyt−1 or fewer participants get nothing about the secret.
In the scheme, anyt−1 or fewer participants’ collusion from different levels cannot obtain the secret with their subshares ξi,j for i=1,…,nh, j=th−1, and h=0,…,m because the Birkhoff interpolation requires t values to determine the unique solution.
(b) The CSP cannot be aware of any valuable information about the secret.
The scheme protects the participant’s privacy, and the CSP does not know the participant’s input and output. An authorized subset oft participants sends encrypted share ξi,j to the CSP. Therefore, the CSP cannot be aware of any valuable information about the secret.Theorem 2.
The outsourcing HTSS scheme can verify malicious behavior, and the malicious behavior can be detected in time.Proof.
(a) The participants and the CSP can check invalid shares.
The public verification informationcr=gar⊕ar′ can check shares whether is correct, and a commitment to the ξi,j can be expressed by the following equation:(17)gξi,j=gσi,j⊗σi,j′=ga0+a1i+⋯+at−1it−1j⊗a0′+a1′i+⋯+at−1′it−1j=ga0⊗a0′+a1⊗a1′ij+⋯+at−1⊗at−1′it−1j=α0jα1ij⋯αt−1it−1j.
Thus, the validity ofξi,j can be checked:(18)gξi,j≡∏r=jt−1crr!/r−j!ir−j=gfjimodp,and the malicious behavior can be detected in time.
(b) The participants can verify the CSP’s calculation result.
The participants can verify the calculation result by a collision-resistant hash function. IfHa0=Hk, the participants can confirm that the CSP’s calculation is correct; otherwise, the result is incorrect. Moreover, the participants can detect the CSP’s malicious behavior in time.Theorem 3.
The scheme is a social Nash equilibrium and collusion-free if the rational participant chooses a cooperation strategy.Proof.
(a) The scheme is not secure if the participants collude with the CSP.
The scheme cannot resist collusion between the server and other participants. In the scheme, ifPi receives the CSP’s collusion invitation and sends a0′ to the CSP, then the CSP can obtain the real secret k instead of k′=k⊕a0′.
(b) Following the method in [25], we consider all participants are rational. Let Coopj define that participant Pj chooses a cooperation strategy where 1≤j≤n+1 and Pn+1=CSP, let Collj define that Pj chooses a collusion strategy, let Coop−j denote that all participants choose a cooperation strategy except for Pj, and let Coop−ij denote that all the participants choose a cooperation strategy except for Pi and Pj.
If all the participants have a choice of cooperating denoted byCoopj,Coop−j, then the payoff functions for choosing cooperation strategy are uiCoopj,Coop−j=Ωρ1ωi+ρ2+ρ3/n+1 and un+1Coopj,Coop−j=ρ1ωn+1 where ωi=3/2−Tip.
IfPi invites CSP to collude and the CSP has a choice of colluding with Pi with a probability of 0.5, then the payoff functions for choosing colluding strategy are uiColli,Colln+1,Coop−in+1=ρ1ωi+ρ2+ρ3/n+2+ρ4 and un+1Colli,Colln+1,Coop−in+1=ρ1ωn+1+ρ2+ρ3/n+2+ρ4 where ρ1≫ρ2≥ρ3≥ρ4; otherwise, if CSP has a choice of not to collude with Pi with a probability of 0.5 and publishes his malicious behavior, then uiColli,Coop−i=−ρ1ωi and un+1Colli,Coop−i=ρ1ωn+1′, where ωi′=3/2−TiP+μx. If the CSP invites Pi to collude and Pi has a choice of colluding with CSP, then un+1Colln+1,Colli,Coop−in+1=ρ1ωn+1+ρ2+ρ3/n+2+ρ4 and uiColln+1,Colli,Coop−in+1=ρ1ωi+ρ2+ρ3/n+2+ρ4; otherwise, if Pi has a choice of not to collude with CSP and publishes his malicious behavior, then un+1Colln+1,Coop−n+1=−ρ1ωn+1 and uiColln+1,Coop−n+1=ρ1ωi′. The payoff function of Pi choosing a collusive strategy is ui=1/2ρ2+ρ3/n+2+ρ4, and the payoff function of Pi choosing a cooperative strategy is ui=1/2ρ1ωi+ρ2+ρ3/n+2+ρ1ωi′. The payoff function of the CSP choosing a collusive strategy is un+1=1/2ρ2+ρ3/n+2+ρ4, and the payoff function of the CSP choosing a cooperative strategy is un+1=1/2ρ1ωn+1′+ρ1ωn+1. The payoff function of cooperative strategy is larger than that of collusive strategy. From the above statements, we can conclude that choosing cooperation is the optimal strategy.


## 5. Performance Analysis

We evaluated the prototype on a PC which has an Intel Core i7-6700 CPU (4-core 2.60 GHz) and 8 GB of RAM. To ignore network latency, we run the server and all clients on the same host. The times of the secret verification and secret reconstruction are given in Table1. In Figure 2, the curve shows the reconstruction time of the scheme. According to the test results, the time varies from 2.17 ms to 2.74 ms. Figure 3 shows the time of the verification, and as the number of participant increases, the verification time increases exponentially. According to the test results, the time varies from 791.52 ms to 7370.42 ms. We conclude that the secret reconstruction requires less time than the verification algorithm.Table 1
Computation time (in ms).
Client
t = 3
t = 4
t = 5
t = 6
Time of secret verification
791.52
868.21
1103.42
7370.42
Time of secret reconstruction
2.17
2.19
2.31
2.74Figure 2
Secret reconstruction time.Figure 3
Secret verification time.In addition, we listed our comparison results in Table2. Maleka et al. [29] analyzed a finite repeated game and an infinite repeated game, but the scheme could not effectively guarantee fairness. Traverso et al. [17] proposed an HTSS scheme that supports verifiability and dynamics, which can add, remove, and renew shares. Although the scheme can check invalid shares, the scheme cannot effectively guarantee fairness. A multistage secret sharing scheme was introduced by Pilaram and Eghlidos [10], which was based on Lattice and could resist quantum attacks. But this scheme requires a trusted third party. In order to achieve desire of fairness, Harn et al. [30] proposed a fair secret sharing scheme, but the scheme requires multiple protocol rounds and cannot be effectively applied to devices with poor computing capabilities.Table 2
Feature comparison of schemes.
Maleka et al. [29]
Harn et al. [30]
Pilaram and Eghlidos [10]
Traverso et al. [17]
Our scheme
Fairness
No
Yes
Yes
No
Yes
Number of rounds
Multiple rounds
Multiple rounds
One round
One round
One round
Trusted third party
No
No
Yes
Yes
No
Interactive
Yes
Yes
No
Yes
No
Computation
User
User
User
User
CSP
Communication cost
O (tk)
O (t)
O (1)
O (t)
O (1)In contrast, our scheme only needs to execute the protocol once. The participants only need to perform the decryption operation, and the communication cost is O (1). In the proposed scheme, complex operations such as homomorphic encryption and verification are outsourced to the CSP. Moreover, our scheme does not require participants to always be online.


## 6. Conclusion

Combining outsourcing computation and a reputation system, we provide an outsourcing HTSS protocol based on reputation. The participants can obtain the secret fairly with a small number of operations in this work. Expensive computing is outsourced to a CSP, and the CSP could learn nothing about the secret. The reputation system can effectively prevent participants from colluding with the server. Participants have their own reputation value, and they are punished or rewarded according to their behavior. Moreover, our protocol could accurately check the malicious behavior of the participants or the server and does not require multiple interactions between the participants and the server, which applies to cloud computing environments and mobile networks.



---

*Source: 6989383-2019-10-10.xml*