Hierarchical secret sharing scheme for WSN based on linear homogeneous recurrence relations

Abstract

Wireless sensor network is a key technology in the sensing layer of the Internet of Things. Data security in wireless sensor network is directly related to the authenticity and validity of data transmitted in the Internet of Things. Due to the large number and different types of nodes in wireless sensor networks, layered secret key sharing technology is increasingly used in wireless sensor networks. In a hierarchical secret sharing scheme, participants are divided into sections with different permissions for each team, but the same permissions for participants in the same team. In this article, we follow the approach of the hierarchical secret sharing scheme derived from the linear homogeneous recurrence relations. We design a hierarchical multi-secret sharing scheme for wireless sensor networks on the basis of the elliptic curve public key cryptosystem combined with the linear homogeneous recurrence relations. In the proposed scheme, we do not make sure that the participants are half-truthful. In addition, the participants’ shadows can be reused. Our scheme is computational security. Only one share from each member is required in our hierarchical multi-secret sharing scheme. It is more suitable for wireless sensor networks compared to the up-to-date schemes.

Introduction

In a secret sharing scheme of $(t,n)$ threshold, ¹ the secret is passed around in $n$ participants, and when it is required, any $t$ or more participants can retrieve the shared secrets by combining their shares. A handy case of secret sharing is the distributed storage of sensitive information. Such a solution is called perfect scheme if any participant of any ineligible subset does not have access to any information about the shared secrets. Shamir ¹ and Blakley ² raised the threshold secret sharing schemes, two exceptional cases where all the participants have the same privileges.

There are restrictions on threshold secret sharing schemes in reality. Therefore, to enhance the feasibility of secret sharing in practice, many researchers concentrate on particular sets of access structures, for instance, weighted threshold access structure, compartmented access structure, graph-based access structures, ³ bipartite access structures ⁴ and hierarchical access structure. ⁵ A large number of studies in our community have been focused on the protection (e.g. privacy, ⁶ security, ⁷ malicious behaviours) ⁸ of our lives, towards constructing a safer information environment. Shamir proposed the weighted threshold secret sharing scheme. ¹ But the secret sharing scheme ¹ is a trivial solution by assigning multiple shares to each participant according to its integral weight, which is inefficient. Simmons ⁹ presented a multipartite access structure, and the definitions of the compartmented access structure and the hierarchical access structure were given by him. After Simmons, Brickell ¹⁰ introduced an approach to give an ideal secret sharing scheme for the multilevel and compartmented access structures. The multipartite access structure can classically be divided into the hierarchical access structure and the compartmented access structure.^2,11

Tassa ¹² proposed some hierarchical threshold access structures rested on Birkhoff interpolation, and the interpolation matrix must satisfy Polya’s condition. ¹² Farras et al. ¹³ gave a comprehensive characteristic of the ideal multipartite access structures. Then the scholars investigated the hierarchical secret sharing schemes by using the findings on integer polymatroids in the solution given by Farras et al. ¹⁴ These techniques offered a characterization of the hierarchical access structures and by these techniques, there admits the ideal and perfect secret sharing scheme existing for the hierarchical access structures.^14,15 Chen et al. ¹⁶ proposed a method to give an ideal scheme that implements the compartmented access structure by the general polymatroid-based method presented in Farras et al.’s solution ¹⁴ and the Gabidulin ¹⁷ codes. Chen et al. ¹⁸ proposed a method of implementing the multipartite access structure. Motivated by the integer polymatroids, the main idea of Chen et al.’s scheme ¹⁸ from Brickell ¹⁰ provides a polynomial-time algorithm to build such a matrix $M$ , which makes all the determinants of those particular multi-matrices non-zero in certain limited domains.

The methods mentioned above do not introduce verifiability. Also, researchers have worked out verifiable resolutions for the classic secret sharing schemes. Motivated by Birkhoff interpolation, Traverso et al. ¹⁹ gave a verifiable hierarchical secret sharing method. But this method has the shortcomings of these schemes rested on Birkhoff interpolation. The drawback of the above hierarchical threshold access structure is that the distributor must perform exponential examinations when allocating identifications and shares to the members. Xu et al. ²⁰ proposed an efficient compartmented secret sharing scheme. Yuan et al. ²¹ provided an ideal polynomial-time hierarchical secret sharing scheme based on linear homogeneous recurrence (LHR) relations. We present a verifiable hierarchical secret sharing scheme rested on Xu et al. ²⁰ So, our method is more efficient than Traverso’s solution. ¹⁹

The rest of the article focuses on the following sections. The second section leads to the secret sharing scheme, LHR relations, as well as Bilinear Pairing and Diffie–Hellman problem. The third section describes the system proposed in our article. In the fourth section, we demonstrate the security analysis of our solution, the significant attributes of our solution and show the comparisons with other solutions. In the fifth section, conclusions are provided.

Preliminary

Secret sharing schemes

In this part, we show the statement of the hierarchical access structure.

Definition 1

A $(t,n)$ threshold secret sharing scheme $\Pi :S\times R\to S_1\times S_2\times ···\times S_n$ over $P$ ( $P$ is the aggregate of game participants, that is $P=\{P_1,P_2,...,P_n\}$ and $|P|=n$ ), satisfying the two following conditions, in which $S$ is the shared secret space, $S_i$ $(1\le i\le n)$ is the share space, and $R$ is an aggregate of random feeds.

A brief overview of the hierarchical access structure is provided in the following section.

Definition 2

Make $n$ indicate the total number of participants. In the hierarchical secret sharing scheme, the participants $P$ can be grouped into classes ${\gamma }_1,{\gamma }_2,...,{\gamma }_m$ of the participants, $P={\cup }_{i=1}^m{\gamma }_i$ and ${\gamma }_i\cap {\gamma }_j=Ø$ for all $1\le i<j\le m.$ The class ${\gamma }_i$ contains $n_i$ participants, in which $i\in \{1,2,...,m\}$ . Let $K=\{k_i{\}}_{i=1}^m$ be assorted in ascending sequence, $0<k_1<k_2<···<k_m.$ The $(K,n)-$ hierarchical threshold access structure is

$$\mathrm{AS}=\{A\subset P:|A\bigcap \left({\bigcup }_{j=1}^i{\gamma }_j\right)|\ge k_i,\forall i\in \{1,2,...,m\}\}$$

LHR relations

We briefly describe the LHR relations. The LHR relations are introduced in detail in the studies by Xu and other peers.^22–25

Theorem 1

Let $h_0,h_1,...,h_j,...,$ be a series of numbers and ${\alpha }_1,{\alpha }_2,...,{\alpha }_m$ be the different roots of the following characteristic equation of the LHR relation with constant coefficients

$$h_j=a_1{h}_{j-1}+a_2{h}_{j-2}+···+a_t{h}_{j-t}$$

(1)

where $a_t\ne 0$ , $a_i$ is chosen over $\mathrm{GF}(q)$ $(j\ge t)$ , and $q$ is a large prime.

If ${\alpha }_i$ is a $t_i$ -fold root of the characteristic equation (1), then the part of the resolution of the recurrence relation with respect to ${\alpha }_i$ is given as

$$\begin{array}{c}\multicolumn{1}{c}{F_j^{(i)}=c_{i1}{\alpha }_i^j+c_{i2}j{\alpha }_i^j+···+c_{i{t}_i}{j}^{t_i-1}{\alpha }_i^j}\\ \multicolumn{1}{c}{=(c_{i1}+c_{i2}j+···+c_{i{t}_i}{j}^{t_i-1}){\alpha }_i^j}\end{array}$$

Let $f_i(j)=(c_{i1}+c_{i2}j+···+c_{i{t}_i}{j}^{t_i-1})$ . We can have

$$F_j^{\left(i\right)}=f_i\left(j\right){\alpha }_i^j$$

For recursive relations, the usual solution is derived from the following

$$h_j=F_j^{\left(1\right)}+F_j^{\left(2\right)}+···+F_j^{\left(m\right)}$$

where $t=\sum _{i=1}^m{t}_i$

If ${\alpha }_1={\alpha }_2=···={\alpha }_m=\alpha ,$ then for the recurrence relation the general solution is

$$h_j=F_j$$

(2)

where

$$F_j=(c_1+c_{2}j+···+c_t{j}^{t-1}){\alpha }^j$$

Diffie–Hellman problem

Given a cycle additive group $G=<g>$ , with $g$ being the generator and the order of $G$ being the large prime $q$ ,

1. The problem of the discrete logarithm is defined as computing $a$ , provided $(g,\mathrm{ag})$ , where $\forall a\in {\mathbb{Z}}_q$ ;

2. The computational Diffie–Hellman (CDHP) problem is defined as computing $(\mathrm{ab})g$ , provided $(g,\mathrm{ag},\mathrm{bg})$ , where $\forall a,b\in {\mathbb{Z}}_q$ ;

3. The decisional Diffie–Hellman problem (DDHP) is defined as deciding whether $(\mathrm{ab})g=\mathrm{cg}$ , provided $(g,\mathrm{ag},\mathrm{bg},\mathrm{cg})$ , where $\forall a,b,c\in {\mathbb{Z}}_q$ .

It is called the GDH group when DDHP is solvable in polynomial time, but no probabilistic algorithm can solve CDHP in the polynomial time with a non-negligible advantage.

Bilinear pairing

Suppose that $G_1$ and $G_2$ are an additive group and a multiplicative group, respectively, with the same prime order $q$ . Here $q$ is a large prime. Let $g$ be a generator of $G_1$ . Suppose that DDHP is easy in $G_1$ and hard in $G_2$ . We assume CDHP in $G_1$ and the DDHP in $G_2$ are hard. We call it the cryptographic bilinear mapping, if a mapping $\hat{e}:G_1\times G_1\to G_2$ satisfies the following properties:

1. Bilinearity: $\forall H_1,Q_1\in G_1,\forall a,b\in {\mathbb{Z}}_q$ , $\hat{e}(a{H}_1,b{Q}_1)=\hat{e}(H_1,Q_1{)}^{\mathrm{ab}}.$

2. Non-degeneracy: If $g$ is a generator of $G_1$ , then the generator of $G_2$ is $\hat{e}(g,g)$ . In other words, if $g\ne 0$ , then $\hat{e}(g,g)\ne 1$ .

3. Computability: $\forall H1,Q1\in G_1$ , there is a polynomial-time algorithm to compute $\hat{e}(H_1,Q_1)$ .

The proposed scheme

In the following section, we show how the proposed scheme works. The proposed scheme is built upon the LHR relations and the elliptic curve public key cryptosystem (ECC). $P=\{P_1,P_2,...,P_n\}$ denotes the set of the participants, where $P_i$ is the ith participant in the set, $1\le i\le n$ . Our scheme is composed of three stages, namely, initialization stage, construction stage and recovery stage. In the initialization stage, we initialize some functions or parameters; in the construction stage, the shared secrets are hidden in these terms $h_1,...,h_l$ , and in the recovery stage, we recover the shared secrets by getting these terms $h_1,...,h_l$ first. The distributor is honest in our scheme. But the participants can be malicious, because in our scheme the participants can be detected if they provide fake pseudo shares. The distributor acts the role in the construction stage and the participants act the role in the recovery stage.

We first describe the main idea of the proposed scheme. The proposed scheme contains $n$ participants and one dealer/distributor. Only one shadow $s_i\in {\mathbb{Z}}_q^{*}$ is held by each participant $P_i$ . The distributor selects $m$ random LHR relations. In the construction stage, the participants in ${\gamma }_1$ are used to construct $m$ LHR relations and the participants in ${\gamma }_i$ are used to build $m-i+1$ LHR relations, where $2\le i\le m$ . So some participants can be replaced by other participants who have the higher privilege. That is, the participants in ${\gamma }_i$ can replace the participants in ${\gamma }_{i-j}$ , where $i-j\ge 1$ . Then, the distributor adds the $m$ general terms of the $m$ LHR relations. From Theorem 1, we know that the sum is a general term of an LHR relation and we denote this LHR relation as $F$ -LHR relation. The distributor selects the shared secrets and keeps the shared secrets hidden in the first several terms of F-LHR relation. So in the recovery stage, the recovery of the shared secrets is achieved through resolving the general term of $F$ -LHR relation. After that, we obtain the items that hide the shared secrets. The notations used are shown in Table 1.

Table 1.

Notation table.

Notation	Description
$P=\{P_1,P_2,...,P_n\}$	The set of participants
$P_i$	The ith participant in set $P$
$\mathrm{ke}{y}_i$	The ith shared secret
$s_i\in {\mathbb{Z}}_q^{*}$	The shadow hold by the ith participant $P_i$
$s_0\in {\mathbb{Z}}_q^{*}$	The shadow hold by the distributor $D$
${\gamma }_i$	The ith subset of the participant
$h_i$	The ith term in the sequences $\{h_i{\}}_{i=0}^n$ and $\{h_i{\}}_{i=0}^n$ is written as $\{h_i\}$ in our scheme. In our scheme, we use $h_i$ to denote the general term
$q$	The large prime
$\mathrm{GF}\left(q\right)$	The finite field
$G_1$	The additive group with the generator $g$ and the order of $G_1$ is $q$
$G_2$	The multiplicative group with the order $q$
$B_0$	The share $g{s}_0$ was generated by distributor $D$ and published
$B_i$	The share $g{s}_i$ was generated by the ith participant and published
$R_i$	The pseudo share $s_i{B}_0$
$f(r,w)$	The double-parameter one-way function
$(h_i^{(j)})$	The jth linear homogeneous recurrence relation
$r_1,r_2,...,r_m$	$m$ random values

Initialization stage

The proposed scheme is rested on the LHR relations in $\mathrm{GF}(q)$ , where $\mathrm{GF}(q)$ is a finite field. $\mathrm{ke}{y}_1,\mathrm{ke}{y}_2,...,\mathrm{ke}{y}_l$ denote the $l$ secrets that can be shared among the participants. The participant $P_i$ herself or himself chooses the shadow $s_i\in {\mathbb{Z}}_q^{*}$ , not the distributor $(D)$ for the selection. In this way, it is possible to protect the key distributor from forgery.

• 1. An elliptic curve $E$ over $\mathrm{GF}(q)$ is selected by $D$ , in which $q$ is a large prime. Assume that $G_1$ is an additive group with the order $q$ . Assume that DDHP is simple and CDHP is tough in $G_1$ .

Suppose $G_1$ to be the elliptic curve. Assume $G_2$ to be a multiplicative group with the same order $q$ . Suppose $\hat{e}:G_1\times G_1\to G_2$ to be a bilinear mapping and the conditions in the section ‘Bilinear pairing’ can be satisfied.

• 2. $D$ selects a generator $g$ for $G_1$ .

• 3. These values $\{G_1,g,q\}$ are published/released by $D$ .

Each participant $P_i$ chooses $s_i\in {\mathbb{Z}}_q^{*}$ to be the shadow for himself/herself and then calculates $B_i=s_{i}g\in G_1$ , $1\le i\le n$ . Each participant $P_i$ keeps $s_i$ and then securely sets $B_i$ to $D$ . $D$ should ensure that $B_i\ne B_j$ , if $i\ne j$ . In the case where $B_i=B_j$ , these participants will then be asked by $D$ to pick their shadows again. $D$ releases $(I{D}_i,B_i)$ , in which $I{D}_i$ is the participant $P_i$ ’s identity. In the last part of this section, we define a double-argument one-way function as given in the study by Chien et al. ¹¹ Given random value $r$ and value $w$ , the $f(r,w)$ represents a double-argument one-way function that is easily computed. In some cases, though, it is difficult to be computed:

1. Knowing $f(r,w)$ and $w$ , $r$ is hard to be worked out.

2. Unknowing $w$ , $f(r,w)$ is hard to be worked out for any $r$ .

3. Knowing $f(r,w)$ and $r$ , $w$ is hard to be calculated.

4. Knowing $f(r,w)$ and $r$ , for $r\prime \ne r$ , $f(r\prime ,w)$ is hard to be calculated.

5. Knowing $w$ , it is quite a challenge to get two such distinct characters $r_2$ and $r_1$ that $f(r_2,w)=f(r_1,w)$ .

Construction stage

In the construction stage, the key distributor $D$ first generates $m$ different LHR sequences $\{h_i^{(1)}\},\{h_i^{(2)}\},...,\{h_i^{(j)}\},...,\{h_i^{(m)}\}$ . In our scheme, $k_1,k_2,...,k_m$ are the degrees of the characteristic equation of the LHR relations $(h_i^{(1)}),(h_i^{(2)}),...,(h_i^{(j)}),...,$ $(h_i^{(m)})$ , where $(h_i^{(j)})$ denotes the jth LHR relation. Figure 1 shows the construction stage, where ${\gamma }_1+{\gamma }_2+\cdots +{\gamma }_{m-1}$ denotes $\bigcup _{i=1}^{m-1}{\gamma }_i$ and Pshare denotes the pseudo share.

Figure 1.

Construction stage.

Theorem 2

The addition of two general terms of two different LHR relations is a general term of an LHR relation.

Proof of Theorem 2

Suppose that $h_i^{(1)}$ and $h_i^{(2)}$ are the general terms of two different LHR relations with the different degrees $t_1$ and $t_2$ , respectively, and assume $h_i=h_i^{(1)}+h_i^{(2)}$ . So, it is only necessary to prove that $h_i$ is the general term of an LHR relation. From Theorem 1, we know $h_i$ is the generic term of an LHR relation, and $t_1+t_2$ is the degree of the LHR relation $(h_i)$ .

The distributor $D$ distributes the shares through the following procedure:

• 1. The distributor $D$ randomly selects the integer $r_1,r_2,...,r_m$ and publishes them.

• 2. $D$ chooses $s_0\in {\mathbb{Z}}_q^{*}$ , computes $B_0=s_{0}g\in G_1$ , makes sure $B_0\ne B_i$ and publishes $B_0$ , where $1\le i\le n$ .

• 3. The distributor $D$ chooses $m$ different integers ${\alpha }_1,{\alpha }_2,...,{\alpha }_m$ over $\mathrm{GF}(q)$ and publishes them, where each of them is non-zero.

• 4. $D$ selects the value ${\alpha }_1$ to make $(x-{\alpha }_1{)}^{k_1}=x^{k_1}+a_{11}{x}^{k_1-1}+···+a_{1k_1}=0$ as the auxiliary function of an LHR relation, where $q>a_{1i}$ and $1\le i\le k_1$ .

• 5. $D$ computes the pseudo share $R_i=s_0{B}_i$ and $I_i^1=f(r_1,R_i)$ , where $i=1,2,...,n_1$ , and $n_1$ is the quantity of participants in the sub-group ${\gamma }_1$ .

• 6. $D$ considers the first LHR sequence which is defined as

$$\{\begin{array}{c}{h}_0^{\left(1\right)}=I_1^1,h_1^{\left(1\right)}=I_2^1,...,h_{k_1-1}^{\left(1\right)}=I_{k_1}^1,\hfill \\ \multicolumn{1}{c}{h_{i+k_1}^{\left(1\right)}+a_{11}{h}_{i+k_1-1}^{\left(1\right)}+···+a_{1k_1}{h}_i^{\left(1\right)}=0}\end{array}i\ge 0$$

(3)

We use the participants in the sub-group ${\gamma }_1$ to build the first LHR sequence. During the recovery stage, the general term of the first LHR sequence is allowed to be retrieved only by the participants in the sub-group ${\gamma }_1$ .

• 7. $D$ computes $h_i^{(1)}$ , where $k_1\le i\le n_1-1$ .

• 8. $D$ computes $y_i^1=I_i^1-h_{i-1}^{(1)}$ and publishes $y_i^1$ , where $k_1<i\le n_1$ .

• 9. $D$ continues to generate $m-1$ LHR sequences. The jth LHR sequence $\{h_i^{(j)}\}$ is generated as follows, for $j\in \{2,3,...,m\}$ .

$$\{\begin{array}{c}{h}_0^{\left(j\right)}=I_1^j,h_1^{\left(j\right)}=I_2^j,...,h_{k_j-1}^{\left(j\right)}=I_{k_j}^j,\hfill \\ \multicolumn{1}{c}{h_{i+k_j}^{\left(j\right)}+a_{11}{h}_{i+k_j-1}^{\left(j\right)}+···+a_{1k_j}{h}_i^{\left(j\right)}=0}\end{array}i\ge 0$$

(4)

We use the participants in the subset $\bigcup _{i=1}^j{\gamma }_i$ to construct the jth LHR sequence. In the recovery stage, only the participants in the subset $\bigcup _{i=1}^j{\gamma }_i$ can recover the general term of the jth LHR sequence.

• 9.4. $D$ computes $h_i^{(j)}$ , where $k_j\le i\le N_j-1$ .

• 9.5. $D$ computes $y_i^j=I_i^j-h_{i-1}^{(j)}$ and publishes $y_i^j$ , where $k_j<i\le N_j$ .

• 10. After the $m$ LHR relations are generated, $D$ combines them into an LHR relation. Let $h_i=h_i^{(1)}+h_i^{(2)}+···+h_i^{(m)}$ . From Theorem 2, we can determine that $h_i$ is the general term of an LHR relation and the degree of this LHR relation $(h_i)$ is $k_1+···+k_m$ . Since the degrees of these LHR relations $(h_i^{(1)}),...,(h_i^{(m)})$ correspond to $k_1,..,k_m$ , respectively, so the sum of these degrees is $k_1+···+k_m$ . However, we define the threshold of the hierarchical secret sharing scheme as $k_m$ , because $k_m$ different participants can recover the shared secrets (Since at least $k_1$ participants from the subset ${\gamma }_1$ , at least $k_2-k_1$ participants from the subset ${\gamma }_2$ and so on, and the last $k_m-k_{m-1}$ participants from the subset ${\gamma }_m$ can recover the LHR relation $(h_i)$ , the threshold of the hierarchical secret sharing scheme is $k_1+(k_2-k_1)+···+(k_m-k_{m-1})=k_m$ ).

• 11. $D$ computes $d_i=\mathrm{ke}{y}_i-h_{i-1}$ and publishes $d_i$ , where $1\le i\le l$ . This means that we can hide the shared secrets in these terms $h_0,h_1,...,h_{l-1}$ .

Remark 1

The double-parameter one-way function makes sure that for the same $R_i$ , the random values $f(r_j,R_i)$ and $f(r_k,R_i)$ are different, where $k\ne j$ . This means that if some participants’ pseudo shares are used to construct different LHR relations, the double-parameter one-way function makes sure that for the same pseudo share, the random values are different.

Recovery stage

In this section, we present how the shared secrets are recovered. First, a proposition is given as follows.

Proposition 1

Provided that ${\alpha }_i$ is a t_i-fold root of the characteristic formula of an LHR relation and the general resolution of this LHR relation is obtained as

$$h_j=\sum _{i=1}^m\left(\sum _{k=1}^{t_i}{c}_{\mathrm{ik}}{j}^{k-1}\right){\alpha }_i^j$$

its coefficient $c_{\mathrm{ik}}$ can then be fixed by the $t$ initial values, which is achieved by resolving the system of linear formulas, in which $t=\sum _{i=1}^m{t}_i.$

The participant $P_i$ can get every participant’s pseudo share $R_j$ by exchanging in a qualified sub-group, where $i\ne j$ . In the qualified sub-group, the participants need to recover $m$ LHR sequences before obtaining the shared secrets. The jth LHR sequence is recovered as follows.

From the construction stage, we know that the order of the jth LHR relation is $k_j$ . We need at least $k_j$ participants when we are trying to recover the jth LHR sequence. But there are $k_{j-1}$ participants from $\bigcup _{i=1}^{j-1}{\gamma }_i$ (if $k_{j-1}$ participants use their pseudo shares to solve the general term $h_i^{(j-1)}$ of the (j-1)th LHR relation, they need to be combined to solve the general term $h_i^{(j)}$ of the jth LHR relation, where $2\le j\le m$ ). The other $k_j-k_{j-1}$ participants are from the subset ${\gamma }_j$ .

With the use of those pseudo shares, the participants of the qualified sub-groups compute $k_j$ items of the jth LHR relation as follows

$$h_{i-1}^{\left(j\right)}=\{\begin{array}{c}{I}_i^{j}1\le i\le k_j\hfill \\ \multicolumn{1}{c}{I_i^j-y_i^j{k}_j<i\le n}\end{array}$$

(5)

Based on Proposition 1, $k_j$ points $(i-1,h_{i-1}^{(j)}/{\alpha }_j^{i-1})$ leads to the determination of the $(k_j-1)\mathrm{th}$ degree polynomial $p^j(x)$ , and its definition is

$$\begin{array}{c}\multicolumn{1}{c}{p^j\left(x\right)=\sum _{i\in A}\frac{h_{i-1}^{\left(j\right)}}{{\alpha }_j^{i-1}}\underset{j\in A}{\overset{j\ne i}{\Pi }}\frac{x-j+1}{i-j}(modq)}\\ \multicolumn{1}{c}{=c_0+c_{1}x+···+c_{k_{j-1}}{x}^{k_j-1}(modq)}\end{array}$$

(6)

where $A\in \{1,2,...,n\}$ and the superscript of $p(x)$ represents different polynomial. According to Theorem 1, $h_i^{(j)}=p^j(i){\alpha }_j^i$ , in which $p^j(i)$ is a $k_j-1$ degree polynomial and $i\ge 0$ , we can have the general term $h_i^{(j)}$ . After obtaining $m$ general terms of $m$ LHR sequences $\{h_i^{(1)}\},\{h_i^{(2)}\},...,\{h_i^{(m)}\}$ , the general term $h_i$ is

$$h_i^{(1)}+h_i^{(2)}+···+h_i^{(m)}$$

where the order of the LHR relation $(h_i)$ is $k_1+···+k_m$ . But the global threshold is $k_m$ (If $k_j-k_{j-1}$ participants from the subsets ${\gamma }_j$ use their pseudo shares to recover the general term $h_i^{(j)}$ , then they must use their pseudo shares to recover the general terms $h_i^{(j+1)},...,h_i^{(m)}$ . For example, if $k_1$ participants from ${\gamma }_1$ use their pseudo shares to recover the general term $h_i^{(1)}$ , $k_1$ participants need to use their pseudo shares to recover the general terms from the second LHR sequences to the last LHR sequences. So the scheme needs at least $k_1+(k_2-k_1)+···+(k_m-k_{m-1})=k_m$ participants to recover the shared secrets). From $d_i=\mathrm{ke}{y}_i-h_{i-1}$ and the published value of $d_i$ , the shared secrets can be obtained by $\mathrm{ke}{y}_i=d_i+h_{i-1}$ , $1\le i\le l$ .

Remark 2

In the recovery stage, a participant $P_j$ can detect whether another participant $P_i$ is honest or not by the function $\hat{e}$ . If $\hat{e}(g,R_i^{\prime })=\hat{e}(B_0,B_i)$ , then the participant $P_j$ can say that the participant $P_i$ is honest, because $\hat{e}(g,R_i^{\prime })=\hat{e}(g,B_0{)}^{s_i}=\hat{e}(B_0,B_i)$ and $B_0,B_i$ are public.

Illustrative sample

We present an example to demonstrate the proposed scheme and show how the LHR relation is useful in the hierarchical access structures in this section. For illustration convenience, we suppose that in a company there are $n$ employees, and the employees are divided into two disjoint levels ${\gamma }_1,{\gamma }_2$ , the managers and the employees (the authorities of the managers are higher than the employees). There are $n_1$ managers in the subset ${\gamma }_1$ and $n_2$ employees in the subset ${\gamma }_2$ , where $n=n_1+n_2$ . At least $k_2$ staff of them can recover the shared secrets, among which at least $k_1$ are managers, where $k_2>k_1$ . We select two values ${\alpha }_1$ and ${\alpha }_2$ , and make

$$\begin{array}{c}{(x-{\alpha }_1)}^{k_1}=x^{k_1}+a_{11}{x}^{k_1-1}+···a_{1k_1}=0\hfill \\ {(x-{\alpha }_2)}^{k_2}=x^{k_2}+a_{21}{x}^{k_2-1}+···a_{2k_2}=0\hfill \end{array}$$

as two different auxiliary functions for the two different LHR relations. After the steps from 5 to 9.5 as described in the construction stage have been done (with $m$  = 2 here), we can have

$$h_i=h_i^{\left(1\right)}+h_i^{\left(2\right)}$$

where

$$\begin{array}{c}{h}_i^{\left(1\right)}=(b_1+b_{2}i+···+b_{k_1}{i}^{k_1-1}){\alpha }_1^i\hfill \\ h_i^{\left(2\right)}=(c_1+c_{2}i+···+c_{k_2}{i}^{k_2-1}){\alpha }_2^i\hfill \end{array}$$

We note that the distributor $D$ uses $n_1$ managers’ pseudo shares to generate the LHR sequence { $h_i^{(1)}$ } and $n_1+n_2$ staff members (include the managers and the employees) to generate the LHR sequence $\{h_i^{(2)}\}$ . That is, only at least $k_1$ managers can solve the general term $h_i^{(1)}$ of the sequence { $h_i^{(1)}$ }. Still, at least $k_2$ staff members can solve the general term $h_i^{(2)}$ of the sequence $\{h_i^{(2)}\}$ , where $k_1$ out of $k_2$ are managers (Because the privilege of the managers is higher than the employees, they should combine the pseudo shares to solve the second general term $h_i^{(2)}$ . If the employees are not enough, other managers except the $k_1$ can combine the employees to pool the pseudo shares to solve $h_i^{(2)}$ .) We hide the shared secrets in these terms $h_1,...,h_l$ .

From the above, we can get that our scheme’s global threshold is $k_2$ , because our scheme needs at least $k_2$ participants from ${\gamma }_1\bigcup {\gamma }_2$ to recover the shared secrets.

The security analysis and discussion of our scheme

In this section, we first present the possible attacks and prove that our scheme is secure. Then we show the performance of our scheme and compare it with the scheme by Traverso et al. ¹⁹

Security analysis

In this section, we call all of $s_i$ and $R_j$ share-related information, where $s_i$ is the shadow that is randomly selected by the participant or distributor himself or herself, $B_i=s_{i}g$ ( $B_i=s_{i}g$ is public), $R_j=s_0{B}_j$ and $0\le i\le n$ , $1\le j\le n$ . First, we prove the security of the share-related information. Second, we prove the security for the participants in the unqualified subset. The security of the share-related information is easy to be proved.

Theorem 3

The share-related information is secure, provided the CDH-assumption is intractable.

Proof of Theorem 3

If the adversaries want to break the share-related information, they should obtain useful information from the public values $B_i=s_{i}g$ , $0\le i\le n$ . We assume that the adversaries can break the share-related information with the non-negligible probability $ϵ$ . That is, given $s_{i}g$ and $s_{j}g$ , the adversaries can get $s_i{s}_{j}g$ or extract $s_i$ (or $s_j$ ) with the non-negligible probability $ϵ$ as well, where $i\ne j$ . This contradicts the Diffie–Hellman problem. The adversaries may give a fake $R{\prime }_i$ , but the other honest participants can decide whether $\hat{e}(g,R_i^{\prime })=\hat{e}(B_0,B_i)$ is right or not (because DDHP is easy in $G_1$ ). If it matches, then the other honest participants can say that the value $R{\prime }_i$ is valid. Otherwise, it is invalid. Thus, the share-related information is secure.

In the following section, we demonstrate why the proposed solution is safe for a subset of participants who do not qualify. When participants in the ineligible subset want to recover the secrets, they must recover every LHR sequence. For illustration convenience, we suppose that the unqualified subset $B$ satisfies the conditions as follows

1. $B\bigcap \left(\bigcup _{i=1}^{j-1}{\gamma }_i\right)\ge k_{j-1}$

2. $B\bigcap \left(\bigcup _{i=1}^j{\gamma }_i\right)=k_j-1$

3. $B\bigcap \left(\bigcup _{i=1}^t{\gamma }_i\right)\ge k_t$

where $1\le j\le m$ , $t\in \{1,2,...,m\}$ , $k_0=0$ and $t\ne j.$ That is to say, the unqualified subset can recover other $m-1$ sequences, except the jth LHR sequence. Since $s_i$ is chosen by himself/herself and $I_i^j=f(r_j,R_i)$ , we can say that each $I_i^j$ is uniformly chosen in ${\mathbb{Z}}_q^{*}$ , that is, for each $I_i^j$ , all values in ${\mathbb{Z}}_q^{*}$ have the same probability. From the public value ${\alpha }_j$ , the characteristic equation of an LHR relation can be determined, according to Theorem 1. If the relation of the sequences is given, the characteristic equation can be determined, and then the root of the characteristic equation can be found. Thus the public value ${\alpha }_i$ discloses no information apart from characteristic equation of an LHR relation, $1\le i\le m$ .

Theorem 4

The $k_j$ degree of the LHR relation is safe to the unqualified participants when and only when the polynomials with $(k_j-1)$ degree is safe to the unqualified participants. ²⁰

Proof of Theorem 4

Assume that the $k_j$ order of the LHR relation is safe to the unqualified participants. Using equations (4), (6) and (2) and the public value ${\alpha }_j\ne 0$ , we could obtain

$$h_i^{\left(j\right)}=p^j\left(i\right){\alpha }_j^i\Rightarrow h_i/{\alpha }_j^i=p^j\left(i\right)$$

(7)

in which the degree of $p^j(i)$ is $k_j-1$ . It is clear from the above that public value ${\alpha }_j$ gives away no information except characteristic equation. If the polynomial with degree $(k_j-1)$ is unsafe for unqualified participants, it means that the $k_j-1$ points can determine a polynomial with degree $(k_j-1)$ . We can also deduce from equation (7) that the $k_j-1$ value can obtain the LHR relation with the degree $k_j$ . This is contradicted with Proposition 1.

(⇐) Assume that the polynomial with the degree $(k_j-1)$ is safe for the unqualified participants. If the LHR relation with degree $k_j$ is insecure, then $k_j-1$ random terms ( $h_{i_1}^{(j)},h_{i_2}^{(j)},...,h_{i_{k_j-1}}^{(j)}$ ) can determine the LHR sequences. Following equation (7), we select the distinct $k_j-1$ terms and then can obtain the $k_j-1$ points of the polynomial $p^j(i)$ with degree $k_j-1$ . Then we can determine the polynomial $p^j(i)$ . It can be said that the $k_j-1$ points could decide a polynomial with degree $(k_j-1)$ . This contradicts our assumptions. Therefore, the question of recovering the jth LHR relation from participants in the disqualified subset $B$ that satisfies the aforementioned condition could be regarded as the question of whether $k_j-1$ points could decide the polynomial with the degree $(k_j-1)$ .

We can draw the conclusion that the possibility of cracking our scheme is no better than the possibility of cracking the Diffie–Hellman problem. Therefore, it can be considered that our scheme is safe.

Performances

From the section ‘The proposed scheme’ and the security analysis above, we conclude that the proposed scheme is a secure and verifiable hierarchical secret sharing scheme. In this section, we show some essential characteristics. In the proposed scheme, each participant’s ID is posted on a publicly available message board, and each participant’s shadow is selected by himself/herself over $\mathrm{GF}(q)$ . Each participant can verify whether the pseudo-random shares of other participants are correct. Throughout the entire process, each participant only needs to hold one shadow, and the shared secrets are selected over $\mathrm{GF}(q)$ . So the shadow held by a participant is as long as the shared secret.

Each participant obtain $k_m-1$ pseudo-random shares from the other participants, and each participant’s communication and computation is the same (Since $k_m$ participants are required to recover the secrets, each participant needs to communicate with $k_m-1$ participants, so the times of the communication for each participant is $k_m-1$ ). The computation refers to recovering the secrets with the obtained pseudo-random shares (including their own and those obtained by exchanging with other participants). In the recovery stage, from equation (6), we know that computational complexity of our scheme depends on the degree of polynomial $p^m(x)$ (because the degree of the polynomial $p^m(x)$ is highest among these polynomials $p^i(x)$ , where $1\le i\le m$ ) and the power of a constant ${\alpha }_m$ . The computational complexity of the polynomial $p^m(x)$ is $O(n^{k_m-1})$ and the computational complexity of the power of a constant is $O(\mathrm{logn})$ . So the computational complexity of our scheme is $O(n^{k_m-1}\mathrm{logn})$ .

In the case when the system needs to be reinitialized with the LHR relations, our scheme only needs to provide the new values $r_1^{\prime },r_2^{\prime },...,r_m^{\prime }$ without changing participants’ shadows. It is possible to obtain a further $I_i=f(r_j^{\prime },R_i)$ while not modifying the shadows.

Comparisons

In the solution by Traverso et al., ¹⁹ when allocating identities and shares to participants, the distributor must perform a potentially exponential number of checks. In our scheme, participants do not have to check the non-regularity of many matrices. They just need to construct $m$ different LHR relations, find the general terms of them and add these terms. More precisely, we can conclude that the participants only need to do the evaluation calculation of polynomials and the summation calculation of different polynomials in our scheme by induction. The computational complexity of the polynomial is $O(n^{k_m-1})$ and the computational complexity of the power of a constant is $O(\mathrm{logn})$ . So the computational complexity of our scheme is $O(n^{k_m-1}\mathrm{logn})$ as given in the study by Yuan et al. ²¹ But more values should be published. So comparing to Traverso’s et al. ¹⁹ scheme, our scheme is more efficient.

Conclusion

We present a hierarchical secret sharing scheme with the LHR relations and the ECC. The performance of the proposed method is also listed below. The LHR relations could be utilized for constructing a verifiable hierarchical secret sharing scheme. The participants’ shadows are selected by themselves in the proposed scheme. Therefore, no deception exists between the distributor of the shared secrets and the participants. In the whole scheme, only one shadow is held by one participant, and the secret is the same length as the shadow. The proposed scheme is not required to keep a safe channel between the distributor and the participant. The participants cannot cheat each other.

Our scheme overcomes the drawbacks that the distributor will have to do potentially exponential multiple checks for distributing identifications and shadows to participants on the basis of Birkhoff interpolation. But our scheme needs more public values than the existing popular schemes.