# A Novel(t,n) Secret Sharing Scheme Based upon Euler’s Theorem

Authors: Hefeng Chen; Chin-Chen Chang
Journal: Security and Communication Networks
 (2019)

---

## Abstract

Thet,n secret sharing scheme is used to protect the privacy of information by distribution. More specifically, a dealer splits a secret inton shares and distributes them privately ton participants, in such a way that anyt or more participants can reconstruct the secret, but no group of fewer thant participants who cooperate can determine it. Many schemes in literature are based on the polynomial interpolation or the Chinese remainder theorem. In this paper, we propose a new solution to the system of congruences different from Chinese remainder theorem and propose a new scheme for t,n secret sharing; its secret reconstruction is based upon Euler’s theorem. Furthermore, our generalized conclusion allows the dealer to refresh the shared secret without changing the original share of the participants.


---

## Body

## 1. Introduction

Secret sharing is used as one of basic cryptographic primitives in computer science including electronic voting [1], distributed cloud computing [2], key management [3], and data hiding [4]. The t,n secret sharing (SS) was first introduced by Shamir [5] based on the Lagrange interpolating polynomial and Blakley [6] based on the hyperplane geometry in 1979, independently. In 1983, Mignotte’s scheme [7] and Asmuth-Bloom’s scheme [8] were proposed based on the Chinese remainder theorem (CRT). A perfect t,n secret sharing scheme [5] has two properties: (1) Any t or more shares can recover the secret. (2) Any t-1 or fewer shares reveal no information about the secret. The research on secret sharing has become the subject of many researchers; different types of secret sharing scheme have been designed to address different application requirements. For example, verifiable secret sharing [9, 10] allows the participants to verify the correctness of their share without leaking the confidentiality of both shares and the secret; weighted secret sharing [11] allows the participants with different privileges by holding the shares with different weights; multi-secret sharing [12] allows more than one secret to be shared. However, the major techniques used can still be categorized in the above three methods.The CRT is to reconstruct a positive integer from its remainders modulo a series of integer moduli. It is widely used in the calculation of large integers, because it allows replacing a calculation for which one knows a bound on the size of the result by several similar computations on small integers. The CRT has many applications in various areas, like secret sharing [3, 4], the RSA decryption algorithm [13], the discrete logarithm algorithm [14], and the radio interferometric positioning system [15], etc.The main contributions of our paper are summarized as follows:(a)
Using Euler’s theorem to present a new method of the solution to the system of congruence(b)
First proposing a new type of secret sharing scheme based upon Euler’s theorem(c)
Using Euler’s theorem to present a new method of the solution to the system of congruence in the generalized CRT(d)
Proposing a refreshable secret sharing scheme to implement the secret refresh mechanism with the same shares.Based on the equivalence between the conclusion of this paper and the CRT, our method is sufficient to be directly applied with the CRT-based scheme to achieve the same goal.The rest of this paper is organized as follows. In Section2, we describe some preliminaries on number theory and prove that the system of congruence has another solution form which is different from the CRT. In Section 3, we review the Asmuth-Bloom’s scheme. In Section 4, we propose the secret sharing scheme based upon Euler’s theorem. In Section 5, the security and performance analysis are given. In Section 6, we generalize the conclusion in Section 2 and propose a refreshable secret sharing scheme. In Section 7, we conclude the paper.


## 2. New Solution to the Congruence System

In this section, we describe the CRT and Euler’s theorem firstly. Then we present another method to give the unique solution of the congruent system, by utilizing the properties of them.The Chinese remainder theorem states that if the remainders of the Euclidean division of an integerx by several integers are known, then the remainder of the division of this integer x by the product of these integers can be uniquely determined, under the condition that the divisors are pairwise coprime.Lemma 1 (Chinese remainder theorem (CRT) [16]).
Supposem1,m2,⋯,mn are pairwise relatively prime positive integers, and suppose r1,r2,⋯,rn are integers. Then the system of n congruences x≡rimodmi1≤i≤n has a unique solution modulo M=∏i=1nmi, which is given by(1)x=∑i=1nriMiyimodM,where Mi=M/mi and yi=Mi-1modmi for 1≤i≤n.Euler’s theorem is a generalization of Fermat’s little theorem and is further generalized by Carmichael’s theorem [17].Lemma 2 (Euler’s theorem [17]).
Ifm and β are coprime positive integers, then (2)βφm≡1modm,where φm called Euler’s phi function is the number of positive integers less than m and relatively prime to m.An efficient way to calculate Euler’s phi functionφb is the following Euler product formula [17]:(3)φm=m∏p∣m1-1p,where the product is over the distinct prime numbers dividing m.Now, we give another method of solving the systems of congruence and prove its correctness.Theorem 3.
Supposem1,m2,⋯,mn are pairwise relatively prime positive integers (i.e., if i≠j then gcdmi,mj=1), and suppose r1,r2,⋯,rn are integers. Then the system of n congruences(4)x≡r1modm1x≡r2modm2⋮x≡rnmodmnhas a unique solution modulo M=∏i=1nmi, which is given by(5)x=∑i=1nriMiφmimodM,where Mi=M/mi for 1≤i≤n.Proof.
The Chinese remainder theorem shows that the function(6)χ:ZM→Zm1×Zm2×⋯×Zmnχx=r1modm1,r2modm2,⋯,rnmodmnis a bijection.
Now, define a functionρ:Zm1×Zm2×⋯×Zmn→ZM as follows:(7)ρr1,r2,⋯,rn=∑i=1nriMiφmimodM.It amounts to show that the function ρ=χ-1.
Denotex=ρr1,r2,⋯,rn, and let 1≤j≤n. Consider a term riMiφmi in the above summation, reduced modulo mj.
m 1 , m 2 , ⋯ , m n are pairwise relatively prime positive integers, and Mi=∏1≤t≤n,t≠imt, for 1≤i≤n.
Ifi=j, it is obvious that gcdMi,mi=1; by Euler’s theorem, we have(8)Miφmimodmi=1.
On the other hand, ifi≠j, because mj∣Mi, we have(9)Miφmimodmj=0.Then(10)x≡∑i=1nriMiφmimodmj=rjmodmj.Since this is true for all j, 1≤j≤n, x is a solution to the system of congruences.Example 4.
Supposen=3, m1=7, m2=11, and m3=13. Then M=1001, φm1=6, φm2=10, and φm3=12. We compute M1=143, M2=91, and M3=77, and then (11)M1φm1modM=1436mod1001=715,M2φm2modM=9110mod1001=364,M3φm3modM=7712mod1001=924.Then the function ρ:Z7×Z11×Z13→Z1001 is(12)ρr1,r2,r3=715r1+364r2+924r3mod1001.
For example, ifx≡5mod7, x≡3mod11, and x≡10mod13, then this formula tells us that(13)x=715×5+364×3+924×10mod1001=13907mod1001=894.This can be verified by reducing 894 modulo 7, 11, and 13.


## 3. Review of Asmuth-Bloom’s Secret Sharing

In 1983, Asmuth and Bloom [8] proposed a novel (t,n) SS, in which the shares are the congruence classes of the secret and the corresponding modulus is broadcasted as the participant’s public key. The secret reconstruction is based on CRT.


### 3.1. Initialization

Then+1 distinct positive integers m0,m1,⋯,mn are chosen subject to the following conditions:(1)
m1<m2<⋯<mn(2)
gcdmi,mj=1 for 0≤i≠j≤n(3)
∏i=1tmi>m0·∏i=1t-1mn-t+i+1


### 3.2. Secret Generation

Suppose the shared secret is the integers∈0,m0. Let s′=s+αm0 where α∈Z is subject to the condition s′∈0,m1·m2·⋯·mt. Then let si≡s′modmii=1,2,⋯,n be the private shares.


### 3.3. Secret Reconstruction

Ifsi1,si2,⋯,sit are known, s′ is obtained by (14)s′=∑j=1tsijNijyijmodN,where N=∏j=1tmij, Nij=N/mij, and yij=Nij-1modmij. Then the shared secret is (15)s=s′modm0.


### 3.4. Security Analysis

However, Harn et al. [18] pointed out that the value s′ need be in thet-threshold range mn-t+2·mn-t+3·⋯·mn,m1·m2·⋯·mt; otherwise, it could be obtained by fewer thant participants. In the following, we give an example to illustrate this vulnerability.Example 5.
Consider Asmuth-Bloom’s2,4 secret sharing scheme.
We have a pairwise relatively prime integer set5,7,11,12,13. The shared secret s is 4. Let s′=s+αm0=4+5×18=94. Then, four shares are generated as(16)m1,s1=7,3,m2,s2=11,6,m3,s3=12,10,m4,s4=13,3.
It is easy to recover the shared secrets by using two shares m3,s3=12,10, m4,s4=13,3 and the CRT, as shown below.
By Euclidean Algorithm, we get(17)y3=13-1mod12=1,y4=12-1mod13=12,and then (18)s′=13×1×10+12×12×3mod156=562mod156=94,and the secret s=94mod5=4 is revealed.
Besides, Hwang and Chang [19] proposed a method to generate a pairwise relative prime integer set which satisfies the requirements of Asmuth-Bloom’s and our schemes, and this specific integer set is not unique.


## 3.1. Initialization

Then+1 distinct positive integers m0,m1,⋯,mn are chosen subject to the following conditions:(1)
m1<m2<⋯<mn(2)
gcdmi,mj=1 for 0≤i≠j≤n(3)
∏i=1tmi>m0·∏i=1t-1mn-t+i+1


## 3.2. Secret Generation

Suppose the shared secret is the integers∈0,m0. Let s′=s+αm0 where α∈Z is subject to the condition s′∈0,m1·m2·⋯·mt. Then let si≡s′modmii=1,2,⋯,n be the private shares.


## 3.3. Secret Reconstruction

Ifsi1,si2,⋯,sit are known, s′ is obtained by (14)s′=∑j=1tsijNijyijmodN,where N=∏j=1tmij, Nij=N/mij, and yij=Nij-1modmij. Then the shared secret is (15)s=s′modm0.


## 3.4. Security Analysis

However, Harn et al. [18] pointed out that the value s′ need be in thet-threshold range mn-t+2·mn-t+3·⋯·mn,m1·m2·⋯·mt; otherwise, it could be obtained by fewer thant participants. In the following, we give an example to illustrate this vulnerability.Example 5.
Consider Asmuth-Bloom’s2,4 secret sharing scheme.
We have a pairwise relatively prime integer set5,7,11,12,13. The shared secret s is 4. Let s′=s+αm0=4+5×18=94. Then, four shares are generated as(16)m1,s1=7,3,m2,s2=11,6,m3,s3=12,10,m4,s4=13,3.
It is easy to recover the shared secrets by using two shares m3,s3=12,10, m4,s4=13,3 and the CRT, as shown below.
By Euclidean Algorithm, we get(17)y3=13-1mod12=1,y4=12-1mod13=12,and then (18)s′=13×1×10+12×12×3mod156=562mod156=94,and the secret s=94mod5=4 is revealed.
Besides, Hwang and Chang [19] proposed a method to generate a pairwise relative prime integer set which satisfies the requirements of Asmuth-Bloom’s and our schemes, and this specific integer set is not unique.


## 4. Proposed Secret Sharing Scheme

The traditionalt,n secret sharing scheme is composed of a trusted dealerD and n participants U1,U2,⋯,Un. Our secret sharing scheme consists of three phases, that is, initialization phase, share generation phase, and secret reconstruction phase. In secret generation phase, we improve Asmuth-Bloom’s scheme by considering the t-threshold range. We do the secret reconstruction by Euler’s phi function, and the correctness is based upon Theorem 3 in Section 2.


### 4.1. Initialization

The dealerD chooses n+1 distinct positive integers m0,m1,m2,⋯,mn such that(1)
m1<m2<⋯<mn(2)
gcdmi,mj=1 for 0≤i≠j≤n(3)
∏i=1tmi>m0+1·∏i=1t-1mn-t+i+1The dealerD broadcasts the value m0 and sends the value mi to participant Ui as his/her public information, for 1≤i≤n.


### 4.2. Share Generation

Suppose the dealerD wants to share the secret s∈Zm0.The dealerD selects an integer α∈∏i=1t-1mn-i+1/m0,∏i=1tmi/m0-1; then let si≡s+αm0modmi be the private share of the participant Ui, for 1≤i≤n.


### 4.3. Secret Reconstruction

Ift participants pool their shares and corresponding modulus, si1,mi1,si2,mi2,⋯,sit,mit, the shared secret can be reconstructed as s=s′modm0, where (19)s′=∑j=1tsij∏1≤k≤t,k≠jmikφmijmod∏1≤k≤tmij.


## 4.1. Initialization

The dealerD chooses n+1 distinct positive integers m0,m1,m2,⋯,mn such that(1)
m1<m2<⋯<mn(2)
gcdmi,mj=1 for 0≤i≠j≤n(3)
∏i=1tmi>m0+1·∏i=1t-1mn-t+i+1The dealerD broadcasts the value m0 and sends the value mi to participant Ui as his/her public information, for 1≤i≤n.


## 4.2. Share Generation

Suppose the dealerD wants to share the secret s∈Zm0.The dealerD selects an integer α∈∏i=1t-1mn-i+1/m0,∏i=1tmi/m0-1; then let si≡s+αm0modmi be the private share of the participant Ui, for 1≤i≤n.


## 4.3. Secret Reconstruction

Ift participants pool their shares and corresponding modulus, si1,mi1,si2,mi2,⋯,sit,mit, the shared secret can be reconstructed as s=s′modm0, where (19)s′=∑j=1tsij∏1≤k≤t,k≠jmikφmijmod∏1≤k≤tmij.


## 5. Security and Performance Analysis

In this section, we first give security analysis of the scheme proposed in Section4 and then compare the performance of our proposed secret sharing with that of two types of classical secret sharing.


### 5.1. Security Analysis

Now we analyze the fact that our proposedt,n secret sharing is perfect, secure as follows.Theorem 6.
Our proposedt,n secret sharing scheme described in Section 4 is perfect, that is, the following two properties are satisfied:(1)
If anyt participants pool their shares, then they can determine the value of s.(2)
If anyt-1 participants pool their shares, then they can determine nothing about the value of s.Proof.
Based on the conditions of our scheme,(20)s′=s+αm0,where ∏i=1t-1mn-i+1/m0≤α<∏i=1tmi/m0-1 and 0≤s<m0.
LetM=∏i=1tmi, we have(21)0+∏i=1t-1mn-i+1m0m0≤s+αm0<m0+M-m0,∏i=1t-1mn-i+1+1≤s′<M.
(1) If anyt participants pool their shares si1,si2,⋯,sit, as described in Theorem 3, the system of t congruences(22)x≡si1modmi1x≡si2modmi2⋮x≡sitmodmithas one unique solution as (23)x=∑j=1tsijNmijφmijmodN,where N=∏j=1tmij.
AsN≥M, this uniquely determines s′=x and thus (24)s=s′modm0.
(2) If onlyt-1 participants pool their shares, sl1,sl1,⋯,slt-1, then all we have is s∗=s′modN-, where N-=∏j=1t-1mlj. The real secret s′∈s∗,s∗+N-,⋯,s∗+M/N--1N-; since gcdN-,m0=1 and M/N->m0, the set of possible values is greater than that of possible secret. Hence, no useful information is compromised.Example 7.
Consider the proposed2,4 secret sharing scheme.
In initialization phase, the dealerD chooses 5 distinct positive integers, m0=5, m1=7, m2=11, m3=12, and m4=13, which satisfies the conditions on initialization listed in Section 4.1. The minimum value m0=5 is broadcasted. And mi1≤i≤4 is sent as the public key of Ui.
In sharing phase, suppose the shared secrets=4. Then dealerD selects an integer α=18∈14,183. So the private shares of U1, U2, U3, and U4, are generated as follows:(25)s1=4+18×5mod7=3,s2=4+18×5mod11=6,s3=4+18×5mod12=10,s4=4+18×5mod13=3.
In reconstructing phase, suppose thatU3 and U4 cooperate; by (19) we have(26)s′=s4m3φm4+s3m4φm3modm4·m3=3×12φ13+10×13φ12mod13×12=94,and, then, the secret can be reconstructed as (27)s=s′modm0=94mod5=4.
As in many literatures, we assume that all participants pool the real shares when they collaborate to recover the shared secret. To enhance the security, it can be combined with other cheater detection mechanisms to check the validity of the shares before recovery of the secret.


### 5.2. Performance Analysis

In this section, we analyze the computational cost of our proposed scheme and compare it with the other two classic secret sharing schemes, as summarized in Table1. In Shamir’s t,n scheme, the secret recovery using the usual polynomial interpolation requires Otlog2⁡t operations. In the Asmuth-Bloom’s scheme, the modular method of secret recovery requires only Ot operations. In our scheme, the computation complexity of MiφmimodM requires at most Olog⁡mn operations. However, this can be improved at the cost of storage room by keeping a table. Once the value of MiφmimodM1≤i≤n is known, it requires only Ot operations to recover the secret.Table 1
Comparison of computational cost.
Scheme Secret recovery Shamir’s scheme [5] O t log 2 ⁡ t Asmuth-Bloom’s scheme [8] O t Our scheme O t


## 5.1. Security Analysis

Now we analyze the fact that our proposedt,n secret sharing is perfect, secure as follows.Theorem 6.
Our proposedt,n secret sharing scheme described in Section 4 is perfect, that is, the following two properties are satisfied:(1)
If anyt participants pool their shares, then they can determine the value of s.(2)
If anyt-1 participants pool their shares, then they can determine nothing about the value of s.Proof.
Based on the conditions of our scheme,(20)s′=s+αm0,where ∏i=1t-1mn-i+1/m0≤α<∏i=1tmi/m0-1 and 0≤s<m0.
LetM=∏i=1tmi, we have(21)0+∏i=1t-1mn-i+1m0m0≤s+αm0<m0+M-m0,∏i=1t-1mn-i+1+1≤s′<M.
(1) If anyt participants pool their shares si1,si2,⋯,sit, as described in Theorem 3, the system of t congruences(22)x≡si1modmi1x≡si2modmi2⋮x≡sitmodmithas one unique solution as (23)x=∑j=1tsijNmijφmijmodN,where N=∏j=1tmij.
AsN≥M, this uniquely determines s′=x and thus (24)s=s′modm0.
(2) If onlyt-1 participants pool their shares, sl1,sl1,⋯,slt-1, then all we have is s∗=s′modN-, where N-=∏j=1t-1mlj. The real secret s′∈s∗,s∗+N-,⋯,s∗+M/N--1N-; since gcdN-,m0=1 and M/N->m0, the set of possible values is greater than that of possible secret. Hence, no useful information is compromised.Example 7.
Consider the proposed2,4 secret sharing scheme.
In initialization phase, the dealerD chooses 5 distinct positive integers, m0=5, m1=7, m2=11, m3=12, and m4=13, which satisfies the conditions on initialization listed in Section 4.1. The minimum value m0=5 is broadcasted. And mi1≤i≤4 is sent as the public key of Ui.
In sharing phase, suppose the shared secrets=4. Then dealerD selects an integer α=18∈14,183. So the private shares of U1, U2, U3, and U4, are generated as follows:(25)s1=4+18×5mod7=3,s2=4+18×5mod11=6,s3=4+18×5mod12=10,s4=4+18×5mod13=3.
In reconstructing phase, suppose thatU3 and U4 cooperate; by (19) we have(26)s′=s4m3φm4+s3m4φm3modm4·m3=3×12φ13+10×13φ12mod13×12=94,and, then, the secret can be reconstructed as (27)s=s′modm0=94mod5=4.
As in many literatures, we assume that all participants pool the real shares when they collaborate to recover the shared secret. To enhance the security, it can be combined with other cheater detection mechanisms to check the validity of the shares before recovery of the secret.


## 5.2. Performance Analysis

In this section, we analyze the computational cost of our proposed scheme and compare it with the other two classic secret sharing schemes, as summarized in Table1. In Shamir’s t,n scheme, the secret recovery using the usual polynomial interpolation requires Otlog2⁡t operations. In the Asmuth-Bloom’s scheme, the modular method of secret recovery requires only Ot operations. In our scheme, the computation complexity of MiφmimodM requires at most Olog⁡mn operations. However, this can be improved at the cost of storage room by keeping a table. Once the value of MiφmimodM1≤i≤n is known, it requires only Ot operations to recover the secret.Table 1
Comparison of computational cost.
Scheme Secret recovery Shamir’s scheme [5] O t log 2 ⁡ t Asmuth-Bloom’s scheme [8] O t Our scheme O t


## 6. Renewable Secret Sharing Scheme

The generalized Chinese remainder theorem (GCRT) [9, 10] is a variation of CRT with an additional integer k introduced as a common modulus. Inspired by GCRT, we have the following result.Theorem 8.
Supposem1,m2,⋯,mn are pairwise relatively prime positive integers (i.e., if i≠j then gcdmi,mj=1), and r1,r2,⋯,rn are integers. Suppose k is an integer satisfying max1≤i≤nri<k<min1≤i≤nmi. Let M=∏i=1nmi. Then the system of n congruences(28)xm1≡r1modkxm2≡r2modk⋮xmn≡rnmodkhas a unique solution modulo kM, which is given by(29)x=∑i=1nRikMiφmimodkM,where Mi=M/mi and Ri=ri·mi/k for 1≤i≤n.Proof.
It amounts to showing thatx in (28) is a solution to the system of congruences (19). The proof of uniqueness is similar to Theorem 3.
For1≤j≤n, consider a term RikMiφmi in the above summation, reduced modulo mj.
Ifi=j, it is obvious that gcdMi,mi=1, by Euler’s theorem; then we have Miφmimodmi=1; i.e., there is an integerλ such that Miφmi+λmi=1; then (30)kMiφmimodkmi=k,because kMiφmi+kλmi=k. On the other hand, if i≠j, because mj∣Mi, we have(31)Miφmimodmj=0,i.e., RikMiφmimodkmj=0. Therefore, (32)xmjmodk=∑i=1nRikMiφmimjmodk=RjkMjφmjmjmodk,because RikMiφmi/mjmodk=0 for i≠j.
SincekMiφmimodkmi=k and k<mi, we have kMiφmi/mimodk=k/mi.
Ifrjmj is a multiple of k, then(33)Rj=rj·mjk=rj·mjk,and we have(34)xmjmodk=rjMjφmjmodk=rj.
Ifrjmj is not a multiple of k, then (35)xmjmodk=rj·mj/kk1+βmjmjmodk=rj·mj/kkmjmodk=rj+1-rj·mjmodk/kkmjmodk=rj,because 1-rj·mjmodk/kk/mj<1 and rj<k.Although more computation is required, more flexible performance can be achieved. In the traditional secret sharing scheme, if we want to refresh the secret, the corresponding congruences system should be modified. However, based upon Theorem8, we can refresh the shared secret without changing the share and the public information of the participants.Compared with the previous scheme, the refreshable secret sharing scheme adds a secret refresh phase. In share generation phase, the dealer needs to broadcast an additional parameter as follows.


### 6.1. Initialization

The dealerD chooses n+1 distinct positive integers m0,m1,⋯,mn such that(1)
m1<m2<⋯<mn(2)
gcdmi,mj=1 for 0≤i≠j≤n(3)
∏i=1tmi>m0+1·∏i=1t-1mn-t+i+1The dealerD broadcasts the value m0 and sends the value mi to participant Ui as his/her public information, for 1≤i≤n.


### 6.2. Share Generation

Suppose the dealerD wants to share the secret s∈Zm0. The dealerD firstly selects and broadcasts an integer k∈0,min1≤i≤nmi. Secondly, the dealerD chooses a random integer(36)α∈∏i=1t-1mn-i+1m0,∏i=1tmim0-1,then generating si≡s+αm0/mimodk, which is the private share of the participant Ui, for 1≤i≤n.


### 6.3. Secret Refreshment

Suppose the dealerD wants to refresh the shared secret without changing the share and the public modulus of the participants which has been sent. The dealerDselects and broadcasts new integer k^∈max1≤i≤nri,min1≤i≤nmi; then the secret s^=s^′modm0 can be shared by n participants with their original share and public modulus si,mi, where (37)s^′=∑i=1nri·mik^k^Miφmimodk^M.


### 6.4. Secret Reconstruction

Ift participants pool their shares and public modulus, si1,mi1,si2,mi2,⋯,sit,mit, with the corresponding parameter k, the shared secret can be reconstructed as s=s′modm0, where (38)s′=∑j=1trij·mijkk∏1≤k≤tk≠jmikφmijmodk∏j=1tmij.


## 6.1. Initialization

The dealerD chooses n+1 distinct positive integers m0,m1,⋯,mn such that(1)
m1<m2<⋯<mn(2)
gcdmi,mj=1 for 0≤i≠j≤n(3)
∏i=1tmi>m0+1·∏i=1t-1mn-t+i+1The dealerD broadcasts the value m0 and sends the value mi to participant Ui as his/her public information, for 1≤i≤n.


## 6.2. Share Generation

Suppose the dealerD wants to share the secret s∈Zm0. The dealerD firstly selects and broadcasts an integer k∈0,min1≤i≤nmi. Secondly, the dealerD chooses a random integer(36)α∈∏i=1t-1mn-i+1m0,∏i=1tmim0-1,then generating si≡s+αm0/mimodk, which is the private share of the participant Ui, for 1≤i≤n.


## 6.3. Secret Refreshment

Suppose the dealerD wants to refresh the shared secret without changing the share and the public modulus of the participants which has been sent. The dealerDselects and broadcasts new integer k^∈max1≤i≤nri,min1≤i≤nmi; then the secret s^=s^′modm0 can be shared by n participants with their original share and public modulus si,mi, where (37)s^′=∑i=1nri·mik^k^Miφmimodk^M.


## 6.4. Secret Reconstruction

Ift participants pool their shares and public modulus, si1,mi1,si2,mi2,⋯,sit,mit, with the corresponding parameter k, the shared secret can be reconstructed as s=s′modm0, where (38)s′=∑j=1trij·mijkk∏1≤k≤tk≠jmikφmijmodk∏j=1tmij.


## 7. Conclusions

In this paper, we first show a new method to reconstruct the secret by the system of congruences utilizing Euler’s theorem and propose a new type of perfect secret sharing scheme based on modular arithmetic. Furthermore, inspired by [20], we introduce an extra integer to help us to refresh the secret without changing the information the participant holds; only one public broadcasting parameter needs to be updated.



---

*Source: 2387358-2019-04-01.xml*