1 Introduction

As the use of cloud computing becomes widespread, security of the cloud computing becomes an important research topic. Secret sharing (SS) is one of most important cryptographic primitives for data outsourcing [1, 2]. In Shamir’s (t, n) threshold SS [3], the user of an outsourced data file, F, splits F into n sub-files, \(f_{1} ,f_{2} , \ldots ,f_{n} ,\) such that each sub-file \(f_{i}\), is padded with some redundant information to make it having the same size as that of F. The file F can be retrieved if t out of n sub-files are available. Nirmala et al. [4] provided a comparative study of SSs in cloud computing.

Threshold cryptography has become one of most important tools in providing secure applications such as password protection [5], cloud computing [1, 2, 4], etc. Threshold cryptography splits a secret into multiple pieces in such a way that only with enough number (i.e., threshold) of pieces of the secret can recover the secret and therefore enable the application; but with fewer than the threshold cannot recover the secret. Shamir’s \((t,n)\) threshold SS [3] based on a univariate polynomial is the most popular SS so far. There are other approaches used to design SSs. For example, Azimuth-Bloom’s SS [6] is based on the Chinese Remainder Theorem (CRT), and Blakely’s SS [7] is based on hyperplane geometry.

The public-key based threshold cryptography which incorporates a public-key algorithm, such as digital signature or encryption scheme, with a SS, called threshold signature/decryption scheme [8,9,10,11], has become one active research area. The threshold signature scheme in which a signature can only be generated if there are enough number of signers working together has become a commercial application [12]. The threshold decryption in which a ciphertext can only be decrypted successfully if there are enough number of receivers working together. The public-key threshold cryptographic schemes have become popular tools to provide security solutions.

While implementing threshold cryptographic scheme over networks, it involves multiple users. Any secure multi-user application needs membership authentication and key establishment in prior of the application; otherwise attackers can participated in the threshold cryptographic applications without being detected. Membership authentication is used to ensure that all users are legitimate members. Most user authentication protocols [13, 14] are one-to-one interactions which involve one prover and one verifier. In a recent paper [15], a new type of authentication, called group authentication, has been proposed based on the SS which authenticates all users at once. But the group authentication can only determine whether all users are members or not. If there are non-members, the group authentication cannot identify non-members. The key establishment enables secret session keys shared among all members in a communication. The session keys will be used to protect exchange information in the application. Key establishment is an active research area. Various key establishment schemes have been proposed. In general, there are two types of key establishment schemes: the centralized [16, 17] and the distributed schemes [18, 19]. The centralized key establishment uses a key generation center (KGC) to distribute keys for members and the distributed key establishment requires members to generate the keys.

In this paper, we propose a novel design which embeds the function of membership authentication and key establishment in threshold cryptographic schemes. We propose a membership authentication and key establishment based on polynomial-based SS. During registration, each member will receive a “token” from the membership registration center (MRC). Tokens are generated by a multivariate polynomial and each share is a univariate polynomial. Each member uses the token for membership authentication, key establishment and threshold cryptographic applications. We propose an efficient way to implement threshold cryptography in network applications. In other words, our design does not need separate membership and key establishment for threshold cryptography. In summary, we list the contributions of this paper below.

  • Instead of using a univariate polynomial in all existing threshold cryptographic schemes, we propose to use a bivariate polynomial in the cryptographic applications.

  • Tokens generated by a bivariate polynomial initially can be used for (a) membership authentication; (b) key establishment and (c) threshold cryptographic applications.

  • Our proposed approach is very efficient since there is no need for additional membership authentication and key establishment.

The rest of this paper is organized as follows: In the next section, we review some preliminaries. Our proposed scheme is given in Sect. 3. In Sect. 4, we analyze our proposed scheme. We conclude in Sect. 5.

2 Preliminaries

In Shamir’s (t, n) threshold SS [3], the dealer selects a univariate polynomial, \(f(x) = a_{0} + a_{1} x + \cdots + a{}_{t - 1}x^{t - 1} nod\,p,\) to generate shares for shareholders. In a bivariate polynomial, \(F(x,y) = a_{0,0} + a_{1,0} x + a_{0,1} y + a{}_{2,0}x^{2} + a_{1,1} xy + a_{0,2} y^{2} + \cdots + a{}_{t - 1,0}x^{t - 1} + a{}_{t - 2,1}x^{t - 2} y + \cdots + a{}_{t - 1,t - 1}x{}^{t - 1}y^{t - 1} nod\;p,\) where \(a_{i,j} \in GF(p),\) if the coefficients satisfy, \(a_{i,j} = a_{j,i} ,\quad \forall i,j,\) it is a symmetric bivariate polynomial. There are many \((t,n)\) verifiable SSs (VSSs) in the literature [20,21,22] use symmetric bivariate polynomials to generate shares. In these schemes, the dealer select a symmetric bivariate polynomial to generate shares. \(F(x_{i} ,y),\) \(i = 1,2, \ldots ,n,\) where \(x_{i}\) is a public information of shareholder, \(U_{i} .\) Each share, \(F(x_{i}^{{}} ,y),\) is a univariate polynomial. Since \(F(x_{i}^{{}} ,x_{j}^{{}} ) = F(x_{j}^{{}} ,x_{i}^{{}} ),\) \(\forall i,\;j \in [0,t - 1],\) a pairwise key, can be shared between any pair of shareholders, \(U_{i}\) and \(U_{j}\). Harn and Xu [24] used a symmetric bivariate polynomial to design a dynamic threshold secret reconstruction scheme. Blundo et al. [23] have proposed a non-interactive k-secure m-conference protocol based on a multivariate polynomial, \(F(x_{1} ,x_{2} \ldots ,x{}_{m}).\) Because each share, \(F(x_{i} ,x_{2} \ldots ,x{}_{m}),\) is a polynomial involving \(m - 1\) variables with degree k, each user needs to store \((k + 1)^{m - 1}\) coefficients. The storage space of each user is exponentially proportional to the size of conference. This makes their protocol impractical. Recently, Harn and Gong [25] proposed a conference key establishment scheme using a special type of multivariate polynomial to overcome the storage problem of each user.

In this paper, we propose a novel design of threshold cryptographic schemes. Our design integrates solutions of both threshold cryptography and secure network together. In other words, we propose to use a multivariate polynomial to generate tokens. The tokens can be used to provide (a) membership authentication; (b) key establishment and (c) threshold applications.

3 Proposed Scheme

In the following discussion, we demonstrate our proposed design using a bivariate polynomial for a (t, n) threshold SS. The similar design can be applied to other threshold cryptographic algorithms [8,9,10,11] such as threshold signature/decryption.

3.1 Phase 1: Registration Phase

The MRC selects a \(l - 1\) degree symmetric polynomial, \(F(x,y) = a_{0,0} + a_{1,0} x + a_{0,1} y + a{}_{2,0}x^{2} + a_{1,1} xy + a_{0,2} y^{2} + \cdots + a{}_{t - 1,0}x^{l - 1} + a{}_{t - 2,1}x^{t - 2} y + \cdots + a{}_{t - 1,t - 1}x^{t - 1} y^{l - 1} nod\;p,\) with \(F(0,0) = a_{0,0} = s\), where \(s\) is the secret. The MRC computes tokens, \(s_{i} (y) = F(x_{i} ,y)\;\bmod \,{\text{p}}\) for members, \(U_{i} ,i = 1,2, \ldots ,n,\) where \(x_{i} \notin \{ 0,1\}\) is the public information associated with each member, \(U_{i}\). The MRC sends each token, \(s_{i} (y),\) to member \(U_{i}\) secretly.

3.2 Phase 2: Membership Authentication and Key Establishment

We assume that \(r\) (i.e., \(t < r \le n\)) members, for example \(\{ U_{{v_{1} }} ,U_{{v_{2} }} , \ldots ,U_{{v_{r} }} \} ,\) want to engage in a threshold cryptographic application.

  • Step 1. Each member \(U_{{v_{i} }}\) broadcasts a random integer, \(r_{i} \in GF(p),\) to all other members.

  • Step 2. Each member \(U_{{v_{i} }}\) uses his token, \(s_{{v_{i} }} (y),\) to compute pairwise shared keys, \(k_{i,j} = s_{{v_{i} }} (x_{{v_{j} }} ) = F(x_{{v_{i} }} ,x_{{v_{j} }} ),\) \(j = 1,2, \ldots ,r,\quad j \ne i,\) where \(k_{i,j}\) is the secret key shared between shareholders, \(U_{{v_{i} }}\) and \(U_{{v_{j} }} .\)

  • Step 3. Each member \(U_{{v_{i} }}\) computes authentication responses, \(Auth{}_{i,j} = h(k_{i,j} \left\| {r{}_{j}} \right.),\) \(j = 1,2, \ldots ,r,\quad j \ne i,\) where \(h(k_{i,j} \left\| {r{}_{j}} \right.)\) is a one-way hash output with \(k_{i,j}\) and \(r_{j}\) as inputs. Each \(Auth{}_{i,j}\) is sent to member \(U_{{v_{j} }}\) publicly for authentication.

  • Step 4. After receiving \(Auth{}_{i,j} = h(k_{i,j} \left\| {r{}_{j}} \right.),\) from member \(U_{{v_{i} }} ,\) member \(U_{{v_{j} }}\) uses his computed pairwise shared key, \(k_{j,i} = s_{{v_{j} }} (x_{{v_{i} }} ) = F(x{}_{{v_{j} }},x_{{i_{j} }} ),\) in Step 2 to check whether \(Auth{}_{i,j} \, \underline{\underline{?}} \, h(k_{j,i} \left\| {r{}_{j}} \right.).\) If the checking is successful, member \(U_{{v_{i} }}\) has been authenticated; otherwise, member \(U_{{v_{i} }}\) has not been authenticated. Repeat this process for all other members \(U_{{v_{i} }}\), \(i = 1,2, \ldots ,r,\quad i \ne j.\)

3.3 Phase 3: Threshold Cryptographic Application

In this phase, members follow a threshold cryptographic algorithm to complete the process. However, all exchange information among members is encrypted under the pairwise shared keys, \(k_{i,j}\), \(j = 1,2, \ldots ,r,\quad j \ne i,\) in Step 2.

In the following discussion, we demonstrate the secret reconstruction in a threshold SS. We assume that all members in \(\{ U_{{v_{1} }} ,U_{{v_{2} }} , \ldots ,U_{{v_{j} }} \}\) have been successfully authenticated in Phase 2.

3.3.1 Secret Reconstruction

  • Step 1. Each member \(U_{{v_{i} }}\) uses his token, \(s_{{v_{i} }} (y),\) to compute \(q{}_{{v_{i} }} = s_{{v_{i} }} (0)\prod\nolimits_{k = 1,k \ne j}^{r} {\frac{{ - x{}_{{v_{k} }}}}{{x_{{v_{j} }} - x{}_{{v_{k} }}}}} \bmod \;p.\)

  • Step 2. Each member \(U_{{v_{i} }}\) uses his computed pairwise shared keys, \(k_{i,j} ,\) \(j = 1,2, \ldots ,r,\quad j \ne i,\) in Phase 2, Step 2 to encrypt \(q{}_{{v_{i} }}\) as \(u{}_{i,j} = E{}_{{k_{i,j} }}(q_{{v_{i} }} ),\) \(j = 1,2, \ldots ,r,\quad j \ne i.\) Member \(U_{{v_{i} }}\) sends each \(u{}_{i,j}\) to member \(U_{{v_{j} }} .\)

  • Step 3. After receiving \(u{}_{j,i},\) from other member, member \(U_{{v_{i} }}\) uses his computed pairwise shared key, \(k_{i,j} ,\) in Phase 2, Step 2 to decrypt as \(q_{{v_{j} }} = E{}_{{k_{i,j} }}(u_{j.i} )\). Repeat this process for all \(u{}_{j,i},\) \(i = 1,2, \ldots ,r,\quad i \ne j.\)

  • Step 4. After obtaining \(q_{{v_{j} }}\). \(j = 1,2, \ldots ,r,\quad j \ne i,\) from all other members, member \(U_{{v_{i} }}\) computes \(\sum\nolimits_{j = 1}^{r} {q{}_{{v_{j} }}} \bmod \;p = \sum\nolimits_{j = 1}^{r} {s_{{j_{i} }} (0)} \prod\nolimits_{k = 1,k \ne j}^{r} {\frac{{ - x{}_{{v_{k} }}}}{{x_{{v_{j} }} - x{}_{{v_{k} }}}}} \bmod \;p = s\).

4 Analysis

4.1 Correctness

In Step 4 of the secret reconstruction, we have \(\sum\nolimits_{j = 1}^{r} {q{}_{{v_{j} }}} \bmod \;p = \sum\nolimits_{j = 1}^{r} {s_{{j_{i} }} (0)} \prod\nolimits_{k = 1,k \ne j}^{r} {\frac{{ - x{}_{{v_{k} }}}}{{x_{{v_{j} }} - x{}_{{v_{k} }}}}} \bmod \;p = \sum\nolimits_{j = 1}^{r} {F(x_{j} ,0)} \prod\nolimits_{k = 1,k \ne j}^{r} {\frac{{ - x{}_{{v_{k} }}}}{{x_{{v_{j} }} - x{}_{{v_{k} }}}}} \bmod p = F(0,0) = s\).

4.2 Threshold of the Secret

There are two major differences between shares generated by a \(t - 1\) degree univariate polynomial and by a \(t - 1\) degree symmetric bivariate polynomial, (a) there are t different coefficients in a \(t - 1\) degree univariate polynomial but there are \(\frac{t(t + 1)}{2}\) different coefficients in a \(t - 1\) degree symmetric bivariate polynomial, and (b) shares by a \(t - 1\) degree univariate polynomial are integers in GF(p); but shares by a \(t - 1\) degree symmetric bivariate polynomial is a univariate polynomial having \(t - 1\) degree. We give the definition of the threshold of a threshold SS.

Definition 1 (Threshold of a threshold SS)

The threshold, \(th,\) of a threshold SS specifies the minimal number of shares needed to reconstruct the secret.

It is well-known that the threshold of shares generated by a \(t - 1\) degree univariate polynomial is \(t\). The following theorem states the threshold of shares generated by a \(t - 1\) degree symmetric bivariate polynomial.

Theorem 1

The threshold of shares generated by a \(t - 1\) degree symmetric bivariate polynomial is \(th = \left\lceil {\frac{t + 1}{2}} \right\rceil\).

Proof

In a \(t - 1\) degree symmetric bivariate polynomial, there are \(\frac{t(t + 1)}{2}\) different coefficients, In addition, each share is a univariate polynomial having \(t - 1\) degree. In other words, it can establish \(t\) linearly independent equations in terms of coefficients of the bivariate polynomial from each share. Having enough number of shares (i.e., \(th\)), the total number of linearly independent equations, \(th \cdot t,\) needs to satisfy \(th \cdot t \ge \left\lceil {\frac{t(t + 1)}{2}} \right\rceil\) in order to recover the bivariate polynomial and therefore to reconstruct the secret. This implies that \(th = \left\lceil {\frac{t + 1}{2}} \right\rceil .\) □

4.3 Possible Attacks

4.3.1 Insider Attackers

Inside attackers are legitimate members who own valid tokens from the MRC during registration. From Theorem 1, we obtain that the threshold of shares generated by a \(t - 1\) degree symmetric bivariate polynomial is \(\left\lceil {\frac{t + 1}{2}} \right\rceil .\) Thus, it needs at least \(\left\lceil {\frac{t + 1}{2}} \right\rceil\) insider attackers to work together to reconstruct the secret.

4.3.2 Outside Attackers

Outside attackers are illegitimate users who do not own any valid tokens from MRC. The outside attackers may try to impersonate members in the secret reconstruction to obtain the secret. However, since in the secret reconstruction, all exchange information of legitimate members are encrypted using pairwise shared keys and outside attackers do not own any valid token to recover any pairwise shared key, so the outside attacker cannot obtain the reconstructed secret.

4.4 Performance

The proposed scheme does not need any additional key establishment and authentication. Membership authentication and pairwise shared keys in the secret reconstruction are based on the same tokens used to reconstruct the secret. Thus, our proposed solution is very efficient in comparing with all existing threshold cryptographic solutions which need additional membership and key establishment schemes to prevent outside attackers.

5 Conclusion

Threshold cryptography is an active research area in network security. We propose a novel design to integrate solutions of both threshold cryptography and network security. Users can use their tokens obtained during registration to provide (a) membership authentication, (b) key establishment and (c) threshold applications.