# A New Efficient and Secure Secret Reconstruction Scheme (SSRS) with Verifiable Shares Based on a Symmetric Bivariate Polynomial

Authors: Chingfang Hsu; Lein Harn; Shan Wu; Lulu Ke
Journal: Mobile Information Systems
 (2020)

---

## Abstract

Secret sharing (SS) schemes have been widely used in secure computer communications systems. Recently, a new type of SS scheme, called the secure secret reconstruction scheme (SSRS), was proposed, which ensures that the secret can only be recovered by participants who present valid shares. In other words, if any outside adversary participated in the secret reconstruction without knowing any valid share, the secret cannot be recovered by anyone including the adversary. However, the proposed SSRS can only prevent an active attacker from obtaining the recovered secret, but cannot prevent a passive attacker from obtaining the secret since exchange information among participants is unprotected. In this paper, based on bivariate polynomials, we propose a novel design for the SSRS that can prevent both active and passive attackers. Furthermore, we propose a verification scheme which can verify all shares at once, i.e., it allows all shareholders to efficiently verify that their shares obtained from the dealer are generated consistently without revealing their shares and the secret. The proposed scheme is really attractive for efficient and secure secret reconstruction in communications systems.


---

## Body

## 1. Introduction

Secret sharing (SS) schemes have been widely used in secure computer communications systems [1–8]. Blakley [9] and Shamir [10] independently introduced the concept of the secret sharing in 1979. In a t,n secret sharing (SS) scheme, the secret s is divided into n shares by a dealer and is shared among n shareholders such that any t or more than t shares can reconstruct the secret, but fewer than t shares cannot obtain any information about the secret s.Shamir’st,n SS scheme used a linear polynomial. But, in practical applications, possible threats make Shamir’s secret reconstruction scheme very complicated, especially when there are more than t participants in the secret reconstruction. One straightforward approach to ensure that all participants are shareholders is to use user authentication scheme among all participants at the beginning of the secret reconstruction. This approach is a time-consuming process since user authentication can authenticate one user at a time. In fact, only the dealer needs to know who is the shareholder initially. In the secret reconstruction, shareholders do not need to know each other. The secret can only be reconstructed successfully if all shares are legitimate. If all shares are legitimate shares, the secret can be reconstructed. On the other hand, if there is any illegitimate share, the secret cannot be reconstructed.Recently, a new type of SS scheme called the secure secret reconstruction scheme [11] (SSR), which ensures that the secret can only be recovered by participants who present valid shares, has been developed. However, the scheme can only prevent an active attacker from obtaining the recovered secret, but cannot prevent a passive attacker from obtaining the secret since exchange information among participants is unprotected.Chor et al. [12] proposed the notion of verifiable secret sharing (VSS) in which shareholders can verify that their shares are valid without revealing the secrecy of their shares and the secret. Based on security assumptions, there are two different types of VSSs, schemes that are computationally secure and unconditionally secure. Feldman [13] and Pedersen [14] VSSs are based on cryptographic commitment schemes. The security of Feldman’s VSS is on the hardness of solving discrete logarithm, while the privacy of Pedersen’s VSS is unconditionally secure and the correctness of the shares is based on a computational assumption. Benaloh [15] proposed an interactive VSS which is unconditionally secure. Stinson et al. [16] proposed an unconditionally secure VSS, and Patra et al. [17] proposed a generalized VSS scheme. Stadler [18] proposed the first publicly verifiable secret sharing (PVSS) scheme which allows each shareholder to verify the validity of all shares. Most noninteractive VSSs [13, 14] can only verify the validity of his/her own share, but not of other shareholders’ shares. PVSSs [18, 19] use interactive proofs of knowledge. These proofs can be made noninteractive using the Fiat–Shamir technique [20]. The security of Schoenmaker’s PVSS [21] is based on the discrete-logarithm problem. The scheme is quite simple, but some noninteractive zero-knowledge proofs have been used. Peng and Wang’s PVSS [22] uses a linear code, and Ruiz and Villar’s PVSS [23] uses Pailler’s cryptosystem [24]. There are noninteractive PVSSs based on bilinear pairing [25, 26]. We can see that most of these VSSs can only verify one share at a time and are computationally secure, which are based on computational assumptions.In summary, let us briefly clarify differences among the SSR [11], VSS, and Changeable secret sharing scheme [27, 28] (TCSS). These three different schemes have different security features. According to Harn [11], in SSR, the secret can only be reconstructed successfully by all participated shareholders who contributed valid shares. In other words, SSR requires every participated shareholder to contribute a share and the secret cannot be reconstructed if there are fewer than the number of participants in the process. Note that this number may be larger than the threshold. In a VSS, shareholders can verify that their shares are generated consistently by a dealer without revealing their shares and the secret. In a TCSS, the threshold can be dynamically changed in the process.The motivation of our paper is to construct an efficient and secure secret reconstruction scheme with verifiable shares. The SSRS can prevent both active and passive attackers at the same time. The scheme is unconditionally secure and can verify all shares at once. Our design is based on symmetric bivariate polynomials. The primary reason to adopt symmetric bivariate polynomials is that shares generated by a symmetric bivariate polynomial can be used to (a) verify all shares at once, (b) recover the secret, and (c) establish pairwise secret keys between shareholders to protect the exchange information in the secret reconstruction. There is no additional user authentication or key distribution needed. Thus, it is very efficient.Following this line of research, in this paper, we propose a novel design for an efficient and secure secret reconstruction scheme with verifiable shares, where the SSRS can prevent both active and passive attackers. At the same time, our VSS allows all shareholders to verify that their shares obtained from the dealer are valid without revealing their shares and the secret, where shareholders just verify that shares are generated by a symmetric bivariate polynomial consistently. Here, we summarize the contributions of our paper.(i)
A secure secret reconstruction scheme based on symmetric bivariate polynomials is proposed(ii)
The proposed secure reconstruction scheme can prevent both active and passive outside attacks(iii)
An efficient VSS which verifies all shares generated by a symmetric polynomial consistently at once is proposedThe rest of this paper is organized as follows: In the next section, we introduce some preliminaries. In section3, we describe models of our proposed schemes including scheme description, adversaries, and properties. We propose our secure secret reconstruction with verifiable shares in section 4. The conclusion is included in section 5.


## 2. Review of SSs Based on Polynomials

In Shamir’st,n SS [9], the dealer selects a univariate polynomial, fx, with degree t−1 and f0=s where s is the secret. The dealer generates shares, fximodp,i=1,2,…,n for shareholders, where p is a prime with p>s and xi is the public information associated with each shareholder, Ui. Each share, fxi, is an integer in GFp Shamir’s t,n SS satisfies security requirements of a t,n SS. That is, (a) with t or more than t shares can reconstruct the secret and (b) with fewer than t shares cannot obtain any information of the secret. Shamir’s SS is unconditionally secure.In Shamir’st,n SS, shareholders cannot verify the validity of their shares obtained from the dealer. In 1985, Chor et al. [12] extended the notion of SS and proposed the first verifiable secret sharing (VSS). Verifiability is the property of a VSS which allows shareholders to verify their shares. Invalid shares may be caused either by the dealer during share generation or by channel noise during transmission. VSS is performed by shareholders after receiving their shares from the dealer and before using their shares to reconstruct the secret. If invalid shares have been detected, shareholders can request the dealer to regenerate new shares. There are many t,n VSSs [29–34] using bivariate polynomials, denoted them as BVSSs. A bivariate polynomial with degree t−1 can be represented as Fx,y=∑i=0t−1∑j=0t−1ai,jxiyjnodp where ai,j∈GFp. We can classify BVSSs into two types, the symmetric BVSSs, denoted as SBVSSs [30, 32, 34], and the asymmetric BVSSs, denoted as ABVSSs, [29, 31, 33]. If the coefficients satisfy ai,j=aj,i,∀i,j∈0,t−1, it is a symmetric bivariate polynomial. Shares generated by a bivariate polynomial can be used to establish pairwise keys between any pair of shareholders. In all t,n SBVSSs, the dealer selects a bivariate polynomial, Fx,y with degree t−1 and F0,0=s where s is the secret. The dealer generates shares, Fxi,ymodp,i=1,2,…,n, for shareholders, where p is a prime with p>s and xi is the public information associated with each shareholder, Ui. Each share, Fxi,y is a univariate polynomial with degree t−1. Note that shares generated in an SBVSS satisfy Fxi,xj=Fxj,xi,∀i,j∈0,t−1 the pairwise key, and Fxi,xj=Fxj,xi can be established between the pair of shareholders, Ui and Uj. In a similar way, in a ABVSS, the dealer generates a pair of shares, Fxi,ymodp and Fx,ximodp,i=1,2,…,n, for each shareholder and the pairwise secret key, Fxi,xj or Fxj,xi, can also be established between the pair of shareholders, Ui and Uj.


## 3. Model

In this section, we describe the model of the proposed schemes including scheme description, adversaries, and properties.


### 3.1. Scheme Description

We propose two schemes in this paper.


#### 3.1.1. Scheme for Verification of Shares

A VSS enables shareholders to verify that their shares of a∀i,j∈0,t−1 SS are generated by the dealer consistently. In other words, without revealing the secret and the shares, shareholders can verify that any subset of t or more than t shares deﬁnes the secret, but any subset of fewer than t shares cannot define the secret. Benaloh [15] presented a notion of t-consistency and uses it to define the objective of a VSS. We include the notion given below.Definition 1.
t-consistency: a set of n shares is said to be t-consistent if any subset of t of the n shares defines the same secret.
Harn and Lin [35] modified the definition of t-consistency and introduce a new notion, called strong t-consistency, which can satisfy the security requirements of a t,n SS.Definition 2.
Strongt-consistency: a set of n shares are said to be strong t-consistent (i.e., t<n) if (a) any subset of t or more than t of the n shares defines the same secret and (b) any subset of fewer than t of the n shares cannot define the same secret.
It is obvious that, in a polynomial-based SS, shares generated by a polynomial having exactt degree are strong t-consistent. Shares have the property of strong t-consistency satisfy the security requirements of a t,n SS. Verifying the property of strong t-consistency of shares is one of the objectives of our proposed VSS. In our proposed secure secret reconstruction, shares of shareholders are generated by a symmetric bivariate polynomial. Thus, shares can not only be used to recover the secret but also be used to establish pairwise secret keys between shareholders in the secret reconstruction. The second objective of our proposed VSS is to verify that shares are generated by a symmetric bivariate polynomial.
We assume that there aren shareholders, U,i for i=1,2,…,m participated in the VSS. These shareholders want to make sure that their shares, si, for i=1,2,…,m obtained from the dealer are strong t-consistent and generated by a symmetric bivariate polynomial. In the proposed VSS, each shareholder computes ci=Fsi as his/her released value, where F is a public function. There is an algorithm, VSS, which allows users to verify that all released values are valid, i.e.,(1)VSS∀ci=Fsi|i=1,2,…,n=0⟶exists invalid sharesi;1⟶all are valid shares.
The proposed VSS is different from most other VSSs which verify one share at a time, but our VSS verifies all shares at once. There are only two possible outcomes of our proposed VSS, that are, either all shares are strongt-consistent and generated by a symmetric bivariate polynomial or there are inconsistent shares. Thus, the proposed VSS is sufficient if all shares are strong t-consistent and generated by a symmetric bivariate polynomial; however, if there are inconsistent shares, it can be treated as a preprocess before applying other VSS to identify invalid shares.


#### 3.1.2. Scheme for Secure Secret Reconstruction

First, we present the notion of a secure secret reconstruction scheme as defined in [11].Definition 3.
Secure secret reconstruction scheme [11]: This scheme ensures that the secret can only be recovered by participants who present valid shares. In other words, if any outside adversary participated in the secret reconstruction, the adversary cannot obtain the secret.
Shamir’s secret reconstruction is a secure secret reconstruction if there are exactt participants since only if t valid shares of participants can recover the secret. When there are more than t participants in the secret reconstruction, it can cause a security. Since only t shares are needed to recover the secret, the adversary can still obtain the secret in the secret reconstruction. Employing a user authentication/VSS scheme in prior of the secret reconstruction can solve the security problem. However, this approach adds additional complexity. A secure secret reconstruction scheme is proposed in [11]. In the scheme, Lagrange components, which are linear combination of shares, are used to reconstruct the secret. The scheme uses the Lagrange component to protect the privacy of shares so the adversary cannot take advantage by releasing value last in the secret reconstruction. This scheme is a simple modification of Shamir’s t,n SS scheme. However, the scheme can only prevent active attackers to obtain the recovered secret, but cannot prevent passive attackers. Our proposed SSRS can prevent both active and passive attackers.


### 3.2. Adversaries

The adversaries in the secret reconstruction can be classified into two types, the outside adversaries and the inside adversaries. The outside adversaries are attackers who do not have any valid share generated by the dealer. There are two different types of attacks associated with outside adversaries, the active and passive attacks. The active attackers impersonate to be legitimate shareholders participating in the secret reconstruction. On the other hand, the passive attackers wiretapped the communication channels to obtain exchange information among participants in the secret reconstruction. If exchange information in the secret reconstruction is not protected in [11], the recovered secret can also be available to the attackers. In this paper, we propose a secure secret reconstruction scheme that can prevent both active and passive attackers. In our proposed scheme, shares of shareholders can not only be used to recover the secret but also used to protect the exchange information in the secret reconstruction.The inside adversaries are shareholders who own valid shares obtained from the dealer. The inside attackers may collude together to recover the secret by themselves. We analyze the security whethert−1 inside adversaries can collude together to reveal the secret. Furthermore, we also need to assure that, in the verification of shares, shareholders cannot obtain other shareholders’ shares and the secret.


### 3.3. Properties

We discuss properties of two schemes separately.


#### 3.3.1. Scheme for Verification of Shares

We propose a VSS with the following properties:Correctness: the outcome of this proposed VSS is positive if all shares aret-threshold consistent; otherwise, there are inconsistent shares.Efficiency: if the outcome of the proposed scheme is negative, the proposed VSS can be treated as a preprocess of other VSS and used to identify inconsistent shares. Thus, the proposed VSS must be efficient.Security: the VSS must be able to protect the secrecy of shares and the secret in verification.


#### 3.3.2. Scheme for Secure Secret Reconstruction

We propose a secure secret reconstruction scheme with the following properties:Correctness: the scheme can satisfy the objective as specified in Definition2.Efficiency: shares of shareholders obtained initially from a dealer can not only be used to recover the secret but also be used to establish pairwise shared keys of shareholders to protect the exchange information. There is no additional user authentication or key distribution needed.Security: the scheme must satisfy following security requirements.(a)
Against active outside attack- the scheme can prevent any outsider to impersonate a shareholder participating in the reconstruction to obtain the secret(b)
Against passive outside attack- the scheme can prevent any outsider to obtain the secret by monitoring the communication channels(c)
Against colluded inside attack- the scheme can prevent up tot−1 colluded insiders to recover the secret


## 3.1. Scheme Description

We propose two schemes in this paper.


### 3.1.1. Scheme for Verification of Shares

A VSS enables shareholders to verify that their shares of a∀i,j∈0,t−1 SS are generated by the dealer consistently. In other words, without revealing the secret and the shares, shareholders can verify that any subset of t or more than t shares deﬁnes the secret, but any subset of fewer than t shares cannot define the secret. Benaloh [15] presented a notion of t-consistency and uses it to define the objective of a VSS. We include the notion given below.Definition 1.
t-consistency: a set of n shares is said to be t-consistent if any subset of t of the n shares defines the same secret.
Harn and Lin [35] modified the definition of t-consistency and introduce a new notion, called strong t-consistency, which can satisfy the security requirements of a t,n SS.Definition 2.
Strongt-consistency: a set of n shares are said to be strong t-consistent (i.e., t<n) if (a) any subset of t or more than t of the n shares defines the same secret and (b) any subset of fewer than t of the n shares cannot define the same secret.
It is obvious that, in a polynomial-based SS, shares generated by a polynomial having exactt degree are strong t-consistent. Shares have the property of strong t-consistency satisfy the security requirements of a t,n SS. Verifying the property of strong t-consistency of shares is one of the objectives of our proposed VSS. In our proposed secure secret reconstruction, shares of shareholders are generated by a symmetric bivariate polynomial. Thus, shares can not only be used to recover the secret but also be used to establish pairwise secret keys between shareholders in the secret reconstruction. The second objective of our proposed VSS is to verify that shares are generated by a symmetric bivariate polynomial.
We assume that there aren shareholders, U,i for i=1,2,…,m participated in the VSS. These shareholders want to make sure that their shares, si, for i=1,2,…,m obtained from the dealer are strong t-consistent and generated by a symmetric bivariate polynomial. In the proposed VSS, each shareholder computes ci=Fsi as his/her released value, where F is a public function. There is an algorithm, VSS, which allows users to verify that all released values are valid, i.e.,(1)VSS∀ci=Fsi|i=1,2,…,n=0⟶exists invalid sharesi;1⟶all are valid shares.
The proposed VSS is different from most other VSSs which verify one share at a time, but our VSS verifies all shares at once. There are only two possible outcomes of our proposed VSS, that are, either all shares are strongt-consistent and generated by a symmetric bivariate polynomial or there are inconsistent shares. Thus, the proposed VSS is sufficient if all shares are strong t-consistent and generated by a symmetric bivariate polynomial; however, if there are inconsistent shares, it can be treated as a preprocess before applying other VSS to identify invalid shares.


### 3.1.2. Scheme for Secure Secret Reconstruction

First, we present the notion of a secure secret reconstruction scheme as defined in [11].Definition 3.
Secure secret reconstruction scheme [11]: This scheme ensures that the secret can only be recovered by participants who present valid shares. In other words, if any outside adversary participated in the secret reconstruction, the adversary cannot obtain the secret.
Shamir’s secret reconstruction is a secure secret reconstruction if there are exactt participants since only if t valid shares of participants can recover the secret. When there are more than t participants in the secret reconstruction, it can cause a security. Since only t shares are needed to recover the secret, the adversary can still obtain the secret in the secret reconstruction. Employing a user authentication/VSS scheme in prior of the secret reconstruction can solve the security problem. However, this approach adds additional complexity. A secure secret reconstruction scheme is proposed in [11]. In the scheme, Lagrange components, which are linear combination of shares, are used to reconstruct the secret. The scheme uses the Lagrange component to protect the privacy of shares so the adversary cannot take advantage by releasing value last in the secret reconstruction. This scheme is a simple modification of Shamir’s t,n SS scheme. However, the scheme can only prevent active attackers to obtain the recovered secret, but cannot prevent passive attackers. Our proposed SSRS can prevent both active and passive attackers.


## 3.1.1. Scheme for Verification of Shares

A VSS enables shareholders to verify that their shares of a∀i,j∈0,t−1 SS are generated by the dealer consistently. In other words, without revealing the secret and the shares, shareholders can verify that any subset of t or more than t shares deﬁnes the secret, but any subset of fewer than t shares cannot define the secret. Benaloh [15] presented a notion of t-consistency and uses it to define the objective of a VSS. We include the notion given below.Definition 1.
t-consistency: a set of n shares is said to be t-consistent if any subset of t of the n shares defines the same secret.
Harn and Lin [35] modified the definition of t-consistency and introduce a new notion, called strong t-consistency, which can satisfy the security requirements of a t,n SS.Definition 2.
Strongt-consistency: a set of n shares are said to be strong t-consistent (i.e., t<n) if (a) any subset of t or more than t of the n shares defines the same secret and (b) any subset of fewer than t of the n shares cannot define the same secret.
It is obvious that, in a polynomial-based SS, shares generated by a polynomial having exactt degree are strong t-consistent. Shares have the property of strong t-consistency satisfy the security requirements of a t,n SS. Verifying the property of strong t-consistency of shares is one of the objectives of our proposed VSS. In our proposed secure secret reconstruction, shares of shareholders are generated by a symmetric bivariate polynomial. Thus, shares can not only be used to recover the secret but also be used to establish pairwise secret keys between shareholders in the secret reconstruction. The second objective of our proposed VSS is to verify that shares are generated by a symmetric bivariate polynomial.
We assume that there aren shareholders, U,i for i=1,2,…,m participated in the VSS. These shareholders want to make sure that their shares, si, for i=1,2,…,m obtained from the dealer are strong t-consistent and generated by a symmetric bivariate polynomial. In the proposed VSS, each shareholder computes ci=Fsi as his/her released value, where F is a public function. There is an algorithm, VSS, which allows users to verify that all released values are valid, i.e.,(1)VSS∀ci=Fsi|i=1,2,…,n=0⟶exists invalid sharesi;1⟶all are valid shares.
The proposed VSS is different from most other VSSs which verify one share at a time, but our VSS verifies all shares at once. There are only two possible outcomes of our proposed VSS, that are, either all shares are strongt-consistent and generated by a symmetric bivariate polynomial or there are inconsistent shares. Thus, the proposed VSS is sufficient if all shares are strong t-consistent and generated by a symmetric bivariate polynomial; however, if there are inconsistent shares, it can be treated as a preprocess before applying other VSS to identify invalid shares.


## 3.1.2. Scheme for Secure Secret Reconstruction

First, we present the notion of a secure secret reconstruction scheme as defined in [11].Definition 3.
Secure secret reconstruction scheme [11]: This scheme ensures that the secret can only be recovered by participants who present valid shares. In other words, if any outside adversary participated in the secret reconstruction, the adversary cannot obtain the secret.
Shamir’s secret reconstruction is a secure secret reconstruction if there are exactt participants since only if t valid shares of participants can recover the secret. When there are more than t participants in the secret reconstruction, it can cause a security. Since only t shares are needed to recover the secret, the adversary can still obtain the secret in the secret reconstruction. Employing a user authentication/VSS scheme in prior of the secret reconstruction can solve the security problem. However, this approach adds additional complexity. A secure secret reconstruction scheme is proposed in [11]. In the scheme, Lagrange components, which are linear combination of shares, are used to reconstruct the secret. The scheme uses the Lagrange component to protect the privacy of shares so the adversary cannot take advantage by releasing value last in the secret reconstruction. This scheme is a simple modification of Shamir’s t,n SS scheme. However, the scheme can only prevent active attackers to obtain the recovered secret, but cannot prevent passive attackers. Our proposed SSRS can prevent both active and passive attackers.


## 3.2. Adversaries

The adversaries in the secret reconstruction can be classified into two types, the outside adversaries and the inside adversaries. The outside adversaries are attackers who do not have any valid share generated by the dealer. There are two different types of attacks associated with outside adversaries, the active and passive attacks. The active attackers impersonate to be legitimate shareholders participating in the secret reconstruction. On the other hand, the passive attackers wiretapped the communication channels to obtain exchange information among participants in the secret reconstruction. If exchange information in the secret reconstruction is not protected in [11], the recovered secret can also be available to the attackers. In this paper, we propose a secure secret reconstruction scheme that can prevent both active and passive attackers. In our proposed scheme, shares of shareholders can not only be used to recover the secret but also used to protect the exchange information in the secret reconstruction.The inside adversaries are shareholders who own valid shares obtained from the dealer. The inside attackers may collude together to recover the secret by themselves. We analyze the security whethert−1 inside adversaries can collude together to reveal the secret. Furthermore, we also need to assure that, in the verification of shares, shareholders cannot obtain other shareholders’ shares and the secret.


## 3.3. Properties

We discuss properties of two schemes separately.


### 3.3.1. Scheme for Verification of Shares

We propose a VSS with the following properties:Correctness: the outcome of this proposed VSS is positive if all shares aret-threshold consistent; otherwise, there are inconsistent shares.Efficiency: if the outcome of the proposed scheme is negative, the proposed VSS can be treated as a preprocess of other VSS and used to identify inconsistent shares. Thus, the proposed VSS must be efficient.Security: the VSS must be able to protect the secrecy of shares and the secret in verification.


### 3.3.2. Scheme for Secure Secret Reconstruction

We propose a secure secret reconstruction scheme with the following properties:Correctness: the scheme can satisfy the objective as specified in Definition2.Efficiency: shares of shareholders obtained initially from a dealer can not only be used to recover the secret but also be used to establish pairwise shared keys of shareholders to protect the exchange information. There is no additional user authentication or key distribution needed.Security: the scheme must satisfy following security requirements.(a)
Against active outside attack- the scheme can prevent any outsider to impersonate a shareholder participating in the reconstruction to obtain the secret(b)
Against passive outside attack- the scheme can prevent any outsider to obtain the secret by monitoring the communication channels(c)
Against colluded inside attack- the scheme can prevent up tot−1 colluded insiders to recover the secret


## 3.3.1. Scheme for Verification of Shares

We propose a VSS with the following properties:Correctness: the outcome of this proposed VSS is positive if all shares aret-threshold consistent; otherwise, there are inconsistent shares.Efficiency: if the outcome of the proposed scheme is negative, the proposed VSS can be treated as a preprocess of other VSS and used to identify inconsistent shares. Thus, the proposed VSS must be efficient.Security: the VSS must be able to protect the secrecy of shares and the secret in verification.


## 3.3.2. Scheme for Secure Secret Reconstruction

We propose a secure secret reconstruction scheme with the following properties:Correctness: the scheme can satisfy the objective as specified in Definition2.Efficiency: shares of shareholders obtained initially from a dealer can not only be used to recover the secret but also be used to establish pairwise shared keys of shareholders to protect the exchange information. There is no additional user authentication or key distribution needed.Security: the scheme must satisfy following security requirements.(a)
Against active outside attack- the scheme can prevent any outsider to impersonate a shareholder participating in the reconstruction to obtain the secret(b)
Against passive outside attack- the scheme can prevent any outsider to obtain the secret by monitoring the communication channels(c)
Against colluded inside attack- the scheme can prevent up tot−1 colluded insiders to recover the secret


## 4. The Proposed Schemes

In Shamir’st,n SS, additional key establishment protocol is needed to protect shares in the secret reconstruction; otherwise, any nonshareholders can also recover the secret. Thus, Shamir’s t,n SS is not a protected secret sharing scheme. In this section, we proposed a t,n SS using a bivariate polynomial. There is one major difference between shares generated by a univariate polynomial and by a bivariate polynomial. The shares generated by a univariate polynomial are integers in GFp but shares generated by a bivariate polynomial are univariate polynomials.


### 4.1. Algorithms

We illustrate this scheme in Figure1, and a concrete instantiation for Figure 1 is given in Figure 2.Figure 1
Share generation.Figure 2
Concrete instantiation for Figure1.From secret sharing homomorphism, we know that the additive sum of shares of each shareholder is a share on the additive sum of polynomials,F1xi,y+F2xi,ymodp, with F10,0+F20,0=s. Thus, in the secret reconstruction scheme, the additive sum of shares of each shareholder is used to reconstruct the secret. The objective of our proposed VSS is to verify that all additive sums of two shares of each shareholder are generated by a polynomial satisfying two conditions: (a) the polynomial has h−1 degree and (b) the polynomial is a symmetric polynomial. We illustrate this scheme in Figure 3, and a concrete instantiation for Figure 3 is given in Figure 4.Figure 3
Verification of shares.Figure 4
Concrete instantiation for Figure3.Assume thatui.e.,t≤u≤n shareholders, Uv1,Uv2,…,Uvu, want to reconstruct the secret. We illustrate this scheme in Figure 5, and a concrete instantiation for Figure 5 is given in Figure 6.Figure 5
Secure secret reconstruction.Figure 6
Concrete instantiation for Figure5.


### 4.2. Property Analysis

#### 4.2.1. Scheme for Verification of Shares

Correctness: from secret sharing homomorphism, we know that additive shareviy of each shareholder is a share on the polynomial, F1x,y+αF2x,ymodp. Since polynomials F1x,yandF2x,y are both symmetric polynomials having h−1 degree each, the additive sum of their polynomials, Gx,y=F1x,y+αF2x,ymodp, must also be a symmetric polynomial having h−1 degree. On the other hand, if Gx,y=F1x,y+αF2x,ymodp is a symmetric polynomial having h−1 degree, then it is most likely that the polynomial F1x,y+F2x,ymodp is also a symmetric polynomial having h−1 degree. This result achieves our VSS objectives.Efficiency: our VSS is very efficient since it verifies all shares of secret at once using polynomial interpolation.Security: in step 2, each released value of shareholder isviy=syi,1+αsyi,2modp. It is impossible to obtain shares syi,1andsyi,2modp from the released value. Furthermore, in step 3, the recovered polynomial, Gx,y=F1x,y+αF2x,ymodp, does not reveal the secrecy of individual polynomials, F1x,yandF2x,ymodp. Thus, the secret cannot be obtained in this VSS scheme.


#### 4.2.2. Scheme for Secure Secret Reconstruction

Correctness: according to the Lagrange interpolation formula, we can get∑i=1usviy∏l=1,l≠iux−xvl/xvi−xvlmodp=F1x,y+F2x,y. Thus, in step 4 of scheme 3, we get ∑i=1uwvimodp=∑i=1usvi0∏l=1,l≠iu−xvl/xvi−xvlmodp=F10,0+F20,0=sThis concludes that, for any qualified subset, A=Uv1,Uv2,…,Uvu∈Γ of shareholders can work together to recover the secret. Hence, it holds that Hs|A=0.Efficiency: in this scheme, each share,si,jy,j∈1,2, is a univariate polynomial with degree h−1 Thus, each shareholder needs to store 2h coefficients of a univariate polynomial. The memory storage of each shareholder is 2hlog2p bits, where p is the modulus. Horner’s rule [24] can be used to evaluate polynomials. In the following discussion, we show the cost for computing wvi=svi0∏l=1,l≠iu−xvl/xvi−xvlmodp in the secret reconstruction. From Horner’s rule, evaluating a polynomial of degree h−1 needs h−1 multiplications and h additions. Since multiplication takes more time than addition, the performance is only addressed to the number of multiplications needed. The computational cost in step 2 of scheme 3 to compute wvi is to evaluate one polynomial. The computational cost in step 1 of scheme 3 to compute pairwise shared keys, ki,j=svixvj,j=1,2,…,u,j≠i, is to evaluate u−1 polynomials, where u is the number of shareholders participated in the secret reconstruction. Overall, the computational cost to reconstruct the secret of each shareholder is to compute uh multiplications.Security: in this section, we will first prove that the scheme meets the security requirements as discussed in Section3.3.Against both active and passive inside attacks: in the proposed scheme, the information exchanged among shareholders is encrypted using pairwise shared keys. Since a nonshareholder does not own any share generated by the dealer, the nonshareholder cannot decrypt any cipher text. Thus, the recovered secret is not available to the nonshareholder. In other words, the nonshareholder obtains no information ons.Against colluded inside attackTheorem 1.
Withh=t, the proposed scheme satisfies both security requirements of a t,n SS. That is, (a) with t or more than t shares can recover the secret and (b) with fewer than t shares cannot recover the secret.Proof.
Since polynomialsF1x,y=∑i=0h−1∑j=0h−1ai,jxiyjnodp and F2x,y=∑i=0h−1∑j=0h−1bi,jxiyjnodp are symmetric polynomials with ai,j=aj,iandbi,j=bj,i,∀i,j∈0,h−1 containing hh+1/2 different coefficients in each polynomial, there are hh+1 different coefficients in total. In the proposed scheme, each share, si,jy,j∈1,2, is a univariate polynomial with degree h−1. In other words, each shareholder can use his shares, si,1yandsi,2y, to establish 2h linearly independent equations in terms of the coefficients of the polynomials.
Witht−1 colluded shareholders together, it can establish 2ht−1 equations; at the same time, their shares contain 2C2t−1=t−1t−2 points on the bivariate polynomial. Thus, these t−1 colluded shares can be used to establish 2ht−1−t−1t−2 linear independent equations in terms of the coefficients of the bivariate polynomial. If hh+1>2ht−1−t−1t−2, these t−1 colluded shareholders cannot recover the bivariate polynomials. Since h=t, as specified in the share generation, we have hh+1>2ht−1−t−1t−2. Hence, any t−1 colluded shareholders cannot recover the secret. This conclusion is obtained without making any computational assumption.
On the other hand, when there aret or more than t shareholders trying to recover the secret, with their shares together, they can establish 2ht equations; at the same time, their shares contain 2C2t=tt−1 points on the bivariate polynomial. Thus, their shares can be used to establish 2ht−2C2t linear independent equations in terms of the coefficients of the bivariate polynomials. If 2ht−2C2t≥hh+1, these t or more than t shareholders can recover the bivariate polynomials. Since h=t, as specified in the share generation, we have 2ht−2C2t≥hh+1. Hence, any t or more than t shareholders can recover the secret.Corollary 1.
For any given threshold,t, the degree of the symmetric polynomial, Fx,y, can be t.Proof.
The proof is straightforward.


### 4.3. Comparison

Since the proposed schemes are based on bivariate polynomials with multiple features, our comparison with other schemes is a high-level comparison only. In a whole, compared with previous related schemes, our proposed VSS and SSRS schemes have the following advantages:(1)
The proposed secure secret reconstruction scheme with verifiable shares is unconditionally secure, which is based on symmetric bivariate polynomials.(2)
The proposed VSS is different from most other VSSs which verify one share at a time; but our VSS verifies all shares at once. There are only two possible outcomes of our proposed VSS, that is, either all shares are strongt-consistent and generated by a symmetric bivariate polynomial or there are inconsistent shares. Thus, the proposed VSS is sufficient if all shares are strong t-consistent and generated by a symmetric bivariate polynomial; however, if there are inconsistent shares, it can be treated as a preprocess before applying other VSS to identify invalid shares.(3)
Previous SSRS can only prevent active attackers to obtain the recovered secret, but cannot prevent passive attackers. Our proposed SSRS can prevent both active and passive attackers.(4)
In our proposed SSRS, shares of shareholders are generated by a symmetric bivariate polynomial. The shares generated by a symmetric bivariate polynomial can be used to (a) verify all shares at once, (b) recover the secret, and (c) establish pairwise secret keys between shareholders to protect the exchange information in the secret reconstruction. There is no additional user authentication or key distribution needed. Thus, it is very efficient.


## 4.1. Algorithms

We illustrate this scheme in Figure1, and a concrete instantiation for Figure 1 is given in Figure 2.Figure 1
Share generation.Figure 2
Concrete instantiation for Figure1.From secret sharing homomorphism, we know that the additive sum of shares of each shareholder is a share on the additive sum of polynomials,F1xi,y+F2xi,ymodp, with F10,0+F20,0=s. Thus, in the secret reconstruction scheme, the additive sum of shares of each shareholder is used to reconstruct the secret. The objective of our proposed VSS is to verify that all additive sums of two shares of each shareholder are generated by a polynomial satisfying two conditions: (a) the polynomial has h−1 degree and (b) the polynomial is a symmetric polynomial. We illustrate this scheme in Figure 3, and a concrete instantiation for Figure 3 is given in Figure 4.Figure 3
Verification of shares.Figure 4
Concrete instantiation for Figure3.Assume thatui.e.,t≤u≤n shareholders, Uv1,Uv2,…,Uvu, want to reconstruct the secret. We illustrate this scheme in Figure 5, and a concrete instantiation for Figure 5 is given in Figure 6.Figure 5
Secure secret reconstruction.Figure 6
Concrete instantiation for Figure5.


## 4.2. Property Analysis

### 4.2.1. Scheme for Verification of Shares

Correctness: from secret sharing homomorphism, we know that additive shareviy of each shareholder is a share on the polynomial, F1x,y+αF2x,ymodp. Since polynomials F1x,yandF2x,y are both symmetric polynomials having h−1 degree each, the additive sum of their polynomials, Gx,y=F1x,y+αF2x,ymodp, must also be a symmetric polynomial having h−1 degree. On the other hand, if Gx,y=F1x,y+αF2x,ymodp is a symmetric polynomial having h−1 degree, then it is most likely that the polynomial F1x,y+F2x,ymodp is also a symmetric polynomial having h−1 degree. This result achieves our VSS objectives.Efficiency: our VSS is very efficient since it verifies all shares of secret at once using polynomial interpolation.Security: in step 2, each released value of shareholder isviy=syi,1+αsyi,2modp. It is impossible to obtain shares syi,1andsyi,2modp from the released value. Furthermore, in step 3, the recovered polynomial, Gx,y=F1x,y+αF2x,ymodp, does not reveal the secrecy of individual polynomials, F1x,yandF2x,ymodp. Thus, the secret cannot be obtained in this VSS scheme.


### 4.2.2. Scheme for Secure Secret Reconstruction

Correctness: according to the Lagrange interpolation formula, we can get∑i=1usviy∏l=1,l≠iux−xvl/xvi−xvlmodp=F1x,y+F2x,y. Thus, in step 4 of scheme 3, we get ∑i=1uwvimodp=∑i=1usvi0∏l=1,l≠iu−xvl/xvi−xvlmodp=F10,0+F20,0=sThis concludes that, for any qualified subset, A=Uv1,Uv2,…,Uvu∈Γ of shareholders can work together to recover the secret. Hence, it holds that Hs|A=0.Efficiency: in this scheme, each share,si,jy,j∈1,2, is a univariate polynomial with degree h−1 Thus, each shareholder needs to store 2h coefficients of a univariate polynomial. The memory storage of each shareholder is 2hlog2p bits, where p is the modulus. Horner’s rule [24] can be used to evaluate polynomials. In the following discussion, we show the cost for computing wvi=svi0∏l=1,l≠iu−xvl/xvi−xvlmodp in the secret reconstruction. From Horner’s rule, evaluating a polynomial of degree h−1 needs h−1 multiplications and h additions. Since multiplication takes more time than addition, the performance is only addressed to the number of multiplications needed. The computational cost in step 2 of scheme 3 to compute wvi is to evaluate one polynomial. The computational cost in step 1 of scheme 3 to compute pairwise shared keys, ki,j=svixvj,j=1,2,…,u,j≠i, is to evaluate u−1 polynomials, where u is the number of shareholders participated in the secret reconstruction. Overall, the computational cost to reconstruct the secret of each shareholder is to compute uh multiplications.Security: in this section, we will first prove that the scheme meets the security requirements as discussed in Section3.3.Against both active and passive inside attacks: in the proposed scheme, the information exchanged among shareholders is encrypted using pairwise shared keys. Since a nonshareholder does not own any share generated by the dealer, the nonshareholder cannot decrypt any cipher text. Thus, the recovered secret is not available to the nonshareholder. In other words, the nonshareholder obtains no information ons.Against colluded inside attackTheorem 1.
Withh=t, the proposed scheme satisfies both security requirements of a t,n SS. That is, (a) with t or more than t shares can recover the secret and (b) with fewer than t shares cannot recover the secret.Proof.
Since polynomialsF1x,y=∑i=0h−1∑j=0h−1ai,jxiyjnodp and F2x,y=∑i=0h−1∑j=0h−1bi,jxiyjnodp are symmetric polynomials with ai,j=aj,iandbi,j=bj,i,∀i,j∈0,h−1 containing hh+1/2 different coefficients in each polynomial, there are hh+1 different coefficients in total. In the proposed scheme, each share, si,jy,j∈1,2, is a univariate polynomial with degree h−1. In other words, each shareholder can use his shares, si,1yandsi,2y, to establish 2h linearly independent equations in terms of the coefficients of the polynomials.
Witht−1 colluded shareholders together, it can establish 2ht−1 equations; at the same time, their shares contain 2C2t−1=t−1t−2 points on the bivariate polynomial. Thus, these t−1 colluded shares can be used to establish 2ht−1−t−1t−2 linear independent equations in terms of the coefficients of the bivariate polynomial. If hh+1>2ht−1−t−1t−2, these t−1 colluded shareholders cannot recover the bivariate polynomials. Since h=t, as specified in the share generation, we have hh+1>2ht−1−t−1t−2. Hence, any t−1 colluded shareholders cannot recover the secret. This conclusion is obtained without making any computational assumption.
On the other hand, when there aret or more than t shareholders trying to recover the secret, with their shares together, they can establish 2ht equations; at the same time, their shares contain 2C2t=tt−1 points on the bivariate polynomial. Thus, their shares can be used to establish 2ht−2C2t linear independent equations in terms of the coefficients of the bivariate polynomials. If 2ht−2C2t≥hh+1, these t or more than t shareholders can recover the bivariate polynomials. Since h=t, as specified in the share generation, we have 2ht−2C2t≥hh+1. Hence, any t or more than t shareholders can recover the secret.Corollary 1.
For any given threshold,t, the degree of the symmetric polynomial, Fx,y, can be t.Proof.
The proof is straightforward.


## 4.2.1. Scheme for Verification of Shares

Correctness: from secret sharing homomorphism, we know that additive shareviy of each shareholder is a share on the polynomial, F1x,y+αF2x,ymodp. Since polynomials F1x,yandF2x,y are both symmetric polynomials having h−1 degree each, the additive sum of their polynomials, Gx,y=F1x,y+αF2x,ymodp, must also be a symmetric polynomial having h−1 degree. On the other hand, if Gx,y=F1x,y+αF2x,ymodp is a symmetric polynomial having h−1 degree, then it is most likely that the polynomial F1x,y+F2x,ymodp is also a symmetric polynomial having h−1 degree. This result achieves our VSS objectives.Efficiency: our VSS is very efficient since it verifies all shares of secret at once using polynomial interpolation.Security: in step 2, each released value of shareholder isviy=syi,1+αsyi,2modp. It is impossible to obtain shares syi,1andsyi,2modp from the released value. Furthermore, in step 3, the recovered polynomial, Gx,y=F1x,y+αF2x,ymodp, does not reveal the secrecy of individual polynomials, F1x,yandF2x,ymodp. Thus, the secret cannot be obtained in this VSS scheme.


## 4.2.2. Scheme for Secure Secret Reconstruction

Correctness: according to the Lagrange interpolation formula, we can get∑i=1usviy∏l=1,l≠iux−xvl/xvi−xvlmodp=F1x,y+F2x,y. Thus, in step 4 of scheme 3, we get ∑i=1uwvimodp=∑i=1usvi0∏l=1,l≠iu−xvl/xvi−xvlmodp=F10,0+F20,0=sThis concludes that, for any qualified subset, A=Uv1,Uv2,…,Uvu∈Γ of shareholders can work together to recover the secret. Hence, it holds that Hs|A=0.Efficiency: in this scheme, each share,si,jy,j∈1,2, is a univariate polynomial with degree h−1 Thus, each shareholder needs to store 2h coefficients of a univariate polynomial. The memory storage of each shareholder is 2hlog2p bits, where p is the modulus. Horner’s rule [24] can be used to evaluate polynomials. In the following discussion, we show the cost for computing wvi=svi0∏l=1,l≠iu−xvl/xvi−xvlmodp in the secret reconstruction. From Horner’s rule, evaluating a polynomial of degree h−1 needs h−1 multiplications and h additions. Since multiplication takes more time than addition, the performance is only addressed to the number of multiplications needed. The computational cost in step 2 of scheme 3 to compute wvi is to evaluate one polynomial. The computational cost in step 1 of scheme 3 to compute pairwise shared keys, ki,j=svixvj,j=1,2,…,u,j≠i, is to evaluate u−1 polynomials, where u is the number of shareholders participated in the secret reconstruction. Overall, the computational cost to reconstruct the secret of each shareholder is to compute uh multiplications.Security: in this section, we will first prove that the scheme meets the security requirements as discussed in Section3.3.Against both active and passive inside attacks: in the proposed scheme, the information exchanged among shareholders is encrypted using pairwise shared keys. Since a nonshareholder does not own any share generated by the dealer, the nonshareholder cannot decrypt any cipher text. Thus, the recovered secret is not available to the nonshareholder. In other words, the nonshareholder obtains no information ons.Against colluded inside attackTheorem 1.
Withh=t, the proposed scheme satisfies both security requirements of a t,n SS. That is, (a) with t or more than t shares can recover the secret and (b) with fewer than t shares cannot recover the secret.Proof.
Since polynomialsF1x,y=∑i=0h−1∑j=0h−1ai,jxiyjnodp and F2x,y=∑i=0h−1∑j=0h−1bi,jxiyjnodp are symmetric polynomials with ai,j=aj,iandbi,j=bj,i,∀i,j∈0,h−1 containing hh+1/2 different coefficients in each polynomial, there are hh+1 different coefficients in total. In the proposed scheme, each share, si,jy,j∈1,2, is a univariate polynomial with degree h−1. In other words, each shareholder can use his shares, si,1yandsi,2y, to establish 2h linearly independent equations in terms of the coefficients of the polynomials.
Witht−1 colluded shareholders together, it can establish 2ht−1 equations; at the same time, their shares contain 2C2t−1=t−1t−2 points on the bivariate polynomial. Thus, these t−1 colluded shares can be used to establish 2ht−1−t−1t−2 linear independent equations in terms of the coefficients of the bivariate polynomial. If hh+1>2ht−1−t−1t−2, these t−1 colluded shareholders cannot recover the bivariate polynomials. Since h=t, as specified in the share generation, we have hh+1>2ht−1−t−1t−2. Hence, any t−1 colluded shareholders cannot recover the secret. This conclusion is obtained without making any computational assumption.
On the other hand, when there aret or more than t shareholders trying to recover the secret, with their shares together, they can establish 2ht equations; at the same time, their shares contain 2C2t=tt−1 points on the bivariate polynomial. Thus, their shares can be used to establish 2ht−2C2t linear independent equations in terms of the coefficients of the bivariate polynomials. If 2ht−2C2t≥hh+1, these t or more than t shareholders can recover the bivariate polynomials. Since h=t, as specified in the share generation, we have 2ht−2C2t≥hh+1. Hence, any t or more than t shareholders can recover the secret.Corollary 1.
For any given threshold,t, the degree of the symmetric polynomial, Fx,y, can be t.Proof.
The proof is straightforward.


## 4.3. Comparison

Since the proposed schemes are based on bivariate polynomials with multiple features, our comparison with other schemes is a high-level comparison only. In a whole, compared with previous related schemes, our proposed VSS and SSRS schemes have the following advantages:(1)
The proposed secure secret reconstruction scheme with verifiable shares is unconditionally secure, which is based on symmetric bivariate polynomials.(2)
The proposed VSS is different from most other VSSs which verify one share at a time; but our VSS verifies all shares at once. There are only two possible outcomes of our proposed VSS, that is, either all shares are strongt-consistent and generated by a symmetric bivariate polynomial or there are inconsistent shares. Thus, the proposed VSS is sufficient if all shares are strong t-consistent and generated by a symmetric bivariate polynomial; however, if there are inconsistent shares, it can be treated as a preprocess before applying other VSS to identify invalid shares.(3)
Previous SSRS can only prevent active attackers to obtain the recovered secret, but cannot prevent passive attackers. Our proposed SSRS can prevent both active and passive attackers.(4)
In our proposed SSRS, shares of shareholders are generated by a symmetric bivariate polynomial. The shares generated by a symmetric bivariate polynomial can be used to (a) verify all shares at once, (b) recover the secret, and (c) establish pairwise secret keys between shareholders to protect the exchange information in the secret reconstruction. There is no additional user authentication or key distribution needed. Thus, it is very efficient.


## 5. Conclusions

A novel design for an efficient SSRS with verifiable shares is introduced in the paper. This SSRS uses bivariate polynomials to generate shares, where shares of shareholders can be used to (a) verify all shares at once, (b) recover the secret, and (c) establish pairwise secret keys between shareholders to protect the exchange information in the secret reconstruction. Moreover, we propose an efficient verification scheme which allows all shares to be verified at once. Security and performance analysis are also included. The proposed scheme is more attractive to be applied in most communications systems.



---

*Source: 1039898-2020-12-15.xml*