Multipartite Secret Sharing Based on CRT

Abstract

Secure communication has become more and more important for system security. Since avoiding the use of encryption one by one can introduce less computation complexity, secret sharing scheme (SSS) has been used to design many security protocols. In SSSs, several authors have studied multipartite access structures, in which the set of participants is divided into several parts and all participants in the same part play an equivalent role. Access structures realized by threshold secret sharing are the simplest multipartite access structures, i.e., unipartite access structures. Since Asmuth–Bloom scheme based on Chinese remainder theorem (CRT) was presented for threshold secret sharing, recently, threshold cryptography based on Asmuth–Bloom secret sharing were firstly proposed by Kaya et al. In this paper, we extend Asmuth–Bloom and Kaya schemes to bipartite access structures and further investigate how SSSs realizing multipartite access structures can be conducted with the CRT. Actually, every access structure is multipartite and, hence, the results in this paper can be seen as a new construction of general SSS based on the CRT. Asmuth–Bloom and Kaya schemes become the special cases of our scheme.

1 Introduction

Secret sharing was first introduced by Blakley [1] and Shamir [2] independently in 1979, which was widely used to design security protocols until now (see [3–7]). In a secret sharing scheme (SSS), a dealer distributes a piece of information (called a share) about a secret to each participant such thatauthorized subsets of participants can reconstruct the secret but unauthorized subsets of participants cannot determine the secret. If any unauthorized subset of participants can not obtain any information about the secret, then the scheme is called perfect. The set of authorized subsets of participants is called access structure and the set of unauthorized subsets of participants is called prohibited structure. In the literature, different mathematical tools have been used to design SSSs including Shamir scheme [2] based on polynomial interpolation, Blakley scheme [1] based on hyperplane geometry, Asmuth–Bloom scheme [8] based on the Chinese Remainder Theorem (CRT), Bloom scheme [9] and McEliece et al. scheme [10] based on a linear code. These schemes are all threshold secret sharing (SS), in which any $t$ or more shares can recover the secret, but any $t-1$ or less shares can obtain no information about the secret. Among these SSs, Shamir scheme [2] is the most popular SS. Shamir scheme is very simple and most straightforward but Asmuth–Bloom scheme needs to understand the CRT. In recent years, attention has been devoted to research of CRT-based SSs and applications [11–15].

Information rate (i.e., the ratio between the size of the secret in bits and the maximum size of a share in bits) is usually used to measure the efficiency of a SSS. A scheme is ideal if the information rate is equal to 1. The central research questions in SS are both the construction of efficient SSSs for several classes of access structures, and finding bounds on the possible efficiency that any such scheme can achieve for a certain access structure. In this paper, we deal with multipartite access structures. An access structure is multipartite if its set of participants can be divided into several parts in such a way that all participants in the same part play an equivalent role in the structure. Because of its practical interest, SS for multipartite access structures has been studied by several authors. Since we can always consider as many parts as participants, every access structure is multipartite. More accurately, we can consider in any access structure the partition that is derived from a suitable equivalence relation on the set of participants. Therefore, we are not restricting ourselves to a family of access structures, but we study the general access structures under a different point of view.

Multipartite access structures were first introduced by Shamir [2] in his seminal work, in which weighted threshold access structures were considered. These structures have been studied also in [16, 17] and a characterization of the ideal weighted access structures has been presented in [18]. Brickell [19] constructed ideal SSSs for several different kinds of multipartite access structures, called multilevel and compartmented, that had been previously considered by Simmons [20]. Other constructions of ideal schemes for these and other multipartite structures have been presented in [21–24], where some complexity issues related to the construction of those ideal schemes are studied. A complete characterization of ideal bipartite access structures was given in [17] and, independently, in [25, 26]. Partial results on the characterization of ideal tripartite access structures have been presented in [18, 21, 27]. A complete characterization of ideal tripartite access structures were given by Farras and Marti-Farre [28].

Access structure realized by the threshold SS is the simplest multipartite access structure, i.e., unipartite access structures. Most well-known CRT-based SSSs were constructed for threshold access structures, such as Asmuth–Bloom scheme [8], Mignotte’s scheme [29] and Kaya’s schemes [11, 12]. Other CRT-based SS of general access structures in which compartmented access structures and weighted threshold access structures are considered is proposed in [13]. But these structures in [13] only belong to two types of multipartite access structures [28]. Due to the fact that every access structure can be viewed as multipartite access structure, this motivates us to explore the design of CRT-based sharing schemes realizing multipartite access structures.

Instead of studying SSS realizing a particular family of access structures, in this paper, we study CRT-based general SSS from the perspective of multipartite SSS. We extend both Asmuth–Bloom and Kaya schemes to bipartite access structures and investigate the design of CRT-based SSSs realizing multipartite access structures. The result presented in this paper is a new way to construct CRT-based general secret sharing. Thus, Asmuth–Bloom and Kaya schemes become special cases in our proposed approach. The main contributions of our paper are summarized below:

• (a) Using the characterizations of multipartite access structures, we propose the first CRT-based multipartite SSS;

• (b) Due to the fact every access structure is multipartite, our result is a new way to construct CRT-based general SS;

• (c) Our proposed CRT-based multipartite SSS is perfect and unconditionally secure since there has not any computational assumption based on.

• (d) Our proposed scheme can be widely applied to wireless communications to ensure its security.

The rest of this paper is organized as follows: In the next section, we give some preliminaries. In Sect. 3, we propose a multipartite SSS based on CRT. We analyze functional sharing schemes in Sect. 4. Performance evaluation of the proposed scheme is discussed in Sect. 5. We conclude in Sect. 6.

2 Definitions and Preliminaries

In this section we review some basic definitions and notations that will be used through the paper.

2.1 Secret Sharing Schemes

Let $P=\{ {p_i :1\le i\le n}\}$ be the set of participants. The dealer is denoted by $D$ and we assume $D\notin P$. $\mathcal{K}$ is the secret set (i.e. the set of all possible secrets) and $\mathcal{S}$ is the share set (i.e. the set of all possible shares). Let $\Gamma$ be a set of subsets of $P$: this is denoted mathematically by the notation $\Gamma \subseteq 2^{P}$. The subsets in $\Gamma$ are those subsets of participants that should be able to reconstruct the secret. $\Gamma$ is called an access structure and the subsets in $\Gamma$ are called authorized subsets. Accordingly, $\Delta =2^{P}\backslash \Gamma$ is called a prohibited structure and the subsets in $\Delta$ are called unauthorized subsets.

When a dealer $D$ wants to share a secret $K\in \mathcal{K}$, he will give each participant a share from $\mathcal{S}$. The shares should be distributed secretly, so no participant knows the share given to another participant. At a later time, a subset of participants will attempt to reconstruct $K$ from the shares they collectively hold. Using Shannon’s entropy function, we will say that a scheme is a perfect SSS realizing the access structure $\Gamma$ provided the following two properties are satisfied:

• 1. Validity $H(K|A)=0,\forall A\in \Gamma$. (Any authorized subset of participants $A\in \Gamma$ who pool their shares together can reconstruct the secret $K)$,

• 2. Security $H(K|A)=H(K),\forall A\in \Delta$. (Any unauthorized subset of participants $A\in \Delta$ who pool their shares together obtain no information on $K$).

The security of cryptographic schemes/protocols can be classified into two types, computational security and unconditional security. Computational security assumes that the adversary has bounded computing power that limits the adversary solving hard mathematical problem, such as factoring a large composite integer into two primes. Unconditional security means that the security holds even if the adversary has unbounded computing power. If a scheme is unconditional secure [30], then no matter how much computational power the attacker cannot break this scheme. Research on developing cryptographic schemes/protocols with unconditional security has received wide attention recently. In this paper, we propose to design a perfect and unconditionally secure SSS.

Suppose that $B\in \Gamma ,\; B\subseteq C\subseteq P$, and the subset $C$ wants to determine $K$. Since $B$ is an authorized subset, it can already determine $K$. Hence, the subset $C$ can determine $K$ by ignoring the shares of the participants in $C\backslash B$. Stated another way, a superset of an authorized set is again an authorized set. What this says is that the access structure should satisfy the monotone increasing property

$$\begin{aligned} \hbox {if}\; B\in \Gamma \;\quad \hbox {and}\;\quad B\subseteq C\subseteq P,\;\quad \hbox {then}\;\quad C\in \Gamma . \end{aligned}$$

If $\Gamma$ is an access structure, then $B\in \Gamma$ is a minimal authorized subset if $A\notin \Gamma$ whenever $A\subseteq B,\; A\ne B$. The set of minimal authorized subsets of $\Gamma$ is denoted $\Gamma _0$ and is called the basis of $\Gamma$. Since $\Gamma$ consists of all subsets of $P$ that are supersets of a subset in the basis $\Gamma _0,\; \Gamma$ is determined uniquely as a function of $\Gamma _{0}$. Expressed mathematically, we have

$$\begin{aligned} \Gamma =\left\{ {C\subseteq P:\;B\subseteq C,\;B\in \Gamma _0 } \right\} . \end{aligned}$$

Symmetrically, the prohibited structure $\Delta$ should satisfy the monotone decreasing property

$$\begin{aligned} \hbox {if}\; B\in \Delta \; \quad \hbox {and}\; \quad C\subseteq B\subseteq P,\;\quad \hbox {then}\; \quad C\in \Delta . \end{aligned}$$

We say $B\in \Delta$ is a maximal unauthorized subset if $A\notin \Delta$ whenever $B\subseteq A,\; A\ne B$.The set of maximal unauthorized subsets of $\Delta$ is denoted $\Delta _1$. Since $\Delta$ consists of all subsets of $P$ that are subsets of a subset in $\Delta _1 ,\; \Delta$ is determined uniquely as a function of $\Delta _1$. Expressed mathematically, we have

$$\begin{aligned} \Delta =\left\{ {C\subseteq P:\;C\subseteq B,\;B\in \Delta _1 } \right\} . \end{aligned}$$

The efficiency of a SSS is measured by the information rate. Suppose $\mathcal{F}$ is a set of distribution rules for a SSS. For $1\le i\le n$, define

$$\begin{aligned} \mathcal{S}_i =\left\{ {f(p_i ):f\in \mathcal{F}} \right\} . \end{aligned}$$

$f$ represents a possible distribution rule and $f(p_i )$ is the share given to $p_i.\,\mathcal{S}_i$ represents the set of possible shares that $p_i$ might receive, of course, $\mathcal{S}_i \subseteq \mathcal{S}$. Now, since the secret $K$ comes from a finite set $\mathcal{K}$, we can think of $K$ as being represented by a bit string of length $\log _2 \left| \mathcal{K} \right|$ by using a binary encoding, for example. In a similar way, a share given to $p_i$ can be represented by a bit string of length $\log _2 \left| {\mathcal{S}_i } \right|$. Intuitively, $p_i$ receives $\log _2 \left| {\mathcal{S}_i } \right|$ bits of information (in his or her share), but the information content of the secret is $\log _2 \left| \mathcal{K} \right|$ bits. The information rate of the scheme denoted by $\rho$ is the ratio

$$\begin{aligned} \rho =\frac{\log _2 \left| \mathcal{K} \right| }{\log _2 \max \left\{ {\left| {\mathcal{S}_i } \right| } \right\} } \end{aligned}$$

2.2 Multipartite Access Structures

We write $\mathcal {P}(P)$ for the power set of the set $P$. An $r$-partition $\Omega =\left\{ {P_1,\ldots ,P_r } \right\}$ of a set $P$ is a disjoint family of $r$ nonempty subsets of $P$ with $P=P_1 \cup \cdots \cup P_r$. Let $\Lambda \subseteq \mathcal {P}(P)$ be a family of subsets of $P$. For a permutation $\sigma$ on $P$, we define $\sigma (\Lambda )=\left\{ {\sigma (A):A\in \Lambda } \right\} \subseteq \mathcal {P}(P)$. A family of subsets $\Lambda \subseteq \mathcal {P}(P)$ is said to be $\Omega$-partite if $\sigma (\Lambda )=\Lambda$ for every permutation $\sigma$ such that $\sigma (P_i )=P_i$ for every $P_i \in \Omega$. We say that $\Lambda$ is $r$-partite if it is $\Omega$-partite for some $r$-partition $\Omega$. These concepts can be applied to access structures, which are actually families of subsets.

For every integer $r\ge 1$, we consider the set $J_r =\left\{ {1,\ldots ,r} \right\}$. Let $\mathbb {Z}_+^r$ denote the set of vectors $u=\left( {u_1,\ldots ,u_r } \right) \in \mathbb {Z}^{r}$ with $u_i \ge 0$ for every $i\in J_r$. For a partition $\Omega =\left\{ {P_1,\ldots ,P_r } \right\}$ of a set $P$ and for every $A\subseteq P$ and $i\in J_r$, we define $\Omega _i (A)=|A\cap P_i |$. Then the partition $\Omega$ defines a mapping $\Omega :\mathcal {P}(P)\rightarrow \mathbb {Z}_+^r$ by considering $\Omega (A)=\left( {\Omega _1 (A),\ldots ,\Omega _r (A)} \right)$. If $\Lambda \subseteq \mathcal {P}(P)$ is $\Omega$-partite, then $A\in \Lambda$ if and only if $\Omega (A)\in \Omega (\Lambda )$. That is, $\Lambda$ is completely determined by the partition $\Omega$ and the set of vectors $\Omega (\Lambda )\subset \mathbb {Z}_+^r$.

If $u,v\in \mathbb {Z}_+^r$, we write $u\le v$ if $u_i \le v_i$ for every $i\in J_r$, and we write $u<v$ if $u\le v$ and $u\ne v$. The vector $w=u\vee v$ is defined by $w_i =\max (u_i ,v_i )$. The modulus of a vector $u\in \mathbb {Z}_+^r$ is $|u|=u_1 +\cdot \cdot \cdot +u_r$. For every subset $X\subseteq J_r$, we write $u(X)=(u_i )_{i\in X} \in \mathbb {Z}_+^{|X|}$ and $|u(X)|=\sum _{i\in X} {u_i }$.

2.3 Asmuth–Bloom SSS

The Asmuth–Bloom SSS has shares distribution and secret reconstruction phases for unipartite access structures as follows:

Shares Distribution To distribute $n$ shares of a secret $K$ among the set of participants $P=\{ {p_i :1\le i\le n}\}$, the dealer $D$ does the following:

• 1. A set of integers $\left\{ {p,\;m_1 <m_2 <\cdots <m_n } \right\}$, where $0\le K<p$, is chosen subject to the following:

  $$\begin{aligned} \gcd (m_i ,m_j )&= 1\;\quad \hbox {for}\; i\ne j,\nonumber \\ \gcd (p,m_i )&= 1\; \quad \hbox {for all}\; i,\nonumber \\ \prod _{i=1}^t {m_i }&> p\prod _{i=1}^{t-1} {m_{n-i+1} }. \end{aligned}$$

  (1)

• 2. Let $M=\prod \nolimits _{i=1}^t {m_i }$. The dealer computes

  $$\begin{aligned} y=K+ap, \end{aligned}$$

  where $a$ is a positive integer generated randomly subject to the condition that $0\le y<M$.

• 3. The share of the $i\hbox {th}$ participant, $1\le i\le n$, is

  $$\begin{aligned} y_i =y\;\hbox {mod}\; m_i. \end{aligned}$$

Secret Construction Assume $C$ is a coalition of $t$ participants to construct the secret. Let $M_C =\prod \nolimits _{i\in C} {m_i}$.

• 1. Given the system

  $$\begin{aligned} y\equiv y_i \, (\hbox {mod}\; m_i ) \end{aligned}$$

  for $i\in C$, solve $y$ in $GF (M_C )$ uniquely using the CRT.

• 2. Compute the secret as

  $$\begin{aligned} K=y\;\hbox {mod}\; p. \end{aligned}$$

  According to the CRT, $y$ can be determined uniquely in $GF (M_C)$. Since $y<M\le M_C$, the solution is also unique in $GF (M)$.

3 The Proposed Schemes

In this section we extend the Asmuth–Bloom SSS from unipartite to bipartite access structures and further investigate how SSSs realizing multipartite access structures can be conducted with the CRT. At the same time, the validity and security proofs of our scheme are given.

3.1 Bipartite SS Based on CRT

Let an access structure $\Gamma$ be $\Omega$-partite for a partition $\Omega =\left\{ {P_1 ,P_2 } \right\}$ of $P=\left\{ {p_i :1\le i\le n} \right\}$, where $\left| {P_1 } \right| =n_1 ,\; \left| {P_2 } \right| =n_2$ and $n_1 +n_2 =n$. Then the partition $\Omega$ defines a mapping $\Omega :\mathcal {P}(P)\rightarrow \mathbb {Z}_+^2$. Let $\Gamma _0$ and $\Delta _1$ be the corresponding minimal access structure and maximal prohibited structure respectively, from which we can determine $\Omega (\Gamma _0 )\subset \mathbb {Z}_+^2$ and $\Omega (\Delta _1 )\subset \mathbb {Z}_+^2$.

The secret sharing scheme for $\Gamma$ has shares distribution and secret reconstruction phase as follows:

Shares Distribution To distribute $n$ shares of a secret $K$ among $P=\left\{ {p_i :1\le i\le n} \right\}$, the dealer $D$ does the following:

• 1. A set of integers $\left\{ p,\;m_1 <m_2 <\cdots <m_{n_1 } ,\;m_{n_1 +1} <m_{n_1 +2} <\cdots <m_n \right\}$, where $0\le K<p$, is chosen subject to the following:

  $$\begin{aligned}&\gcd (m_i ,m_j )=1\;\quad \hbox {for}\; i\ne j,\nonumber \\&\gcd (p,m_i )=1\; \quad \hbox {for all}\; i,\nonumber \\ M_1&= \min \left( \prod _{i=1}^{u_1 } {m_i } \prod _{j=1}^{u_2 } {m_j } ,\hbox { for all }(u_1 ,u_2 )\in \Omega (\Gamma _0 )\right) ,\nonumber \\ M_2&= \max \left( \prod _{i=1}^{v_1 } {m_{n_1 \hbox {+}i-\hbox {1}} } \prod _{j=1}^{v_2 } {m_{n_2 +j-1} } ,\hbox { for all }(v_1 ,v_2 )\in \Omega (\Delta _1 )\right) ,\nonumber \\&M_1 >pM_2. \end{aligned}$$

  (2)

• 2. The dealer computes

  $$\begin{aligned} y=K+ap \end{aligned}$$

  where $a$ is a positive integer generated randomly subject to the condition that $0\le y<M_1$.

• 3. The $n_1$ shares,

  $$\begin{aligned} y_i =y\;\hbox {mod}\; m_i \; \quad \hbox {for}\; i=1,\ldots ,n_1 , \end{aligned}$$

  are distributed randomly to participants in $P_1$ with one to one correspondence, and the $n_2$ shares,

  $$\begin{aligned} y_{n_1 +j} =y\;\hbox {mod}\; m_{n_1 +j}\;\quad \hbox {for}\;j=1,\ldots ,n_2 , \end{aligned}$$

  are distributed randomly to participants in $P_2$ with one to one correspondence. Hence, the shares distribution defines a mapping $f:\left\{ {y_1,\ldots ,y_n } \right\} \rightarrow P$.

Secret Construction Assume $C$ is a coalition of participants in $\Gamma$ to construct the secret. Let $M_C =\prod \nolimits _{f(y_i )\in C} {m_i }$.

• 1. Given the system

  $$\begin{aligned} y\equiv y_i \;(\hbox {mod}\; m_i ) \end{aligned}$$

  for $f(y_i )\in C$, solve $y$ in $GF (M_C )$ uniquely using the CRT.

• 2. Compute the secret as

  $$\begin{aligned} K=y\;\hbox {mod}\; p. \end{aligned}$$

Theorem 1

The proposed bipartite SSS is a perfect SSS.

Proof

According to the Chinese remainder theorem (CRT) [31], in which given the following system of equations as

$$\begin{aligned} x&= s_1\; \hbox {mod}\; p_1 ;\\ x&= s_2\; \hbox {mod}\; p_2 ;\\&\quad \quad \vdots \\ x&= s_t \;\hbox {mod}\; p_t , \end{aligned}$$

there is one unique solution as $x=\sum _{i=1}^t {\frac{N}{p_i }} \cdot y_i \cdot s_1\; \hbox {mod}\; N,$ where $\frac{N}{p_i }\cdot y_i \;\hbox {mod}\; p_i =1,$ and $N=p_1 \cdot p_2 \cdot \ldots \cdot p_t ,$ if all moduli are pairwise coprime (i.e., $\gcd (p_i ,p_j )=1$ for every $i\ne j)$.

From the above CRT, in our bipartite scheme $y$ can be determined uniquely in $GF (M_C )$. Since $y<M_1 \le M_C$, the solution is also unique in $GF (M_1 )$. Hence, it holds that $H(K|C)=0,\forall C\in \Gamma$. (Any authorized subset of participants $C\in \Gamma$ who pool their shares together can reconstruct the secret $K)$.

At the same time, we assume that a coalition $C^{\prime }$ of malicious participants in $\Delta$ has gathered. Let $y^{\prime }$ be the unique solution for $y$ in $GF (M_{C^{\prime }} )$. According to (2) and $M_2 >M_{C{^\prime }}$, we obtain $M_1 /M_{C^{\prime }} >p$, hence $y^{\prime }+jM_{C^{\prime }}$ is smaller than $M_1$ for $0\le j<p$. Since $\gcd (p,M_{C^{\prime }} )=1$, all $(y^{\prime }+jM_{C^{\prime }} )\;\hbox {mod}\; p$ are distinct for $0\le j<p$, and there are $p$ of them. That is, $K$ can be any integer from $GF (p)$, and the coalition $C^{\prime }$ obtains no information on $K$. Hence, it holds that $H(K|C^{\prime })=H(K),\forall C^{\prime }\in \Delta$. (Any unauthorized subset of participants $C^{\prime }\in \Delta$ who pool their shares together obtain no information on $K$).

Therefore, according to the definition in Sect. 2.1, the proposed bipartite SS is a perfect SSS. $\square$

As a consequence, based on the CRT, the SSS realizing bipartite access structures is constructed.

3.2 Multipartite SS Based on CRT

This construction method can be extended to the general case, i.e., the SSSs realizing multipartite access structures.

Let an access structure $\Gamma$ be $\Omega$-partite for a partition $\Omega =\left\{ {P_1 ,\ldots ,P_r } \right\}$ of $P=\left\{ {p_i :1\le i\le n} \right\}$, where $\left| {P_1 } \right| =n_1,\ldots ,\left| {P_r } \right| =n_r$ and $n_1 +\cdot \cdot \cdot +n_r =n$. Then the partition $\Omega$ defines a mapping $\Omega :\mathcal {P}(P)\rightarrow \mathbb {Z}_+^r$. Let $\Gamma _0$ and $\Delta _1$ be the corresponding minimal access structure and maximal prohibited structure respectively, from which we can determine $\Omega (\Gamma _0 )\subset \mathbb {Z}_+^r$ and $\Omega (\Delta _1 )\subset \mathbb {Z}_+^r$.

The SSS for $\Gamma$ has shares distribution and secret reconstruction phase as follows:

Shares Distribution To distribute $n$ shares of a secret $K$ among $P=\left\{ {p_i :1\le i\le n} \right\}$, the dealer $D$ does the following:

• 1. A set of integers $\left\{ p,\hbox { }m_1 <\cdots <m_{n_1 } ,\;m_{n_1 +1} <\cdots <m_{n_1 +n_2 } ,\;\ldots \;,\;m_{n-n_r +1} <\cdots <m_n \right\}$, where $0\le K<p$, is chosen subject to the following:

  $$\begin{aligned}&\gcd (m_i ,m_j )=1\;\hbox {for}\; i\ne j,\nonumber \\&\gcd (p,m_i )=1\; \hbox {for all}\; i,\nonumber \\ M_3&= \min \left( \prod _{j=1}^r {\prod _{i=1}^{u_j } {m_i } } ,\hbox { for all }(u_1 ,\ldots ,u_r )\in \Omega (\Gamma _0 )\right) ,\nonumber \\ M_4&= \max \left( \prod _{j=1}^r {\prod _{i=1}^{v_j } {m_{n_j +i-1} } } ,\hbox { for all }(v_1 ,\ldots ,v_r )\in \Omega (\Delta _1 )\right) ,\nonumber \\&M_3 >pM_4. \end{aligned}$$

  (3)

• 2. The dealer computes

  $$\begin{aligned} y=K+ap \end{aligned}$$

  where $a$ is a positive integer generated randomly subject to the condition that $0\le y<M_3$.

• 3. For $j=1,\ldots ,r$, the $n_j$ shares,

  $$\begin{aligned} y_i =y\;\hbox {mod}\; m_i \quad \hbox {for}\; i=1,\ldots ,n_j , \end{aligned}$$

  are distributed randomly to participants in $P_j$ with one to one correspondence. Hence, the shares distribution defines a mapping $f:\left\{ {y_1,\ldots ,y_n } \right\} \rightarrow P$.

Secret Construction Assume $C$ is a coalition of participants in $\Gamma$ gathered to construct the secret. Let $M_C =\prod _{f(y_i )\in C} {m_i }$.

• 1. Given the system

  $$\begin{aligned} y\equiv y_i \;(\hbox {mod}\; m_i ) \end{aligned}$$

  for $f(y_i )\in C$, solve $y$ in $GF (M_C )$ uniquely using the CRT.

• 2. Compute the secret as

  $$\begin{aligned} K=y\;\hbox {mod}\; p. \end{aligned}$$

Theorem 2

The proposed SS realizing multipartite access structures is a perfect SSS.

Proof

According to the CRT [31], in which given the following system of equations as

$$\begin{aligned} x&= s_1 \;\hbox {mod}\; p_1 ;\\ x&= s_2 \;\hbox {mod}\; p_2 ;\\&\quad \quad \vdots \\ x&= s_t \;\hbox {mod}\; p_t , \end{aligned}$$

there is one unique solution as $x=\sum \nolimits _{i=1}^t {\frac{N}{p_i }} \cdot y_i \cdot s_1 \;\hbox {mod}\; N,$ where $\frac{N}{p_i }\cdot y_i\; \hbox {mod}\; p_i =1,$ and $N=p_1 \cdot p_2 \cdot \ldots \cdot p_t ,$ if all moduli are pairwise coprime (i.e., $\gcd (p_i ,p_j )=1$ for every $i\ne j)$.

From the above CRT, we obtain that in our multipartite scheme $y$ can be determined uniquely in $GF (M_C )$. Since $y<M_1 \le M_C$, the solution is also unique in $GF (M_1 )$. Hence, it holds that $H(K|C)=0,\forall C\in \Gamma$ (Any authorized subset of participants $C\in \Gamma$ who pool their shares together can reconstruct the secret $K)$.

At the same time, we assume that a coalition $C^{\prime }$ of malicious participants in $\Delta$ has gathered. Let $y^{\prime }$ be the unique solution for $y$ in $GF (M_{C^{\prime }} )$. According to (3) and $M_4 >M_{C^{\prime }}$, we obtain $M_3 /M_{C^{\prime }} >p$, hence $y^{\prime }+jM_{C^{\prime }}$ is smaller than $M_3$ for $0\le j<p$. Since $\gcd (p,M_{C^{\prime }} )=1$, all $(y^{\prime }+jM_{C^{\prime }} )\hbox {mod}\; p$ are distinct for $0\le j<p$, and there are $p$ of them. That is, $K$ can be any integer from $GF (p)$, and the coalition $C^{\prime }$ obtains no information on $K$. Hence, it holds that $H(K|C^{\prime })=H(K),\forall C^{\prime }\in \Delta$ (Any unauthorized subset of participants $C^{\prime }\in \Delta$ who pool their shares together obtain no information on $K$).

Therefore, according to the definition in Sect. 2.1, the proposed multipartite SS is a perfect SSS. $\square$

As a consequence, based on the CRT, the SSS realizing multipartite access structures is constructed.

Remark 1

In a verifiable SSS the validity of the shares can be verified, hence participants are not able to cheat. Based on our scheme, we can further construct an ideal verifiable multi-SSS by adding the existing verifiability methods where the intractability of discrete logarithm problem is frequently used.

4 Functional Sharing Schemes Based on Our Scheme

Besides dealing with the problem of sharing a secret, a further requirement of a cryptosystem can be that the subject function (e.g., a digital signature) should be computable without the participants disclosing their secret shares. This is known as the functional sharing problem. A function sharing scheme (FSS) requires distributing the function’s computation according to the underlying SSS such that each part of the computation can be carried out by a different participant and then the partial results can be combined to yield the functional value without disclosing the individual secrets. Several protocols for functional sharing [3–7] have been proposed in the literature. Nearly all existing solutions for functional sharing are based on the Shamir SSS. In [11], Kaya et al. firstly show how sharing of threshold cryptographic functions can be achieved using the Asmuth–Bloom SSS. They proposed two novel FSSs, one for the RSA signature and the other for the ElGamal decryption functions, both based on the Asmuth–Bloom SSS. Since our scheme is the extension of Asmuth–Bloom SSS, the construction of FSSs based on our scheme, such as FSSs for the RSA signature and the ElGamal decryption functions, may be similar to Kaya et al.’s scheme. Due to this fact, we will not describe it in details. As a consequence, cryptography based on our SSS can extend Kaya scheme from the threshold case to the general case.

5 Discussion of Our Scheme

In our scheme, the information rate is

$$\begin{aligned} \frac{\log _2 p}{\log _2 \max \left\{ {m_i ,\,\hbox {for}1\le i\le n} \right\} }, \end{aligned}$$

where the secret and the shares are chosen from finite fields $GF (p)$ and $GF (m_i )$ respectively.

Except the generation algorithm of the set of integers $\left\{ p,\;m_1 <\cdots <m_{n_1 } ,\;m_{n_1 +1} <\cdots <m_{n_1 +n_2 } ,\ldots , m_{n-n_r +1} <\cdots <m_n \right\}$, the performance of our scheme is the same as the performance of Asmuth–Bloom SSS. The monotone increasing property of access structures, the monotone decreasing property of prohibited structures and estimates of the density of primes show that one could find primes $m_i (1\le i\le n)$ and $p$ to satisfy (3). To find composite $m_i (1\le i\le n)$ and $p$ is still easier. A specific algorithm for generating $m_i (1\le i\le n)$ and $p$ is deferred to our future work.

6 Conclusion

In this paper, we extend Asmuth–Bloom and Kaya schemes to bipartite access structures and further present how SSSs realizing multipartite access structures can be conducted with the CRT. Due to the fact that every access structure is multipartite, the results in this paper can be seen as a new construction of general SS based on the CRT. Asmuth–Bloom and Kaya schemes become the special cases of our scheme.