# An Efficient Compartmented Secret Sharing Scheme Based on Linear Homogeneous Recurrence Relations

Authors: Guoai Xu; Jiangtao Yuan; Guosheng Xu; Zhongkai Dang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Multipartite secret sharing schemes are those that have multipartite access structures. The set of the participants in those schemes is divided into several parts, and all the participants in the same part play the equivalent role. One type of such access structure is the compartmented access structure, and the other is the hierarchical access structure. We propose an efficient compartmented multisecret sharing scheme based on the linear homogeneous recurrence (LHR) relations. In the construction phase, the shared secrets are hidden in some terms of the linear homogeneous recurrence sequence. In the recovery phase, the shared secrets are obtained by solving those terms in which the shared secrets are hidden. When the global threshold ist, our scheme can reduce the computational complexity of the compartmented secret sharing schemes from the exponential time to polynomial time. The security of the proposed scheme is based on Shamir’s threshold scheme, i.e., our scheme is perfect and ideal. Moreover, it is efficient to share the multisecret and to change the shared secrets in the proposed scheme.


---

## Body

## 1. Introduction

Shamir [1] and Blakley [2] proposed the threshold secret sharing schemes in 1979. Their schemes were based on the Lagrange interpolation algorithm and the linear projective geometry, respectively. In the (t, n) threshold secret sharing scheme, the secrets can be shared among n participants, and any t or more participants can recover the shared secrets by pooling their shares since greater than or equal to t participants (let P=P1,P2,…,Pn be the set of the participants, where Pi is the ith participant in the set P, 1≤i≤n) can construct a qualified subset. Less than t participants cannot get the shared secrets since less than t participants cannot construct a qualified subset. If the participants of any unqualified subset cannot obtain any information about the shared secrets, then the scheme is called as the perfect scheme. We call the secret sharing scheme the ideal scheme, when each participant holds the share as long as the shared secret. The threshold secret sharing schemes proposed by Shamir and Blakley are only special cases when all the participants have the same authority. Many applications [3, 4] were developed based on the secret sharing scheme. This is the reason that the secret sharing scheme is still popular today.


### 1.1. Related Works

The threshold secret sharing schemes have many limitations in some conditions. Hence, other access structures were proposed successively. Shamir proposed the weighted threshold secret sharing scheme [1]. The construction of this scheme is simple: take a threshold scheme and give as many shares as its weight to each participant. Nevertheless, the obtained scheme is not ideal anymore. In 1987, Ito et al. first proposed a scheme to achieve the secret sharing on the general access structure [5]. Simmons first proposed the multipartite access structure [6]. Brickell proposed a method to construct an ideal secret sharing scheme for the multilevel and compartmented access structures [7], but it is not efficient. The definition of the compartmented access structure can be found in Section 2.2.2. Computational complexity and storage space size are usually used to measure the efficiency of a scheme. The information rate is usually used to measure the efficiency of a secret sharing scheme. Therefore, to improve the efficiency of the secret sharing scheme, many researchers focused on the study of specific families of access structures, such as graph-based access structures [8], weighted threshold access structures [9], bipartite access structures [10–12], tripartite access structures [13, 14], and threshold access structures [15]. Especially Farràs and Martł-Farr gave a complete characterization of the ideal multipartite access structures [16]. The multipartite secret sharing scheme can be divided into two types. The one is the compartmented secret sharing scheme, and the other is the hierarchical secret sharing scheme.Recently, there were some research studies on the compartmented access structure [17–19]. Tassa et al. proposed two types of the compartmented secret sharing schemes based on the bivariate Lagrange interpolation [20]. Though some of the existing schemes are proved to be ideal, the abovementioned methods are not efficient. Farràs and Martł-Farr used the matroids and the integer polymatroids to study the compartmented access structure [16, 19], and it is easy to determine whether the secret sharing schemes are ideal or not by the matroids and the integer polymatroids. The problem that how to design a scheme to realize a compartmented access structure can be considered as the problem that how to find a representation of a matroid from the presentation of its associated polymatroid [21]. Chen et al. [21] proposed a compartmented secret sharing scheme based on the general polymatroid and the Gabidulin codes, but the scheme is also to try to obtain nonsingular matrices. Later, Chen et al. [22] gave another method based on the idea of Brickell [7], and this scheme also needed to check many matrices for nonsingularity. But Farràs and Martł-Farr [16, 19] showed that it remains open whether or not there exist efficient algorithms to obtain the representations of multipartite matroids from representations of their associated polymatroids in general. Especially, the compartmented access structure is useful in some applications. For example, a company is divided into several departments. A decision of this company needs the approval of at least some persons in each department. That is to say, a decision requires the cooperation of all departments, and a minimum number of employees in each department needs to involve in it.Mashhadi and Dehkordi first introduced the Linear Homogeneous Recurrence (LHR) relations to thet,n threshold secret sharing scheme [23]. Later, they introduced the linear nonhomogeneous recurrence (LNHR) relations to the secret sharing scheme [24]. But the participants have the equal authority, and the qualified subset A satisfies A≥t in Mashhadi and Dehkordis schemes. Yuan et al. [25] introduced the LHR relations to the hierarchical secret sharing scheme. They reduced the computational complexity of the hierarchical secret sharing schemes from exponential time to polynomial time (Onkm−1logn) (km in [25] is different to it in our scheme). But there is no scheme that realizes the compartmented secret sharing scheme in polynomial time. Thus, in this paper, we mainly discuss the compartmented access structure.


### 1.2. Our Contributions

The motivation of our scheme is to design an efficient secret sharing scheme with the access structures which are more general than the threshold access structures. One of the key contributions is to introduce the LHR relations into the compartmented access structure, which divides the degreet of a polynomial into the low degrees of some polynomials, and each low degree equals to a fixed compartment threshold minus one. In the proposed scheme, the compartmented access structure is realized by using the linear homogeneous recurrence (LHR) relations. The LHR relations are suitable for the compartmented access structure since it has the ability to associate each compartment with a different polynomial. Another key contribution is to reduce the computational complexity of the compartmented secret sharing schemes from exponential time to polynomial time (Onmaxti−1logn). It is easy to share multisecret in our scheme. Each participant holds a share that is as long as the secret. The security of the proposed scheme is based on Shamir’s threshold scheme.The remainder of this paper is organized as follows. Section2 introduces the basic knowledge of the linear homogeneous recurrence relations and secret sharing scheme. Section 3 gives the proposed scheme. In Section 4, we analyze the security of the proposed scheme. Section 5 discusses some important properties of the proposed scheme and its performance. Finally, Section 6 draws our conclusion.


## 1.1. Related Works

The threshold secret sharing schemes have many limitations in some conditions. Hence, other access structures were proposed successively. Shamir proposed the weighted threshold secret sharing scheme [1]. The construction of this scheme is simple: take a threshold scheme and give as many shares as its weight to each participant. Nevertheless, the obtained scheme is not ideal anymore. In 1987, Ito et al. first proposed a scheme to achieve the secret sharing on the general access structure [5]. Simmons first proposed the multipartite access structure [6]. Brickell proposed a method to construct an ideal secret sharing scheme for the multilevel and compartmented access structures [7], but it is not efficient. The definition of the compartmented access structure can be found in Section 2.2.2. Computational complexity and storage space size are usually used to measure the efficiency of a scheme. The information rate is usually used to measure the efficiency of a secret sharing scheme. Therefore, to improve the efficiency of the secret sharing scheme, many researchers focused on the study of specific families of access structures, such as graph-based access structures [8], weighted threshold access structures [9], bipartite access structures [10–12], tripartite access structures [13, 14], and threshold access structures [15]. Especially Farràs and Martł-Farr gave a complete characterization of the ideal multipartite access structures [16]. The multipartite secret sharing scheme can be divided into two types. The one is the compartmented secret sharing scheme, and the other is the hierarchical secret sharing scheme.Recently, there were some research studies on the compartmented access structure [17–19]. Tassa et al. proposed two types of the compartmented secret sharing schemes based on the bivariate Lagrange interpolation [20]. Though some of the existing schemes are proved to be ideal, the abovementioned methods are not efficient. Farràs and Martł-Farr used the matroids and the integer polymatroids to study the compartmented access structure [16, 19], and it is easy to determine whether the secret sharing schemes are ideal or not by the matroids and the integer polymatroids. The problem that how to design a scheme to realize a compartmented access structure can be considered as the problem that how to find a representation of a matroid from the presentation of its associated polymatroid [21]. Chen et al. [21] proposed a compartmented secret sharing scheme based on the general polymatroid and the Gabidulin codes, but the scheme is also to try to obtain nonsingular matrices. Later, Chen et al. [22] gave another method based on the idea of Brickell [7], and this scheme also needed to check many matrices for nonsingularity. But Farràs and Martł-Farr [16, 19] showed that it remains open whether or not there exist efficient algorithms to obtain the representations of multipartite matroids from representations of their associated polymatroids in general. Especially, the compartmented access structure is useful in some applications. For example, a company is divided into several departments. A decision of this company needs the approval of at least some persons in each department. That is to say, a decision requires the cooperation of all departments, and a minimum number of employees in each department needs to involve in it.Mashhadi and Dehkordi first introduced the Linear Homogeneous Recurrence (LHR) relations to thet,n threshold secret sharing scheme [23]. Later, they introduced the linear nonhomogeneous recurrence (LNHR) relations to the secret sharing scheme [24]. But the participants have the equal authority, and the qualified subset A satisfies A≥t in Mashhadi and Dehkordis schemes. Yuan et al. [25] introduced the LHR relations to the hierarchical secret sharing scheme. They reduced the computational complexity of the hierarchical secret sharing schemes from exponential time to polynomial time (Onkm−1logn) (km in [25] is different to it in our scheme). But there is no scheme that realizes the compartmented secret sharing scheme in polynomial time. Thus, in this paper, we mainly discuss the compartmented access structure.


## 1.2. Our Contributions

The motivation of our scheme is to design an efficient secret sharing scheme with the access structures which are more general than the threshold access structures. One of the key contributions is to introduce the LHR relations into the compartmented access structure, which divides the degreet of a polynomial into the low degrees of some polynomials, and each low degree equals to a fixed compartment threshold minus one. In the proposed scheme, the compartmented access structure is realized by using the linear homogeneous recurrence (LHR) relations. The LHR relations are suitable for the compartmented access structure since it has the ability to associate each compartment with a different polynomial. Another key contribution is to reduce the computational complexity of the compartmented secret sharing schemes from exponential time to polynomial time (Onmaxti−1logn). It is easy to share multisecret in our scheme. Each participant holds a share that is as long as the secret. The security of the proposed scheme is based on Shamir’s threshold scheme.The remainder of this paper is organized as follows. Section2 introduces the basic knowledge of the linear homogeneous recurrence relations and secret sharing scheme. Section 3 gives the proposed scheme. In Section 4, we analyze the security of the proposed scheme. Section 5 discusses some important properties of the proposed scheme and its performance. Finally, Section 6 draws our conclusion.


## 2. Preliminary Knowledge

In this section, first of all, we introduce the basic mathematical knowledge used in the proposed scheme. A detailed description of the linear homogeneous recurrence relations can be found in [24–28]. We also give a brief description about the perfect scheme, ideal scheme, and the compartmented access structure.


### 2.1. Linear Homogeneous Recurrence Relations

Theorem 1 (Richard [26]).
Leth0,h1,…,hj,… be a sequence of integers, and let α1,α2,…,αm be the distinct roots of the following characteristic equation of the linear homogeneous recurrence relation with constant coefficients:(1)hj=a1hj−1+a2hj−2+⋯+athj−t,where ai≠0, ai is selected over GF (q) (j≥t), and q is a large prime.Ifαi is a ti-fold root of the characteristic equation of (1), then the part of the general solution of this recurrence relation corresponding to αi is given as(2)Fji=ci1αij+ci2jαij+⋯+citijti−1αij=ci1+ci2j+⋯+citijti−1αij.Letfij=ci1+ci2j+⋯+citijti−1. So, we can get(3)Fji=fijαij.The general solution of the recurrence relation is(4)hj=Fj1+Fj2+⋯+Fjm,where t=∑i=1mti.Corollary 1.
Ifα1=α2=⋯=αm=α, then the general solution of the recurrence relation is(5)hj=Fj,where(6)Fj=c1+c2j+⋯+ctjt−1αj.Definition 2 (Richard [26]).
Leth0,h1,…,hj,… be an infinite sequence of numbers. Its generating function is defined to be the infinite series:(7)gx=∑i=0∞hixi.
The coefficient ofxj in gx is the nth term hj. Thus, xj acts as a placeholder for hj. A finite sequence h1,…,hj can be regarded as the infinite sequence h1,…,hj,0,0,…, in which all but a finite number of terms equal 0. Hence, every finite sequence has a generating function:(8)gx=∑i=0nhixi,which is a polynomial.Theorem 2 (Richard [26]).
Suppose that the LHR sequence {hi} is defined as (1), and the characteristic equation a1xt−1+⋯+at=xt has m different roots α1,α2,…,αm with multiplicities t1,t2,…,tm, where t1+t2+⋯+tm=t. Then, the generating function of the sequence {hi} is(9)gx=Rx1−a1xt11−a2xt2…1−amxtm,where Rx is a polynomial function of x with the degree at most t−1. Thus, we can get(10)hj=f1jα1j+f2jα2j+⋯+fmjαmj,where fij is a polynomial function of j with the degree at most ti−1. Conversely, given such polynomials,(11)Rxand1−a1xt11−a2xt2…1−amxtm,and there is a sequence h0,h1,…,hj,… satisfying a linear homogeneous recurrence relation with constant coefficients of order t of type (1) whose generating function is given by (5).


### 2.2. Secret Sharing Schemes

In the following section, we will give the definition of the perfect scheme and ideal scheme, and the hierarchical access structure is also listed.


#### 2.2.1. Perfect Scheme and Ideal Scheme

Definition 3.
A (t, n) threshold secret sharing scheme ∏:S×R⟶S1×S2×⋯×Sn over M, where S is the shared secret space, R is a set of random inputs, and Si (1≤i≤n) is the share space, satisfies the following two conditions:(1)
For allA⊆M and A≥t, HS|SA=0, where A is the subset of the participants, A is the number of the participants in the subset A, SA denotes the information of the shares to be obtained by the participants in the subset A, and H is the entropy.(2)
For allB⊆M and B<t, 0<HS|SB≤HS. If HS|SB=HS, then the scheme is called as the perfect scheme.Definition 4 (Tassa and Dyn [20]).
Let∑Pi denote the set of possible shares for the participant Mi∈M. The information rate of the scheme is defined as(12)ρ=minlog2Slog2∑Pi,where S denotes the size of the shared secret and ∑Pi denotes the size of the shares saved by the participant Mi. If ρ=1, the scheme is called as the ideal scheme.


#### 2.2.2. Compartmented Access Structure

n is used to denote the total number of the participants in the set P=P1,P2,…,Pn, i.e., n=P. In the compartmented secret sharing scheme, the set P is divided into disjoint compartments γ1,γ2,…,γm, i.e., P=∪i=1mγi and γi∩γj=∅,i≠j. The participants in the same compartment play an equivalent role. Let ti be the compartment γi threshold. The compartment γi contains ki participants, where n=Σi=1mki and i∈1,…,m. The qualified subset of the compartmented threshold secret sharing scheme contains at least ti participants from the compartment γi, where i∈1,…,m and ti≤ki. In the proposed scheme, we suppose that the global threshold t is equal to ∑i=1mti. The compartmented access structure AS is given by(13)AS=A∈2M|A≥t∧∀j=1,…,mA∧γj≥tj.


## 2.1. Linear Homogeneous Recurrence Relations

Theorem 1 (Richard [26]).
Leth0,h1,…,hj,… be a sequence of integers, and let α1,α2,…,αm be the distinct roots of the following characteristic equation of the linear homogeneous recurrence relation with constant coefficients:(1)hj=a1hj−1+a2hj−2+⋯+athj−t,where ai≠0, ai is selected over GF (q) (j≥t), and q is a large prime.Ifαi is a ti-fold root of the characteristic equation of (1), then the part of the general solution of this recurrence relation corresponding to αi is given as(2)Fji=ci1αij+ci2jαij+⋯+citijti−1αij=ci1+ci2j+⋯+citijti−1αij.Letfij=ci1+ci2j+⋯+citijti−1. So, we can get(3)Fji=fijαij.The general solution of the recurrence relation is(4)hj=Fj1+Fj2+⋯+Fjm,where t=∑i=1mti.Corollary 1.
Ifα1=α2=⋯=αm=α, then the general solution of the recurrence relation is(5)hj=Fj,where(6)Fj=c1+c2j+⋯+ctjt−1αj.Definition 2 (Richard [26]).
Leth0,h1,…,hj,… be an infinite sequence of numbers. Its generating function is defined to be the infinite series:(7)gx=∑i=0∞hixi.
The coefficient ofxj in gx is the nth term hj. Thus, xj acts as a placeholder for hj. A finite sequence h1,…,hj can be regarded as the infinite sequence h1,…,hj,0,0,…, in which all but a finite number of terms equal 0. Hence, every finite sequence has a generating function:(8)gx=∑i=0nhixi,which is a polynomial.Theorem 2 (Richard [26]).
Suppose that the LHR sequence {hi} is defined as (1), and the characteristic equation a1xt−1+⋯+at=xt has m different roots α1,α2,…,αm with multiplicities t1,t2,…,tm, where t1+t2+⋯+tm=t. Then, the generating function of the sequence {hi} is(9)gx=Rx1−a1xt11−a2xt2…1−amxtm,where Rx is a polynomial function of x with the degree at most t−1. Thus, we can get(10)hj=f1jα1j+f2jα2j+⋯+fmjαmj,where fij is a polynomial function of j with the degree at most ti−1. Conversely, given such polynomials,(11)Rxand1−a1xt11−a2xt2…1−amxtm,and there is a sequence h0,h1,…,hj,… satisfying a linear homogeneous recurrence relation with constant coefficients of order t of type (1) whose generating function is given by (5).


## 2.2. Secret Sharing Schemes

In the following section, we will give the definition of the perfect scheme and ideal scheme, and the hierarchical access structure is also listed.


### 2.2.1. Perfect Scheme and Ideal Scheme

Definition 3.
A (t, n) threshold secret sharing scheme ∏:S×R⟶S1×S2×⋯×Sn over M, where S is the shared secret space, R is a set of random inputs, and Si (1≤i≤n) is the share space, satisfies the following two conditions:(1)
For allA⊆M and A≥t, HS|SA=0, where A is the subset of the participants, A is the number of the participants in the subset A, SA denotes the information of the shares to be obtained by the participants in the subset A, and H is the entropy.(2)
For allB⊆M and B<t, 0<HS|SB≤HS. If HS|SB=HS, then the scheme is called as the perfect scheme.Definition 4 (Tassa and Dyn [20]).
Let∑Pi denote the set of possible shares for the participant Mi∈M. The information rate of the scheme is defined as(12)ρ=minlog2Slog2∑Pi,where S denotes the size of the shared secret and ∑Pi denotes the size of the shares saved by the participant Mi. If ρ=1, the scheme is called as the ideal scheme.


### 2.2.2. Compartmented Access Structure

n is used to denote the total number of the participants in the set P=P1,P2,…,Pn, i.e., n=P. In the compartmented secret sharing scheme, the set P is divided into disjoint compartments γ1,γ2,…,γm, i.e., P=∪i=1mγi and γi∩γj=∅,i≠j. The participants in the same compartment play an equivalent role. Let ti be the compartment γi threshold. The compartment γi contains ki participants, where n=Σi=1mki and i∈1,…,m. The qualified subset of the compartmented threshold secret sharing scheme contains at least ti participants from the compartment γi, where i∈1,…,m and ti≤ki. In the proposed scheme, we suppose that the global threshold t is equal to ∑i=1mti. The compartmented access structure AS is given by(13)AS=A∈2M|A≥t∧∀j=1,…,mA∧γj≥tj.


## 2.2.1. Perfect Scheme and Ideal Scheme

Definition 3.
A (t, n) threshold secret sharing scheme ∏:S×R⟶S1×S2×⋯×Sn over M, where S is the shared secret space, R is a set of random inputs, and Si (1≤i≤n) is the share space, satisfies the following two conditions:(1)
For allA⊆M and A≥t, HS|SA=0, where A is the subset of the participants, A is the number of the participants in the subset A, SA denotes the information of the shares to be obtained by the participants in the subset A, and H is the entropy.(2)
For allB⊆M and B<t, 0<HS|SB≤HS. If HS|SB=HS, then the scheme is called as the perfect scheme.Definition 4 (Tassa and Dyn [20]).
Let∑Pi denote the set of possible shares for the participant Mi∈M. The information rate of the scheme is defined as(12)ρ=minlog2Slog2∑Pi,where S denotes the size of the shared secret and ∑Pi denotes the size of the shares saved by the participant Mi. If ρ=1, the scheme is called as the ideal scheme.


## 2.2.2. Compartmented Access Structure

n is used to denote the total number of the participants in the set P=P1,P2,…,Pn, i.e., n=P. In the compartmented secret sharing scheme, the set P is divided into disjoint compartments γ1,γ2,…,γm, i.e., P=∪i=1mγi and γi∩γj=∅,i≠j. The participants in the same compartment play an equivalent role. Let ti be the compartment γi threshold. The compartment γi contains ki participants, where n=Σi=1mki and i∈1,…,m. The qualified subset of the compartmented threshold secret sharing scheme contains at least ti participants from the compartment γi, where i∈1,…,m and ti≤ki. In the proposed scheme, we suppose that the global threshold t is equal to ∑i=1mti. The compartmented access structure AS is given by(13)AS=A∈2M|A≥t∧∀j=1,…,mA∧γj≥tj.


## 3. The Proposed Scheme

Our scheme is based on the linear homogeneous recurrence relations. In the compartmented secret sharing, the set of participants is partitioned into compartments and the shared secrets can be recovered only if the number of participants from any compartment is greater than or equal to a fixed compartment thresholdti, and the total number of participants is greater than the global threshold t. In our scheme, we suppose that t=∑i=1mti. The proposed scheme consists of three phases, i.e., the initialization phase, the construction phase (share generation phase and share distribution phase), and the recovery phase. The basic idea of the proposed scheme is illustrated as follows. The system consists of some participants and a distributor. The distributor generates a LHR relation with m different roots, where m is the number of the disjoint compartment. Then, the distributor chooses the shared secrets and hides the shared secrets in some terms of this LHR sequence. The difficulty of our scheme is how to generate this LHR relation. The recovery of the shared secrets is realized by solving the general term of the LHR sequence {hi}. Then, the participants who want to recover the shared secrets should get those terms in which the shared secrets are hidden.


### 3.1. Initialization Phase

In the proposed scheme, suppose that the compartmented access structure is monotone, that is, if there existsA and A∈AS (the access structure), ∀A′∈2P, and A⊆A′, then we can get A′∈AS. Ito et al. presented that if the access structure AS was monotone, then there existed a perfect secret sharing scheme for the access structure [29].The proposed scheme requires a public bulletin board. Any person has the right to read or download the contents from the public bulletin board. Only the legitimate participants in the system can publish the information to the directory and modify or update the published content according to their own permissions.The proposed scheme is based on the LHR relation overGFq, where q is a large prime and GFq is the finite field. s1,s2,…,sl denotes l shared secrets that can be shared among the participants. The distributor D selects xij over GFq as the jth participant’s ID in γi, where xij∈GFq\1,2,…,l (this makes sure that we can hide the shared secrets in the first terms h1,h2,…,hl of the sequence), i∈1,…,m and j∈1,…,ki. Pij denotes j-th participant in compartment γi, where j∈1,…,ki. Then, the distributor D publishes the ID on the public bulletin board.


### 3.2. Construction Phase

The dealerD performs the following steps to generate the shares, distribute the shares, and hide the shared secrets in the first terms h1,h2,…,hl:(1)
The dealerD chooses m different integers α1,α2,…,αm over GFq, where each of them is not zero and m corresponds to the number of disjoint compartments of the participants.(2)
The dealerD chooses m different polynomials over GFq. Let f1,f2,…,fm denote m different polynomials. The degree of the polynomial fi is equal to ti−1, and ti is the fixed compartment γi threshold, that is,(14)fi=fix=ci1+ci2x+ci3x2+⋯+citixti−1,where the global thresholdt is equal to ∑i=1mti and i∈1,2,…,m.(3)
D computes fixij and sends the share fixij to Pij in compartment γi privately in a secure channel, where 1≤i≤m and 1≤j≤ki. This participant Pij keeps the share fixij.(4)
After all the shares have been sent to the participants throughfi, where 1≤i≤m, the dealer D computes(15)f1jα1j+f2jα2j+⋯+fmjαmjOver GFq.Let(16)hj=f1jα1j+f2jα2j+⋯+fmjαmjOver GFq.(5)
After the general term is obtained, the dealerD continues to compute h1,h2,...,hl. Then, D hides the shared secrets s1,s2,…,sl in these terms h1,h2,...,hl.(6)
The dealerD computes yi=hi−si, where 1≤i≤l.(7)
The dealerD publishes yi1≤i≤l,α1,α2,…,αm, and q on the public bulletin board.Remark 1.
From Step (3) above, we know that the polynomialfi corresponds to the compartment γi, and just greater or equal to ti participants in the compartment γi can recover the polynomial fi by pooling their shares.Remark 2.
From Theorem1, we can determine that hj is the general solution of a LHR relation with degree t and the roots of the characteristic equation of this LHR relation are α1,α2,…,αm. The multiplicity of the root αi is ti.


### 3.3. Recovery Phase

If the participants in the qualified subset want to recover the shared secretss1,s2,…,sl, they should recover the polynomials f1,f2,…,fm firstly. From the construction phase, we know that the order of the polynomial fi is ti−1. ti is equal to the fixed compartment γi threshold, and only the participants in the compartment γi can recover the polynomial fi. Since the order of fi is ti−1, we need greater or equal to ti participants in the compartment γi to recover the polynomial fi.So, these participants in the qualified subset contain at leastti participants from the subset γi=Pi1,Pi2,…,Piki, where 1≤i≤m. Suppose that the subset A⊆P satisfies these conditions. A participant in the subset A can obtain the share of each participant by the exchange in the secure channel. Assume that the participants in the qualified subset A want to recover the shared secrets. In the subset A, ti participants from the compartment γi pool the shares, where 1≤i≤m. By using these shares, these participants can determine the polynomial fi, where 1≤i≤m. After all the polynomials f1,f2,…,fm have been obtained, from Theorem 1 and the public parameters α1,α2,…,αm on the public bulletin board, the participants in the subset A can determine the general solution of the recurrence relation, that is,(17)hj=f1jα1j+f2jα2j+⋯+fmjαmjmodq.From (17), the participants in the subset A can compute h1,h2,...,hl. From Step (6) of the construction phase, the participants in the subset A can obtain the shared secrets by si=hi−yi, where 1≤i≤l.


### 3.4. Example

In this section, we give a example to show how the dealerD distributes the secrets in the construction phase and the participants recover the shared secrets in the recovery phase.


#### 3.4.1. Initialization Phase

(1)
Suppose that the setP of the participants is divided into two disjoint compartments γ1=4 and γ2=6, i.e., P=γ1∪γ2=10, and let k1=4andk2=6. Let t1=2 and t2=3.(2)
D randomly selects two shared secrets s1=5ands2=6 over GF21, where the prime q=21. Set x11=3,x12=4,x13=5,x14=6,x21=7,x22=8,x23=9,x24=10,x25=11,andx26=12 over GF21/0,1,2.


#### 3.4.2. Construction Phase

(1)
D selects two values α1=2andα2=1.(2)
D randomly selects two polynomials f1andf2 over GF21. Let f1=2x+1mod21 and f2=x2+x+3mod21.(3)
D distributes the share fixij to the jth participant Pij in γi, where 1≤i≤2 and 1≤j≤ki. These shares are listed as follows:(18)f1x11=7,f1x12=9,f1x13=11,f1x14=13,f2x21=17,f2x22=12,f2x23=9,f2x24=8,f2x25=9,f2x26=12.(4)
Lethj=2j+12j+j2+j+3mod21. Then, D computes h1=11andh2=8.(5)
D computes y1=h1−s1=11−5=6andy2=h2−s2=8−6=2.(6)
D publishes y1,y2,α1,α2, and q.


#### 3.4.3. Recovery Phase

Before the participants can recover the shared secrets, these participants should recover the two polynomialsf1andf2 firstly. For t1=2 and t2=3, a qualified subset must contain at least two participants from γ1 and three participants from γ2. These participants recover the shared secrets by exchanging their shares. We suppose two participants P11andP13 from γ1 and three participants P21,P23,andP24 from γ2. The two polynomials are recovered as follows.(1)
Firstly, we show how the polynomialf1 is recovered by P11andP13. For the two points (3, 7) and (5, 11), a polynomial can be determined by(19)f1x=7x−53−5+11x−35−3=2x+1mod21.(2)
Secondly, the polynomialf2 is recovered by P21,P23,andP24. For the three points (7, 17), (9, 9), and (10, 8), a polynomial can be determined by(20)f2x=17x−9x−107−97−10+9x−7x−109−79−10+8x−7x−910−710−9=17x2−19x+906−9x2−17x+702+8x2−16x+633mod21=x2+x+3mod21.(3)
From the public valuesα1=2andα2=1, these participants can get(21)hj=f1j2j+f2jmod21=2j+12j+j2+j+3mod21.Note: from Section 3.4.2, Construction Phase, we know that the participants in the subsetγ1 obtain the shares through f1 and the participants in the subset γ2 get the shares through f2, respectively. Thus, the participants P11andP13 just only can recover f1, and the participants P21,P23,andP24 just only can recover f2.(4)
These participants computeh1=11andh2=8.(5)
From the public valuesy1andy2, these participants can obtain the two shared secrets through the following equation:(22)si=hi−yi,1≤i≤2,sos1=5ands2=6.


## 3.1. Initialization Phase

In the proposed scheme, suppose that the compartmented access structure is monotone, that is, if there existsA and A∈AS (the access structure), ∀A′∈2P, and A⊆A′, then we can get A′∈AS. Ito et al. presented that if the access structure AS was monotone, then there existed a perfect secret sharing scheme for the access structure [29].The proposed scheme requires a public bulletin board. Any person has the right to read or download the contents from the public bulletin board. Only the legitimate participants in the system can publish the information to the directory and modify or update the published content according to their own permissions.The proposed scheme is based on the LHR relation overGFq, where q is a large prime and GFq is the finite field. s1,s2,…,sl denotes l shared secrets that can be shared among the participants. The distributor D selects xij over GFq as the jth participant’s ID in γi, where xij∈GFq\1,2,…,l (this makes sure that we can hide the shared secrets in the first terms h1,h2,…,hl of the sequence), i∈1,…,m and j∈1,…,ki. Pij denotes j-th participant in compartment γi, where j∈1,…,ki. Then, the distributor D publishes the ID on the public bulletin board.


## 3.2. Construction Phase

The dealerD performs the following steps to generate the shares, distribute the shares, and hide the shared secrets in the first terms h1,h2,…,hl:(1)
The dealerD chooses m different integers α1,α2,…,αm over GFq, where each of them is not zero and m corresponds to the number of disjoint compartments of the participants.(2)
The dealerD chooses m different polynomials over GFq. Let f1,f2,…,fm denote m different polynomials. The degree of the polynomial fi is equal to ti−1, and ti is the fixed compartment γi threshold, that is,(14)fi=fix=ci1+ci2x+ci3x2+⋯+citixti−1,where the global thresholdt is equal to ∑i=1mti and i∈1,2,…,m.(3)
D computes fixij and sends the share fixij to Pij in compartment γi privately in a secure channel, where 1≤i≤m and 1≤j≤ki. This participant Pij keeps the share fixij.(4)
After all the shares have been sent to the participants throughfi, where 1≤i≤m, the dealer D computes(15)f1jα1j+f2jα2j+⋯+fmjαmjOver GFq.Let(16)hj=f1jα1j+f2jα2j+⋯+fmjαmjOver GFq.(5)
After the general term is obtained, the dealerD continues to compute h1,h2,...,hl. Then, D hides the shared secrets s1,s2,…,sl in these terms h1,h2,...,hl.(6)
The dealerD computes yi=hi−si, where 1≤i≤l.(7)
The dealerD publishes yi1≤i≤l,α1,α2,…,αm, and q on the public bulletin board.Remark 1.
From Step (3) above, we know that the polynomialfi corresponds to the compartment γi, and just greater or equal to ti participants in the compartment γi can recover the polynomial fi by pooling their shares.Remark 2.
From Theorem1, we can determine that hj is the general solution of a LHR relation with degree t and the roots of the characteristic equation of this LHR relation are α1,α2,…,αm. The multiplicity of the root αi is ti.


## 3.3. Recovery Phase

If the participants in the qualified subset want to recover the shared secretss1,s2,…,sl, they should recover the polynomials f1,f2,…,fm firstly. From the construction phase, we know that the order of the polynomial fi is ti−1. ti is equal to the fixed compartment γi threshold, and only the participants in the compartment γi can recover the polynomial fi. Since the order of fi is ti−1, we need greater or equal to ti participants in the compartment γi to recover the polynomial fi.So, these participants in the qualified subset contain at leastti participants from the subset γi=Pi1,Pi2,…,Piki, where 1≤i≤m. Suppose that the subset A⊆P satisfies these conditions. A participant in the subset A can obtain the share of each participant by the exchange in the secure channel. Assume that the participants in the qualified subset A want to recover the shared secrets. In the subset A, ti participants from the compartment γi pool the shares, where 1≤i≤m. By using these shares, these participants can determine the polynomial fi, where 1≤i≤m. After all the polynomials f1,f2,…,fm have been obtained, from Theorem 1 and the public parameters α1,α2,…,αm on the public bulletin board, the participants in the subset A can determine the general solution of the recurrence relation, that is,(17)hj=f1jα1j+f2jα2j+⋯+fmjαmjmodq.From (17), the participants in the subset A can compute h1,h2,...,hl. From Step (6) of the construction phase, the participants in the subset A can obtain the shared secrets by si=hi−yi, where 1≤i≤l.


## 3.4. Example

In this section, we give a example to show how the dealerD distributes the secrets in the construction phase and the participants recover the shared secrets in the recovery phase.


### 3.4.1. Initialization Phase

(1)
Suppose that the setP of the participants is divided into two disjoint compartments γ1=4 and γ2=6, i.e., P=γ1∪γ2=10, and let k1=4andk2=6. Let t1=2 and t2=3.(2)
D randomly selects two shared secrets s1=5ands2=6 over GF21, where the prime q=21. Set x11=3,x12=4,x13=5,x14=6,x21=7,x22=8,x23=9,x24=10,x25=11,andx26=12 over GF21/0,1,2.


### 3.4.2. Construction Phase

(1)
D selects two values α1=2andα2=1.(2)
D randomly selects two polynomials f1andf2 over GF21. Let f1=2x+1mod21 and f2=x2+x+3mod21.(3)
D distributes the share fixij to the jth participant Pij in γi, where 1≤i≤2 and 1≤j≤ki. These shares are listed as follows:(18)f1x11=7,f1x12=9,f1x13=11,f1x14=13,f2x21=17,f2x22=12,f2x23=9,f2x24=8,f2x25=9,f2x26=12.(4)
Lethj=2j+12j+j2+j+3mod21. Then, D computes h1=11andh2=8.(5)
D computes y1=h1−s1=11−5=6andy2=h2−s2=8−6=2.(6)
D publishes y1,y2,α1,α2, and q.


### 3.4.3. Recovery Phase

Before the participants can recover the shared secrets, these participants should recover the two polynomialsf1andf2 firstly. For t1=2 and t2=3, a qualified subset must contain at least two participants from γ1 and three participants from γ2. These participants recover the shared secrets by exchanging their shares. We suppose two participants P11andP13 from γ1 and three participants P21,P23,andP24 from γ2. The two polynomials are recovered as follows.(1)
Firstly, we show how the polynomialf1 is recovered by P11andP13. For the two points (3, 7) and (5, 11), a polynomial can be determined by(19)f1x=7x−53−5+11x−35−3=2x+1mod21.(2)
Secondly, the polynomialf2 is recovered by P21,P23,andP24. For the three points (7, 17), (9, 9), and (10, 8), a polynomial can be determined by(20)f2x=17x−9x−107−97−10+9x−7x−109−79−10+8x−7x−910−710−9=17x2−19x+906−9x2−17x+702+8x2−16x+633mod21=x2+x+3mod21.(3)
From the public valuesα1=2andα2=1, these participants can get(21)hj=f1j2j+f2jmod21=2j+12j+j2+j+3mod21.Note: from Section 3.4.2, Construction Phase, we know that the participants in the subsetγ1 obtain the shares through f1 and the participants in the subset γ2 get the shares through f2, respectively. Thus, the participants P11andP13 just only can recover f1, and the participants P21,P23,andP24 just only can recover f2.(4)
These participants computeh1=11andh2=8.(5)
From the public valuesy1andy2, these participants can obtain the two shared secrets through the following equation:(22)si=hi−yi,1≤i≤2,sos1=5ands2=6.


## 3.4.1. Initialization Phase

(1)
Suppose that the setP of the participants is divided into two disjoint compartments γ1=4 and γ2=6, i.e., P=γ1∪γ2=10, and let k1=4andk2=6. Let t1=2 and t2=3.(2)
D randomly selects two shared secrets s1=5ands2=6 over GF21, where the prime q=21. Set x11=3,x12=4,x13=5,x14=6,x21=7,x22=8,x23=9,x24=10,x25=11,andx26=12 over GF21/0,1,2.


## 3.4.2. Construction Phase

(1)
D selects two values α1=2andα2=1.(2)
D randomly selects two polynomials f1andf2 over GF21. Let f1=2x+1mod21 and f2=x2+x+3mod21.(3)
D distributes the share fixij to the jth participant Pij in γi, where 1≤i≤2 and 1≤j≤ki. These shares are listed as follows:(18)f1x11=7,f1x12=9,f1x13=11,f1x14=13,f2x21=17,f2x22=12,f2x23=9,f2x24=8,f2x25=9,f2x26=12.(4)
Lethj=2j+12j+j2+j+3mod21. Then, D computes h1=11andh2=8.(5)
D computes y1=h1−s1=11−5=6andy2=h2−s2=8−6=2.(6)
D publishes y1,y2,α1,α2, and q.


## 3.4.3. Recovery Phase

Before the participants can recover the shared secrets, these participants should recover the two polynomialsf1andf2 firstly. For t1=2 and t2=3, a qualified subset must contain at least two participants from γ1 and three participants from γ2. These participants recover the shared secrets by exchanging their shares. We suppose two participants P11andP13 from γ1 and three participants P21,P23,andP24 from γ2. The two polynomials are recovered as follows.(1)
Firstly, we show how the polynomialf1 is recovered by P11andP13. For the two points (3, 7) and (5, 11), a polynomial can be determined by(19)f1x=7x−53−5+11x−35−3=2x+1mod21.(2)
Secondly, the polynomialf2 is recovered by P21,P23,andP24. For the three points (7, 17), (9, 9), and (10, 8), a polynomial can be determined by(20)f2x=17x−9x−107−97−10+9x−7x−109−79−10+8x−7x−910−710−9=17x2−19x+906−9x2−17x+702+8x2−16x+633mod21=x2+x+3mod21.(3)
From the public valuesα1=2andα2=1, these participants can get(21)hj=f1j2j+f2jmod21=2j+12j+j2+j+3mod21.Note: from Section 3.4.2, Construction Phase, we know that the participants in the subsetγ1 obtain the shares through f1 and the participants in the subset γ2 get the shares through f2, respectively. Thus, the participants P11andP13 just only can recover f1, and the participants P21,P23,andP24 just only can recover f2.(4)
These participants computeh1=11andh2=8.(5)
From the public valuesy1andy2, these participants can obtain the two shared secrets through the following equation:(22)si=hi−yi,1≤i≤2,sos1=5ands2=6.


## 4. Security Analysis

In this section, we will analyze that the unqualified subset cannot obtain the shared secrets and prove that the public valuesα1,α2,…,αm cannot leak any information about the shared secrets. First, we give a proposition below.Proposition 1.
Ifαi is a ti-fold root of the characteristic equation of LHR relation and the general solution for this LHR relation is given by(23)hj=∑i=1m∑k=1ticikjk−1αij,then its coefficient cik can be determined by t initial values by solving the linear system of equation, where t=∑i=1mti.From (17), we know when the participants in a unqualified subset want to recover the shared secrets, they must recover every polynomial fi, 1≤i≤m. Assume that the number of the participants is t−1 in the unqualified subset. If the total number of the participants in the unqualified subset is t−1, where t=∑i=1mti, then there exists the situation that the number of the participants contained in some compartment γi is ti−1.Theorem 3.
The general term of a linear homogeneous recurrence relation is secure for the unqualified participants if and only if the polynomial is secure for the unqualified participants.Proof.
First, we give an analysis that the public valuesα1,α2,…,αm do not leak any information about the shared secrets. From the public values α1,α2,…,αm, the characteristic equation of a LHR relation can be determined, according to Theorem 1. If a LHR relation is given, then the characteristic equation of this LHR relation can be determined and the root of the characteristic equation can be found. Thus, the public values α1,α2,…,αm do not leak any information except the characteristic equation of a LHR relation. From (4), we have(24)hj″=hj−f1jα1j+⋯+fi−1jαi−1j+fi+1jαi+1j+⋯+fmjαmj=fijαijmodq⟹hj″/αij=fijmodq.
For Corollary1, hj″ is also the general term of a LHR relation with ti degree, where the order of the polynomial fi⋅ is ti−1. We have supposed that the unqualified subset contains t−1 participants and ti−1 out of t−1 is in γi (let the ti−1 random terms be hi1,hi2,…,hiti−1).⇒ Suppose that the general term of the linear homogeneous recurrence relation with ti degree is secure for the unqualified participants. From the above, we know that public value αi does not leak any information except the characteristic equation. If the polynomial with degree ti−1 is not secure for the unqualified participants, that is to say, the ti−1 points can determine a polynomial with degree ti−1. From (5), we also infer that the ti−1 values can determine the general term of a linear homogeneous recurrence relation with degree ti. This is contradictory to our assumption.(⇐) Suppose that the polynomial with degree ti−1 is secure for the unqualified participants. If the general term of the linear homogeneous recurrence relation with degree ti is not secure for the unqualified participants, then ti−1 random terms (hi1,hi2,…,hiti−1) can determine the general term of the linear homogeneous recurrence relation. According to (24), we pick up ti−1 different terms and then can get ti−1 different points of the polynomial fij. Since the degree of the random polynomial fi⋅ is ti−1, we can say that ti−1 points can determine a random polynomial with the degree ti−1. This is contradictory to our assumption.
Therefore, when the participants in the unqualified subset want to obtain the shared secrets, our scheme is safe. Each share is sent through a secure channel, so we do not discuss about the shares’ leakage.


## 5. Discussion

In our scheme, each participant just holds one share to recover the secretssi,s2,…,sl in the whole recovery process. In this section, firstly, we prove that our scheme is perfect and ideal, and we also show that it is efficient to distribute multiple secrets. Secondly, we compare the popular schemes with our scheme.


### 5.1. Performance

We first show that the proposed scheme is perfect. So, we should prove that, for allA⊆P and A<t, HS|SA=HS. Equivalently, we require that, for any shared secrets sands′∈S and viewA∈S1×⋯×Sn,(25)Pr∏s,R|A=viewA=Pr∏s′,R|A=viewA,where A=P1,P2,…,Pt−1, and s is distributed by the linear homogeneous recurrence (LHR) relation (hj). We use hj to denote the linear homogeneous recurrence relation. The other s′ is distributed through the linear homogeneous recurrence (LHR) relation (hj′). Since the number of the participants in the subset A is t−1, there exists the situation that the number of the participants contained in some compartment γi is less than the threshold ti. We assume that the participants in the subset A can recover all the polynomials except fi. Suppose that two linear homogeneous recursive (LHR) sequences hj and hj′ satisfy the following conditions, that is,(26)hj=f1jα1j+f2jα2j+⋯+fmjαmjmodq,hj′=f1′jα1j+f2′jα2j+⋯+fm′jαmjmodq.The degrees of the polynomialsfi and fi′ are ti−1. Since we can determine all the polynomials except fi and fi′, if we can recover two polynomials fi and fi′, then hj and hj′ can be determined. Thus, we can determine the shared secrets s and s′. Since(27)fixi2=b0+b1xi2+⋯+bti−1xi2ti−1,fixi3=b0+b1xi3+⋯+bti−1xi3ti−1,⋮fixiti=b0+b1xiti+⋯+bti−1xititi−1,fi′xi2=b0′+b1′xi2+⋯+bti−1′xi2ti−1,fi′xi3=b0′+b1′xi3+⋯+bti−1′xi3ti−1,⋮fi′xiti=b0′+b1′xiti+⋯+bti−1′xititi−1,we can get(28)Cb0,…,bti−1T=fixi2,…,fixitiT,Cb0′,…,bti−1′T=fi′xi2,…,fi′xitiT,where(29)CT=1111xi2xi3⋯xiti⋮⋮⋯⋮xi2ti−1xi3ti−1⋯xititi−1,and xij is a participant’s ID.From the characteristic of the Vandermonde matrix, we can deducerankC=ti−1. There is no unique solution to (28). The probabilities of determining the vector b0,…,bti−1T and the vector b0′,…,bti−1′T are equal. Since, in the proposed scheme, when m polynomials are determined, then the shared secrets can be determined. So, the probabilities of determining s and s′ are equal, i.e.,(30)Pr∏s,R|A=viewA=Pr∏s′,R|A=viewA,so HS|SA=HS. Therefore, the proposed scheme is perfect.In our scheme, each participant’sID is published on the public bulletin board, and each participant’s share is selected over GFq. Each participant just should hold one share, and the shared secrets are selected over GFq. So, each share is as long as each secret. Therefore, the proposed scheme is ideal.For safety reasons or a certain requirement, we should change the shared secrets. The process of changing the shared secrets is given as follows.(1)
D chooses l new shared secrets(2)
D computes yi=hi−si, where 1≤i≤l(3)
D updates yi on the public bulletin board, where 1≤i≤lFrom the above process, we know that the computational cost is low to change the shared secrets.


### 5.2. Efficiency

When the global thresholdt is large, it usually takes a lot of computation to obtain the pairs of points of the polynomial. Because the order of the polynomial may also be t−1, it costs a lot of time to evaluate a polynomial with a large degree. In our scheme, we divide the global threshold t into m small thresholds t1,t2,…,tm, where t=∑i=1mti. Each threshold ti corresponds to a polynomial with the degree ti−1. Since the global order t is divided into m small low thresholds in the proposed scheme, it is efficient to get the evaluations on these low order polynomials. When the threshold is t, the computational complexity is usually higher than Ont−1. Before the hierarchical secret sharing scheme [25] was proposed, the computational complexity of the multipartite secret sharing schemes is exponential time. Yuan and Yang [25] reduced the computational complexity of the hierarchical secret sharing scheme from exponential time to polynomial time Onkm−1logn (km in [25] is different to it in our scheme, and ti in our scheme is usually smaller than km in [25]), but the computational complexity of our scheme can reduce to Onmaxti−1logn. So, the computational efficiency of the compartmented secret sharing scheme is better than the computational efficiency of the hierarchical secret sharing scheme, when the two types of the secret sharing schemes are based on LHR relations. In the recently popular compartmented secret sharing scheme [21], the nonsingular matrices are also needed to be obtained, and this computational complexity is exponential time. Comparing to the popular scheme [21], the computational complexity of our scheme is polynomial time (Onmaxti−1logn). So, our scheme is more efficient than the existing popular compartmented secret sharing schemes. But our scheme needs more public values than the existing popular compartmented secret sharing scheme [21].


## 5.1. Performance

We first show that the proposed scheme is perfect. So, we should prove that, for allA⊆P and A<t, HS|SA=HS. Equivalently, we require that, for any shared secrets sands′∈S and viewA∈S1×⋯×Sn,(25)Pr∏s,R|A=viewA=Pr∏s′,R|A=viewA,where A=P1,P2,…,Pt−1, and s is distributed by the linear homogeneous recurrence (LHR) relation (hj). We use hj to denote the linear homogeneous recurrence relation. The other s′ is distributed through the linear homogeneous recurrence (LHR) relation (hj′). Since the number of the participants in the subset A is t−1, there exists the situation that the number of the participants contained in some compartment γi is less than the threshold ti. We assume that the participants in the subset A can recover all the polynomials except fi. Suppose that two linear homogeneous recursive (LHR) sequences hj and hj′ satisfy the following conditions, that is,(26)hj=f1jα1j+f2jα2j+⋯+fmjαmjmodq,hj′=f1′jα1j+f2′jα2j+⋯+fm′jαmjmodq.The degrees of the polynomialsfi and fi′ are ti−1. Since we can determine all the polynomials except fi and fi′, if we can recover two polynomials fi and fi′, then hj and hj′ can be determined. Thus, we can determine the shared secrets s and s′. Since(27)fixi2=b0+b1xi2+⋯+bti−1xi2ti−1,fixi3=b0+b1xi3+⋯+bti−1xi3ti−1,⋮fixiti=b0+b1xiti+⋯+bti−1xititi−1,fi′xi2=b0′+b1′xi2+⋯+bti−1′xi2ti−1,fi′xi3=b0′+b1′xi3+⋯+bti−1′xi3ti−1,⋮fi′xiti=b0′+b1′xiti+⋯+bti−1′xititi−1,we can get(28)Cb0,…,bti−1T=fixi2,…,fixitiT,Cb0′,…,bti−1′T=fi′xi2,…,fi′xitiT,where(29)CT=1111xi2xi3⋯xiti⋮⋮⋯⋮xi2ti−1xi3ti−1⋯xititi−1,and xij is a participant’s ID.From the characteristic of the Vandermonde matrix, we can deducerankC=ti−1. There is no unique solution to (28). The probabilities of determining the vector b0,…,bti−1T and the vector b0′,…,bti−1′T are equal. Since, in the proposed scheme, when m polynomials are determined, then the shared secrets can be determined. So, the probabilities of determining s and s′ are equal, i.e.,(30)Pr∏s,R|A=viewA=Pr∏s′,R|A=viewA,so HS|SA=HS. Therefore, the proposed scheme is perfect.In our scheme, each participant’sID is published on the public bulletin board, and each participant’s share is selected over GFq. Each participant just should hold one share, and the shared secrets are selected over GFq. So, each share is as long as each secret. Therefore, the proposed scheme is ideal.For safety reasons or a certain requirement, we should change the shared secrets. The process of changing the shared secrets is given as follows.(1)
D chooses l new shared secrets(2)
D computes yi=hi−si, where 1≤i≤l(3)
D updates yi on the public bulletin board, where 1≤i≤lFrom the above process, we know that the computational cost is low to change the shared secrets.


## 5.2. Efficiency

When the global thresholdt is large, it usually takes a lot of computation to obtain the pairs of points of the polynomial. Because the order of the polynomial may also be t−1, it costs a lot of time to evaluate a polynomial with a large degree. In our scheme, we divide the global threshold t into m small thresholds t1,t2,…,tm, where t=∑i=1mti. Each threshold ti corresponds to a polynomial with the degree ti−1. Since the global order t is divided into m small low thresholds in the proposed scheme, it is efficient to get the evaluations on these low order polynomials. When the threshold is t, the computational complexity is usually higher than Ont−1. Before the hierarchical secret sharing scheme [25] was proposed, the computational complexity of the multipartite secret sharing schemes is exponential time. Yuan and Yang [25] reduced the computational complexity of the hierarchical secret sharing scheme from exponential time to polynomial time Onkm−1logn (km in [25] is different to it in our scheme, and ti in our scheme is usually smaller than km in [25]), but the computational complexity of our scheme can reduce to Onmaxti−1logn. So, the computational efficiency of the compartmented secret sharing scheme is better than the computational efficiency of the hierarchical secret sharing scheme, when the two types of the secret sharing schemes are based on LHR relations. In the recently popular compartmented secret sharing scheme [21], the nonsingular matrices are also needed to be obtained, and this computational complexity is exponential time. Comparing to the popular scheme [21], the computational complexity of our scheme is polynomial time (Onmaxti−1logn). So, our scheme is more efficient than the existing popular compartmented secret sharing schemes. But our scheme needs more public values than the existing popular compartmented secret sharing scheme [21].


## 6. Conclusion

In this paper, based on the linear homogeneous recurrence relations, we propose a compartmented multisecret sharing scheme. We prove that the proposed scheme is perfect and ideal. The security of our scheme is based on Shamir’s threshold scheme. Each polynomial corresponds to a different subset of the participants, and the degree of the polynomial is equal to the threshold of the compartment minus one, i.e., we divide thet-th degree polynomial into m different polynomials, and the sum of the degrees of m different polynomials is equal to t−m. It is more efficient to distribute or recover the shared secrets by using some polynomials with low degrees than to distribute/recover the shared secrets by using a polynomial with a large degree, i.e., the computational complexity is reduced from time exponential time to Onmaxti−1logn. Moreover, our scheme is efficient when we share the multisecret. Especially, when we want to change the shared secrets, we can find that the proposed scheme is more efficient than the existing popular multisecret sharing schemes that were not based on the linear homogeneous recurrence relations. In the proposed scheme, each participant only needs to hold one share in the whole process. The limitation of our scheme is that our scheme needs more public values.



---

*Source: 5566179-2021-07-20.xml*