# Unordered Multisecret Sharing Based on Generalized Chinese Remainder Theorem

Authors: Xiaoping Li; Hefeng Chen; Yanjun Liu; Chin-Chen Chang
Journal: Security and Communication Networks
 (2020)

---

## Abstract

Multisecret sharing schemes have been widely used in the area of information security, such as cloud storage, group authentication, and secure parallel communications. One of the issues for these schemes is to share and recover multisecret from their shareholders. However, the existing works consider the recovery of multisecret only when the correspondences between the secrets and their shares are definite. In this paper, we propose a multisecret sharing scheme to share and recover two secrets among the participants based on the generalized Chinese Remainder Theorem (GCRT), where the multisecret and their shares are unordered. To overcome the leakage of information, we propose an improved scheme including the improved sharing phase and the recovery phase. The improved scheme has not only a more secure performance but also a lower computation complexity. The conditions for recovery failure and success are also explored.


---

## Body

## 1. Introduction

Secret sharing plays a critical role in numerous applications, such as in threshold cryptography, access control, cloud computing, data hiding, and digital watermarking [1–3]. In a secret-sharing scheme (SS), a dealer divides a secret into several pieces and then shares them among the shareholders. In 1979, Shamir and Blakley independently introduced the threshold schemes based on the interpolating polynomial in [4] and the linear projective geometry in [5], respectively. For a t,n SS with threshold t, a secret s is divided into n pieces to be sheared among n shareholders by a dealer. It shows that the secret can be recovered by any no less than t shares, while the recovery failure with fewer than t shares. Besides this kind of SS scheme, there are many other types, such as Mignotte’s scheme [6], the Chinese Remainder Theorem- (CRT-) based Asmuth-Bloom scheme [7] and its generalizations [8, 9], and ramp secret-sharing scheme [10, 11].Naturally, a secret-sharing scheme can be generalized to the case of multiple secrets, i.e., multisecret sharing [12, 13]. Several schemes for multisecret sharing have been proposed in [14–22]. According to the way of recovering, the existing works can be grouped into two categories. One is to recover multisecret in a stage-by-stage way, the other is to recover multisecret simultaneously. In [15], a one-way function-based multistage secret-sharing scheme was proposed to share multisecret. The authors presented a public shift scheme to obtain the true pieces and then used the proper one-way function to reconstruct the secrets stage-by-stage in a predetermined order. For this scheme, it needs a large number of public values. An improved method was proposed in [16], where a less number of public values is needed. In fact, the scheme presented in [15] is actually of one-time use. To overcome this drawback, a one-way hash function-based multiuse threshold secret-sharing scheme was proposed in [17]. In [18], a multistage multisecret-sharing scheme and a multilevel multisecret-sharing scheme are proposed, which are based on Mignotte’s sequence and Asmuth’s Bloom sequence, respectively. For the second category of the recovery method, multisecret is recovered simultaneously by a bivariate function [19–21]. One of the disadvantages is that the required function is hard to get, although the computational load can be reduced by optimizing some existing algorithms. In a word, this approach is inconvenient in practical applications.All the above works consider the case when the correspondences between multisecret and elements in each share are definite. When the correspondences between multisecret and elements in each share are unclear, we say that the shares are unordered. Sharing and recovering multisecret are more challenging when the shares are unordered. For this type of sharing scheme, it is more safe since multisecret cannot be recovered directly from the given unordered shares. It is a generalization of single case and has a wide application in the scenarios of keeping some sensitive and important information, such as passwords of opening bank safes or launching missile [23, 24]. This paper gives a novel scheme to share and recover multisecret from the unordered shares. Motivated by the works in [25–27], we propose a generalized CRT-based multisecret-sharing and recovering scheme. The proposed scheme is not a perfect SS since information can be leaked. To overcome this drawback, we propose an improved multisecret-sharing scheme. The improved scheme not only is more secure but also has a lower computation complexity.The rest of the paper is organized as follows. In Section2, we introduce the unordered multisecret-sharing problem and then briefly recall the basic idea of the generalized CRT. In Section 3, we present a generalized CRT-based multisecret-sharing scheme. In Section 4, we present the improved multisecret-sharing scheme. In Section 5, we conclude this paper.


## 2. Unordered Multisecret Sharing and the Generalized CRT

In this section, we first introduce the unordered multisecret-sharing problem considered in this paper. Then, we model the problem as the generalized CRT. Some existing results for the generalized CRT are also introduced.


### 2.1. Problem of Unordered Multisecret Sharing

Suppose that we have a set of two secretss1,s2 and n shares U1,U2,…,Un. For each share Ui, we have Ui=r1,i,r2,i with modulus mi, where r1,i,r2,i are the remainders of s1,s2 modulo a positive integer mi. Notice that the correspondences between the remainders in each share r1,i,r2,i and their secrets s1,s2 are unknown. In other words, we cannot determine whether r1,i is the remainder of s1 or s2 modulo mi. For the recovery phase, the problem is how to efficiently recover the two secrets s1,s2 from the given shareholders?


### 2.2. Model of the Unordered Multisecret Sharing

If multisecret is viewed as multiple unknown integers, then the pieces of shares are the remainders of multiple integer modulo some given moduli, where the correspondences between multiple integers and the remainders are unknown. Consequently, the problem of recovering unordered multisecret sharing can be modeled as the generalized CRT that determines multiple integers from their residue sets.Traditional CRT tells us that an unknown integer can be uniquely recovered from its remainder modulo several given moduli, if and only if the unknown integer is less than the least common multiple (lcm) of the given moduli [28]. One of the generalization is to recover two unknown integers s1,s2 from their remainders modulo several moduli. Different from the traditional CRT, the remainders of s1,s2 modulo a given modulus are two remainders in a same set, which is called the residue set. For example, the remainders of 26,38 modulo three moduli 5, 7, and 11 are the residue sets 1,3, 3,5, and 4,5, respectively. For this kind of generalized CRT, two integers s1,s2 should be simultaneously determined from their residue sets.There are two differences between this kind of generalized CRT and the traditional CRT. One is that the correspondence between the integerss1,s2 and their remainders in the residue sets is unknown. As the above example shows, for the first residue set 1,3, it is not known whether 1 is the remainder of 26 or 38 modulo 5. The other difference is how large the two integers can be uniquely determined from their residue sets for the given moduli, which will be explained below. For the traditional CRT, the largest integer that can be uniquely determined from its remainders for some given moduli is the least common multiple of all the moduli. However, this conclusion may not be true for the generalized CRT. Consider the above example again. If the two integers are less than lcm5,7,11=385, then we have four candidates:26,38, 103,346, 136,313, and 213,236, where all of them have the same residue sets 1,3, 3,5, and 4,5 with moduli 5, 7, and 11, respectively. Hence, the two unknown integers s1,s2 cannot be uniquely determined from the given residue sets when the two integers are restricted in range of 0,385.


### 2.3. Model of the Unordered Multisecret Sharing

In order to uniquely determine the two integers from their residue sets for some given moduli, the concept of the dynamic range was introduced [25], where the dynamic range is a range that any multiple integers within it can be uniquely determined from their residue set modulo the given moduli. In [26], the largest dynamic range of the two integers for the given moduli was obtained. For convenience of description, we denote the remainder of x modulo y as xy.For any given modulus setℳ=m1,m2,…,mn, the largest dynamic range Dℳ can be determined by the following results [26].Proposition 1.
Ifℳ=2,2k+1 for some positive integers k, then(1)Dℳ=2k+2.Proposition 2.
Letn pairwise coprime integers be 2≤m1<m2<⋯<mn. If mn−1≥3, then(2)Dℳ=minI⊆1,2,…,n∏i∈Imi+∏i∈I¯mi,where I¯ is the complement of I in 1,2,…,n.
As an example, we consider the largest dynamic range of the two modulus setsℳ1=2,13 and ℳ2=11,13,17,19. According to Propositions 1 and 2, we have Dℳ1=14 and Dℳ2=11×19+13×17=430, respectively.


## 2.1. Problem of Unordered Multisecret Sharing

Suppose that we have a set of two secretss1,s2 and n shares U1,U2,…,Un. For each share Ui, we have Ui=r1,i,r2,i with modulus mi, where r1,i,r2,i are the remainders of s1,s2 modulo a positive integer mi. Notice that the correspondences between the remainders in each share r1,i,r2,i and their secrets s1,s2 are unknown. In other words, we cannot determine whether r1,i is the remainder of s1 or s2 modulo mi. For the recovery phase, the problem is how to efficiently recover the two secrets s1,s2 from the given shareholders?


## 2.2. Model of the Unordered Multisecret Sharing

If multisecret is viewed as multiple unknown integers, then the pieces of shares are the remainders of multiple integer modulo some given moduli, where the correspondences between multiple integers and the remainders are unknown. Consequently, the problem of recovering unordered multisecret sharing can be modeled as the generalized CRT that determines multiple integers from their residue sets.Traditional CRT tells us that an unknown integer can be uniquely recovered from its remainder modulo several given moduli, if and only if the unknown integer is less than the least common multiple (lcm) of the given moduli [28]. One of the generalization is to recover two unknown integers s1,s2 from their remainders modulo several moduli. Different from the traditional CRT, the remainders of s1,s2 modulo a given modulus are two remainders in a same set, which is called the residue set. For example, the remainders of 26,38 modulo three moduli 5, 7, and 11 are the residue sets 1,3, 3,5, and 4,5, respectively. For this kind of generalized CRT, two integers s1,s2 should be simultaneously determined from their residue sets.There are two differences between this kind of generalized CRT and the traditional CRT. One is that the correspondence between the integerss1,s2 and their remainders in the residue sets is unknown. As the above example shows, for the first residue set 1,3, it is not known whether 1 is the remainder of 26 or 38 modulo 5. The other difference is how large the two integers can be uniquely determined from their residue sets for the given moduli, which will be explained below. For the traditional CRT, the largest integer that can be uniquely determined from its remainders for some given moduli is the least common multiple of all the moduli. However, this conclusion may not be true for the generalized CRT. Consider the above example again. If the two integers are less than lcm5,7,11=385, then we have four candidates:26,38, 103,346, 136,313, and 213,236, where all of them have the same residue sets 1,3, 3,5, and 4,5 with moduli 5, 7, and 11, respectively. Hence, the two unknown integers s1,s2 cannot be uniquely determined from the given residue sets when the two integers are restricted in range of 0,385.


## 2.3. Model of the Unordered Multisecret Sharing

In order to uniquely determine the two integers from their residue sets for some given moduli, the concept of the dynamic range was introduced [25], where the dynamic range is a range that any multiple integers within it can be uniquely determined from their residue set modulo the given moduli. In [26], the largest dynamic range of the two integers for the given moduli was obtained. For convenience of description, we denote the remainder of x modulo y as xy.For any given modulus setℳ=m1,m2,…,mn, the largest dynamic range Dℳ can be determined by the following results [26].Proposition 1.
Ifℳ=2,2k+1 for some positive integers k, then(1)Dℳ=2k+2.Proposition 2.
Letn pairwise coprime integers be 2≤m1<m2<⋯<mn. If mn−1≥3, then(2)Dℳ=minI⊆1,2,…,n∏i∈Imi+∏i∈I¯mi,where I¯ is the complement of I in 1,2,…,n.
As an example, we consider the largest dynamic range of the two modulus setsℳ1=2,13 and ℳ2=11,13,17,19. According to Propositions 1 and 2, we have Dℳ1=14 and Dℳ2=11×19+13×17=430, respectively.


## 3. Unordered Multisecret-Sharing Scheme

In this section, we propose two algorithms, i.e., the unordered multisecret generation phase and the recovery phase. Some results of the proposed scheme are also given.


### 3.1. Unordered Multisecret Generation

Suppose that the shareholders have the public informationmi, where mi is pairwise coprime integer satisfying 2≤m1<m2<⋯<mn. Note that the scheme of multisecret sharing is trivial when n≤2, and we only consider n≥3 in this paper. Let t be a positive integer satisfying t<n. The generation of n shares from two unordered secrets s1,s2 contains two steps. First, determine the largest range of two secrets such that t shares or more than t shares can lead to a unique recovery of s1,s2. Second, obtain n shares U1,U2,…,Un by reducing s1,s2 modulo moduli m1,m2,…,mn, respectively. For convenience, we denote(3)ℳ1=mn−t+2,…,mn,ℳ2=m1,m2…,mt.Define(4)i0=mini:∏j=inmj<Dℳ2,1≤i≤n.It is not difficult to find that(5)n−i0+1<t.If not, i.e.,n−i0+1≥t, then we have(6)Dℳ2<∏i=1tmi≤∏j=1n−i0+1mj≤∏j=i0nmj,by the definition of Dℳ in (2), which contradicts with (4). For convenience, we let(7)t0=n−i0+1,and let(8)DL=max∏j=i0nmj,Dℳ1.Then, two unordered secretss1,s2 can be selected in the range of DL,Dℳ2, i.e.,(9)DL<si<Dℳ2,i=1,2.Consequently, sharesUi=r1,i,r2,i can be obtained by(10)s1,s2≡r1,i,r2,imodmi,i=1,2,…,n.That is,(11)Ui=s1mi,s2mi,i=1,2,…,n.To sum up, we have the following unordered multisecret generation phase for the pairwise coprime integersm1,m2,…,mn, which is shown in Table 1 below.Table 1
Generalized CRT-based unordered multisecret-sharing algorithm.
Unordered multisecret-sharing algorithmStep 1. Determineℳ1 and compute Dℳ2 by (3) and (2), respectivelyStep 2. Determinei0 by (4)Step 3. DetermineDL by (8)Step 4. Select two unordered secretss1,s2 satisfying (9)Step 5. Obtainn shares U1,U2…,Un by (10)


### 3.2. Unordered Multisecret Recovery

Now, we consider the problem of recovering the two secretss1,s2 from the given l shares Ui1,Ui2,…,Uil, where 1≤ij≤n and l>t. Table 2 gives the generalized CRT-based algorithm to recover the two secrets.Table 2
Generalized CRT-based unordered multisecret recovery algorithm.
Unordered multisecret recovery algorithmStep 1. For each shareUij, compute qij=r1,ij+r2,ijmij,j=1,2,…,lStep 2. ComputeM=mi1mi2⋯mil, Mij=M/mil, and M¯ij satisfying M¯ijMij≡1modmijStep 3. Computeξ1=∑j=1lM¯ijMijqijMStep 4. Letk=max0,⌈ξ1−2M⌉, then compute ξ2=∑j=1lM¯ijMijr1,ij−kr2,ij−kMStep 5. Obtain the two secretss1,s2 by solving x−k2−ξ1−2kx−k+ξ2=0Next theorem gives some results of the multisecret-sharing scheme discussed above.Theorem 1.
Let the two secretss1,s2 be defined in (9), and let Ui1,Ui2,…,Uil be l shares with the corresponding modulus set ℳ=mi1,mi2,…,mil, where 1≤il≤n for j=1,2,…,l. Then, we have the following results.(1)
Ifl≤t0, then s1,s2 cannot be recovered, where t0 is defined in (7).(2)
Ift0<l<t, then s1,s2 cannot be recovered in 0,Dℳ. Moreover, the two secrets cannot be uniquely recovered in 0,lcmℳ, where lcmℳ≥Dℳ2.(3)
Ifl≥t, then s1,s2 can be uniquely recovered.Proof.
(1)
We consider the case whenl=t0. For any t0=n−i0+1 shares Ui1,Ui2,…,Uin−i0+1, we have the corresponding moduli mi1,mi2,…,min−i0+1. According to the definition of i0 in (4), we have(12)∏j=1n−i0+1mij≤∏j=i0nmj.Note thatlcmℳ≤∏j=1n−i0+1mij. It follows that(13)lcmℳ≤∏j=i0nmj.IfDℳ1≥∏j=i0nmj, then we obtain from (8) that DL=Dℳ1. From (9) and (13), we have(14)lcmℳ≤Dℳ1=DL<si,i=1,2.IfDℳ1<∏j=i0nmj, then we obtain from (8) that DL=∏j=i0nmj. From (9) and (13), we have(15)lcmℳ≤DL<si,i=1,2.Thus, the two secretss1,s2 cannot be reconstructed from t0 shares. For the case of the less than t0 shares, the proof is obvious and it is omitted here.(2)
We consider the reconstruction of anyl=t−1 shares Ui1,Ui2,…,Uit−1 that is different from the shares Un−t+2,Un−t+3,…,Un. For convenience, we denote ℳ′=mi1,mi2,…,mit−1 and suppose(16)mi1<mi2<⋯<mit−1,without loss of generality. Recall thatm1<m2<⋯<mn. Hence, we have(17)mi1<mn−t+2,mi2<mn−t+3,…,mit−1<mn,and then(18)minI⊆i1,i2,…,it−1∏i∈Imi+∏i∈I¯mi<minI⊆n−t+2,…,n∏i∈Imi+∏i∈I¯mi.According to (2), we have(19)Dℳ′<Dℳ1.By (8) and (9), we obtain(20)Dℳ′<si,i=1,2.According to the generalized CRT, we know thats1,s2 cannot be recovered in the range of 0,Dℳ′ from their shares Ui1,Ui2,…,Uil. For the case of l<t−1, the conclusion also holds. Next, we consider the recovery of the two secrets in 0,lcmℳ.Letl shares be Ui1=r1,i1,r2,i1,…,Uil=r1,il,r2,il. According to (11), we have(21)Ui1=s1mi1,s2mi1,…,Uil=s1mil,s2mil.Note that(22)si<Dℳ2≤lcmℳ,i=1,2.Hence, the two secretss1 and s2 can be recovered separately by using the CRT when the remainders in the residue sets are properly ordered. More details can be seen in Remark 1 below.(3)
We considert shares Ui1,Ui2,…,Uit, where 1≤ij≤n. Let Ui1,Ui2,…,Uit. Similar to the proof of (2) above, we can prove that the dynamic range ℳ″ satisfies(23)Dℳ″>Dℳ2>si,i=1,2.
Hence,s1,s2 can be uniquely reconstructed from their shares Ui1,Ui2,…,Uit by the generalized CRT. For the case of more than t shares, the proof is obvious and it is omitted here.Remark 1.
Theorem1 tells us that the two secrets cannot be recovered when the number of shares l≤t0, where t0 is defined in (7). When l>t, the two secrets can be uniquely recovered by using the proposed generalized CRT. When t0<l<t, the two secrets cannot be successfully recovered. To be specific, the two secrets cannot be recovered in the range of 0,Dℳ in this case. In addition, the two secrets cannot be uniquely recovered in 0,lcmℳ by using the CRT since the correspondences between the two secrets and the elements in each shareholder are unclear. It is clear that the remainder of s1 or s2 cannot be determined from any share Ui. To recover s1 and s2, we have 2l−1 possible cases of remainders with moduli mi:s1mi1,s2mi2,…,s2mil and s2mi1,s1mi2,…,s1mil;…,s1mi1,s1mi2,…,s1mil and s2mi1,s2mi2,…,s2mil.
According to the CRT,s1 and s2 can be recovered only from the last tuples in the range of 0,lcmℳ.
Now, we consider the computational complexity of the proposed scheme. According to Algorithm 2, we know that the computational complexity of each shareholder isO1. For the proposed generalized CRT-based multisecret recovery algorithm, the computational complexity is O12l. For the CRT algorithm, the computational complexity is O2l−1 as discussed above.Example 1.
Let us consider a two secret-sharing and recovering process when moduli arem1=11,m2=13,m3=17,m4=19, and m5=20. Set t=4. By the definition of ℳ1 and ℳ2 in (3), we have ℳ1=17,19,20 and ℳ2=11,13,17,19. By Proposition 2, we have Dℳ1=343 and Dℳ2=430. Since m4m5=380, we have i0=4 and then DL=380 by Step 2 in Table 1. Let two secrets be s1,s2=398,426, which are in the range of 380,430. Then, we have five shares U1=2,8, U2=8,10, U3=1,7, U4=8,18, and U5=6,18 with moduli m1,m2,…,m5, respectively.
Now, we consider the recovery of two secrets froml shareholders. We have three cases below.(1)
l≤2.Suppose that the two shares areUi1 and Ui2 with 1≤i1,i2≤5. Clearly,(24)lcmmi1,mi2≤m4m5<si,i=1,2.Hence, the two secretss1,s2 cannot be recovered.(2)
l=3.LetUi1,Ui2,andUi3 be three shares, and let ℳ=mi1,mi2,mi3. In this case, the two secrets cannot be determined in 0,Dℳ since Dℳ<s1 and Dℳ<s2. Moreover, the two secrets cannot be uniquely determined in 0,lcmℳ. For example, given three shares U1,U2,andU3, we have four candidates: 398,426,959,2296,970,2285,and1531,1724. In other words, all these candidates have the same shares U1,U2,andU3 with moduli m1,m2,andm3, respectively. Table 3 gives the illustration of recovering the two secrets for all cases, where Zn=0,1,…,n−1.(3)
l≥4.
In this case, the two secrets can be uniquely determined. Suppose that the shares areU1,U2,U3, and U4. Next, we recover s1,s2 by using the proposed generalized CRT algorithm.
Note thatM=m1m2m3m4=46189, M1=4199, M¯1=7, M2=3553, M¯2=10, M3=2717, M¯3=11, M4=2431, and M¯4=18. By Step 1 in Table 2, we have q1=10, q2=5, q3=8, and q4=7. According to Step 3, we have ξ1=824. By Step 4, we have k=395, and then ξ2=93. By Step 5, we have the quadratic equation x2−824x+169548=0. By solving it, we can obtain the two secrets: s1,s2=398,426.
From (11), we know that Ui are the remainders of two secrets s1,s2 modulo mi. By Theorem 1, we know that the two secrets can be recovered after putting no less than t shares together without any other information. For example, in example 1, the two secrets can be recovered from any four shareholders directly by the generalized CRT. It is clear that each shareholder has partial information of the two secrets. In other words, the proposed multisecret-sharing scheme above is not a perfect SS. To overcome this drawback, we propose an improved multisecret-sharing scheme in the following.Table 3
Recovery of two secrets using three shares.
SharesDℳlcmℳRecovery inDℳCandidates inZlcmℳU1,U2,U31602431∅398,426,959,2296,970,2285,1531,1724U1,U2,U41622717∅8,816,151,673,255,569,398,426U1,U2,U51632860∅398,426,959,2296,970,2285,1531,1724U1,U3,U42063553∅398,426,987,3390,1718,2659,2098,2279U1,U3,U52073740∅398,426,1146,3418,1718,2846,2098,2466U1,U4,U52294180∅46,778,398,426,1718,3286,2098,2906U2,U3,U42404199∅75,749,398,426,1310,3713,1633,3390U2,U3,U52414420∅86,738,398,426,2166,3078,2506,2738U2,U4,U52674940∅398,426,1386,4378,2298,3466,2478,3286U3,U4,U53436460∅18,806,398,426,1718,5566,2098,5186


## 3.1. Unordered Multisecret Generation

Suppose that the shareholders have the public informationmi, where mi is pairwise coprime integer satisfying 2≤m1<m2<⋯<mn. Note that the scheme of multisecret sharing is trivial when n≤2, and we only consider n≥3 in this paper. Let t be a positive integer satisfying t<n. The generation of n shares from two unordered secrets s1,s2 contains two steps. First, determine the largest range of two secrets such that t shares or more than t shares can lead to a unique recovery of s1,s2. Second, obtain n shares U1,U2,…,Un by reducing s1,s2 modulo moduli m1,m2,…,mn, respectively. For convenience, we denote(3)ℳ1=mn−t+2,…,mn,ℳ2=m1,m2…,mt.Define(4)i0=mini:∏j=inmj<Dℳ2,1≤i≤n.It is not difficult to find that(5)n−i0+1<t.If not, i.e.,n−i0+1≥t, then we have(6)Dℳ2<∏i=1tmi≤∏j=1n−i0+1mj≤∏j=i0nmj,by the definition of Dℳ in (2), which contradicts with (4). For convenience, we let(7)t0=n−i0+1,and let(8)DL=max∏j=i0nmj,Dℳ1.Then, two unordered secretss1,s2 can be selected in the range of DL,Dℳ2, i.e.,(9)DL<si<Dℳ2,i=1,2.Consequently, sharesUi=r1,i,r2,i can be obtained by(10)s1,s2≡r1,i,r2,imodmi,i=1,2,…,n.That is,(11)Ui=s1mi,s2mi,i=1,2,…,n.To sum up, we have the following unordered multisecret generation phase for the pairwise coprime integersm1,m2,…,mn, which is shown in Table 1 below.Table 1
Generalized CRT-based unordered multisecret-sharing algorithm.
Unordered multisecret-sharing algorithmStep 1. Determineℳ1 and compute Dℳ2 by (3) and (2), respectivelyStep 2. Determinei0 by (4)Step 3. DetermineDL by (8)Step 4. Select two unordered secretss1,s2 satisfying (9)Step 5. Obtainn shares U1,U2…,Un by (10)


## 3.2. Unordered Multisecret Recovery

Now, we consider the problem of recovering the two secretss1,s2 from the given l shares Ui1,Ui2,…,Uil, where 1≤ij≤n and l>t. Table 2 gives the generalized CRT-based algorithm to recover the two secrets.Table 2
Generalized CRT-based unordered multisecret recovery algorithm.
Unordered multisecret recovery algorithmStep 1. For each shareUij, compute qij=r1,ij+r2,ijmij,j=1,2,…,lStep 2. ComputeM=mi1mi2⋯mil, Mij=M/mil, and M¯ij satisfying M¯ijMij≡1modmijStep 3. Computeξ1=∑j=1lM¯ijMijqijMStep 4. Letk=max0,⌈ξ1−2M⌉, then compute ξ2=∑j=1lM¯ijMijr1,ij−kr2,ij−kMStep 5. Obtain the two secretss1,s2 by solving x−k2−ξ1−2kx−k+ξ2=0Next theorem gives some results of the multisecret-sharing scheme discussed above.Theorem 1.
Let the two secretss1,s2 be defined in (9), and let Ui1,Ui2,…,Uil be l shares with the corresponding modulus set ℳ=mi1,mi2,…,mil, where 1≤il≤n for j=1,2,…,l. Then, we have the following results.(1)
Ifl≤t0, then s1,s2 cannot be recovered, where t0 is defined in (7).(2)
Ift0<l<t, then s1,s2 cannot be recovered in 0,Dℳ. Moreover, the two secrets cannot be uniquely recovered in 0,lcmℳ, where lcmℳ≥Dℳ2.(3)
Ifl≥t, then s1,s2 can be uniquely recovered.Proof.
(1)
We consider the case whenl=t0. For any t0=n−i0+1 shares Ui1,Ui2,…,Uin−i0+1, we have the corresponding moduli mi1,mi2,…,min−i0+1. According to the definition of i0 in (4), we have(12)∏j=1n−i0+1mij≤∏j=i0nmj.Note thatlcmℳ≤∏j=1n−i0+1mij. It follows that(13)lcmℳ≤∏j=i0nmj.IfDℳ1≥∏j=i0nmj, then we obtain from (8) that DL=Dℳ1. From (9) and (13), we have(14)lcmℳ≤Dℳ1=DL<si,i=1,2.IfDℳ1<∏j=i0nmj, then we obtain from (8) that DL=∏j=i0nmj. From (9) and (13), we have(15)lcmℳ≤DL<si,i=1,2.Thus, the two secretss1,s2 cannot be reconstructed from t0 shares. For the case of the less than t0 shares, the proof is obvious and it is omitted here.(2)
We consider the reconstruction of anyl=t−1 shares Ui1,Ui2,…,Uit−1 that is different from the shares Un−t+2,Un−t+3,…,Un. For convenience, we denote ℳ′=mi1,mi2,…,mit−1 and suppose(16)mi1<mi2<⋯<mit−1,without loss of generality. Recall thatm1<m2<⋯<mn. Hence, we have(17)mi1<mn−t+2,mi2<mn−t+3,…,mit−1<mn,and then(18)minI⊆i1,i2,…,it−1∏i∈Imi+∏i∈I¯mi<minI⊆n−t+2,…,n∏i∈Imi+∏i∈I¯mi.According to (2), we have(19)Dℳ′<Dℳ1.By (8) and (9), we obtain(20)Dℳ′<si,i=1,2.According to the generalized CRT, we know thats1,s2 cannot be recovered in the range of 0,Dℳ′ from their shares Ui1,Ui2,…,Uil. For the case of l<t−1, the conclusion also holds. Next, we consider the recovery of the two secrets in 0,lcmℳ.Letl shares be Ui1=r1,i1,r2,i1,…,Uil=r1,il,r2,il. According to (11), we have(21)Ui1=s1mi1,s2mi1,…,Uil=s1mil,s2mil.Note that(22)si<Dℳ2≤lcmℳ,i=1,2.Hence, the two secretss1 and s2 can be recovered separately by using the CRT when the remainders in the residue sets are properly ordered. More details can be seen in Remark 1 below.(3)
We considert shares Ui1,Ui2,…,Uit, where 1≤ij≤n. Let Ui1,Ui2,…,Uit. Similar to the proof of (2) above, we can prove that the dynamic range ℳ″ satisfies(23)Dℳ″>Dℳ2>si,i=1,2.
Hence,s1,s2 can be uniquely reconstructed from their shares Ui1,Ui2,…,Uit by the generalized CRT. For the case of more than t shares, the proof is obvious and it is omitted here.Remark 1.
Theorem1 tells us that the two secrets cannot be recovered when the number of shares l≤t0, where t0 is defined in (7). When l>t, the two secrets can be uniquely recovered by using the proposed generalized CRT. When t0<l<t, the two secrets cannot be successfully recovered. To be specific, the two secrets cannot be recovered in the range of 0,Dℳ in this case. In addition, the two secrets cannot be uniquely recovered in 0,lcmℳ by using the CRT since the correspondences between the two secrets and the elements in each shareholder are unclear. It is clear that the remainder of s1 or s2 cannot be determined from any share Ui. To recover s1 and s2, we have 2l−1 possible cases of remainders with moduli mi:s1mi1,s2mi2,…,s2mil and s2mi1,s1mi2,…,s1mil;…,s1mi1,s1mi2,…,s1mil and s2mi1,s2mi2,…,s2mil.
According to the CRT,s1 and s2 can be recovered only from the last tuples in the range of 0,lcmℳ.
Now, we consider the computational complexity of the proposed scheme. According to Algorithm 2, we know that the computational complexity of each shareholder isO1. For the proposed generalized CRT-based multisecret recovery algorithm, the computational complexity is O12l. For the CRT algorithm, the computational complexity is O2l−1 as discussed above.Example 1.
Let us consider a two secret-sharing and recovering process when moduli arem1=11,m2=13,m3=17,m4=19, and m5=20. Set t=4. By the definition of ℳ1 and ℳ2 in (3), we have ℳ1=17,19,20 and ℳ2=11,13,17,19. By Proposition 2, we have Dℳ1=343 and Dℳ2=430. Since m4m5=380, we have i0=4 and then DL=380 by Step 2 in Table 1. Let two secrets be s1,s2=398,426, which are in the range of 380,430. Then, we have five shares U1=2,8, U2=8,10, U3=1,7, U4=8,18, and U5=6,18 with moduli m1,m2,…,m5, respectively.
Now, we consider the recovery of two secrets froml shareholders. We have three cases below.(1)
l≤2.Suppose that the two shares areUi1 and Ui2 with 1≤i1,i2≤5. Clearly,(24)lcmmi1,mi2≤m4m5<si,i=1,2.Hence, the two secretss1,s2 cannot be recovered.(2)
l=3.LetUi1,Ui2,andUi3 be three shares, and let ℳ=mi1,mi2,mi3. In this case, the two secrets cannot be determined in 0,Dℳ since Dℳ<s1 and Dℳ<s2. Moreover, the two secrets cannot be uniquely determined in 0,lcmℳ. For example, given three shares U1,U2,andU3, we have four candidates: 398,426,959,2296,970,2285,and1531,1724. In other words, all these candidates have the same shares U1,U2,andU3 with moduli m1,m2,andm3, respectively. Table 3 gives the illustration of recovering the two secrets for all cases, where Zn=0,1,…,n−1.(3)
l≥4.
In this case, the two secrets can be uniquely determined. Suppose that the shares areU1,U2,U3, and U4. Next, we recover s1,s2 by using the proposed generalized CRT algorithm.
Note thatM=m1m2m3m4=46189, M1=4199, M¯1=7, M2=3553, M¯2=10, M3=2717, M¯3=11, M4=2431, and M¯4=18. By Step 1 in Table 2, we have q1=10, q2=5, q3=8, and q4=7. According to Step 3, we have ξ1=824. By Step 4, we have k=395, and then ξ2=93. By Step 5, we have the quadratic equation x2−824x+169548=0. By solving it, we can obtain the two secrets: s1,s2=398,426.
From (11), we know that Ui are the remainders of two secrets s1,s2 modulo mi. By Theorem 1, we know that the two secrets can be recovered after putting no less than t shares together without any other information. For example, in example 1, the two secrets can be recovered from any four shareholders directly by the generalized CRT. It is clear that each shareholder has partial information of the two secrets. In other words, the proposed multisecret-sharing scheme above is not a perfect SS. To overcome this drawback, we propose an improved multisecret-sharing scheme in the following.Table 3
Recovery of two secrets using three shares.
SharesDℳlcmℳRecovery inDℳCandidates inZlcmℳU1,U2,U31602431∅398,426,959,2296,970,2285,1531,1724U1,U2,U41622717∅8,816,151,673,255,569,398,426U1,U2,U51632860∅398,426,959,2296,970,2285,1531,1724U1,U3,U42063553∅398,426,987,3390,1718,2659,2098,2279U1,U3,U52073740∅398,426,1146,3418,1718,2846,2098,2466U1,U4,U52294180∅46,778,398,426,1718,3286,2098,2906U2,U3,U42404199∅75,749,398,426,1310,3713,1633,3390U2,U3,U52414420∅86,738,398,426,2166,3078,2506,2738U2,U4,U52674940∅398,426,1386,4378,2298,3466,2478,3286U3,U4,U53436460∅18,806,398,426,1718,5566,2098,5186


## 4. Improved Unordered Multisecret-Sharing Scheme

In this section, we give an improved generalized CRT-based unordered multisecret-sharing scheme, which includes the improved unordered multisecret generation phase and recovery phase. Some results of the proposed scheme are also given.


### 4.1. Improved Unordered Multisecret Generation Phase

Firstly, select an integerp satisfying(25)p,mi=1,i=1,2,…,m,(26)pDL<Dℳ2,where DL is defined in (8). Then, the dealer transmits it secretly to secret combiner. Let two secrets be s1,s2 and satisfy(27)si<p,i=1,2.Consequently, select two positive integersαi satisfying(28)si+αip∈DL,Dℳ2,i=1,2.Let(29)x1,x2=s1+α1p,s2+α2p.Then, the sharesUi=r1,i,r2,i can be generated by(30)x1,x2≡r1,i,r2,imodmi,i=1,2,…,n.That is,(31)Ui=x1mi,x2mi,i=1,2,…,n.According to (29), the shares can be rewritten as(32)Ui=s1+α1pmi,s2+α2pmi,i=1,2,…,n.Recall that the secrets of the first approach are leaked. For the improved approach, the obtained sharesUi are s1+α1pmi,s2+α2pmi for i=1,2,…,n, which are different from the two secrets s1,s2. Hence, the secrets of each shareholder are not leaked.In summary, we have the improved unordered multisecret-sharing algorithm for the pairwise coprime integersm1,m2,…,mn, which is shown in Table 4 below.Table 4
Improved unordered multisecret-sharing algorithm.
Improved unordered multisecret-sharing algorithmStep 1. Determineℳ1 and compute Dℳ2 by (3) and (2), respectivelyStep 2. Determinep by (19) and (20)Step 3. Select two unordered secretss1,s2 satisfying (21)Step 4. Determineαi by (19) and (20)Step 5. Obtainn shares U1,U2…,Un by (26)


### 4.2. Improved Unordered Multisecret Recovery Phase

Givenl shares Ui1,Ui2…,Uil, where 1≤ij≤n and l>t, then the two secrets s1,s2 can be recovered by the generalized CRT-based algorithm, which is shown in Table 5 below.Table 5
Improved unordered multisecret recovery algorithm.
Improved unordered multisecret recovery algorithmStep 1. For each shareUij, compute qij=r1,ij+r2,ijmij,j=1,2,…,lStep 2. ComputeM=mi1mi2⋯mil, Mij=M/mij, and M¯ij satisfying M¯ijMij≡1modmijStep 3. Computeξ1=∑j=1lM¯ijMijqijMStep 4. Letk=max0,⌈ξ1−2M⌉, then compute ξ2=∑j=1lM¯ijMijr1,ij−kr2,ij−kMStep 5. Obtain two solutionsx1,x2 by solving x−k2−ξ1−2kx−k+ξ2=0Step 6. Obtain the two secrets bys1,s2=x1p,x2pIt is not difficult to find that the proposed recovery algorithm has a computational complexity ofO12l, which is much smaller than the searching algorithm that has a computational complexity of O2l−1. Based on the above multisecret recovery phase, we have the following results.Theorem 2.
Lets1,s2 be two secrets satisfying (27), and let Ui1,Ui2,…,Uil be l shares defined in (32), where 1≤ij≤n for j=1,2,…,n. Then, we have the following results.(1)
Ifl≤t0, then s1,s2 cannot be reconstructed, where t0 is defined in (7).(2)
Ift0<l<t, then s1,s2 cannot be uniquely determined.(3)
Ifl≥t, then s1,s2 can be uniquely reconstructed.Proof.
(1)
By Theorem1, we know that x1,x2=s1+α1p,s2+α2p cannot be reconstructed in this case. Hence, the two secrets s1,s2 cannot be recovered.(2)
In this case,x1,x2=s1+α1p,s2+α2p cannot be determined in 0,Dℳ and cannot be uniquely determined in 0,lcmℳ. Hence, s1,s2 cannot be successfully recovered in 0,p.(3)
In this case,x1,x2=s1+α1p,s2+α2p can be uniquely reconstructed. Consequently, the two secrets s1,s2 can be recovered by(33)s1,s2=s1+α1pp,s2+α2pp.Example 2.
Let us consider an example when moduli arem1=23,m2=29,m3=31,andm4=37.
Lett=3. Then, we have ℳ1=31,37 and ℳ2=23,29,31. By (2), we obtain Dℳ1=68 and Dℳ2=698. According to (4), we have i0=4, and then DL=68 by (8). From (26), we obtain p<349/34. Let p=10. By Step 3, in Table 4, we select two secrets s1,s2=5,9, which are satisfied with the condition in (27). By Step 4, we select α=55 and then obtain x1,x2=555,559. By (30), we have four shares U1=3,7, U2=4,8, U3=1,28, and U4=0,4 with moduli m1,m2,m3, and m4, respectively.
Now, we consider the recovery of two secrets froml shareholders. We have three cases below.(1)
l=1.Clearly, for any sharesUij, we have lcmmij<DL<xi for 1≤ij≤4,i=1,2. Hence, two integers x1,x2 cannot be successfully reconstructed and hence the two secrets s1,s2 cannot be recovered.(2)
l=2.In this cases, the two integersx1,x2 cannot be reconstructed from the two shares Ui1,Ui2 in 0,Dℳ as Dℳ<x1 and Dℳ<x2. Moreover, x1,x2 cannot be uniquely determined in 0,lcmℳ, where ℳ=mi1,mi2. Hence, s1,s2 cannot be successfully recovered in 0,p. For example, given two shares U1,U2, we have two candidates: 2,5,5,9. In other words, all these candidates have the same shares. Table 6 gives all the cases of the reconstruction, where p=10.(3)
l≥3.
In this case, the two secrets can be uniquely recovered. Suppose that the shares areU1,U3, and U4. By the proposed generalized CRT, we have x1,x2=555,559 and then s1,s2=55510,55910=5,9.Table 6
Recovery of two secrets using two shares.
SharesDℳlcmℳRecovery inDℳCandidates inZlcmℳCandidates ofs1,s2U1,U252667∅95,352,555,5992,5,5,9U1,U354713∅187,214,555,5994,7,5,9U1,U460851∅444,670,555,5990,4,5,9U2,U360899∅497,617,555,5997,7,5,9U2,U4661073∅4,37,555,5994,7,5,9U3,U4681147∅152,962,555,5992,5,9


## 4.1. Improved Unordered Multisecret Generation Phase

Firstly, select an integerp satisfying(25)p,mi=1,i=1,2,…,m,(26)pDL<Dℳ2,where DL is defined in (8). Then, the dealer transmits it secretly to secret combiner. Let two secrets be s1,s2 and satisfy(27)si<p,i=1,2.Consequently, select two positive integersαi satisfying(28)si+αip∈DL,Dℳ2,i=1,2.Let(29)x1,x2=s1+α1p,s2+α2p.Then, the sharesUi=r1,i,r2,i can be generated by(30)x1,x2≡r1,i,r2,imodmi,i=1,2,…,n.That is,(31)Ui=x1mi,x2mi,i=1,2,…,n.According to (29), the shares can be rewritten as(32)Ui=s1+α1pmi,s2+α2pmi,i=1,2,…,n.Recall that the secrets of the first approach are leaked. For the improved approach, the obtained sharesUi are s1+α1pmi,s2+α2pmi for i=1,2,…,n, which are different from the two secrets s1,s2. Hence, the secrets of each shareholder are not leaked.In summary, we have the improved unordered multisecret-sharing algorithm for the pairwise coprime integersm1,m2,…,mn, which is shown in Table 4 below.Table 4
Improved unordered multisecret-sharing algorithm.
Improved unordered multisecret-sharing algorithmStep 1. Determineℳ1 and compute Dℳ2 by (3) and (2), respectivelyStep 2. Determinep by (19) and (20)Step 3. Select two unordered secretss1,s2 satisfying (21)Step 4. Determineαi by (19) and (20)Step 5. Obtainn shares U1,U2…,Un by (26)


## 4.2. Improved Unordered Multisecret Recovery Phase

Givenl shares Ui1,Ui2…,Uil, where 1≤ij≤n and l>t, then the two secrets s1,s2 can be recovered by the generalized CRT-based algorithm, which is shown in Table 5 below.Table 5
Improved unordered multisecret recovery algorithm.
Improved unordered multisecret recovery algorithmStep 1. For each shareUij, compute qij=r1,ij+r2,ijmij,j=1,2,…,lStep 2. ComputeM=mi1mi2⋯mil, Mij=M/mij, and M¯ij satisfying M¯ijMij≡1modmijStep 3. Computeξ1=∑j=1lM¯ijMijqijMStep 4. Letk=max0,⌈ξ1−2M⌉, then compute ξ2=∑j=1lM¯ijMijr1,ij−kr2,ij−kMStep 5. Obtain two solutionsx1,x2 by solving x−k2−ξ1−2kx−k+ξ2=0Step 6. Obtain the two secrets bys1,s2=x1p,x2pIt is not difficult to find that the proposed recovery algorithm has a computational complexity ofO12l, which is much smaller than the searching algorithm that has a computational complexity of O2l−1. Based on the above multisecret recovery phase, we have the following results.Theorem 2.
Lets1,s2 be two secrets satisfying (27), and let Ui1,Ui2,…,Uil be l shares defined in (32), where 1≤ij≤n for j=1,2,…,n. Then, we have the following results.(1)
Ifl≤t0, then s1,s2 cannot be reconstructed, where t0 is defined in (7).(2)
Ift0<l<t, then s1,s2 cannot be uniquely determined.(3)
Ifl≥t, then s1,s2 can be uniquely reconstructed.Proof.
(1)
By Theorem1, we know that x1,x2=s1+α1p,s2+α2p cannot be reconstructed in this case. Hence, the two secrets s1,s2 cannot be recovered.(2)
In this case,x1,x2=s1+α1p,s2+α2p cannot be determined in 0,Dℳ and cannot be uniquely determined in 0,lcmℳ. Hence, s1,s2 cannot be successfully recovered in 0,p.(3)
In this case,x1,x2=s1+α1p,s2+α2p can be uniquely reconstructed. Consequently, the two secrets s1,s2 can be recovered by(33)s1,s2=s1+α1pp,s2+α2pp.Example 2.
Let us consider an example when moduli arem1=23,m2=29,m3=31,andm4=37.
Lett=3. Then, we have ℳ1=31,37 and ℳ2=23,29,31. By (2), we obtain Dℳ1=68 and Dℳ2=698. According to (4), we have i0=4, and then DL=68 by (8). From (26), we obtain p<349/34. Let p=10. By Step 3, in Table 4, we select two secrets s1,s2=5,9, which are satisfied with the condition in (27). By Step 4, we select α=55 and then obtain x1,x2=555,559. By (30), we have four shares U1=3,7, U2=4,8, U3=1,28, and U4=0,4 with moduli m1,m2,m3, and m4, respectively.
Now, we consider the recovery of two secrets froml shareholders. We have three cases below.(1)
l=1.Clearly, for any sharesUij, we have lcmmij<DL<xi for 1≤ij≤4,i=1,2. Hence, two integers x1,x2 cannot be successfully reconstructed and hence the two secrets s1,s2 cannot be recovered.(2)
l=2.In this cases, the two integersx1,x2 cannot be reconstructed from the two shares Ui1,Ui2 in 0,Dℳ as Dℳ<x1 and Dℳ<x2. Moreover, x1,x2 cannot be uniquely determined in 0,lcmℳ, where ℳ=mi1,mi2. Hence, s1,s2 cannot be successfully recovered in 0,p. For example, given two shares U1,U2, we have two candidates: 2,5,5,9. In other words, all these candidates have the same shares. Table 6 gives all the cases of the reconstruction, where p=10.(3)
l≥3.
In this case, the two secrets can be uniquely recovered. Suppose that the shares areU1,U3, and U4. By the proposed generalized CRT, we have x1,x2=555,559 and then s1,s2=55510,55910=5,9.Table 6
Recovery of two secrets using two shares.
SharesDℳlcmℳRecovery inDℳCandidates inZlcmℳCandidates ofs1,s2U1,U252667∅95,352,555,5992,5,5,9U1,U354713∅187,214,555,5994,7,5,9U1,U460851∅444,670,555,5990,4,5,9U2,U360899∅497,617,555,5997,7,5,9U2,U4661073∅4,37,555,5994,7,5,9U3,U4681147∅152,962,555,5992,5,9


## 5. Conclusions

In this paper, we consider the problem of recovering unordered multisecret from some shares with unordered remainders. The main difference between this work and the previous ones is that the correspondence between the remainders in each share and the secrets is unknown in our work, while it is definite in previous works. A generalized CRT-based unordered multisecret-sharing scheme and recovery algorithm are proposed. The conditions for recovery failure and success are also explored. Furthermore, for making a perfect SS such that the secrets will not be leaked, an improved sharing and recovery approach is proposed.



---

*Source: 6073721-2020-07-14.xml*