Secret sharing schemes for compartmented access structures

Abstract

In this paper, we devise ideal and probabilistic secret sharing schemes for two kinds of compartmented access structures. The first one is a compartmented access structures with hierarchical compartments. The second one is the compartmented access structures with strictly lower bounds. We propose ideal and probabilistic schemes for these two compartmented access structures by using the idea of bivariate interpolation.

1 Introduction

Secret sharing schemes (SSSs) were introduced independently by Shamir [13] and Blakley [1]. A secret sharing scheme (SSS) is a method that a dealer distributes shares of a secret to participants such that only authorized subsets of participants can recover the secret from their shares. Shamir’s scheme is called (t,n)threshold SSS. In the scheme, the authorized set is the set that contains t or more participants. The threshold scheme was generalized to ones with access structure (AS). Although there exists a linear SSS for every AS [4, 11], but the known general constructions are impractical because the size of the shares is exponential. Since the seminal work of Shamir, many applications of SSS to several different kinds of cryptographic protocols have appeared. For instance, SSS can be used in multiparty computation and secure key management schemes. The relation between SSS and linear code has also been studied for a long time(set [5–8] for example). SSS plays an important role in cryptography. So, it is interesting to devise efficient and practical schemes for different kinds of access structures. For further introductions to secret sharing, the interested readers can refer to [3, 15] and the references therein. The definitions of the ASs appeared in this section will be given in Section 2.

We focused on compartmented AS in this work. Let us suppose the ASs are monotone throughout this paper, some results of the general non-monotone AS can be found in [12]. Compartmented AS was introduced by Simmons [14]. After that, Brickell [2] gave a more general family, that is the so-called compartmented access structure with lower bounds (LCAS) in [16]. There is an efficient and probabilistic SSS for the AS [20]. Recently, Farràs et al. [9, 10] characterized some new ideal compartmented ASs, such as the compartmented access structure with upper and lower bounds and the compartmented access structures with hierarchical compartments (CASHC). Some SSS for certain compartmented AS can be found in [19]. Following the work of Farràs et al. [9], Wang et al. [18] presented the compartmented access structures with strictly lower bounds (SLCAS). The new AS can provide better fairness among the groups in recovering the secret. However, both Farràs [9] and Wang [18] didn’t give efficient, ideal and perfect SSSs for these ASs, as by far there is not an efficient algorithm to obtain a representation of a multipartite matroid from a representation of its associated integer polymatroid.

In this paper, we give a perfect (with probability) and ideal SSS for one of the CASHC which were introduced in [9]. Then, we construct a SSS for the SLCAS which was given in [18]. As far as we know, there does not exist any efficient, ideal and perfect schemes for these ASs. Although our schemes are probabilistic, they are simple and easy understanding for the purpose of practical applications.

2 Preliminaries

2.1 Secret sharing

In a secret sharing scheme, let $\mathcal {P}=\{p_{1},\cdots ,p_{n}\}$ be the set of participants. An access structure (AS) is a monotone collection ${\Gamma } \subseteq 2^{\mathcal {P}}$: we have C∈Γ if B∈Γ and $B \subseteq C$. The notation $2^{\mathcal {P}}$ is the power set of $\mathcal {P}$. Sets in Γ are called authorized or qualified, and sets not in Γ are called unauthorized or unqualified. B is called a minimal qualified set, if B∈ Γ and for any $C\subsetneq B$ imply that C∉ Γ. Γ can be determined by all the minimal qualified sets [15]. We let ${\Delta }=2^{\mathcal {P}}\setminus {\Gamma }$, Δ is called an adversary structure which is the set of all unauthorized sets. $B\subseteq \mathcal {P}$ is called a maximal unqualified set, if B is an unqualified set and any superset of B is a qualified set. Δ can be determined by all the maximal unqualified sets [15].

A SSS requires that the participants of qualified set can recover the secret, and the participants from unqualified set cannot get the secret. Furthermore, if participants from unauthorized set cannot get any information of the secret in the information theoretic sense, then such SSS is called perfect. A SSS is called ideal if |S _i |=|S| for every 1≤i≤n, where S is the domain of the secret s, and S _i is the share domain of participant i. An AS is called ideal if there exists an ideal SSS realizing it. A SSS is called linear if the secret s is a linear combination of participants’ shares that from qualified set. We define the probabilistic secret sharing scheme as in [20]. That is, although V∈Γ, sometimes the participants in V cannot recover the secret either, but that is only a small probability event.

2.2 Compartmented access structure

Every participant in threshold access structure has the same effect when recovering the secret. We can generalize threshold AS like this: we divide $\mathcal {P}$ into several disjoint groups, and every group has its own threshold value. The participants in the same group have the same power just like that in threshold AS. AS like this are called compartmented AS.

Farràs et al. [9] found some new ideal compartmented ASs, one of them is the compartmented access structure with hierarchical compartments (CASHC). The definition of the CASHC is given as follows. Through this paper, we use [m] denotes the set {1,2,⋯ ,m}. For a set $\mathcal {S}$, $b\in _{R}\mathcal {S}$ denotes that the element b was selected randomly from the set $\mathcal {S}$.

Definition 1

Let $\mathcal {P}=\bigcup \limits _{i=1}^{m} \mathcal {U}_{i}$, where $\mathcal {U}_{i}\cap \mathcal {U}_{j}=\emptyset$, for i≠j. Furthermore, let $\mathcal {U}_{i}=\bigcup \limits _{j=1}^{n}\mathcal {U}_{ij}$, where $\mathcal {U}_{ik}\cap \mathcal {U}_{il}=\emptyset$, for k≠l. Let t and b _i,n ≥b _i,n−1≥⋯≥b _i,1 (1≤i≤m) be integers such that $\sum \limits _{i=1}^{m}b_{i,n}\geq t+m-1$. Then the CASHC is

$${\Gamma}_{1}=\left\{ V\subseteq \mathcal{P}:\ |V|\geq t,\ or\ \exists\ i\in[m],\ \exists\ k\in[n]\ s.t.\ \left|V\cap \bigcup\limits_{j=1}^{k} \mathcal{U}_{ij}\right|\geq b_{i,k} \right\}. $$

In the CASHC, we require the qualified set V at least has cardinality of t, or the qualified set must contain b _{i k} participants that come from the first k subgroups in group $\mathcal {U}_{i}$, for some i∈[m] and k∈[n]. The notation ∃ in Γ₁ means that once 1 of m groups and 1 of n subgroups satisfy the condition, then they can recover the secret. For every group $\mathcal {U}_{i}$, i∈[m], there is a hierarchy among the subgroups $\mathcal {U}_{ij}$, 1≤j≤n. When recovering the secret, participants from the subgroup $\mathcal {U}_{il}$ can replace the participants from $\mathcal {U}_{ik}$, for 1≤l<k≤n. The hierarchical structure among every group is analogous to the disjunctive hierarchical AS in [17]. We will construct a SSS for the CASHC in Section 3.

Wang et al. [18] presented a new ideal compartmented AS, which is called compartmented access structure with strictly lower bounds (SLCAS). We give its definition here.

Definition 2

Let $\mathcal {P}=\bigcup \limits _{i=1}^{m} \mathcal {U}_{i}$, where $\mathcal {U}_{i}\cap \mathcal {U}_{j}=\emptyset$, for i≠j. Let t, t _i , (1≤i≤m), k be integers satisfy $t\geq \sum \limits _{i=1}^{m}t_{i}$ and $1\leq k\leq \min \{m,t-\sum \limits _{i=1}^{m}t_{i}\}$. Then the SLCAS is

$${\Gamma}_{2}=\left\{V\subseteq \mathcal{P}:\ |V|\geq t,\ |V\cap \mathcal{U}_{i}|\geq t_{i}, for\ \forall\ i\in [m],\ and \left|\{i:\ |V\cap \mathcal{U}_{i}|>t_{i}\}\right|\geq k\right\}. $$

If we delete the condition $\left |\{i:\ |V\cap \mathcal {U}_{i}|>t_{i}\}\right |\geq k$ in Γ₂, then the AS becomes the compartmented access structure with lower bounds (LCAS) in [9, 16]. AS stated in [18], although LCAS can be used to protect the rights of some ’weak’ groups, one or few groups can still dominate the reconstruction. For instance, if $t\gg {\sum }_{i=1}^{m}t_{i}$ (the notation A≫B means that A much larger than B) and $|\mathcal {U}_{m}|$ is large enough, then $t-{\sum }_{i=1}^{m-1}t_{i}$ participants in $|\mathcal {U}_{m}|$ can partaking the recover phase. In this case, $|\mathcal {U}_{m}|$ performs a more powerful role than the other groups and dominate the reconstructing procedure. But, the SLCAS can provide better fairness among groups, as it requires that at least k groups of participants are strictly greater than the lower bounds t _i . We will propose a SSS for the SLCAS in Section 4.

We introduce a lemma, which provides an upper bound for the number of zeros of a multivariate polynomial over a finite field. The lemma is necessary for our proofs in the following sections.

Lemma 1

(Schwartz-Zippel Lemma) [16] Let G(z ₁ ,z ₂ ,⋯ ,z _k ) be a nonzero polynomial of k variables over a finite field $\mathbb {F}$ of size q. Assume that the highest degree of each of the variables z _j in G is not larger than d. Then the number of zeros of G in $\mathbb {F}^{k}$ is bounded from above by kdq ^k−1.

3 Secret sharing scheme for CASHC

In this section, we design a simple, ideal and perfect (with probability) scheme for Γ₁. Our method is the bivariate interpolation which was introduced in [16]. Our SSS implementing Γ₁ is the Secret Sharing Scheme 1.

Let $\mathbb {F}_{q}$ be a finite field and $s\in \mathbb {F}_{q}$ be the secret to be shared. Set p _i,1(x)=s+a _i,1 x+⋯+a _{i,b i,1 −1} x ^b _i,1−1, and p _i,j (x)=p _i,j−1(x)+a _{i,b i,j−1} x ^b _i,j−1 + ⋯ + a _{i,b i,j−1} x ^b _i,j−1 for 2≤j≤n, 1≤i≤m, where $a_{i,k}\in _{R} \mathbb {F}_{q}$, 1≤k≤b _i,n −1.

Let $y_{i}\in _{R}\mathbb {F}_{q},\ 1\leq i\leq m$, be m distinct elements. Put $L_{i}(y)=\prod \limits _{1\leq j\leq m,j\neq i}\frac {y-y_{j}}{y_{i}-y_{j}}$, 1≤i≤m. We set $p(x,y)=\sum \limits _{i=1}^{m}p_{i,n}(x)L_{i}(y)$. Let $b_{0}={\sum }_{i=1}^{m}b_{i,n}-m+1$ and γ=b ₀−t. Then our SSS for CASHC is as follows.

Secret Sharing Scheme 1

• (1) For the participant u _{i j k} from $\mathcal {U}_{ij}$, his identity is $x_{ijk}\in _{R}\mathbb {F}_{q}$, x _{i j k} ≠x _{r s t} for (i,j,k)≠(r,s,t). The dealer sends p _i,j (x _{i j k} ) to u _{i j k} secretly as his share.

• (2) The dealer publishes the values of p(x,y) at γ distinct points $(z_{i},y_{i}^{\prime })\in _{R}\mathbb {F}_{q}^{2}$, where $y_{i}^{\prime }\in \{y_{1},y_{2},\cdots ,y_{m}\}$, 1≤i≤γ.

We explain the idea of the scheme here. The qualified set V must satisfy $|V\cap \bigcup _{j=1}^{k} \mathcal {U}_{ij}|\geq b_{i,k}$ for some i∈[m], k∈[n], the threshold in this case just like that in Shamir scheme. So we use a polynomial of degree b _i,j −1 to distribute the share for participants in $\mathcal {U}_{ij}$, the constant term of the polynomial is the secret. Moreover, the AS requires that participants from $\mathcal {U}_{ij}$ can replace the participants from $\mathcal {U}_{ik}$, (j<k), so we set p _i,j (x) as a part of p _i,k (x). To ensure that the participant set V with |V|≥t, can recover the secret, we publish b ₀−t values of the p(x,y). The total unknown coefficients in p(x,y) is b ₀, so V can get the secret by solving a linear equation system. We will analyze the security of the scheme in Theorem 1.

Now, we give an example of this scheme in our real life. Suppose the n participants belong to an organization. The organization have m groups. In every group, some people has more power than others, and there is n levels of power. When a signature requested, t of n participants can make a signature. Moreover, every group that contains certain number of members can represent the organization to make the signature, and members from superior level of power can replace the members from inferior level to make the signature. Our proposed scheme can be used in this example.

We consider the adversary structure Δ₁ which is the adversary structure of Γ₁. We have

$${\Delta}_{1}=\left\{V\subseteq P:\ |V|<t,\ and\ \left|V\cap \bigcup\limits_{j=1}^{k} \mathcal{U}_{ij} \right|<b_{ik}\ for\ \forall\ i\in[m],k\in[n]\right\}. $$

Theorem 1

If V∈Γ ₁ , the participants in V can recover the secret s with probability 1−C ₁ /q, where the constant C ₁ depends on b _i,j ,t and m. If V∉Γ, V cannot get any information about the secret with probability 1−C ₂ /q, where the constant C ₂ depends on b _i,j ,t and m.

Proof

We prove the first part of the theorem firstly. We just need to consider the minimal qualified set, this is |V|=t or $|V\cap \bigcup _{j=1}^{k}\mathcal {U}_{ij}|=b_{ik}$ for some i∈[m] and k∈[n].

• Case 1: |V|=t.

In this case, let $|V\cap \mathcal {U}_{i}|=s_{i}$, 1≤i≤m, obviously, ${\sum }_{i=1}^{m}s_{i}=t$. The participants in V can get the linear equation system

$$ \textbf{MX}=\textbf{F}, $$

(1)

where X=(s,a _1,1,a _1,2,⋯ ,a _{1,b 1,n} −1⋯ ,a _m,1,⋯ ,a _{m,b m,n−1}), F is the vector composed of their corresponding shares, and

$$\textbf{M}=\left(\begin{array}{ccccc} \textbf{1}_{s_{1}} & \textbf{M}_{1} & & & \\ \textbf{1}_{s_{2}} & & \textbf{M}_{2} & & \\ {\vdots} & & {\vdots} & & \\ \textbf{1}_{s_{m}}& & & & \textbf{M}_{m} \\ \textbf{L}_{\gamma}&{H}_{1} & \textbf{H}_{2} & {\cdots} &\textbf{H}_{m} \end{array}\right)_{b_{0}\times b_{0}}. $$

The matrices $\textbf {1}_{s_{i}}$, M _i and H _i are as follows.

$$\textbf{1}_{s_{i}}=\left(\begin{array}{l} 1\\ 1\\ \vdots\\ 1 \end{array}\right)_{s_{i}\times 1},\ \textbf{M}_{i}=\left(\begin{array}{cccc} x_{i1} & x_{i1}^{2} & {\cdots} & x_{i1}^{b_{i,n}-1}\\ {\vdots} & {\vdots} & & \vdots\\ x_{is_{i}} & x_{is_{i}}^{2} &{\cdots} & x_{i,s_{i}}^{b_{i,n}-1} \end{array}\right)_{s_{i}\times (b_{i,n}-1)}, \ 1\leq i\leq m. $$

$$\textbf{L}_{\gamma}=\left(\begin{array}{cc} {\sum}_{i=1}^{m} L_{i}(y_{i}^{\prime})\\ {\sum}_{i=1}^{m} L_{i}(y_{i}^{\prime})\\ \vdots\\ {\sum}_{i=1}^{m} L_{i}(y_{i}^{\prime}) \end{array}\right)_{\gamma\times 1},\ \textbf{H}_{i}=\left(\begin{array}{cccc} L_{i}(y_{i}^{\prime})z_{1} & L_{i}(y_{i}^{\prime}){z_{1}^{2}} & {\cdots} & L_{i}(y_{i}^{\prime})z_{1}^{b_{1,n}-1}\\ {\vdots} & {\vdots} & & \vdots\\ L_{i}(y_{i}^{\prime})z_{\gamma} & L_{i}(y_{i}^{\prime})z_{\gamma}^{2} &{\cdots} & L_{i}(y_{i}^{\prime})z_{\gamma}^{b_{1,n}-1} \end{array}\right)_{\gamma\times (b_{i,n}-1)}, $$

for 1≤i≤m. The equation system has t+γ=b ₀ equations and b ₀ variables. We only need to prove the event that |M| =0 happens with a negligible probability, where the notation |M| denotes the determine of M. We view the determine of M as a γ-variate polynomial g(z ₁,z ₂,⋯ ,z _γ ). There are two cases as follows: the case where g(z ₁,z ₂,⋯ ,z _γ ) is identically zero and the case that is not. We consider the case g(z ₁,z ₂,⋯ ,z _γ ) is not identically zero firstly. According to the lemma 1, the number of zero of g(z ₁,z ₂,⋯ ,z _γ ) in $\mathbb {F}_{q}^{\gamma }$ is bounded by γ(b−1)q ^γ−1, where $b=\max \limits _{1\leq i\leq m}b_{i,n}$. Since z _i were randomly selected from $\mathbb {F}_{q}$, the probability of (z ₁,z ₂,⋯ ,z _γ ) being one of the zero of g(z ₁,z ₂,⋯ ,z _γ ) is bounded from above by γ(b−1)/q. We consider the case g(z ₁,z ₂,⋯ ,z _γ )≡0. g(z ₁,z ₂,⋯ ,z _γ )≡0 if and only if all of its coefficients are zero, where each of the coefficients is a polynomial in b ₀ variables whose degree with respect to each of its variables is bounded by $d=\max \{b-1,m-1\}$. So, the probability of one of the coefficient to be zero is b ₀ d/q. Then the probability of g(z ₁,z ₂,⋯ ,z _γ )≡0 is C/q, where the constant C depends on b _i,n ,m and t.

• Case 2: ∃i∈[m],k∈[n] s.t. $\left |V\cap \bigcup _{j=1}^{k} \mathcal {U}_{ij}\right |=b_{i,k}$.

Let $|V\cap \mathcal {U}_{ij}|=\alpha _{ij}$, ${\sum }_{j=1}^{k}\alpha _{ij}=b_{i,k}$. In this case, V can construct the following equation:

$$\textbf{MX}=\textbf{F}, $$

where X=(s,a _i,1,a _i,2,⋯ ,a _{i,b i,k−1}), F is the share vector, and

$$\textbf{M}=\left(\begin{array}{ccccc} \textbf{1}_{\alpha_{i1}} & \textbf{M}_{1} & & & \\ \textbf{1}_{\alpha_{i2}} & & \textbf{M}_{2} & & \\ {\vdots} & & {\vdots} & & \\ \textbf{1}_{\alpha_{ik}} & & & & \textbf{M}_{k} \end{array}\right)_{b_{i,k}\times b_{i,k}}. $$

Here the matrices $\textbf {1}_{\alpha _{il}}$ and M _l are as follows:

$$\textbf{1}_{\alpha_{il}}=\left(\begin{array}{l} 1\\ 1\\ \vdots\\ 1 \end{array}\right)_{\alpha_{il}\times 1},\ \textbf{M}_{l}=\left(\begin{array}{cccc} x_{ij1}^{b_{i,j-1}} & x_{ij1}^{b_{i,j-1}+1} & {\cdots} & x_{ij1}^{b_{i,j}-1}\\ {\vdots} & {\vdots} & & \vdots\\ x_{ij\alpha_{ij}}^{b_{i,j-1}} & x_{ij\alpha_{ij}}^{b_{i,j-1}+1} & {\cdots} & x_{ij\alpha_{ij}}^{b_{i,j}-1} \end{array}\right)_{\alpha_{ij}\times (b_{i,j}-b_{i,j-1})}, $$

where b _i,0=1 and 1≤l≤k. Just like the analysis in Case 1, we can get the result that the probability of |M|=0 is b _i,k (b _i,k −1)/q. Up to now, we have proved that the qualified set V can reconstruct the secret with probability 1−C ₁/q, where the constant C ₁ depends on b _i,j ,t and m.

Next, we prove the second part of this theorem. Let V be the maximal unqualified set, that is, |V|=t−1 and $|V\cap \bigcup _{j=1}^{k}\mathcal {U}_{ij}|=b_{i,k}-1$ for every i∈[m] and k∈[n]. For any i∈[m] and k∈[n], the participants in V only can construct the linear equation system M _i X=F, where X=(s,a _i,1,a _i,2,⋯ ,a _{i,b i,k−1}), F is the vector of shares, and

$$\textbf{M}_{i}=\left(\begin{array}{ccccc} 1 & x_{i1} & x_{i1}^{2} &{\cdots} &x_{i1}^{b_{i,k}-1}\\ & & {\vdots} & & \\ 1 & x_{ib_{i,k}-1} & x_{ib_{i,k}-1}^{2} &{\cdots} &x_{ib_{i,k}-1}^{b_{i,k}-1} \end{array}\right)_{(b_{i,k}-1)\times b_{i,k}}. $$

We need to show that the vector e ₁=(1,0,⋯ ,0) is most probably not spanned by the rows of M _i . In other words, we need to prove that the vector e ₁=(1,0,⋯ ,0) cannot be spanned by the rows of M _i with probability close to 1, where the probability is calculated over all the possible M _i in the finite field. Let $\textbf {M}_{i}^{\prime }=\binom {\textbf {e}_{1}}{\textbf {M}_{i}}$, we claim that the probability of $|\textbf {M}_{i}^{\prime }|=0$ is (b _i,k −1)²/q. The proof is similar to that in the first part of the theorem. Moreover, if the participants in V use the public γ points of p(x,y), they can construct b ₀−1 linear equations with respect to b ₀ variables. By the same method, we can conclude that V cannot get any information about the secret with probability 1−C ₂/q, where the constant C ₂ depends on b _i,j ,t and m. □

4 Secret sharing schemes for SLCAS

In this section, we consider the SSS for Γ₂. Our SSS for this AS is the Secret Sharing Scheme 2. The SSS can be seen as the generalization of the scheme for LCAS in [20].

Secret Sharing Scheme 2

• (1) Let $s\in \mathbb {F}_{q}$ be the secret, $x_{i}\in \mathbb {F}_{q}$, 1≤i≤m, are distinct nonzero element. Let $f(x)={\sum }_{i=0}^{k-1}a_{i}x^{i}$, $p_{i}(y)={\sum }_{j=0}^{t_{i}}b_{i,j}y^{j}$ and $R(z)={\sum }_{i=1}^{l}c_{i}z^{i}$, where $a_{i}\in _{R}\mathbb {F}_{q},b_{i,j}\in _{R}\mathbb {F}_{q}$ and $c_{i}\in _{R}\mathbb {F}_{q}$ such that $s=a_{0}+c_{1}+{\sum }_{i=1}^{m}b_{i,1}$. Moreover, b _i,0=f(x _i ), 1≤i≤m, and $l=t-{\sum }_{i=1}^{m}t_{i}-k$. Put Q _i (y,z)=p _i (y)+R(z).

• (2) Participant u _{i j} from $\mathcal {U}_{ij}$, uniquely identified by (x _i ,y _{i j} ,z _{i j} ), $y_{ij},z_{ij}\in \mathbb {F}_{q}$. The dealer sends Q _i (y _{i j} ,z _{i j} ) to u _{i j} as his share.

The adversary structure Δ₂ of Γ₂ is as follows.

$${\Delta}_{2}=\{V\subseteq P: |V|\leq t-1,\ or\ \exists i\in [m],s.t.\ |V\cap \mathcal{U}_{i}|\leq t_{i}-1, $$

$$\ or\ \left|\{i:\ |V\cap \mathcal{U}_{i}|>t_{i}\}\right|\leq k-1\}. $$

We discuss the security of the scheme for Γ₂ in the following Theorem 2.

Theorem 2

If V∈Γ ₂ , the participants in V can recover the secret with probability 1−C ₃ /q, where the constant C ₃ depends on k,t and t _i . If V∉Γ ₂ , V cannot get any information about the secret with probability 1−C ₄ /q, where the constant C ₄ depends on t,t _i and k.

Proof

Suppose that V is a minimal qualified set, i.e. that is |V|=t and $|V \cap \mathcal {U}_{i}|=s_{i}\geq t_{i}$ for any i∈[m], ${\sum }_{i=1}^{m}s_{i}=t$, and $\left |\{i:\ |V\cap \mathcal {U}_{i}|>t_{i}\}\right |= k$. The participants in V can construct the linear equation system: MX=F, where X=(a ₀,a ₁,⋯ ,a _k−1,b _1,1,⋯ ,b _1,tt>k−1,b _1,1,⋯ ,b _m,1,⋯ ,b _{m,t m} ,c ₁,⋯ ,c _l ), F is the vector of shares, and

$$\textbf{M}=\left(\begin{array}{llllll} \textbf{W}_{1} &{M}_{1}& & & &\textbf{N}_{1}\\ \textbf{W}_{2} & &{M}_{2} & & &\textbf{N}_{2}\\ & & & {\vdots} & & \\ \textbf{W}_{m} & & & &{M}_{m} & \textbf{N}_{m} \end{array}\right)_{t\times t}, $$

with

$$\textbf{W}_{i}=\left(\begin{array}{cccc} 1 & x_{i} &{\cdots} &x_{i}^{k-1}\\ 1 & x_{i} &{\cdots} &x_{i}^{k-1}\\ & & {\vdots} & \\ 1 & x_{i} &{\cdots} &x_{i}^{k-1} \end{array}\right)_{s_{i}\times k}, \textbf{M}_{i}=\left(\begin{array}{cccc} y_{i1} & y_{i1}^{2} &{\cdots} &y_{i1}^{t_{i}}\\ y_{i2} & y_{i2}^{2} &{\cdots} &y_{i2}^{t_{i}}\\ & & {\vdots} & \\ y_{is_{i}} & y_{is_{i}}^{2} &{\cdots} &y_{is_{i}}^{t_{i}} \end{array}\right), \textbf{N}_{i}=\left(\begin{array}{cccc} z_{i1} & z_{i1}^{2} &{\cdots} &z_{i1}^{l}\\ z_{i2} & z_{i2}^{2} &{\cdots} &z_{i2}^{l}\\ & & {\vdots} & \\ z_{is_{i}} & z_{is_{i}}^{2} &{\cdots} &z_{is_{i}}^{l} \end{array}\right), $$

for each 1≤i≤m. By the same method used in Theorem 1, we can prove that the probability of |M|=0 is C ₃/q, where C ₃ depends on k,t and t _i . So V can get the secret with probability 1−C ₃/q.

Now, we prove the second part of the theorem. Assuming that V is a maximal unqualified set, let $A\triangleq \{i:\ |V\cap \mathcal {U}_{i}|>t_{i}\}$, then there are three cases:

• Case 1: |V|=t−1, $|V\cap \mathcal {U}_{i}|\geq t_{i}$, ∀i∈[m] and |A|≥k.

The participants in V can construct t−1 equations with respect to t variables. We can conclude that V cannot get any information about the secret with probability 1−C ₄/q, where the constant C ₄ depends on t,t _i ,k. The proof goes along the sam line of arguments as in the proof of Theorem 1.

• Case 2: $\exists i\in [m],\ s.t. \ |V\cap \mathcal {U}_{i}|=t_{i}-1$ and $|V\cap \mathcal {U}_{j}|=|\mathcal {U}_{j}|$, for j≠i.

In this case, the participants in V cannot recover b _i,1, as they only can construct the linear equation system M _i X=F that involving b _i,1, where X=(b _i,1,b _i,2,⋯ ,b _{i,t i} ), F=(Q _i (y _i,1,z _i,1)−R(z _i,1)−f(x _i ),⋯ , Q _i (y _{i,t i−1},z _{i,t i−1})−R(z _{i,t i−1})−f(x _i )) and

$$\textbf{M}_{i}=\left(\begin{array}{cccc} y_{i,1} & y_{i,1}^{2} &{\cdots} &y_{i,1}^{t_{i}}\\ y_{i,2} & y_{i,2}^{2} &{\cdots} &y_{i,2}^{t_{i}}\\ & & {\vdots} & \\ y_{i,t_{i}-1} & y_{i,t_{i}-1}^{2} &{\cdots} &y_{i,t_{i}-1}^{t_{i}} \end{array}\right)_{t_{i}-1\times t_{i}}. $$

Participants from $V\cap \mathcal {U}_{j}$ with j≠i, have no contributions to the recovery of the b _i,1. So V cannot get any information about the secret from the security of Shamir scheme.

• Case 3: |A|=k−1, $|V\cap \mathcal {U}_{j}|=t_{j}$ for j∉A, and $|V\cap \mathcal {U}_{j}|=|\mathcal {U}_{j}|$ for j∈A.

The participants of V can reconstruct b _i,0 only when $|V\cap \mathcal {U}_{i}|>t_{i}$. Since b _i,0=f(x _i ) and d e g(f)=k−1, the participants can recover a ₀ only when they have k distinct values f(x _i ). That is to say, they can recover a ₀ only when |A|≥k. So V cannot get any information about the secret in this case. □

Next, we give an example of Γ₂ and use our Secret Sharing Scheme 2 to realize it.

Example 1

Let $\mathcal {P}=\bigcup _{i=1}^{3}\mathcal {U}_{i}$, $\mathcal {U}_{i}\cap \mathcal {U}_{j}=\emptyset$ for i≠j. Suppose that m=3,t ₁=2,t ₂=3,t ₃=3,t=12,and k=2. We have the access structure ${\Gamma }=\{V\subseteq \mathcal {P}: |V|\geq 12,\ |V\cap \mathcal {U}_{i}|\geq t_{i},\ for\ \forall i\in [3],\ |\{i:|V\cap \mathcal {U}_{i}|>t_{i}\}|\geq 2\}$. Let $s\in \mathbb {F}_{q}$ be the secret, we design SSS for the Γ as follows:

Let f(x)=a ₀+a ₁ x, p ₁(y)=b _1,0+b _1,1 y+b _1,2 y ², p ₂(y)=b _2,0+b _2,1 y+b _2,2 y ²+b _2,3 y ³, p ₃(y)=b _3,0+b _3,1 y+b _3,2 y ²+b _3,3 y ³, R(z)=c ₁ z+c ₂ z ². The coefficients a ₀,a ₁,c ₁,c ₂,b _i,j , 1≤i≤3, 1≤j≤t _i , were selected randomly from $\mathbb {F}_{q}$ such that s=c ₁+a ₀+b _1,1+b _2,1+b _3,1. Moreover, b _i,0=f(x _i ), 1≤i≤3, where $x_{i}\in _{R}\mathbb {F}_{q}$. Put Q _i (y,z)=p _i (y)+R(z), 1≤i≤3.

The participant u _i,j in $\mathcal {U}_{i}$ is uniquely identified by (x _i ,y _i,j ,z _i,j ), where $y_{i,j},z_{i,j}\in _{R}\mathbb {F}_{q}$. The dealer send Q _i (y _i,j ,z _i,j ) to u _i,j as his share. We discuss the security of the above scheme in the following cases.

Let $V\subseteq \mathcal {P}$, V=12, $|V\cap \mathcal {U}_{1}|=2$, $|V\cap \mathcal {U}_{2}|=5$ and $|V\cap \mathcal {U}_{3}|=5$. V is a minimal qualified set. The participants in V can construct the equation MX=F, where X=(a ₀,a ₁,b _1,1,b _1,2,b _2,1,b _2,2,b _2,3,b _3,1,b _3,2,b _3,3,c ₁,c ₂), F=(Q ₁(y _1,1,z _1,1),Q ₁(y _1,2,z _1,2),Q ₂(y _2,1,z _2,1),⋯ ,Q ₂(y _2,5,z _2,5),Q ₃(y _3,1,z _3,1), ⋯ ,Q ₃(y _3,5,z _3,5)), and

$$\textbf{M}=\left(\begin{array}{cccccccccccc} 1 & x_{1} & y_{1,1}& y_{1,1}^{2} & & & & & & & z_{1,1}& z_{1,1}^{2}\\ 1&x_{1}&y_{1,2}&y_{1,2}^{2}& & & & & & &z_{1,2}& z_{1,2}^{2}\\ 1&x_{2}& & &y_{2,1} &y_{2,1}^{2} &y_{2,1}^{3} & & & &z_{2,1}& z_{2,1}^{2}\\ 1&x_{2}& & &y_{2,2} &y_{2,2}^{2} &y_{2,2}^{3} & & & &z_{2,2}& z_{2,2}^{2}\\ & \vdots& &{\vdots} & &{\vdots} & & & & & \vdots& \\ 1&x_{2}& & &y_{2,5} &y_{2,5}^{2} &y_{2,5}^{3} & & & &z_{2,5}& z_{2,5}^{2}\\ 1&x_{3}& & & & & &y_{3,1} &y_{3,1}^{2} &y_{3,1}^{3}&z_{3,1}&z_{3,1}^{2} \\ 1&x_{3}& & & & & &y_{3,2} &y_{3,2}^{2} &y_{3,2}^{3}&z_{3,2}&z_{3,2}^{2} \\ & \vdots& &{\vdots} & &{\vdots} & & & & & \vdots& \\ 1&x_{3}& & & & & &y_{3,5} &y_{3,5}^{2} &y_{3,5}^{3}&z_{3,5}&z_{3,5}^{2} \end{array}\right)_{12\times 12} $$

So the probability of M=0 is about 81/q, the participants in V can get the secret s with probability 1−81/q. When q>8.1×10³, the probability of V can recover s is larger than 0.99.

Let $V\subseteq \mathcal {P}$, $|V|=11,|V\cap \mathcal {U}_{1}|=2,$ $|V\cap \mathcal {U}_{2}|=5$ and $|V\cap \mathcal {U}_{3}|=4$. V is a maximal unqualified set. In this case, V can construct $\textbf {M}^{\prime }\textbf {X}=\textbf {F}^{\prime }$, where X is the vector as above, $\textbf {F}^{\prime }$ is composed of the first 11 elements of the vector F and $\textbf {M}^{\prime }$ is composed of the first 11 rows of M. Let e ₁=(1,0,1,0,1,0,0,1,0,0,1,0), we need to prove that e ₁, most probability, cannot be span by the rows of $\textbf {M}^{\prime }$. After analysis, we get that the probability of $\left |\begin {array}{l} \textbf {e}_{1}\\ \textbf {M}^{\prime } \end {array}\right |=0$ is about 75/q. So V cannot get any information about the secret with probability 1−75/q approximately. Put $V\subseteq \mathcal {P}$: $|V|=n-|\mathcal {U}_{1}|+1$, $|V\cap \mathcal {U}_{1}|=1$, $|V\cap \mathcal {U}_{2}|=\mathcal {U}_{2}$ and $|V\cap \mathcal {U}_{3}|=\mathcal {U}_{3}$. V is a maximal unqualified set. In this case, there are only one linear equation that related to the variable b _1,1:

$$\left(y_{1,1},y_{1,1}^{2}\right)\binom{b_{1,1}}{b_{1,2}}=Q(y_{1,1},z_{1,1})-R(z_{1,1})-f(x_{1}). $$

But the equation has two variables b _1,1,b _1,2. So the participants cannot get any information about b _1,1. Then V cannot recover the secret.

Let $V\subseteq \mathcal {P}:$ $|V\cap \mathcal {U}_{1}|=\mathcal {U}_{1}+6$, $|V\cap \mathcal {U}_{2}|=3$ and $|V\cap \mathcal {U}_{3}|=3$. V is a maximal unqualified set. In this case, participants from $V\cap \mathcal {U}_{1}$ can recover b _1,0=f(x ₁), while participants of $V\cap \mathcal {U}_{2}$ have M ₂ X=F, where X=(a ₀,a ₁,b _2,1,b _2,2,b _2,3), $\textbf {F}=\left (Q_{2}(y_{2,1},z_{2,1})-R(z_{2,1}),Q_{2}(y_{2,2},z_{2,2})-R(z_{2,2}),Q_{2}(y_{2,3},z_{2,3})-R(z_{2,3})\right )$ and

$$M_{2}=\left(\begin{array}{cccc} 1&x_{2}&y_{2,1}&y_{2,1}^{2},y_{2,1}^{3}\\ 1&x_{2}&y_{2,2}&y_{2,2}^{2},y_{2,2}^{3}\\ 1&x_{2}&y_{2,3}&y_{2,3}^{2},y_{2,3}^{3} \end{array}\right). $$

The linear equation system has only three equations with four variables. So they cannot recover b _2,0=f(x ₂)=a ₀+a ₁ x ₂. Similarly, participants of $V\cap \mathcal {U}_{3}$ cannot get b _3,0=f(x ₃). Up to now, V only get the value of f(x ₁). Hence V cannot recover a ₀, and V can not reconstruct the secret further.

5 Conclusions

We devised ideal secret sharing scheme for CASHC and SLCAS respectively. Our ideas come from the bivariate interpolation [16]. Since these ASs are generations of some known ASs, our proposed schemes may be suitable for much real-world scenarios. Although our schemes have a probability of failure, but as we know the probability is negligible when the cardinality of the finite field is big enough. Obviously, the complexity of the computation of the SSS increase with the increase of the cardinality of the field. In the process of distribution, we only need the operations of addition and multiplication. The share distribution process is analogous to that of Shamir scheme. In the process of recovery, we need to solve a system of linear equations. By using the Gauss elimination which needs O(n ³) operations over the field, we can finish the reconstruction of the secret. In order to implement the proposed scheme more easier, we can construct the tables of addition and multiplication operation over the finite field. The processes of distribution and reconstruction can be speeded up by finding these tables.

We should note that the open problem in [9, 18] that finding ideal, perfect and efficient SSS for these ASs are not solved here. So far there are not any ideal, efficient and perfect (without the probability) schemes for these ASs. The skill in [17] may have some inspiration for us. If we can allocate the identity of participant reasonably, we may get the deterministic scheme for these ASs without the probability.