# Fair and Efficient Robust Secret Sharing Scheme against Rushing Adversaries

Authors: En Zhang; Renlin Yang; Haiju Fan; Leiyong Qin
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Robust secret sharing (RSS) is an extension of secret sharing, which can reconstruct a secret correctly even if anyt shares are incorrect. The existing scheme would not effectively achieve fairness. Moreover, even for an optimal scheme, RSS still has the problem that one party is verified by multiple parties, leading to expensive communication costs. In this work, we construct a blockchain-aided RSS scheme that can ensure decentralization and fairness. The central building block for our scheme to handle a rushing adversary is a bulletin board we implement on the InterPlanetary File System. Furthermore, we design a monetary penalty mechanism to impose real penalties on corrupt parties. Each participant either uploads his share correctly or loses his deposit. In addition, our scheme eliminates considerable communication between participants. Compared with the previous schemes, our scheme has a lower communication complexity, which is close to O˜n. We conduct experiments to show the performance of our scheme. To our knowledge, this is the first implementation of a fair RSS scheme. For shares with a length of 128 bits, the time for each participant to execute the verification phase is 470 ms.


---

## Body

## 1. Introduction

Robust secret sharing (RSS) is an extension of secret sharing that was introduced by the seminal works of Shamir [1] and Blakley [2]. In a t-out-of-n RSS scheme, a dealer splits the secret s into shares and sends these shares to n participants. The secret s can be reconstructed successfully even if t shares are incorrect due to natural damage or being corrupted by an adversary. Robust secret sharing is widely used in practical scenarios, such as the following: (1) data storage: users store their data on multiple cloud servers. The privacy and integrity of these data cannot be damaged even if up to t clouds collude. (2) Secure communication: when users send data over a communication network, the security and integrity of the users’ data are still guaranteed even if up to t communication channels are controlled by an adversary.Recently, research on the share size has made great progress, and the known optimal share size is close toO˜κ. However, existing RSS schemes either require a trusted third party or require multiple interactions in the reconstruction phase, which causes expensive communication costs. In addition, previous RSS schemes cannot impose practical penalties on the corrupt party and cannot effectively achieve fairness. In this study, we solve the problems of centralization and fairness, and we improve the communication complexity to On.


### 1.1. Related Work

Secret sharing was initially introduced by Shamir [1] and Blakley [2]. Many works consider stronger concepts based on the secret sharing, such as hierarchical secret sharing and threshold secret sharing [3–13]. Rabin et al. [14] first proposed the concept of robust secret sharing in 1989. In a robust secret sharing scheme, the number of corrupt parties is less than half of all participants. Therefore, the maximum corruption in a RSS scheme is set to n=2t+1. The failure probability of the reconstruction is negligible when the relationship between n and t becomes n/3≤t≤n/2 [15]. In 1997, Carlo et al. [16] analyzed the lower bound of the share size and the probability of deception in an RSS scheme.Serge Fehr [15] proposed an RSS scheme and proved that the average bit length of a share is lower-bounded by the bit length of the secret. Compared with [14], Serge Fehr improved the message authentication code (MAC) algorithm to reduce the share size to m+On+κ, and the MAC algorithm that they used can verify the correctness of shares; however, their scheme cannot fight a rushing adversary. To solve this problem, Cevallos [17] constructed a new RSS scheme that can maintain security against a rushing adversary. Furthermore, the share size of their scheme is close to that of [15]. However, each participant needs to verify the shares of all other participants, which causes a high communication cost during the reconstruction phase. In addition, Cevallos reduced the length of the tag in the message authentication code; therefore, the probability of corrupt parties colluding together to pass the MAC authentication is not negligible.Later, Bishop et al. [18] designed an essential optimal RSS scheme, and the share size of this scheme is m+Oκlog4n+log3nlogκ. The scheme can successfully reconstruct the secret in the case of the maximum corruption. The basic idea behind their reconstruction phase is the minimum graph. The scheme used a graph algorithm to make a judgement on the participants, which can verify whether they are good or bad. The graph recognition algorithm can eventually collect the shares of all good participants. Allison Bishop innovatively eliminated the linear relationship between the share size and the number of participants. However, the scheme is not able to fight a rushing adversary that can choose incorrect authentication keys freely. Fehr and Yuan [19] proposed a new scheme that can fight a rushing adversary. In addition, the share size of this scheme is close to m+Oκnε. The participants are required to submit shares in multiple rounds, which can limit the relationship between correct and incorrect shares. Unlike [18], participants do not need an authentication key for authentication. Each participant can verify whether his neighbour is good or bad. The algorithm eventually outputs a set that contains the shares of all good participants. In this way, the Solomon algorithm has enough redundant codes to reconstruct a secret efficiently. However, the algorithm has a high probability of success only if it starts with an honest party. In 2020, Fehr and Yuan [20] designed a new scheme that has the optimal share size, can guarantee safety against rushing adversaries, and can also run in polynomial time.Regarding the share size, Bishop et al. [21] introduced a nearly optimal scheme that optimizes the share size to m1+O1+On. In short, the scheme first fixes the original secret with the detection of algebraic manipulation (AMD) code [22]. The algorithm outputs a short list containing the correct keys, which allows the reconstruction phase of the scheme to efficiently identify error messages. Then, the scheme used the folded Reed–Solomon codes [23] to construct error-correcting codes. Compared with the existing Solomon code, the folded Reed–Solomon codes can construct error-correcting codes more efficiently. Unfortunately, the scheme cannot fight a rushing adversary. Manurangsi et al. [24] presented a new scheme that can fight a rushing adversary. The share size of the scheme is further optimized to m+Oλlognlogn+logm. The reconstruction phase of the scheme is a two-step process. In the first round, each participant publishes his share. In the second round, the scheme uses a private MAC to verify whether each party has changed his share. If the party does not modify his share, the scheme labels him as good. Otherwise, the scheme labels him as bad. The reconstruction phase eventually outputs a set that contains all the good parties. Moreover, the scheme uses fixed-point recognition algorithms to make the second round more efficient. Finally, the participants can use this set to reconstruct the secret locally. However, the scheme still has the problem that one party is verified by multiple parties, which causes high communication costs.We summarize the above schemes, as shown in Table1. The above schemes either cannot provide security against rushing adversaries or have higher communication complexity. In addition, none of the above schemes can effectively achieve fairness.Table 1
Summary of results in robust secret sharing scheme.
PaperShare sizeCommunication complexityRemark[1]m+OnκOn2Corruption setting witht<n/3[16]——Give the lower bounds for RSS[17]m+On+κOn2Secure against rushing adversaries[18]m+OκOndForn=2t+1[19]m+OκOndSecure against rushing adversaries[20]m+OκOn with a third partySecure against rushing adversaries[21]m+OκOn2Forn=2t+1[24]m+Oκlognlogn+logmOn2Secure against rushing adversaries


### 1.2. Contribution

In this study, we construct a decentralized and fair RSS scheme based on smart contracts, and the share size of our scheme is close tom+O˜κ. The flow of the scheme is shown in Figure 1, and the main contributions are as follows.Figure 1
Robust secret sharing scheme based on smart contract.


#### 1.2.1. The Scheme Is Secure against Rushing Adversaries

We implemented a bulletin board on the InterPlanetary File System (IPFS) to broadcast all tags before the reconstruction phase. Because the tag cannot be changed, our scheme can easily verify whether the party has changed his share.


#### 1.2.2. The Scheme Can Guarantee Fairness in Malicious Model

We implemented a monetary penalty mechanism, which can impose real penalties on corrupt parties. Each participant either uploads his share correctly or loses his deposit. This motivates all parties to be honest and ensures the fairness of our scheme.


#### 1.2.3. The Communication Complexity of This Scheme Is Close toOn

We designed a smart contract with the functions of collecting, verifying, and broadcasting shares. Compared with the scheme of [19] (Eurocrypt 2019), we have a lower communication complexity.


#### 1.2.4. This Is the First Implementation of a Fair RSS Scheme

We demonstrate the implementation of a fair and decentralized RSS scheme using the blockchain. For shares with a length of 128 bits, the time for each participant to run the verification phase is 470 ms.


### 1.3. Roadmap

The organization of the study is as follows: in Section2, the preliminary of message authentication code, Reed–Solomon code, InterPlanetary File System, and Ethereum are introduced. Section 3 introduces our smart contract model, and Section 4 introduces our protocol. We analyze the security proof of the protocol in Section 5. We did the simulation experiment in Section 6. Finally, we present our conclusion in Section 7.


## 1.1. Related Work

Secret sharing was initially introduced by Shamir [1] and Blakley [2]. Many works consider stronger concepts based on the secret sharing, such as hierarchical secret sharing and threshold secret sharing [3–13]. Rabin et al. [14] first proposed the concept of robust secret sharing in 1989. In a robust secret sharing scheme, the number of corrupt parties is less than half of all participants. Therefore, the maximum corruption in a RSS scheme is set to n=2t+1. The failure probability of the reconstruction is negligible when the relationship between n and t becomes n/3≤t≤n/2 [15]. In 1997, Carlo et al. [16] analyzed the lower bound of the share size and the probability of deception in an RSS scheme.Serge Fehr [15] proposed an RSS scheme and proved that the average bit length of a share is lower-bounded by the bit length of the secret. Compared with [14], Serge Fehr improved the message authentication code (MAC) algorithm to reduce the share size to m+On+κ, and the MAC algorithm that they used can verify the correctness of shares; however, their scheme cannot fight a rushing adversary. To solve this problem, Cevallos [17] constructed a new RSS scheme that can maintain security against a rushing adversary. Furthermore, the share size of their scheme is close to that of [15]. However, each participant needs to verify the shares of all other participants, which causes a high communication cost during the reconstruction phase. In addition, Cevallos reduced the length of the tag in the message authentication code; therefore, the probability of corrupt parties colluding together to pass the MAC authentication is not negligible.Later, Bishop et al. [18] designed an essential optimal RSS scheme, and the share size of this scheme is m+Oκlog4n+log3nlogκ. The scheme can successfully reconstruct the secret in the case of the maximum corruption. The basic idea behind their reconstruction phase is the minimum graph. The scheme used a graph algorithm to make a judgement on the participants, which can verify whether they are good or bad. The graph recognition algorithm can eventually collect the shares of all good participants. Allison Bishop innovatively eliminated the linear relationship between the share size and the number of participants. However, the scheme is not able to fight a rushing adversary that can choose incorrect authentication keys freely. Fehr and Yuan [19] proposed a new scheme that can fight a rushing adversary. In addition, the share size of this scheme is close to m+Oκnε. The participants are required to submit shares in multiple rounds, which can limit the relationship between correct and incorrect shares. Unlike [18], participants do not need an authentication key for authentication. Each participant can verify whether his neighbour is good or bad. The algorithm eventually outputs a set that contains the shares of all good participants. In this way, the Solomon algorithm has enough redundant codes to reconstruct a secret efficiently. However, the algorithm has a high probability of success only if it starts with an honest party. In 2020, Fehr and Yuan [20] designed a new scheme that has the optimal share size, can guarantee safety against rushing adversaries, and can also run in polynomial time.Regarding the share size, Bishop et al. [21] introduced a nearly optimal scheme that optimizes the share size to m1+O1+On. In short, the scheme first fixes the original secret with the detection of algebraic manipulation (AMD) code [22]. The algorithm outputs a short list containing the correct keys, which allows the reconstruction phase of the scheme to efficiently identify error messages. Then, the scheme used the folded Reed–Solomon codes [23] to construct error-correcting codes. Compared with the existing Solomon code, the folded Reed–Solomon codes can construct error-correcting codes more efficiently. Unfortunately, the scheme cannot fight a rushing adversary. Manurangsi et al. [24] presented a new scheme that can fight a rushing adversary. The share size of the scheme is further optimized to m+Oλlognlogn+logm. The reconstruction phase of the scheme is a two-step process. In the first round, each participant publishes his share. In the second round, the scheme uses a private MAC to verify whether each party has changed his share. If the party does not modify his share, the scheme labels him as good. Otherwise, the scheme labels him as bad. The reconstruction phase eventually outputs a set that contains all the good parties. Moreover, the scheme uses fixed-point recognition algorithms to make the second round more efficient. Finally, the participants can use this set to reconstruct the secret locally. However, the scheme still has the problem that one party is verified by multiple parties, which causes high communication costs.We summarize the above schemes, as shown in Table1. The above schemes either cannot provide security against rushing adversaries or have higher communication complexity. In addition, none of the above schemes can effectively achieve fairness.Table 1
Summary of results in robust secret sharing scheme.
PaperShare sizeCommunication complexityRemark[1]m+OnκOn2Corruption setting witht<n/3[16]——Give the lower bounds for RSS[17]m+On+κOn2Secure against rushing adversaries[18]m+OκOndForn=2t+1[19]m+OκOndSecure against rushing adversaries[20]m+OκOn with a third partySecure against rushing adversaries[21]m+OκOn2Forn=2t+1[24]m+Oκlognlogn+logmOn2Secure against rushing adversaries


## 1.2. Contribution

In this study, we construct a decentralized and fair RSS scheme based on smart contracts, and the share size of our scheme is close tom+O˜κ. The flow of the scheme is shown in Figure 1, and the main contributions are as follows.Figure 1
Robust secret sharing scheme based on smart contract.


### 1.2.1. The Scheme Is Secure against Rushing Adversaries

We implemented a bulletin board on the InterPlanetary File System (IPFS) to broadcast all tags before the reconstruction phase. Because the tag cannot be changed, our scheme can easily verify whether the party has changed his share.


### 1.2.2. The Scheme Can Guarantee Fairness in Malicious Model

We implemented a monetary penalty mechanism, which can impose real penalties on corrupt parties. Each participant either uploads his share correctly or loses his deposit. This motivates all parties to be honest and ensures the fairness of our scheme.


### 1.2.3. The Communication Complexity of This Scheme Is Close toOn

We designed a smart contract with the functions of collecting, verifying, and broadcasting shares. Compared with the scheme of [19] (Eurocrypt 2019), we have a lower communication complexity.


### 1.2.4. This Is the First Implementation of a Fair RSS Scheme

We demonstrate the implementation of a fair and decentralized RSS scheme using the blockchain. For shares with a length of 128 bits, the time for each participant to run the verification phase is 470 ms.


## 1.2.1. The Scheme Is Secure against Rushing Adversaries

We implemented a bulletin board on the InterPlanetary File System (IPFS) to broadcast all tags before the reconstruction phase. Because the tag cannot be changed, our scheme can easily verify whether the party has changed his share.


## 1.2.2. The Scheme Can Guarantee Fairness in Malicious Model

We implemented a monetary penalty mechanism, which can impose real penalties on corrupt parties. Each participant either uploads his share correctly or loses his deposit. This motivates all parties to be honest and ensures the fairness of our scheme.


## 1.2.3. The Communication Complexity of This Scheme Is Close toOn

We designed a smart contract with the functions of collecting, verifying, and broadcasting shares. Compared with the scheme of [19] (Eurocrypt 2019), we have a lower communication complexity.


## 1.2.4. This Is the First Implementation of a Fair RSS Scheme

We demonstrate the implementation of a fair and decentralized RSS scheme using the blockchain. For shares with a length of 128 bits, the time for each participant to run the verification phase is 470 ms.


## 1.3. Roadmap

The organization of the study is as follows: in Section2, the preliminary of message authentication code, Reed–Solomon code, InterPlanetary File System, and Ethereum are introduced. Section 3 introduces our smart contract model, and Section 4 introduces our protocol. We analyze the security proof of the protocol in Section 5. We did the simulation experiment in Section 6. Finally, we present our conclusion in Section 7.


## 2. Preliminaries

### 2.1. Message Authentication Code

The message authentication code (MAC) can guarantee the integrity of the message and detect whether others have tampered with the message. Unconditionally secure MAC was invented by Carter and Wegman [25], and the definition is as follows.Definition 1.
A message authentication code for a finite message spaceℳ composed of a specific function: T←ℳ×K. This MAC is secure if and only if it follows: for any m,m′∈ℳ and m≠m′, any t,t′∈T and t≠t′, and a negligible function polyx, there is as follows:(1)Prk←KMACm′,k=t′|MACm,k=t≤polyx.
The MAC authentication we used in this study is a key-dependent hash-based message authentication code (HMAC). Regarding the security of HMAC, researchers use various methods to attack it, such as collision attack and length extension attacks, but none of them have a good effect. Later, [26] gave a strict security proof about the HMAC and proved the close relationship between the security of HMAC and hash function. If the HMAC has security problems, then the bottom hash function must have security problems. Therefore, theoretically the security of HMAC is proved.


### 2.2. Reed–Solomon Code

The idea behind the Solomon code can be represented as polynomial, and it relies on an algebraic theory that anyk points can construct a polynomial of degree k−1. In the first place, the sender S has a message m=m1,…,mk. There is a polynomial fx of degree k−1 in a finite field, which is constructed with k data points. S picks k values x1,…,xk at random. The polynomial codes the data point according to the corresponding value of each point such as fxi=yi. S sends these values to the receiver R, but these values can be corrupted for some reasons during transmission. Therefore, we added some additional data points called redundant codes. The final number of these data points that S sends to R is actually nn>k. R starts decoding after receiving these data points. R can compute the polynomial fx and reconstruct the raw data as long as R receives sufficient number of values correctly. There are many decoding methods for the Solomon codes, among which the Berlekamp–Welch algorithm [27] can efficiently reconstruct the polynomial fx from y1,…,yk. The error correction ability of this algorithm is related to the shortest Hamming distance d=n−k+1. The algorithm can correct n−k/2 errors if the location of the error message is not known before the error correction. The algorithm can correct n−k errors if the location of the error message is known before the error correction. Later, Gao [28] used fast Fourier transform (FFT) to greatly improve the decoding efficiency without reducing its error correction capability.


### 2.3. Blockchain

The blockchain is a distributed shared ledger and database, which was first proposed by Satoshi Nakamoto. The blockchain can store an ever-growing and unmodifiable list of records. These records are called blocks and are linked to previous blocks. Recently, the business models based on blockchain have developed rapidly. Researchers are exploring the blockchain business model in different fields, such as energy and physical products [29]. The development of the blockchain has made smart contracts possible. Blockchain-based smart contracts are computer programs executed by many nodes that can be tracked and immutable. Therefore, the design of smart contract must follow the principle of low cost. To enable smart contracts to perform more complex algorithms, off-chain smart contract frameworks are being developed [30].


### 2.4. InterPlanetary File System

The InterPlanetary File System (IPFS) is a distributed network transport protocol for storing and sharing files. A user uploads a file to an IPFS node and obtains a hash valueH. Other users can use H to download the file directly from the IPFS node. In [31], Benet stated that the IPFS combines distributed hash tables, BitTorrent, Git, self-certified file systems, and the blockchain to save and transfer files. These systems bring significant characteristics to IPFS as follows:(i)
Permanent and decentralized storage of documents.(ii)
Users can use a specific hash value to find a stored file.(iii)
The document modification history can be traced.These characteristics give the IPFS great potential in the field of cryptography. Compared with the blockchain, the IPFS has a large advantage in storing large files. In this study, we implement a bulletin board on the IPFS that contains the tags of all participants’ shares, so that the corrupt party cannot cheat on the tags. Meanwhile, the share size is reduced toO˜κ.


### 2.5. Security Model

The existing secure multiparty computing (MPC) protocol needs a security proof to ensure its security. In this study, ideal and real models are used as the security models of security proofs. The precise definition of the security model was proposed in [32], which argues that there is a trusted third party that can communicate securely with the participants and run the protocol honestly in an ideal world. The scheme is secure if participants’ output and view in the real model are indistinguishable from those in the ideal model. In this section, we will provide the exact definition of this model as follows:(i)
Real World: in the real world, the honest party runs the scheme∏ correctly. There is a malicious adversary A that can corrupt any participants. All message from the corrupt party is determined by the adversary A. In addition, A can interact with ∏ at will to obtain some useful information. The input of the scheme generated by the participants is sent to ∏ directly, and the output of ∏ is returned to A. Finally, A outputs Real∏,Ax1,…,xn as the output of the real world.(ii)
(ii)Ideal World: in an ideal world, there is a trusted third party that receives an input from the participant to safely compute functionF. A simulator sim can extract the behaviour of an adversary and receive the input of the honest party in the real world. The input of the scheme generated by sim is sent to the function F directly, and the output of the function is returned to sim. Finally, sim outputs IdealF,simx1,…,xn as the output of the ideal world.


## 2.1. Message Authentication Code

The message authentication code (MAC) can guarantee the integrity of the message and detect whether others have tampered with the message. Unconditionally secure MAC was invented by Carter and Wegman [25], and the definition is as follows.Definition 1.
A message authentication code for a finite message spaceℳ composed of a specific function: T←ℳ×K. This MAC is secure if and only if it follows: for any m,m′∈ℳ and m≠m′, any t,t′∈T and t≠t′, and a negligible function polyx, there is as follows:(1)Prk←KMACm′,k=t′|MACm,k=t≤polyx.
The MAC authentication we used in this study is a key-dependent hash-based message authentication code (HMAC). Regarding the security of HMAC, researchers use various methods to attack it, such as collision attack and length extension attacks, but none of them have a good effect. Later, [26] gave a strict security proof about the HMAC and proved the close relationship between the security of HMAC and hash function. If the HMAC has security problems, then the bottom hash function must have security problems. Therefore, theoretically the security of HMAC is proved.


## 2.2. Reed–Solomon Code

The idea behind the Solomon code can be represented as polynomial, and it relies on an algebraic theory that anyk points can construct a polynomial of degree k−1. In the first place, the sender S has a message m=m1,…,mk. There is a polynomial fx of degree k−1 in a finite field, which is constructed with k data points. S picks k values x1,…,xk at random. The polynomial codes the data point according to the corresponding value of each point such as fxi=yi. S sends these values to the receiver R, but these values can be corrupted for some reasons during transmission. Therefore, we added some additional data points called redundant codes. The final number of these data points that S sends to R is actually nn>k. R starts decoding after receiving these data points. R can compute the polynomial fx and reconstruct the raw data as long as R receives sufficient number of values correctly. There are many decoding methods for the Solomon codes, among which the Berlekamp–Welch algorithm [27] can efficiently reconstruct the polynomial fx from y1,…,yk. The error correction ability of this algorithm is related to the shortest Hamming distance d=n−k+1. The algorithm can correct n−k/2 errors if the location of the error message is not known before the error correction. The algorithm can correct n−k errors if the location of the error message is known before the error correction. Later, Gao [28] used fast Fourier transform (FFT) to greatly improve the decoding efficiency without reducing its error correction capability.


## 2.3. Blockchain

The blockchain is a distributed shared ledger and database, which was first proposed by Satoshi Nakamoto. The blockchain can store an ever-growing and unmodifiable list of records. These records are called blocks and are linked to previous blocks. Recently, the business models based on blockchain have developed rapidly. Researchers are exploring the blockchain business model in different fields, such as energy and physical products [29]. The development of the blockchain has made smart contracts possible. Blockchain-based smart contracts are computer programs executed by many nodes that can be tracked and immutable. Therefore, the design of smart contract must follow the principle of low cost. To enable smart contracts to perform more complex algorithms, off-chain smart contract frameworks are being developed [30].


## 2.4. InterPlanetary File System

The InterPlanetary File System (IPFS) is a distributed network transport protocol for storing and sharing files. A user uploads a file to an IPFS node and obtains a hash valueH. Other users can use H to download the file directly from the IPFS node. In [31], Benet stated that the IPFS combines distributed hash tables, BitTorrent, Git, self-certified file systems, and the blockchain to save and transfer files. These systems bring significant characteristics to IPFS as follows:(i)
Permanent and decentralized storage of documents.(ii)
Users can use a specific hash value to find a stored file.(iii)
The document modification history can be traced.These characteristics give the IPFS great potential in the field of cryptography. Compared with the blockchain, the IPFS has a large advantage in storing large files. In this study, we implement a bulletin board on the IPFS that contains the tags of all participants’ shares, so that the corrupt party cannot cheat on the tags. Meanwhile, the share size is reduced toO˜κ.


## 2.5. Security Model

The existing secure multiparty computing (MPC) protocol needs a security proof to ensure its security. In this study, ideal and real models are used as the security models of security proofs. The precise definition of the security model was proposed in [32], which argues that there is a trusted third party that can communicate securely with the participants and run the protocol honestly in an ideal world. The scheme is secure if participants’ output and view in the real model are indistinguishable from those in the ideal model. In this section, we will provide the exact definition of this model as follows:(i)
Real World: in the real world, the honest party runs the scheme∏ correctly. There is a malicious adversary A that can corrupt any participants. All message from the corrupt party is determined by the adversary A. In addition, A can interact with ∏ at will to obtain some useful information. The input of the scheme generated by the participants is sent to ∏ directly, and the output of ∏ is returned to A. Finally, A outputs Real∏,Ax1,…,xn as the output of the real world.(ii)
(ii)Ideal World: in an ideal world, there is a trusted third party that receives an input from the participant to safely compute functionF. A simulator sim can extract the behaviour of an adversary and receive the input of the honest party in the real world. The input of the scheme generated by sim is sent to the function F directly, and the output of the function is returned to sim. Finally, sim outputs IdealF,simx1,…,xn as the output of the ideal world.


## 3. The Smart Contract Model

Section3 describes the smart contract model we designed, which includes each time point, the function of each module, and the transaction process of the smart contract, as shown in Figure 2.Figure 2
Smart contract model of RSS scheme.A reconstruction scheme consists of two phases: thesubmissionphase and the verificationphase. Participants submit shares in two rounds during the submission phase, which limits the relationship between correct and incorrect shares. The verification phase includes tag verification and MAC verification. The tag verification can check whether Ti is correct, and the MAC verification can check whether si has been changed. We define some time points that are as follows:tregister: all participants must pay deposit d and register their eligibility to participate in the smart contract before tregister. If the participant does not pay the deposit before tregister, the scheme will be terminated.tsubmit1: for each i∈n, Pi must upload HT,Ti,si to the smart contract before tsubmit1. If Pi does not upload HT,Ti,si within the specified time, his deposit will be deducted.tsubmit2: for each i∈n, Pi must upload keyi to the smart contract before tsubmit2. If Pi does not upload keyi within the specified time, his deposit will be deducted.The description of every phase is as follows.


### 3.1. Initialization

(1)
For eachi∈n, participant Pi has share HT,z,si,Ti,keyi and cannot access others’ shares.(2)
The smart contract defines a depositd. The value of d is greater than the secret s.(3)
Pi pays a deposit and registers to participate in the smart contract until he finds the transaction RSC⋅register in the blockchain.


### 3.2. Submission Phase

(1)
RSC⋅submit1: The smart contract broadcasts the transaction address of RSC⋅submit1. Pi submits si,Ti. The smart contract stores the share and address of Pi.(2)
RSC⋅submit2: The smart contract broadcasts the transaction address of RSC⋅submit2. Pi submits keyi. The smart contract stores the share and address of Pi.(3)
All participants wait for smart contract to broadcast the transaction addresses ofRSC⋅submit1 and RSC⋅submit2.(4)
If the transaction addresses ofRSC⋅submit1 and RSC⋅submit1 do not appear in the blockchain before tsubmit1 and tsubmit2, respectively, the smart contract refunds the deposit.


### 3.3. Verification Phase

(1)
RSC tag verification: the smart contract broadcasts the transaction address ofRSC⋅tagverification and verifies whether Ti is in HT.(2)
RSC MAC verification: the smart contract broadcasts the transaction address ofRSC⋅MACverification and verifies whether Ti=HMACsi,keyi is established.


### 3.4. Broadcast and Refund Phase

After the verification phase, the smart contract can get the setI, which contains all the honest parties and passive adversaries.The smart contract broadcasts the transaction address ofRSC⋅refund. For each i∈I, Pi can use the transaction address to query transaction information. Meanwhile, the smart contract broadcasts the correct shares si and returns the deposit to the party Pi.


## 3.1. Initialization

(1)
For eachi∈n, participant Pi has share HT,z,si,Ti,keyi and cannot access others’ shares.(2)
The smart contract defines a depositd. The value of d is greater than the secret s.(3)
Pi pays a deposit and registers to participate in the smart contract until he finds the transaction RSC⋅register in the blockchain.


## 3.2. Submission Phase

(1)
RSC⋅submit1: The smart contract broadcasts the transaction address of RSC⋅submit1. Pi submits si,Ti. The smart contract stores the share and address of Pi.(2)
RSC⋅submit2: The smart contract broadcasts the transaction address of RSC⋅submit2. Pi submits keyi. The smart contract stores the share and address of Pi.(3)
All participants wait for smart contract to broadcast the transaction addresses ofRSC⋅submit1 and RSC⋅submit2.(4)
If the transaction addresses ofRSC⋅submit1 and RSC⋅submit1 do not appear in the blockchain before tsubmit1 and tsubmit2, respectively, the smart contract refunds the deposit.


## 3.3. Verification Phase

(1)
RSC tag verification: the smart contract broadcasts the transaction address ofRSC⋅tagverification and verifies whether Ti is in HT.(2)
RSC MAC verification: the smart contract broadcasts the transaction address ofRSC⋅MACverification and verifies whether Ti=HMACsi,keyi is established.


## 3.4. Broadcast and Refund Phase

After the verification phase, the smart contract can get the setI, which contains all the honest parties and passive adversaries.The smart contract broadcasts the transaction address ofRSC⋅refund. For each i∈I, Pi can use the transaction address to query transaction information. Meanwhile, the smart contract broadcasts the correct shares si and returns the deposit to the party Pi.


## 4. The Robust Secret Sharing Scheme

### 4.1. The Construction

Lett be an arbitrary positive integer, and n=2t+1. This scheme randomly selects n interpolation points x1,…,xn in a field F and F>n. In addition, we use a HMAC algorithm with secret s∈F. Assume that the adversary can obtain the profit worth d after breaking the RSS. The detailed steps of the RSS scheme are shown in Figure 3.Figure 3
RSS scheme based on smart contract.


### 4.2. Analysis of the Construction

In the malicious model, there are always adversaries colluding to pass the MAC authentication of the protocol with the wrong shares, which makes the RSS cannot reconstruct the secret. In this section, we use the Chernoff bounds [33] to prove that this probability is small.We define a setC, which contains all corrupt parties. There are two types of corrupt parties we define. One type is the active corrupt party, and they will provide the wrong shares, which are represented by set A and A=a. The other type is the passive corrupt party, and they will provide the correct shares, which are represented by set P and P=p. Obviously, t=a+p.In the case ofp≥t/2, even if all active corrupt parties have passed MAC authentication, the Solomon decoding algorithm can still reconstruct the correct secret, so we do not consider this situation. We only pay attention to PrA∩I>0 in the case of p<t/2.LetX be a random variable and a∈R. According to the Markov inequality [34], we have the following:(2)∀l>0,PrX≥a=PrelX≥ela≤EelXela,where MXl=EelX. We compute the Taylor expansion of EelX, and assuming it is convergent:(3)MXlMXl=E1+lX+12l2X2+13l3X3+⋯=∑i=0∞1i!liEXi.The message about distribution can be encoded byEXi. We limit the moment generating function of each Xi to derive the Chernoff bounds.Lemma 1.
Given independent and random variablesX1,X2,…,Xn, where X=∑i=1nXi, then:(4)MXl=∏i=1nMXil.Proof.
(5)MXl=EelX=Eel∑i=1nXi=E∏i=1nelXi=∏i=1nMXil.
Before deriving the Chernoff bounds, we use the Bernoulli trial to complete the following lemma.Lemma 2.
Given a random variableY, and PrY=1=p,PrY=0=1−p, then(6)∀l∈R,MYl=EelY≤epel−1.Proof.
(7)MYl=EelY=p×el+1−p×1=1+pel−1,where y=pel−1, and then:(8)MYl≤epel−1.
From Lemmas1 and 2, we start to derive the Chernoff bounds.Corollary 1.
Given independent and random variablesX1,X2,…,Xn, and X=∑i=1nXi, where PrXi=1=pi,PrXi=0=1−pi, and μ=EX=∑i=1npi, then:(9)∀δ>0,PrX≥1+δμ≤eδ1+δ1+δμ≤eδ−δ2μ.Proof.
(10)MXl=∏i=1nMXix≤∏i=1nepiel−1=eel−1∑i=1npi=eel−1μ.
Leta=1+δμ,l=ln1+δ. Applying (2), we can obtain the following:(11)PrX≥1+δμ≤EelXela=elμel1+δμ.
When0<l<el−1, we have the following:(12)PrX≥1+δμ≤eel−1μel1+δμ=eδ1+δ1+δμ.
Taking the logarithm of thelneδ/1+δ1+δμ, we can obtain the following:(13)μδ−1+δln1+δ.
For anyx>0,a<1+x, there is ln1+x≥ax/1+x, and then:(14)μδ−1+δln1+δ≤δ−δ2μ.Theorem 1.
For any positive integert, any positive integer n = 2t+1, and any HMAC, the (n, t) robust secret sharing scheme has a small probability of failure with:(15)Prfailure<1etpolyx−1.Proof.
Considert corrupt parties as t random variables X1,X2,…Xt. If Xi passes HMAC authentication, Xi=1. Otherwise, Xi=0. PrXi=1=ε,PrXi=0=1−ε. We can obtain the following:(16)μ=EX=∑i=1tε=tε.
Applying Corollary1, we have the following:(17)PrX≥1≤e1/μ−11/μ1/μ≤e1−1/tεμ=1etpolyx−1.


## 4.1. The Construction

Lett be an arbitrary positive integer, and n=2t+1. This scheme randomly selects n interpolation points x1,…,xn in a field F and F>n. In addition, we use a HMAC algorithm with secret s∈F. Assume that the adversary can obtain the profit worth d after breaking the RSS. The detailed steps of the RSS scheme are shown in Figure 3.Figure 3
RSS scheme based on smart contract.


## 4.2. Analysis of the Construction

In the malicious model, there are always adversaries colluding to pass the MAC authentication of the protocol with the wrong shares, which makes the RSS cannot reconstruct the secret. In this section, we use the Chernoff bounds [33] to prove that this probability is small.We define a setC, which contains all corrupt parties. There are two types of corrupt parties we define. One type is the active corrupt party, and they will provide the wrong shares, which are represented by set A and A=a. The other type is the passive corrupt party, and they will provide the correct shares, which are represented by set P and P=p. Obviously, t=a+p.In the case ofp≥t/2, even if all active corrupt parties have passed MAC authentication, the Solomon decoding algorithm can still reconstruct the correct secret, so we do not consider this situation. We only pay attention to PrA∩I>0 in the case of p<t/2.LetX be a random variable and a∈R. According to the Markov inequality [34], we have the following:(2)∀l>0,PrX≥a=PrelX≥ela≤EelXela,where MXl=EelX. We compute the Taylor expansion of EelX, and assuming it is convergent:(3)MXlMXl=E1+lX+12l2X2+13l3X3+⋯=∑i=0∞1i!liEXi.The message about distribution can be encoded byEXi. We limit the moment generating function of each Xi to derive the Chernoff bounds.Lemma 1.
Given independent and random variablesX1,X2,…,Xn, where X=∑i=1nXi, then:(4)MXl=∏i=1nMXil.Proof.
(5)MXl=EelX=Eel∑i=1nXi=E∏i=1nelXi=∏i=1nMXil.
Before deriving the Chernoff bounds, we use the Bernoulli trial to complete the following lemma.Lemma 2.
Given a random variableY, and PrY=1=p,PrY=0=1−p, then(6)∀l∈R,MYl=EelY≤epel−1.Proof.
(7)MYl=EelY=p×el+1−p×1=1+pel−1,where y=pel−1, and then:(8)MYl≤epel−1.
From Lemmas1 and 2, we start to derive the Chernoff bounds.Corollary 1.
Given independent and random variablesX1,X2,…,Xn, and X=∑i=1nXi, where PrXi=1=pi,PrXi=0=1−pi, and μ=EX=∑i=1npi, then:(9)∀δ>0,PrX≥1+δμ≤eδ1+δ1+δμ≤eδ−δ2μ.Proof.
(10)MXl=∏i=1nMXix≤∏i=1nepiel−1=eel−1∑i=1npi=eel−1μ.
Leta=1+δμ,l=ln1+δ. Applying (2), we can obtain the following:(11)PrX≥1+δμ≤EelXela=elμel1+δμ.
When0<l<el−1, we have the following:(12)PrX≥1+δμ≤eel−1μel1+δμ=eδ1+δ1+δμ.
Taking the logarithm of thelneδ/1+δ1+δμ, we can obtain the following:(13)μδ−1+δln1+δ.
For anyx>0,a<1+x, there is ln1+x≥ax/1+x, and then:(14)μδ−1+δln1+δ≤δ−δ2μ.Theorem 1.
For any positive integert, any positive integer n = 2t+1, and any HMAC, the (n, t) robust secret sharing scheme has a small probability of failure with:(15)Prfailure<1etpolyx−1.Proof.
Considert corrupt parties as t random variables X1,X2,…Xt. If Xi passes HMAC authentication, Xi=1. Otherwise, Xi=0. PrXi=1=ε,PrXi=0=1−ε. We can obtain the following:(16)μ=EX=∑i=1tε=tε.
Applying Corollary1, we have the following:(17)PrX≥1≤e1/μ−11/μ1/μ≤e1−1/tεμ=1etpolyx−1.


## 5. Security Proof

In this section, we present the secure analysis of the scheme.Theorem 2.
This scheme achieves perfect privacy.Proof.
There is a setC⊂n that contains all the corrupt parties, and C=t. First, we assume that the secret s∈F is randomly distributed and the distributeshare phase is safely executed locally. Our purpose is to prove that the distribution of σi∈C is not related to s. Here, σi=HT,z,si,Ti,keyi.
In our RSS scheme, the secrets can only be reconstructed with more than t participants. For each i∈C, they cannot reconstruct the secret s even if all the corrupt parties join in the collusion. Therefore, si is independent of s. In addition, the values of zi and keyi are selected randomly, so they are also not related to the secret s. The label Ti is generated by the MAC algorithm to verify the integrity of si, so Ti is independent of the shares si because of the nature of “privacy over randomness.” HT is a hash value generated by the IPFS, so it is obviously independent of si. In summary, the privacy of secret s is guaranteed.Theorem 3.
RSS scheme based on smart contract is secure when anyt participants are corrupted.Proof.
The rushing adversary can determine how to change the share of corrupt parties after receiving the share of honest parties. In this study, we implemented a bulletin board on the IPFS to store all tags before the reconstruction phase. The rushing adversary cannot change the tags due to the immutable nature of IPFS. Because the tag cannot be changed, the probability that the rushing adversary passes the share verification phase is negligible if he changes the share. Therefore, our scheme can fight against a rushing adversary.
LetΠ denote the RSS scheme based on smart contract and F denote a function based on smart contract. There is a real-world scenario in which the participants can execute an RSS scheme. We built a simulator Sim that can extract a probabilistic polynomial time (PPT) adversary’s operation in the real world such that REALΠ,A≈IDEALF,Sim. In addition, the adversary A can corrupt any t participants. First, we think that A cannot obtain any information about the shares from the channel between dealer D and other participants in the share distribution phase. The following section will prove the indistinguishability between the ideal world and the real world.
In the reconstruction phase, our scheme uses authenticated private channels. The simulatorSim can extract the view and input of A in the real world and can also simulate the input of honest participants in the real world. There are a set C that contains all the corrupt parties and a set H that contains all the honest parties. The capabilities of Sim are as follows:(i)
For eachi∈H, Sim accesses the smart contract and initiates the transaction RSC⋅submit1. Sim sends the transaction address to Pi and receives HT,Ti,si,keyi. Sim uploads these shares to the smart contract. Similarly, Sim sends transaction RSC⋅submit2 to Pi and receives keyi. Sim uploads keyi to the smart contract.(ii)
For eachi∈C, Sim accesses the smart contract and initiates the transaction RSC⋅submit1. Sim invokes A and internally hands A the transaction address as if it was sent by Pi. Sim outputs whatever A outputs. If A does not upload HT,Ti,si to the Sim before tsubmit1, the smart contract can keep his deposit. Similarly, Sim invokes A and internally hands A the transaction RSC⋅submit2. Sim outputs whatever A outputs. If A does not upload keyi to the smart contract before tsubmit2, the smart contract can keep his deposit.(iii)
For eachi∈n, Sim sends the transaction RSC⋅tagverification to the smart contract. If Ti∉HT, Pi loses his deposit d. Similarly, Sim sends the transaction RSC⋅MACverification to the smart contract. If Ti≠MACkeyi,si, Pi loses his deposit d. If all the above transactions have been executed, then Pi honestly sends the right shares.
In an ideal world, the view of each corrupt party would be the same as that of each corrupt party in the real world due to the open and transparent nature of smart contracts. The privacy of shares is proved. The smart contract is deployed in the blockchain.A cannot tamper with the smart contract and obtain the deducted deposit unless he can construct a new blockchain. Finally, the smart contract outputs the correct share si for i∈I, and the honest parties are able to successfully reconstruct the original secret s using Solomon’s algorithm. We can prove that(18)REALΠ,A≈IDEALF,Sim.


## 6. Performance Analysis

We compare our work with other RSS schemes and show the results in Table2. Shamir [1] first proposed the concept of secret sharing. Cevallos et al. [17] improved the share size and optimized the share size to On+k. However, a participant needs to verify all other participants and also needs to be verified by all other participants in the reconstruction phase, which causes a large communication cost. In 2015, Allison Bishop et al. [18] designed an essentially optimal RSS scheme, whose share size is close to the optimal O˜κ. They innovatively eliminated the linear relationship between the share size and the number of participants, but their scheme cannot fight a rushing adversary. Fehr et al. [19] proposed a RSS scheme that can fight a rushing adversary. Unfortunately, their algorithm needs to start with an honest participant.Table 2
Feature comparison of schemes.
Paper[1][17][18][19]This workShare sizeOnκOn+κO˜κO˜κO˜κRushing adversaryNoYesNoYesYesFairnessNoNoNoNoYesCommunication complexityOn2On2OndOndOnCommunication topologyWe ran our scheme on a local laptop that has the 64-bit Windows system, an Intel (R) Core (TM) i5-9300H CPU (2.40 GHz), and 16 GB of RAM. The scheme uses Solidity to program the smart contract. Solidity is a language that was created to implement smart contract. We compiled the smart contract via Ethereum’s official website and deployed it on the private chain that we created locally.Every step of implementing the smart contract can be considered to be a transaction, which is open and transparent. Before the test, we set the security parameterκ to 128 bits. The parts we tested contain two rounds of the share submission phase, label verification phase, and MAC verification phase. The gas cost of each part is shown in Table 3. We use Figure 4 to vividly show the relationship between the gas cost and the number of participants. The figure shows that the gas cost is linearly related to the number of participants; the more participants there are, the more expensive it is to execute the smart contract.Table 3
Table of gas cost.
Participantm=5m=6m=7m=8m=9m=10submit1350 841421 086491 203561 448631 693701 938submit2245 845295 014344 183393 352442 649491 946Tag verification257 005308 406359 807411 208462 609514 010MAC verification623 926759 801886 2341013 1861139 4191265 852total1477 6171784 3072081 4272379 1942676 3702973 746Figure 4
Gas cost.The time cost of each part is shown in Table4. It takes approximately 170 ms for label verification and approximately 300 ms for MAC verification. Similarly, we also use Figure 5 to illustrate the relationship between the time cost and the number of participants. The figure shows that the time cost is linearly related to the number of participants; the more participants there are, the more time it takes to execute the smart contract.Table 4
Table of time cost (ms).
Participantm=5m=6m=7m=8m=9m=10submit1112113281379149517521916submit2668881973114213251517Tag verification93010831215137415361728MAC verification163319272285254327873163reconstruction0.310.460.520.680.781.09Figure 5
Time cost.


## 7. Conclusion

We proposed a new RSS scheme based on smart contracts that ensure fairness and decentralization. Compared with previous schemes, the communication complexity of our scheme is reduced toOn. Out scheme is secure against a rushing adversary. The previous discussion shows that our scheme can finally reconstruct the correct secret by means of the Solomon decoding algorithm even if any corrupt parties (less than t) submit the wrong shares.Unfortunately, the cost of executing smart contracts is expensive when the number of shares is large. The scheme is applicable to the situation where the number of shares is less than215. Our work can be improved as follows. We can extend RSS to hierarchical robust secret sharing scheme, which allows secret shares to be distributed to different levels of parties [35]. What is more, the RSS scheme can be applied in the situation where the number of shares is large [36]. Also, we can apply RSS in other fields such as robust secret image sharing and threshold private set intersection [37, 38].



---

*Source: 7926057-2022-05-02.xml*