# Grouped Secret Sharing Schemes Based on Lagrange Interpolation Polynomials and Chinese Remainder Theorem

Authors: Fuyou Miao; Yue Yu; Keju Meng; Yan Xiong; Chin-Chen Chang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

In at,n threshold secret sharing (SS) scheme, whether or not a shareholder set is an authorized set totally depends on the number of shareholders in the set. When the access structure is not threshold, (t,n) threshold SS is not suitable. This paper proposes a new kind of SS named grouped secret sharing (GSS), which is specific multipartite SS. Moreover, in order to implement GSS, we utilize both Lagrange interpolation polynomials and Chinese remainder theorem to design two GSS schemes, respectively. Detailed analysis shows that both GSS schemes are correct and perfect, which means any authorized set can recover the secret while an unauthorized set cannot get any information about the secret.


---

## Body

## 1. Introduction

The notion of secret sharing (SS) was first introduced by Shamir [1] and Blakley [2], respectively, in 1979. In an SS scheme, a dealer D divides a secret s into some pieces s1,s2,…,sn. Each piece si is called a share of the secret. Then, the dealer can design an access structure Γ=A1,A2,…,Am, where Ai is a minimal authorized set, i.e., any superset of Ai can recover the secret. According to the access structure, the dealer sends each shares to the corresponding shareholder in private. After share generation, if a shareholder set P is a superset of an authorized set, i.e., Ai⊂P, P can reconstruct the secret as long as the shareholders in Ai release shares to the others in P. If there does not exist any Ai such that Ai⊂P, the secret cannot be recovered by P.SS schemes are classified into many types, such ast,n threshold SS [3, 4], weighted threshold SS [5, 6], hierarchical threshold SS [7, 8], multilevel threshold SS [9, 10], multipartite SS [11, 12], and so on. The most classical SS is t,n threshold SS. There are n shareholders in a t,n threshold SS scheme. A dealer divides a secret s into n shares and sends each share to a shareholder securely. Then, any t or more than t shareholders can collaborate to obtain the secret s by pooling their shares together while any up to t−1 shareholders cannot. The value of t is called the threshold of the SS scheme.Obviously, in at,n threshold SS scheme, whether or not a shareholder set is able to recover the secret is totally dependent on the number of shareholders in the set. Hence, t,n SS cannot work in many cases. For example, suppose a big company BC consists of five constituent companies which share the final decision rights of BC equally. Each constituent company has several shareholders who can represent the constituent company to confer with representatives of the other constituent companies on the final decision of BC. Although different shareholders in a constituent company own different shares, they have the same rights. In such a scene, if a shareholder set is able to make a decision of BC, at least five shareholders are included in the set. However, it is far from that any five shareholders can do that. Only if a shareholder set includes the representatives from all the five constituent companies, the set can make a decision of BC. Therefore, the given access structure is not just threshold.Farras et al. [11] first proposed the notion of multipartite SS which can solve the above problem. In a multipartite SS scheme, shareholders are divided into several disjoint partitions and each partition has a part access structure. If a shareholder set satisfies all the part access structures, it can recover the secret. But as long as the shareholder set does not satisfy any one part access structure of a partition, the secret cannot be obtained. Later, Tassa and Dyn [12] and Hsu and Harn [13] utilized bivariate interpolation and Chinese remainder theorem (CRT) to implement multipartite SS schemes. Obviously, if each threshold of part access structure equals one, the above problem can be solved. However, in the multipartite SS schemes, if the threshold is equal to one in a partition, all the shareholders in the partition get the same share. In terms of security, different shareholders are supposed to keep different shares even when they are in the same partition. For this purpose, we propose a new SS named grouped secret sharing (GSS) in this paper.Informally, suppose that there are totallyn shareholders in a SS scheme. They are divided into m disjoint groups. Each shareholder keeps a distinct share and belongs to a group. If a shareholder set shares at least one shareholder with every group, the shareholder set is allowed to recover the secret. Otherwise, the secret cannot be reconstructed. Then, the SS scheme is a GSS scheme.In order to implement GSS, this paper uses Lagrange interpolation polynomials (LIPs) and Chinese remainder theorem (CRT) to design two GSS schemes, respectively. Thereinto, LIP as a method of linear combination plays an important role in numerical analysis. Shamir first used it to design at,n threshold SS scheme [1] in 1979. Later, LIP became the most common tool to design SS schemes because it is very simple and efficient. There are many schemes [14, 15] based on LIP. CRT is used to solve systems of linear congruence equations. Mignotte first proposed a t,n threshold SS scheme [16] based on CRT in 1982, but the scheme is ramp instead of perfect because even an unauthorized shareholder set can obtain part of information about the secret. Asmuth and Bloom modified Mignotte’s scheme to give a perfect t,n threshold SS scheme [17]. There are also many other kinds of SS schemes [18, 19] based on CRT.Based on the above, the contributions of the paper are listed as follows:(1)
The paper proposes a kind of SS named grouped secret sharing (GSS).(2)
Both LIP and CRT are utilized to construct two GSS schemes.(3)
Although shareholders in a same group keep different shares, each one of them can represent the group to participate in secret reconstruction.The outline of the paper is as follows. In the next section, we provide the notion of CRT, Shamirt,n SS scheme, Asmuth–Bloom t,n SS scheme, and the formal definition of GSS as the preliminaries. A GSS scheme based on LIP and correlative correctness and security analyses are shown in Section 3. Analogously, a GSS scheme based on CRT and correlative analyses are given in Section 4. For a better illustration, we give two numerical examples in Section 5. Some discussions about perfectness and information rate are shown in Section 6. We conclude the work in Section 7.


## 2. Preliminaries

In this section, we introduce some preliminaries including CRT, Shamirt,n SS scheme, Asmuth–Bloom t,n SS scheme, and the formal definition of GSS.


### 2.1. Chinese Remainder Theorem (CRT) [20]

Given the following system of linear congruence equations:(1)x≡a1modm1;x≡a2modm2;⋮x≡anmodmn,if all moduli are pairwise co-prime, i.e., gcdmi,mj=1 for i≠j, CRT illustrates that the system must have solutions for any integer of a1,a2,…,an. Define M=m1,m2,…,mn, Mi=M/mi, and ti≡Mi−1modmi for i=1,…,n. Then, the system has an unique solution in ℤM:(2)x=∑i=1naitiMimodM.


### 2.2. Shamir’st,n Threshold SS Scheme

In Shamir’st,n threshold SS scheme, there are n shareholders U=U1,U2,…,Un and a dealer D who is trusted by all shareholders. The scheme consists of two algorithms.


#### 2.2.1. Share Generation

The dealerD randomly selects a polynomial fx of degree t−1: fx=a0+a1x+a2x2+⋯+at−1xt−1modp, where all coefficients are in ℤp. The secret is constant term of fx, i.e., s=f0=a0. D picks n different positive integers to compute n shares si=fxi for i=1,2,…,n, where xi is public information associated with shareholder Ui. Then, the dealer D securely sends the share si to the corresponding shareholder Ui.


#### 2.2.2. Secret Reconstruction

Assume thatmm≥t shareholders U1,U2,…,Um work together to recover the secret. Each shareholder Ui releases its share si to the others. After a shareholder receives the other m−1 shares, it can use LIP to recover the secret:(3)s=f0=∑i=1mfxi∏j=1,j≠imxjxj−ximodp.


### 2.3. Asmuth–Bloomt,n Threshold SS Scheme

There is a dealerD and n shareholders U=U1,U2,…,Un in Asmuth–Bloom t,n threshold SS scheme which also consists of two algorithms.


#### 2.3.1. Share Generation

At first, the dealerD picks a prime number p0 and a sequence of pairwise co-prime positive integers p1,p2,…,pn with p1<p2<⋯<pn, p0,pn−t+2,pn−t+1,…,pn<p1,p2,…,pt, and gcdp0,pi=1 for i=1,2,…,n. Then, D picks a random integer α and a secret s in ℤp0, such that s+αp0<p1,p2,…,pt. Next, D computes n shares si=s+αp0modpi for i=1,2,…,n, where pi is public information associated with shareholder Ui. Finally, the dealer D securely sends the share si to the corresponding shareholder Ui.


#### 2.3.2. Secret Reconstruction

Assume thatmm≥t shareholders U1,U2,…,Um want to recover the secret. Each of them releases its share to the others. After a shareholder receives the other m−1 shares, he gets a system of linear congruence equations:(4)s+αp0≡s1modp1;s+αp0≡s2modp2;⋮s+αp0≡smmodpm.Using the standard CRT, the value ofs+αp0 can be computed as(5)s+αp0=∑i=1mPpiyisimodP,where P=p1,p2,…,pm and yiP/pimodpi=1. Then, the secret s can be obtained as s=s+αp0modp0.


### 2.4. Grouped Secret Sharing (GSS)

In the following, we give a formal definition of GSS.Definition 1.
(grouped secret sharing). For an SS scheme, letU be a set of n shareholders and assume that U is composed of m disjoint groups, i.e., U=∪i=1mUi, where Ui is a set of nishareholders such thatn=n1+n2+⋯+nm and Ui∩Uj=∅ for all 1≤i≤m,1≤j≤m and i≠j. Every shareholder keeps a unique share. If the access structure Γ of the scheme is shown as(6)Γ=P|P⊂U,P∩Ui≠∅,∀i∈1,2,…,m,where P is a shareholder set.
In other words, ifP can reconstruct the secret, it must share at least one shareholder with each of the m disjoint groups. If so, the SS scheme is a GSS scheme. Figure 1 shows the model of GSS.Figure 1
The model of GSS.


### 2.5. Introduction to Lattice

Because some security analyses need to use lattice, we give some definitions about lattice.Definition 2.
(lattice). Givenn linearly independent vectors b1,b1,…,bn∈ℤm, the lattice generated by the n vectors is(7)ℒb1,b2,…,bn|=∑xibixi|∈ℤ.
Vectorsb1,b1,…,bn∈ℤm are the basis of L.Definition 3.
(the closest vector problem). Given a vectorw that is not in a lattice L, find a vector v∈L that is closest to w.
In the lattice with high dimensions, it is difficult to solve CVP in polynomial time. However, CVP is solvable in a reduced basis with low dimensions. LLL algorithm was proposed by Lenstra, Lenstra, and Lovász, and thus it is called LLL algorithm. LLL algorithm uses Schmidt orthogonalization repeatedly to obtain a reduced basis. The detailed algorithm is shown in paper [21].


## 2.1. Chinese Remainder Theorem (CRT) [20]

Given the following system of linear congruence equations:(1)x≡a1modm1;x≡a2modm2;⋮x≡anmodmn,if all moduli are pairwise co-prime, i.e., gcdmi,mj=1 for i≠j, CRT illustrates that the system must have solutions for any integer of a1,a2,…,an. Define M=m1,m2,…,mn, Mi=M/mi, and ti≡Mi−1modmi for i=1,…,n. Then, the system has an unique solution in ℤM:(2)x=∑i=1naitiMimodM.


## 2.2. Shamir’st,n Threshold SS Scheme

In Shamir’st,n threshold SS scheme, there are n shareholders U=U1,U2,…,Un and a dealer D who is trusted by all shareholders. The scheme consists of two algorithms.


### 2.2.1. Share Generation

The dealerD randomly selects a polynomial fx of degree t−1: fx=a0+a1x+a2x2+⋯+at−1xt−1modp, where all coefficients are in ℤp. The secret is constant term of fx, i.e., s=f0=a0. D picks n different positive integers to compute n shares si=fxi for i=1,2,…,n, where xi is public information associated with shareholder Ui. Then, the dealer D securely sends the share si to the corresponding shareholder Ui.


### 2.2.2. Secret Reconstruction

Assume thatmm≥t shareholders U1,U2,…,Um work together to recover the secret. Each shareholder Ui releases its share si to the others. After a shareholder receives the other m−1 shares, it can use LIP to recover the secret:(3)s=f0=∑i=1mfxi∏j=1,j≠imxjxj−ximodp.


## 2.2.1. Share Generation

The dealerD randomly selects a polynomial fx of degree t−1: fx=a0+a1x+a2x2+⋯+at−1xt−1modp, where all coefficients are in ℤp. The secret is constant term of fx, i.e., s=f0=a0. D picks n different positive integers to compute n shares si=fxi for i=1,2,…,n, where xi is public information associated with shareholder Ui. Then, the dealer D securely sends the share si to the corresponding shareholder Ui.


## 2.2.2. Secret Reconstruction

Assume thatmm≥t shareholders U1,U2,…,Um work together to recover the secret. Each shareholder Ui releases its share si to the others. After a shareholder receives the other m−1 shares, it can use LIP to recover the secret:(3)s=f0=∑i=1mfxi∏j=1,j≠imxjxj−ximodp.


## 2.3. Asmuth–Bloomt,n Threshold SS Scheme

There is a dealerD and n shareholders U=U1,U2,…,Un in Asmuth–Bloom t,n threshold SS scheme which also consists of two algorithms.


### 2.3.1. Share Generation

At first, the dealerD picks a prime number p0 and a sequence of pairwise co-prime positive integers p1,p2,…,pn with p1<p2<⋯<pn, p0,pn−t+2,pn−t+1,…,pn<p1,p2,…,pt, and gcdp0,pi=1 for i=1,2,…,n. Then, D picks a random integer α and a secret s in ℤp0, such that s+αp0<p1,p2,…,pt. Next, D computes n shares si=s+αp0modpi for i=1,2,…,n, where pi is public information associated with shareholder Ui. Finally, the dealer D securely sends the share si to the corresponding shareholder Ui.


### 2.3.2. Secret Reconstruction

Assume thatmm≥t shareholders U1,U2,…,Um want to recover the secret. Each of them releases its share to the others. After a shareholder receives the other m−1 shares, he gets a system of linear congruence equations:(4)s+αp0≡s1modp1;s+αp0≡s2modp2;⋮s+αp0≡smmodpm.Using the standard CRT, the value ofs+αp0 can be computed as(5)s+αp0=∑i=1mPpiyisimodP,where P=p1,p2,…,pm and yiP/pimodpi=1. Then, the secret s can be obtained as s=s+αp0modp0.


## 2.3.1. Share Generation

At first, the dealerD picks a prime number p0 and a sequence of pairwise co-prime positive integers p1,p2,…,pn with p1<p2<⋯<pn, p0,pn−t+2,pn−t+1,…,pn<p1,p2,…,pt, and gcdp0,pi=1 for i=1,2,…,n. Then, D picks a random integer α and a secret s in ℤp0, such that s+αp0<p1,p2,…,pt. Next, D computes n shares si=s+αp0modpi for i=1,2,…,n, where pi is public information associated with shareholder Ui. Finally, the dealer D securely sends the share si to the corresponding shareholder Ui.


## 2.3.2. Secret Reconstruction

Assume thatmm≥t shareholders U1,U2,…,Um want to recover the secret. Each of them releases its share to the others. After a shareholder receives the other m−1 shares, he gets a system of linear congruence equations:(4)s+αp0≡s1modp1;s+αp0≡s2modp2;⋮s+αp0≡smmodpm.Using the standard CRT, the value ofs+αp0 can be computed as(5)s+αp0=∑i=1mPpiyisimodP,where P=p1,p2,…,pm and yiP/pimodpi=1. Then, the secret s can be obtained as s=s+αp0modp0.


## 2.4. Grouped Secret Sharing (GSS)

In the following, we give a formal definition of GSS.Definition 1.
(grouped secret sharing). For an SS scheme, letU be a set of n shareholders and assume that U is composed of m disjoint groups, i.e., U=∪i=1mUi, where Ui is a set of nishareholders such thatn=n1+n2+⋯+nm and Ui∩Uj=∅ for all 1≤i≤m,1≤j≤m and i≠j. Every shareholder keeps a unique share. If the access structure Γ of the scheme is shown as(6)Γ=P|P⊂U,P∩Ui≠∅,∀i∈1,2,…,m,where P is a shareholder set.
In other words, ifP can reconstruct the secret, it must share at least one shareholder with each of the m disjoint groups. If so, the SS scheme is a GSS scheme. Figure 1 shows the model of GSS.Figure 1
The model of GSS.


## 2.5. Introduction to Lattice

Because some security analyses need to use lattice, we give some definitions about lattice.Definition 2.
(lattice). Givenn linearly independent vectors b1,b1,…,bn∈ℤm, the lattice generated by the n vectors is(7)ℒb1,b2,…,bn|=∑xibixi|∈ℤ.
Vectorsb1,b1,…,bn∈ℤm are the basis of L.Definition 3.
(the closest vector problem). Given a vectorw that is not in a lattice L, find a vector v∈L that is closest to w.
In the lattice with high dimensions, it is difficult to solve CVP in polynomial time. However, CVP is solvable in a reduced basis with low dimensions. LLL algorithm was proposed by Lenstra, Lenstra, and Lovász, and thus it is called LLL algorithm. LLL algorithm uses Schmidt orthogonalization repeatedly to obtain a reduced basis. The detailed algorithm is shown in paper [21].


## 3. GSS Based on LIP

In this section, we first show how to implement a GSS based on Shamir’st,n threshold SS scheme. The correctness and security analyses are given in the next two subsections, respectively.


### 3.1. Implementing a GSS Based on Shamir SS Scheme

According to the above definition of GSS, any shareholderUki can represent the group Ui to participate in secret reconstruction but different shareholders should keep different shares even when they are in a same group. Hence, this paper focuses on how to generate different shares in a group while all shares can be used to recover the same secret.Our GSS scheme based on LIP consists of three algorithms: (1) main share generation for a group; (2) subshare generation for a shareholder; and (3) secret reconstruction.


#### 3.1.1. Main Share Generation for a Group

LetU be a set of n shareholders. All the shareholders are divided into m disjoint groups U=U1∪U2∪⋯∪Um. A shareholder only belongs to one group, i.e., Ui∩Uj=∅ if i≠j. Each group has ni shareholders such that n=n1+n2+⋯+nm.A dealerD chooses two prime numbers p and g with p>mg2. Then, D randomly picks a polynomial fx of degree m−1: fx=a0+a1x+a2x2+⋯+am−1xm−1modp, where a0∈ℤg but the other coefficients are limited in ℤp, i.e., ai∈ℤp for i=1,2,…,m−1. The secret s is equal to the constant term of fx, i.e., s=f0=a0.As for a groupUi, the dealer D selects a positive integer xi from ℤp as public information associated with Ui, where xi≠0 and xi≠xj if i≠j. Then, D computes a main share for group Ui as si=fxi.


#### 3.1.2. Subshare Generation for a Shareholder

After Algorithm 1, each groupUi is allocated a main share. If there just exists one shareholder in a group, the dealer can use 0 as the random integer to generate a subshare for the only shareholder. Otherwise, for each shareholder Ukii (superscript i denotes that the shareholder is in group Ui and subscript ki is an integer from the interval 1,ni and denotes that the shareholder is the ki-th shareholder in Ui), the dealer D computes a subshare skii as(8)skii=si∏j=1,j≠imxjxj−xi+rkiigmodp,where rkii is a random integer picked by D and rkii∈ℤg. D sends skii as private share to the corresponding shareholder Ukii securely.


#### 3.1.3. Secret Reconstruction

Note that any SS scheme has the monotone property. In other words, if a shareholder setℳ can recover the secret, any superset of ℳ can also realize secret reconstruction.If a shareholder setP is allowed to recover the secret s, at least one shareholder Ukii is included in P for i=1,2,…,m, where ki is a random integer in ℤmi+1. Then, without loss of generality, P can be divided into two subsets ℳ1 and ℳ2, where ℳ1=Uk11,Uk22,…,Ukmm and ℳ2=P−ℳ1. In terms of definition of GSS, the subset ℳ1 is able to recover the secret.Each shareholder inℳ1 releases its subshare to the other shareholders in P. After that, all the shareholders in P get m shares sk11,sk22,…,skmm. Then, the secret can be obtained by computing(9)s=∑i=1mskiimodpmodg.


### 3.2. Correctness Analysis

In order to demonstrate that the proposed GSS scheme based on LIP can work correctly, we give two steps to prove the equations=∑i=1mskiimodpmodg (Table 1).Step 1:s+∑i=1mrkiig<p.Step 2:s=∑i=1mskiimodpmodg.(10)∑i=1mskiimodpmodg=∑i=1msi∏j=1,j≠imxjxj−xi+rkiigmodpmodg=∑i=1msi∏j=1,j≠imxjxj−ximodp+∑i=1mrkiigmodpmodg=s+∑i=1mrkiigmodpmodg=s+∑i=1mrkiigmodg=s.Table 1
Proof of step 1 in GSS based on LIP.
FormulasRemarkss+∑i=1mrkiig≤s+mgg−1Remark3.1:rkii∈ℤg<g+mg2−mgRemark3.2:s∈ℤg<p.Remark3.3:p>mg2On account of Step 1 and Step 2, it is proven that the secrets can be obtained by computing ∑i=1mskiimodpmodg.


### 3.3. Security Analysis

In this section, we give two theorems to prove the security of the proposed GSS based on LIP. Because secrets is uniformly distributed in ℤg, the probability of obtaining s from no share is 1/q. In general, g is a large number such that it is impossible to guess the secret s directly without any information. Therefore, if the probability of an event occurring is equal to or less than 1/q, the event can be considered as impossibility.Theorem 1.
In the GSS based on LIP, a subshareskiiis valid just in the groupUi, while it is invalid in any other groupUjwherei≠j.Proof.
In the light of correctness analysis, we have proved that the subshareskii is valid in Ui. Hence, we give the proof of the latter part of Theorem 1 in the following. In more detail, we should prove that the probability of skii being valid in Uj is no more than 1/q.
Ifskii is valid in Uj, it means skii=sj∏h=1,h≠jmxh/xh−xj+rkjjgmodp. In the equation, sj has a uniform distribution in ℤp since it is computed as sj=fxj and all the coefficients of fx are unknown. And rkjj can be any integer over ℤg. From the equation, we get(11)sj=∏h=1,h≠jmxhxh−xj−1skii−rkjjgmodp.
Defineqrkjj=skii−rkjjgmodp with only one independent variable rkjjrkjj∈ℤg. Then, given a fixed value of skii, qrxj=qryj holds if and only if rxj=ryj for rxj,ryj∈ℤg. Because if there exist rxj and ryj such that qrxj=qryj, there must be an integer v such that rxj−ryjg=vp, i.e., p|rxj−ryj. In this way, we can get rxj=ryj, i.e., v=0 because rxj,ryj∈ℤg and p>mg2. Furthermore, qrkjj is a 1-to-1 function, i.e., qrkjj also has g values corresponding to g values of rkjj. In the same way, sj has g values corresponding to g values of qrkjj because ∏h=1,h≠jmxh/xh−xj−1 is a fixed value. However, sj has a uniform distribution in ℤp. Hence, the probability that equation (11) holds is g/p, which is less than 1/g due to p>mg2. This means it is impossible to make equation (11) true. In other words, the subshare skii is invalid in any other group Uj, where i≠j.Theorem 2.
In the GSS based on LIP, for a shareholder setP, if there exists a groupUisuch thatP∩Ui=∅, the setPcannot recover the secrets.Proof.
Without loss generality, suppose thatP=U−U1. In other words, P includes shareholders in all the groups except U1. Besides, suppose that at least two shareholders exist in a group.
Now, let us prove that ifP can recover the secret s, it must know the exact value of the main share s1.
In groupUii≠1, we have(12)s1i=sic+r1igmodp,s2i=sic+r2igmodp,where c=∏j=1,j≠imxj/xj−xi. In the equation, s1i,s2i,c, and g are known, while si,r1i, and r2i are unknown. Although there exist three unknown numbers in two equations, they can still be recovered because s1i,s2i∈ℤp, si,r1i,r2i∈ℤg while p>mg2. In other words, si,r1i,r2i are very short compared with s1i,s2i, Therefore, we can construct a lattice and utilize lattice basis reduction algorithm to recover si,r1i,r2i. From equation (12), we can deduce(13)s1ic−s2icg−1modp≡r1ic−r2icmodp.
Then, construct a latticeL as follows:(14)L=Mp00Mc10Mc01.
Define a target vectort=Ms1ic−s2icg−1modp,0,0, where M is a prime greater than g to guarantee the distance of any lattice vector far away from t is greater than M.
Note thatr1i,r2i∈ℤg; then, the distance of t far away from lattice L is(15)0,r1i,r2i=r1i2+r2i2≤2g.
We claim that vectorv=Ms1ic−s2icg−1modp,r1i,r2i is the closest lattice point far away from t. Finally, we invoke LLL algorithm to recover r1i and r2i by solving the closest vector problem (CVPv,L). Once we recover r1i and r2i, si can be obtained easily. After that, we get m−1 main shares si for i=2,3,…,m to construct m−1 coordinates on the original polynomial fx such as xi,si.
Now, suppose that we can recover the secrets; it means that we obtain another coordinate 0,s. Then, fx can be reconstructed from 0,s and m−1 coordinates xi,si because the degree of fx is m−1.
If we obtainfx, the main share s1 can be computed as fx1 easily. However, we do not have any information about s1, since no shareholder in group U1 is concluded in P. As a deduction, it means that P cannot recover the secret s if there exists a group Ui such that P∩Ui=∅.


## 3.1. Implementing a GSS Based on Shamir SS Scheme

According to the above definition of GSS, any shareholderUki can represent the group Ui to participate in secret reconstruction but different shareholders should keep different shares even when they are in a same group. Hence, this paper focuses on how to generate different shares in a group while all shares can be used to recover the same secret.Our GSS scheme based on LIP consists of three algorithms: (1) main share generation for a group; (2) subshare generation for a shareholder; and (3) secret reconstruction.


### 3.1.1. Main Share Generation for a Group

LetU be a set of n shareholders. All the shareholders are divided into m disjoint groups U=U1∪U2∪⋯∪Um. A shareholder only belongs to one group, i.e., Ui∩Uj=∅ if i≠j. Each group has ni shareholders such that n=n1+n2+⋯+nm.A dealerD chooses two prime numbers p and g with p>mg2. Then, D randomly picks a polynomial fx of degree m−1: fx=a0+a1x+a2x2+⋯+am−1xm−1modp, where a0∈ℤg but the other coefficients are limited in ℤp, i.e., ai∈ℤp for i=1,2,…,m−1. The secret s is equal to the constant term of fx, i.e., s=f0=a0.As for a groupUi, the dealer D selects a positive integer xi from ℤp as public information associated with Ui, where xi≠0 and xi≠xj if i≠j. Then, D computes a main share for group Ui as si=fxi.


### 3.1.2. Subshare Generation for a Shareholder

After Algorithm 1, each groupUi is allocated a main share. If there just exists one shareholder in a group, the dealer can use 0 as the random integer to generate a subshare for the only shareholder. Otherwise, for each shareholder Ukii (superscript i denotes that the shareholder is in group Ui and subscript ki is an integer from the interval 1,ni and denotes that the shareholder is the ki-th shareholder in Ui), the dealer D computes a subshare skii as(8)skii=si∏j=1,j≠imxjxj−xi+rkiigmodp,where rkii is a random integer picked by D and rkii∈ℤg. D sends skii as private share to the corresponding shareholder Ukii securely.


### 3.1.3. Secret Reconstruction

Note that any SS scheme has the monotone property. In other words, if a shareholder setℳ can recover the secret, any superset of ℳ can also realize secret reconstruction.If a shareholder setP is allowed to recover the secret s, at least one shareholder Ukii is included in P for i=1,2,…,m, where ki is a random integer in ℤmi+1. Then, without loss of generality, P can be divided into two subsets ℳ1 and ℳ2, where ℳ1=Uk11,Uk22,…,Ukmm and ℳ2=P−ℳ1. In terms of definition of GSS, the subset ℳ1 is able to recover the secret.Each shareholder inℳ1 releases its subshare to the other shareholders in P. After that, all the shareholders in P get m shares sk11,sk22,…,skmm. Then, the secret can be obtained by computing(9)s=∑i=1mskiimodpmodg.


## 3.1.1. Main Share Generation for a Group

LetU be a set of n shareholders. All the shareholders are divided into m disjoint groups U=U1∪U2∪⋯∪Um. A shareholder only belongs to one group, i.e., Ui∩Uj=∅ if i≠j. Each group has ni shareholders such that n=n1+n2+⋯+nm.A dealerD chooses two prime numbers p and g with p>mg2. Then, D randomly picks a polynomial fx of degree m−1: fx=a0+a1x+a2x2+⋯+am−1xm−1modp, where a0∈ℤg but the other coefficients are limited in ℤp, i.e., ai∈ℤp for i=1,2,…,m−1. The secret s is equal to the constant term of fx, i.e., s=f0=a0.As for a groupUi, the dealer D selects a positive integer xi from ℤp as public information associated with Ui, where xi≠0 and xi≠xj if i≠j. Then, D computes a main share for group Ui as si=fxi.


## 3.1.2. Subshare Generation for a Shareholder

After Algorithm 1, each groupUi is allocated a main share. If there just exists one shareholder in a group, the dealer can use 0 as the random integer to generate a subshare for the only shareholder. Otherwise, for each shareholder Ukii (superscript i denotes that the shareholder is in group Ui and subscript ki is an integer from the interval 1,ni and denotes that the shareholder is the ki-th shareholder in Ui), the dealer D computes a subshare skii as(8)skii=si∏j=1,j≠imxjxj−xi+rkiigmodp,where rkii is a random integer picked by D and rkii∈ℤg. D sends skii as private share to the corresponding shareholder Ukii securely.


## 3.1.3. Secret Reconstruction

Note that any SS scheme has the monotone property. In other words, if a shareholder setℳ can recover the secret, any superset of ℳ can also realize secret reconstruction.If a shareholder setP is allowed to recover the secret s, at least one shareholder Ukii is included in P for i=1,2,…,m, where ki is a random integer in ℤmi+1. Then, without loss of generality, P can be divided into two subsets ℳ1 and ℳ2, where ℳ1=Uk11,Uk22,…,Ukmm and ℳ2=P−ℳ1. In terms of definition of GSS, the subset ℳ1 is able to recover the secret.Each shareholder inℳ1 releases its subshare to the other shareholders in P. After that, all the shareholders in P get m shares sk11,sk22,…,skmm. Then, the secret can be obtained by computing(9)s=∑i=1mskiimodpmodg.


## 3.2. Correctness Analysis

In order to demonstrate that the proposed GSS scheme based on LIP can work correctly, we give two steps to prove the equations=∑i=1mskiimodpmodg (Table 1).Step 1:s+∑i=1mrkiig<p.Step 2:s=∑i=1mskiimodpmodg.(10)∑i=1mskiimodpmodg=∑i=1msi∏j=1,j≠imxjxj−xi+rkiigmodpmodg=∑i=1msi∏j=1,j≠imxjxj−ximodp+∑i=1mrkiigmodpmodg=s+∑i=1mrkiigmodpmodg=s+∑i=1mrkiigmodg=s.Table 1
Proof of step 1 in GSS based on LIP.
FormulasRemarkss+∑i=1mrkiig≤s+mgg−1Remark3.1:rkii∈ℤg<g+mg2−mgRemark3.2:s∈ℤg<p.Remark3.3:p>mg2On account of Step 1 and Step 2, it is proven that the secrets can be obtained by computing ∑i=1mskiimodpmodg.


## 3.3. Security Analysis

In this section, we give two theorems to prove the security of the proposed GSS based on LIP. Because secrets is uniformly distributed in ℤg, the probability of obtaining s from no share is 1/q. In general, g is a large number such that it is impossible to guess the secret s directly without any information. Therefore, if the probability of an event occurring is equal to or less than 1/q, the event can be considered as impossibility.Theorem 1.
In the GSS based on LIP, a subshareskiiis valid just in the groupUi, while it is invalid in any other groupUjwherei≠j.Proof.
In the light of correctness analysis, we have proved that the subshareskii is valid in Ui. Hence, we give the proof of the latter part of Theorem 1 in the following. In more detail, we should prove that the probability of skii being valid in Uj is no more than 1/q.
Ifskii is valid in Uj, it means skii=sj∏h=1,h≠jmxh/xh−xj+rkjjgmodp. In the equation, sj has a uniform distribution in ℤp since it is computed as sj=fxj and all the coefficients of fx are unknown. And rkjj can be any integer over ℤg. From the equation, we get(11)sj=∏h=1,h≠jmxhxh−xj−1skii−rkjjgmodp.
Defineqrkjj=skii−rkjjgmodp with only one independent variable rkjjrkjj∈ℤg. Then, given a fixed value of skii, qrxj=qryj holds if and only if rxj=ryj for rxj,ryj∈ℤg. Because if there exist rxj and ryj such that qrxj=qryj, there must be an integer v such that rxj−ryjg=vp, i.e., p|rxj−ryj. In this way, we can get rxj=ryj, i.e., v=0 because rxj,ryj∈ℤg and p>mg2. Furthermore, qrkjj is a 1-to-1 function, i.e., qrkjj also has g values corresponding to g values of rkjj. In the same way, sj has g values corresponding to g values of qrkjj because ∏h=1,h≠jmxh/xh−xj−1 is a fixed value. However, sj has a uniform distribution in ℤp. Hence, the probability that equation (11) holds is g/p, which is less than 1/g due to p>mg2. This means it is impossible to make equation (11) true. In other words, the subshare skii is invalid in any other group Uj, where i≠j.Theorem 2.
In the GSS based on LIP, for a shareholder setP, if there exists a groupUisuch thatP∩Ui=∅, the setPcannot recover the secrets.Proof.
Without loss generality, suppose thatP=U−U1. In other words, P includes shareholders in all the groups except U1. Besides, suppose that at least two shareholders exist in a group.
Now, let us prove that ifP can recover the secret s, it must know the exact value of the main share s1.
In groupUii≠1, we have(12)s1i=sic+r1igmodp,s2i=sic+r2igmodp,where c=∏j=1,j≠imxj/xj−xi. In the equation, s1i,s2i,c, and g are known, while si,r1i, and r2i are unknown. Although there exist three unknown numbers in two equations, they can still be recovered because s1i,s2i∈ℤp, si,r1i,r2i∈ℤg while p>mg2. In other words, si,r1i,r2i are very short compared with s1i,s2i, Therefore, we can construct a lattice and utilize lattice basis reduction algorithm to recover si,r1i,r2i. From equation (12), we can deduce(13)s1ic−s2icg−1modp≡r1ic−r2icmodp.
Then, construct a latticeL as follows:(14)L=Mp00Mc10Mc01.
Define a target vectort=Ms1ic−s2icg−1modp,0,0, where M is a prime greater than g to guarantee the distance of any lattice vector far away from t is greater than M.
Note thatr1i,r2i∈ℤg; then, the distance of t far away from lattice L is(15)0,r1i,r2i=r1i2+r2i2≤2g.
We claim that vectorv=Ms1ic−s2icg−1modp,r1i,r2i is the closest lattice point far away from t. Finally, we invoke LLL algorithm to recover r1i and r2i by solving the closest vector problem (CVPv,L). Once we recover r1i and r2i, si can be obtained easily. After that, we get m−1 main shares si for i=2,3,…,m to construct m−1 coordinates on the original polynomial fx such as xi,si.
Now, suppose that we can recover the secrets; it means that we obtain another coordinate 0,s. Then, fx can be reconstructed from 0,s and m−1 coordinates xi,si because the degree of fx is m−1.
If we obtainfx, the main share s1 can be computed as fx1 easily. However, we do not have any information about s1, since no shareholder in group U1 is concluded in P. As a deduction, it means that P cannot recover the secret s if there exists a group Ui such that P∩Ui=∅.


## 4. GSS Based on CRT

In this section, we first implement a GSS based on Asmuth–Bloomt,n threshold SS scheme. The related correctness and security analyses are given in the following.


### 4.1. Implementing a GSS Based on Asmuth–Bloom SS Scheme

Our GSS scheme based on CRT consists of three algorithms: (1) main share generation for a group; (2) subshare generation for a shareholder; and (3) secret reconstruction.


#### 4.1.1. Main Share Generation for a Group

LetU be a set of n shareholders. All the shareholders are divided into m disjoint groups U=U1∪U2∪⋯∪Um. A shareholder only belongs to one group, i.e., Ui∩Uj=∅ if i≠j. Each group has ni shareholders such that n=n1+n2+⋯+nm.At first, the dealerD picks a prime number p0 and a sequence of pairwise co-prime positive integers p1,p2,…,pm with p1<p2<⋯<pm, mp03/p0−1<p1 and gcdp0,pi=1 for i=1,2,…,m, where pi is a public modulus associated with the group Ui. Then, D picks a random integer α and secret s in ℤp0, such that y=s+αp0<p1,p2,…,pm/p0. Finally, for each group Ui, the dealer D computes a main share si as si=s+αp0modpi.


#### 4.1.2. Subshare Generation for a Shareholder

AfterAlgorithm 1, each group Ui is allocated a main share. Let P=p1,p2,…,pm and ai=P/pi−1modpi. If there just exists one shareholder in a group, the dealer can use 0 as the random integer to generate a subshare for the only shareholder. Otherwise, for each shareholder Ukii in group Ui, the dealer D computes a subshare skii as(16)skii=siPpiai+rkiiPpip0modP,where rkii is a random integer picked by D and rkii∈ℤp0. D securely sends skii as a private share to the corresponding shareholder Ukii.


#### 4.1.3. Secret Reconstruction

If a shareholderP can recover the secret, without loss of generality, it is divided into two subsets ℳ1 and ℳ2, where ℳ1=Uk11,Uk22,…,Ukmm and ℳ2=P−ℳ1. ℳ1 can recover the secret due to the definition of GSS.Each shareholder inℳ1 releases its subshare to the other shareholders in P. After that, all the shareholders in P get m shares sk11,sk22,…,skmm. Then, the secret can be obtained by computing(17)s=∑i=1mskiimodPmodp0.


### 4.2. Correctness Analysis

In order to demonstrate that the proposed GSS scheme based on CRT can work correctly, we give two steps to proves=∑i=1mskiimodPmodp0 (Table 2).Step 1:y+∑i=1mrkiiP/pip0<P.Step 2:s=∑i=1mskiimodPmodp0.(18)∑i=1mskiimodPmodp0=∑i=1msiPpiai+rkiiPpip0modPmodp0=∑i=1msiPpiaimodP+∑i=1mrkiiPpip0modPmodp0=y+∑i=1mrkiiPpip0modPmodp0=s+αp0+∑i=1mrkiiPpip0modp0=s.Table 2
Proof of step 1 in GSS based on CRT.
FormulasRemarksy+∑i=1mrkiiP/pip0<s+αp0+mp02P/piRemark4.1:rkii∈ℤp0<s+αp0+mp02P/p1Remark4.2:p1<p2<⋯<pm<s+αp0+p0−1P/p0Remark4.3:mp03<p1p0−1<P/p0+p0−1P/p0Remark4.4:s+αp0<p1,p2,…,pm/p0=P.On account of Step 1 and Step 2, it is proven that the secrets can be obtained by computing ∑i=1mskiimodPmodp0.


### 4.3. Security Analysis

In this section, we give two theorems to prove the security of the proposed GSS based on CRT. Because the secrets is uniformly distributed in ℤp0, the probability of obtaining s from no information is 1/p0. Therefore, if the probability of an event occurring is equal to or less than 1/p0, the event can be considered as impossibility.Theorem 3.
In the GSS based on CRT, a subshareskiiis valid just in the groupUi, while it is invalid in any other groupUjwherei≠j.Proof.
According to the correctness analysis, we have proved that the subshareskii is valid in Ui. Hence, we give the proof of the latter part of Theorem 3 in the following. In more detail, we should prove that the probability of skii being valid in Uj is no more than 1/p0.
Ifskii is valid in Uj, it means(19)skii=sjPpjaj+rkjjPpjp0mod,where skii, P/pj, and aj are fixed values; sj has uniform distributions in ℤpi; and rkjj can be any integer over ℤp0. Because rkjj has p0 alternative values, there are at most p0 alternative values of sj to make equation (19) true. And due to sj∈ℤpj, the probability that equation (19) holds is less than p0/pj. Then, on account of p1<p2<⋯<pm and mp03/p0−1<p1, we can get p0/pj<p0/p1<1/p0. Therefore, equation (19) cannot be satisfied. In other words, the subshare skii is invalid in any other group Uj, where i≠j.Theorem 4.
In the GSS based on CRT, for a shareholder setP, if there exists a groupUisuch thatP∩Ui=∅, the setPcannot recover the secrets.Proof.
Without loss generality, suppose thatP=U−U1. In other words, P includes shareholders in all the groups except U1. Besides, suppose that at least two shareholders exist in a group.
Let us prove the following proposition firstly.Proposition 1.
IfP can recover the secret s, s can also be recovered from m−1 main shares si for i=2,3,…,m.From the correctness analysis, we know all subshares in the same groupUi are totally equivalent, i.e., ski is equivalent to shi when they are used to participate in secret reconstruction, where ski=siP/piai+rkiP/pip0modP, shi=siP/piai+rhiP/pip0modP and rki≠rhi. Therefore, we can use m−1 main shares and random integers which are all selected from ℤp0 to generate another set P′ such that P∩Ui=P′∩Ui for i=2,3,…,m. Then, if P can recover the secret, it means s can also be reconstructed from P′.Now, the correctness of Proposition1 has been proved. Its converse-negative proposition can be stated as follows. If s cannot be recovered from m−1 main shares si for i=2,3,…,m, P also cannot recover the secret s. Obviously, the converse-negative proposition is also true.Then, we will use the deduction to prove Theorem4. In group Uii≠1, we have(20)s1i=siPpiai+r1iPpip0modP⟹s1ipiP=siai+r1ip0modpi,because P/pi|s1i, gcdP/pi,pi=1, and gcdai,pi=1. Then, we get(21)e1i=siai+r1ip0modpi,e2i=siai+r2ip0modpi,where e1i=s1ipj/Pmodpi and e2i=s2ipj/Pmodpi. In the equation, e1i,e2i,c, and p0 are known, while si,r1i, and r2i are unknown. In a similar way, although there exist three unknown numbers in two equations, they can still be recovered because e1i,e2i∈ℤpi, si,r1,r2∈ℤp0 while pi>p1>mp03/p0−1. In other words, si,r1i,r2i are very short compared with e1i,e2i, Therefore, we still construct a lattice and utilize lattice basis reduction algorithm to recover si,r1i,r2i. From equation (21), we can deduce(22)e1iai−e2iaip0−1modpi≡r1iai−r2iaimodpi.Then, we still construct the latticeL as follows:(23)L=Mp00Mai10Mai01.Define a target vectort=Me1iai−e2iaip0−1modpi,0,0, where M is a prime greater than p0 to guarantee the distance of any lattice vector far away from t is greater than M.Note thatr1i,r2i∈ℤp0; then, the distance of t far away from lattice L is(24)0,r1i,r2i=r1i2+r2i2≤2p0.We claim that vectorv=Me1iai−e2iaip0−1modpi,r1i,r2i is the closest lattice point far away from t. Finally, we still invoke LLL algorithm to recover r1i and r2i by solving the closest vector problem (CVPv,L). Once we recover r1i and r2i, si can be obtained easily.After that, we getm−1 main shares si for i=2,3,…,m. Given the m−1 main shares, we can just obtain y′ by CRT from the following system of equations:(25)y′≡s2modp2,y′≡s3modp3,⋯y′≡smmodpm,where y′∈ℤP′, P′=p2,p3,…,pm, and y′=ymodP′, i.e., y=y′+βP′ from some integer β. However, from Figure 2, there are at least P/p0/P′=p1/p0>mp02/p0−1>p0 possible values of β such that y=y′+βP′. In other words, the probability of recovering s from m−1 main shares is less than 1/p0. According to the converse-negative nature of Proposition 1, the set P cannot recover the secret s if there exists a group Ui such that P∩Ui=∅.Figure 2
Relationship among parameters.


## 4.1. Implementing a GSS Based on Asmuth–Bloom SS Scheme

Our GSS scheme based on CRT consists of three algorithms: (1) main share generation for a group; (2) subshare generation for a shareholder; and (3) secret reconstruction.


### 4.1.1. Main Share Generation for a Group

LetU be a set of n shareholders. All the shareholders are divided into m disjoint groups U=U1∪U2∪⋯∪Um. A shareholder only belongs to one group, i.e., Ui∩Uj=∅ if i≠j. Each group has ni shareholders such that n=n1+n2+⋯+nm.At first, the dealerD picks a prime number p0 and a sequence of pairwise co-prime positive integers p1,p2,…,pm with p1<p2<⋯<pm, mp03/p0−1<p1 and gcdp0,pi=1 for i=1,2,…,m, where pi is a public modulus associated with the group Ui. Then, D picks a random integer α and secret s in ℤp0, such that y=s+αp0<p1,p2,…,pm/p0. Finally, for each group Ui, the dealer D computes a main share si as si=s+αp0modpi.


### 4.1.2. Subshare Generation for a Shareholder

AfterAlgorithm 1, each group Ui is allocated a main share. Let P=p1,p2,…,pm and ai=P/pi−1modpi. If there just exists one shareholder in a group, the dealer can use 0 as the random integer to generate a subshare for the only shareholder. Otherwise, for each shareholder Ukii in group Ui, the dealer D computes a subshare skii as(16)skii=siPpiai+rkiiPpip0modP,where rkii is a random integer picked by D and rkii∈ℤp0. D securely sends skii as a private share to the corresponding shareholder Ukii.


### 4.1.3. Secret Reconstruction

If a shareholderP can recover the secret, without loss of generality, it is divided into two subsets ℳ1 and ℳ2, where ℳ1=Uk11,Uk22,…,Ukmm and ℳ2=P−ℳ1. ℳ1 can recover the secret due to the definition of GSS.Each shareholder inℳ1 releases its subshare to the other shareholders in P. After that, all the shareholders in P get m shares sk11,sk22,…,skmm. Then, the secret can be obtained by computing(17)s=∑i=1mskiimodPmodp0.


## 4.1.1. Main Share Generation for a Group

LetU be a set of n shareholders. All the shareholders are divided into m disjoint groups U=U1∪U2∪⋯∪Um. A shareholder only belongs to one group, i.e., Ui∩Uj=∅ if i≠j. Each group has ni shareholders such that n=n1+n2+⋯+nm.At first, the dealerD picks a prime number p0 and a sequence of pairwise co-prime positive integers p1,p2,…,pm with p1<p2<⋯<pm, mp03/p0−1<p1 and gcdp0,pi=1 for i=1,2,…,m, where pi is a public modulus associated with the group Ui. Then, D picks a random integer α and secret s in ℤp0, such that y=s+αp0<p1,p2,…,pm/p0. Finally, for each group Ui, the dealer D computes a main share si as si=s+αp0modpi.


## 4.1.2. Subshare Generation for a Shareholder

AfterAlgorithm 1, each group Ui is allocated a main share. Let P=p1,p2,…,pm and ai=P/pi−1modpi. If there just exists one shareholder in a group, the dealer can use 0 as the random integer to generate a subshare for the only shareholder. Otherwise, for each shareholder Ukii in group Ui, the dealer D computes a subshare skii as(16)skii=siPpiai+rkiiPpip0modP,where rkii is a random integer picked by D and rkii∈ℤp0. D securely sends skii as a private share to the corresponding shareholder Ukii.


## 4.1.3. Secret Reconstruction

If a shareholderP can recover the secret, without loss of generality, it is divided into two subsets ℳ1 and ℳ2, where ℳ1=Uk11,Uk22,…,Ukmm and ℳ2=P−ℳ1. ℳ1 can recover the secret due to the definition of GSS.Each shareholder inℳ1 releases its subshare to the other shareholders in P. After that, all the shareholders in P get m shares sk11,sk22,…,skmm. Then, the secret can be obtained by computing(17)s=∑i=1mskiimodPmodp0.


## 4.2. Correctness Analysis

In order to demonstrate that the proposed GSS scheme based on CRT can work correctly, we give two steps to proves=∑i=1mskiimodPmodp0 (Table 2).Step 1:y+∑i=1mrkiiP/pip0<P.Step 2:s=∑i=1mskiimodPmodp0.(18)∑i=1mskiimodPmodp0=∑i=1msiPpiai+rkiiPpip0modPmodp0=∑i=1msiPpiaimodP+∑i=1mrkiiPpip0modPmodp0=y+∑i=1mrkiiPpip0modPmodp0=s+αp0+∑i=1mrkiiPpip0modp0=s.Table 2
Proof of step 1 in GSS based on CRT.
FormulasRemarksy+∑i=1mrkiiP/pip0<s+αp0+mp02P/piRemark4.1:rkii∈ℤp0<s+αp0+mp02P/p1Remark4.2:p1<p2<⋯<pm<s+αp0+p0−1P/p0Remark4.3:mp03<p1p0−1<P/p0+p0−1P/p0Remark4.4:s+αp0<p1,p2,…,pm/p0=P.On account of Step 1 and Step 2, it is proven that the secrets can be obtained by computing ∑i=1mskiimodPmodp0.


## 4.3. Security Analysis

In this section, we give two theorems to prove the security of the proposed GSS based on CRT. Because the secrets is uniformly distributed in ℤp0, the probability of obtaining s from no information is 1/p0. Therefore, if the probability of an event occurring is equal to or less than 1/p0, the event can be considered as impossibility.Theorem 3.
In the GSS based on CRT, a subshareskiiis valid just in the groupUi, while it is invalid in any other groupUjwherei≠j.Proof.
According to the correctness analysis, we have proved that the subshareskii is valid in Ui. Hence, we give the proof of the latter part of Theorem 3 in the following. In more detail, we should prove that the probability of skii being valid in Uj is no more than 1/p0.
Ifskii is valid in Uj, it means(19)skii=sjPpjaj+rkjjPpjp0mod,where skii, P/pj, and aj are fixed values; sj has uniform distributions in ℤpi; and rkjj can be any integer over ℤp0. Because rkjj has p0 alternative values, there are at most p0 alternative values of sj to make equation (19) true. And due to sj∈ℤpj, the probability that equation (19) holds is less than p0/pj. Then, on account of p1<p2<⋯<pm and mp03/p0−1<p1, we can get p0/pj<p0/p1<1/p0. Therefore, equation (19) cannot be satisfied. In other words, the subshare skii is invalid in any other group Uj, where i≠j.Theorem 4.
In the GSS based on CRT, for a shareholder setP, if there exists a groupUisuch thatP∩Ui=∅, the setPcannot recover the secrets.Proof.
Without loss generality, suppose thatP=U−U1. In other words, P includes shareholders in all the groups except U1. Besides, suppose that at least two shareholders exist in a group.
Let us prove the following proposition firstly.Proposition 1.
IfP can recover the secret s, s can also be recovered from m−1 main shares si for i=2,3,…,m.From the correctness analysis, we know all subshares in the same groupUi are totally equivalent, i.e., ski is equivalent to shi when they are used to participate in secret reconstruction, where ski=siP/piai+rkiP/pip0modP, shi=siP/piai+rhiP/pip0modP and rki≠rhi. Therefore, we can use m−1 main shares and random integers which are all selected from ℤp0 to generate another set P′ such that P∩Ui=P′∩Ui for i=2,3,…,m. Then, if P can recover the secret, it means s can also be reconstructed from P′.Now, the correctness of Proposition1 has been proved. Its converse-negative proposition can be stated as follows. If s cannot be recovered from m−1 main shares si for i=2,3,…,m, P also cannot recover the secret s. Obviously, the converse-negative proposition is also true.Then, we will use the deduction to prove Theorem4. In group Uii≠1, we have(20)s1i=siPpiai+r1iPpip0modP⟹s1ipiP=siai+r1ip0modpi,because P/pi|s1i, gcdP/pi,pi=1, and gcdai,pi=1. Then, we get(21)e1i=siai+r1ip0modpi,e2i=siai+r2ip0modpi,where e1i=s1ipj/Pmodpi and e2i=s2ipj/Pmodpi. In the equation, e1i,e2i,c, and p0 are known, while si,r1i, and r2i are unknown. In a similar way, although there exist three unknown numbers in two equations, they can still be recovered because e1i,e2i∈ℤpi, si,r1,r2∈ℤp0 while pi>p1>mp03/p0−1. In other words, si,r1i,r2i are very short compared with e1i,e2i, Therefore, we still construct a lattice and utilize lattice basis reduction algorithm to recover si,r1i,r2i. From equation (21), we can deduce(22)e1iai−e2iaip0−1modpi≡r1iai−r2iaimodpi.Then, we still construct the latticeL as follows:(23)L=Mp00Mai10Mai01.Define a target vectort=Me1iai−e2iaip0−1modpi,0,0, where M is a prime greater than p0 to guarantee the distance of any lattice vector far away from t is greater than M.Note thatr1i,r2i∈ℤp0; then, the distance of t far away from lattice L is(24)0,r1i,r2i=r1i2+r2i2≤2p0.We claim that vectorv=Me1iai−e2iaip0−1modpi,r1i,r2i is the closest lattice point far away from t. Finally, we still invoke LLL algorithm to recover r1i and r2i by solving the closest vector problem (CVPv,L). Once we recover r1i and r2i, si can be obtained easily.After that, we getm−1 main shares si for i=2,3,…,m. Given the m−1 main shares, we can just obtain y′ by CRT from the following system of equations:(25)y′≡s2modp2,y′≡s3modp3,⋯y′≡smmodpm,where y′∈ℤP′, P′=p2,p3,…,pm, and y′=ymodP′, i.e., y=y′+βP′ from some integer β. However, from Figure 2, there are at least P/p0/P′=p1/p0>mp02/p0−1>p0 possible values of β such that y=y′+βP′. In other words, the probability of recovering s from m−1 main shares is less than 1/p0. According to the converse-negative nature of Proposition 1, the set P cannot recover the secret s if there exists a group Ui such that P∩Ui=∅.Figure 2
Relationship among parameters.


## 5. Numerical Examples

In this section, we give two numerical examples to illustrate the two GSS schemes, respectively. In both examples, suppose that there arem=3 groups U1 with 2 shareholders, U2 with 3 shareholders, and U3 with 2 shareholders.Example 1.
Firstly, the dealerD selects two prime numbers g=7 and p=157 such that p>mg2. Then, D generates a degree-2 polynomial fx=5+128x+73x2modp, where secret s is equal to 5.
For groupU1, D selects an integer x1=35 as the public information associated with U1 and computes fx1=24 as its main share. For group U2, D selects an integer x2=92 as the public information associated with U2 and computes fx2=83 as its main share. For group U3, D selects an integer x3=136 as the public information associated with U3 and computes fx3=151 as its main share.
For the two shareholdersU11 and U21 in U1, the dealer D uses two random integers r11=2 and r21=5 to compute subshares s11=s1x2/x2−x1x3/x3−x1+r11gmodp=12 and s21=s1x2/x2−x1x3/x3−x1+r21gmodp=33. For three shareholders U12, U22, and U32 in U2, D selects three random integers r12=1, r22=3, and r32=6 to compute subshares s12=24, s22=38, and s32=59. For the two shareholders U13 and U23 in U3, D picks two random integers r13=2 and r23=6 to compute subshares s13=4 and s23=32. After that, the dealer D sends each subshare to the corresponding shareholder securely.
Secret reconstruction 1: IfU11, U32 and U23 work together to recover the secret, each of them releases its share to the others. Then, the secret is evaluated as s=s11+s32+s23modpmodg=12+59+32mod157mod7=5.
Secret reconstruction 2: IfU21, U12 and U13 collaborate to recover the secret, each of them releases its share to the others. Then, the secret is evaluated as s=s21+s12+s13modpmodg=33+24+4mod157mod7=5.Example 2.
Firstly, the dealerD picks a prime number p0=7 and 3 pairwise co-prime moduli p1=173, p2=179 and p3=181 such that mp03/p0−1<p1 and gcdp0,p1=gcdp0,p2=gcdp0,p3=1, where pi is public modulus associated with group Ui for i=1,2,3. Then, D selects a secret s=5 and a random integer α=7569 such that s+αp0<p1p2p3/p0.
For groupU1, the dealer D computes a main share s1=s+αp0modp1=50. Main shares for U2 and U3 are computed as s2=s+αp0modp2=4 and s3=s+αp0modp3=136.
For the two shareholdersU11 and U21 in U1, the dealer D uses two random integers r11=2 and r21=4 to compute subshares s11=s1P/p1a1+r11P/p1p0modP=4924648 and s21=s1P/p1a1+r21P/p1p0modP=5378234, where P=p1∗p2∗p3 and a1P/p1=1modp1. For the three shareholders U12, U22 and U32 in U2, D selects three random integers r12=1, r22=3 and r32=5 to compute subshares s12=3945438, s22=4383820 and s32=4822202. For the two shareholders U13 and U23 in U3, D picks two random integers r13=3 and r23=6 to compute subshares s13=3716040 and s23=4366347. After that, the dealer D sends each subshare to the corresponding shareholder securely.
Secret reconstruction 1: ifU21, U12, and U23 work together to recover the secret, each of them releases its share to the others. Then, the secret is evaluated as s=s21+s12+s23modPmodp0=5378234+3945438+4366347mod5605027mod7=2479965mod7=5.
Secret reconstruction 2: ifU11, U22, and U13 collaborate to recover the secret, each of them releases its share to the others. Then, the secret is evaluated as s=s11+s22+s13modPmodp0=4924648+4383820+3716040mod5605027mod7=1814454mod7=5.


## 6. Discussion

In this section, we show both the two GSS schemes are perfect SS schemes. Then, we give some discussions about the information rate for the two GSS schemes.


### 6.1. Perfect SS

Definition 4.
Perfect SS: in an SS scheme, lets, S, P, and λ be the secret, secret space, a shareholder set, and share set of P. The SS is perfect with respect to probability distribution of s on the secret space S if(1)
Hs≥0.(2)
Hs|λ=0 if P is an authorized set.(3)
Is;λ=Hs−Hs|λ=0 if P is not an authorized set.
In the GSS scheme based on LIP, secret space isS=ℤg, and hence Hs=log2g>0. From the correctness analysis in Section 3, any authorized set can recover the secret by executing the algorithm in secret reconstruction, so the second condition holds. From Theorem 2, the probability of obtaining the secret from the shares kept by an unauthorized shareholder set P is also 1/g, i.e., Hs|λ=Hs=log2g. Therefore, the GSS scheme based on LIP is a perfect SS scheme.
In the same way, we can get that the GSS scheme based on CRT is also a perfect SS scheme.


### 6.2. Information Rate

Definition 5.
Information rate: in an SS scheme, lets be the secret and S=s1,s2,…,sn be the share set. Then, the information rate of the scheme is defined as(26)ρ=minsi∈Slog2slog2si.
According to [22], the information rate of a prefect SS scheme is no more than 1. Besides, the higher ρ is, the more effectively the SS scheme works. In the GSS scheme based on LIP, secret s is in ℤg while every share si is in ℤp. Therefore, the information rate ρ is equal to log2g/log2p, which is between 1/3 and 1/2 because p>mg2. Although ρ is less than 1, it is still acceptable. However, in the GSS based on CRT, secret s is in ℤp0 while every share si is in ℤP, where P is a product of m module and each modulus is greater than p0. Therefore, the information rate is very low. We just show the scheme to prove that CRT also can be used to design GSS scheme. In practice, the first GSS scheme based on LIP is more advisable.


## 6.1. Perfect SS

Definition 4.
Perfect SS: in an SS scheme, lets, S, P, and λ be the secret, secret space, a shareholder set, and share set of P. The SS is perfect with respect to probability distribution of s on the secret space S if(1)
Hs≥0.(2)
Hs|λ=0 if P is an authorized set.(3)
Is;λ=Hs−Hs|λ=0 if P is not an authorized set.
In the GSS scheme based on LIP, secret space isS=ℤg, and hence Hs=log2g>0. From the correctness analysis in Section 3, any authorized set can recover the secret by executing the algorithm in secret reconstruction, so the second condition holds. From Theorem 2, the probability of obtaining the secret from the shares kept by an unauthorized shareholder set P is also 1/g, i.e., Hs|λ=Hs=log2g. Therefore, the GSS scheme based on LIP is a perfect SS scheme.
In the same way, we can get that the GSS scheme based on CRT is also a perfect SS scheme.


## 6.2. Information Rate

Definition 5.
Information rate: in an SS scheme, lets be the secret and S=s1,s2,…,sn be the share set. Then, the information rate of the scheme is defined as(26)ρ=minsi∈Slog2slog2si.
According to [22], the information rate of a prefect SS scheme is no more than 1. Besides, the higher ρ is, the more effectively the SS scheme works. In the GSS scheme based on LIP, secret s is in ℤg while every share si is in ℤp. Therefore, the information rate ρ is equal to log2g/log2p, which is between 1/3 and 1/2 because p>mg2. Although ρ is less than 1, it is still acceptable. However, in the GSS based on CRT, secret s is in ℤp0 while every share si is in ℤP, where P is a product of m module and each modulus is greater than p0. Therefore, the information rate is very low. We just show the scheme to prove that CRT also can be used to design GSS scheme. In practice, the first GSS scheme based on LIP is more advisable.


## 7. Conclusions

In this paper, we propose a kind of secret sharing which is named group secret sharing (GSS). By modifying Shamir and Asmuth–Bloomt,n threshold SS schemes, we implement two GSS schemes based on LIP and CRT, respectively. The correctness analysis shows that the two GSS schemes can work correctly and the security analysis proves that the two schemes are secure. For a better illustration, two numerical examples are also given. Both the two GSS schemes are perfect, but the GSS based on LIP is more effective because its information rate is higher than the other one.



---

*Source: 6678345-2021-04-05.xml*