An IBE Scheme with Verifiable Outsourced Key Generation Based on a Single Server

ABSTRACT

It is well known that private key generation is a computing bottleneck in an identity-based encryption scheme when a large number of users exist. Outsourcing computation can greatly reduce the users’ computational cost, but the existing schemes are all based on two servers, which are not feasible in the real cloud environment. In this paper, we first propose a scheme where the PKG outsources the task of private key generation to a single server, and the results can be verified effectively. Moreover, PKG only needs to execute 1 modular exponentiation, so it is more efficient when compared with previous schemes. Meanwhile, we prove the indistinguishability of the ciphertext and verifiability of the outsourcing results in the security model. Finally, the proposed algorithm is realized in a simulation environment. Theoretical analysis and experimental results show that total computing time of PKG and the server in the outsourced algorithm is far less than that of direct computation.

KEYWORDS:

• Identity-based encryption
• Private key generation
• Verifiable outsourcing computation

1. INTRODUCTION

With the rapid development of cloud computing, the safety and efficiency of outsourcing computation have attracted widespread attention. By outsourcing computation, outsourcers with limited ability can outsource complex computing tasks to powerful servers, which will greatly reduce users’ computational costs. However, outsourcing computing tasks to servers also presents some security risks because the servers are not completely trusted. Verifiable outsourcing schemes can keep the information of users confidential and verify computational results returned from the server. At present, verifiable outsourcing schemes have involved in many aspects in cryptography, such as modular exponentiation [1,2], polynomial operations [3], attribute-based encryption operations [4,5], image feature extraction [6], and so on.

Modular exponentiation is one of the most time-consuming and commonly used operations in cryptography, and many outsourcing schemes for modular exponentiations have been proposed. Hohenbergerd et al. [7] first proposed an outsourcing scheme for single modular exponentiation with two non-colluding servers, where the outsourcer could check the fault that the servers might make with a probability of 1/2, and they also defined the security model of outsourcing calculation. Then Wang et al. [8] presented an outsourcing solution for batch modular exponentiations based on a single untrusted server with increased security, but the checkability was only 1/(s + 1)(where s is the number of modular exponentiations), which means it was not efficient and the checkability was only 1/2 for outsourcing single modular exponentiation. Different from the previous schemes, Liu et al. [9] did the work for outsourcing composite modular exponentiations. Ye et al. [10] proposed a new secure outsourcing algorithm based on a single server, and the verifiable probability is close to 1 while the outsourcer appended much computation cost. Chen et al. [11] firstly presented an efficient outsourcing algorithm for bilinear pairing based on two untrusted servers and the outsourcer need not any expensive operations in their algorithm. Then another outsourcing algorithm was proposed with improved checkability based on two servers for bilinear pairing [12]. Recently, Ren et al. [13] presented a new outsourcing algorithm of bilinear pairing with a verifiability of close to 1 if one of the servers misbehaved, which improved the checkability without an interactive operation between the server and the outsourcer.

In identity-based cryptography, the user’s identity is directly used as a public key, and the private key generator needs to generate a private key or perform key update for each user. The identity-based cryptography was firstly proposed in 1984 by Shamir [14], but the first $\text{IBE}$ scheme was constructed by Boneh and Franklin in 2001 [15]. In order to reduce the risk of key leakage, Ren et al. [16] proposed an identity-based parallel key encryption scheme, then Yu et al. [17] presented a securer solution because this algorithm supports frequent key updates without increasing the risk of key leakage. With the increase of users, the calculation burden of PKG will be heavy and it may cause the bottleneck of the system. In order to solve this problem effectively, Li et al. [18] proposed an outsourced deletion algorithm based on identity encryption scheme, which transfers the calculation burden of deleting users from PKG to cloud server. Recently, Ren et al. [19] firstly proposed a verifiable algorithm for outsourcing private key generation in the IBE scheme. Based on the $\text{LW}-\text{IBE}$ scheme [20], PKG can outsource the tasks of generating private keys and verify the correctness of returned results. This scheme can verify the results with a probability of 1 if one of the servers returned fault results, but it is based on two untrusted servers. So far, there is no relevant algorithm proposed based on a single server.

Our contributions: In this paper, we introduce the concept of verifiable computation into the identity-based encryption scheme, and then propose an IBE scheme that includes an outsourcing private key generation algorithm. In the proposed scheme, PKG outsources the tasks of generating the private key and verifies the returned results effectively. The outsourcing algorithm is based on a single server and it can greatly reduce the computational cost of PKG, meanwhile, the server cannot obtain PKG or the private key of any user during the outsourcing process. The PKG can detect the failure with a probability of about 1 if the server misbehaves, the experiment shows the time cost for PKG is much smaller than that of generating the private keys directly and the server in the outsourcing algorithm.

2. DEFINITION AND SECURITY MODEL

In this section, we introduce some definitions including bilinear groups with the order of composite number, the identity-based encryption scheme and the security model of $\text{IBE}$.

2.1 Bilinear Groups with Order of Composite Number

People first presented bilinear groups with the order of composite number in [20], the algorithm takes security parameter $\lambda$ as input and then outputs ($N=p_1{p}_2{p}_3,G,G_T,e$), where $p_1,p_2,p_3$ are distinct primes, $G$ and $G_T$ are cyclic groups with order $N=p_1{p}_2{p}_3$, if it has following conditions, then $e$: $G\times G\to G_T$ is a bilinear map:

1. (Bilinear): $\mathrm{\forall }g,h\in ,G$, $a,b\in Z_N$, $e\left(g^a,h^b\right)=e(g,h{)}^{ab}$.

2. (Non-degenerate): $\mathrm{\exists }g\in G$, which makes $e\left(g,g\right)$ is a generator of $G_T$.

3. (Computable): There is an efficient algorithm to compute $e\left(g,h\right)$ for all $g\in G,h\in G$.

Let $G_{p_1},G_{p_2},G_{p_3}$ represent the subgroups of $G$ with order $p_1,p_2,p_3,$ respectively. $G_{r,p_1}$, $G_{r,p_2}$, $G_{r,p_3}$ represent the subgroups of $G_T$ with order $p_1,p_2,p_3$, respectively. So $G=G_{p_1}\times G_{p_2}\times G_{p_3}$, $G_T=G_{r,p_1}\times G_{r,p_2}\times G_{r,p_3}$. Assume $\text{g}$ is a generator of $\text{G}$, and then $g^{p_2{p}_3}$, $g^{p_1{p}_3}$, $g^{p_1{p}_2}$ are generators of $G_{p_1}$, $G_{p_2}$, $G_{p_3}$ respectively, $\mathrm{\forall }{h}_i\in G_{pi}$, $h_j\in G_{pj}$ and $i\ne j$, we have $e\left(h_i,h_j\right)=1$. If $h_1\in G_{p_1}$, $h_2\in G_{p_2}$, since that $g^{p_1{p}_2{p}_3}=g^N=1$, then, for some $a$ and $b,h_1=(g^{p_2{p}_3}{)}^a$, $h_2=(g^{p_1{p}_3}{)}^b$, and $e\left(h_1,h_2\right)=(g^{a{p}_3},g^b{)}^{p_1{p}_2{p}_3}=1$.

2.2 Identity-Based Encryption Scheme

An IBE scheme is usually composed of four aspects, including Setup, KeyGen, Encrypt, and Decrypt algorithms [20], which typically involves two entities, PKG, and users (including sender and receiver). If PKG sends the task of outsourcing private key generation to the server, the $\text{KeyGe}{\text{n}}_{\mathrm{Out}}$ algorithm will be added and the scheme consists of the following algorithms.

Setup ($\mathit{\lambda }$): The setup algorithm takes a security parameter $\lambda$ as input, and outputs the master key $MK$ and the public key $PK$. The key $PK$ is public and the master key is kept secret.

KeyGen ($\mathit{M}\mathit{K}$,$\mathit{I}\mathit{D},\mathit{P}\mathit{K}$): The private key generation algorithm takes the public key $PK$, an identity $ID$ and the master key $MK$ as input, and outputs a private key $\text{S}{\text{K}}_{ID}$ corresponding to the identity $ID$.

Encrypt ($\mathit{M}$,$\mathit{I}\mathit{D},\mathit{P}\mathit{K}$): The encryption algorithm takes an identity $ID$, a public key $PK$ and a message $M$ as input, and outputs the ciphertext $CT$.

Decrypt ($\mathit{C}\mathit{T},\mathit{S}{\mathit{K}}_{\mathit{I}\mathit{D}},\mathit{P}\mathit{K}$): The decryption algorithm takes the ciphertext $CT$, a private key $\text{S}{\text{K}}_{ID}$ and the public key $PK$ as input, and it returns a message $M$ or an error $\mathrm{\perp }$.

If PKG outsources the task of generating private keys to the server, then the following algorithm is appended. The computation model of the scheme is shown in Figure 1.

Figure 1: Computation model of the scheme

$\mathbf{K}\mathbf{e}\mathbf{y}\mathbf{G}\mathbf{e}{\mathbf{n}}_{\mathbf{O}\mathbf{u}\mathbf{t}}$($\mathit{I}\mathit{D}$): The algorithm takes the identity $ID$ as input, PKG generates outsourcing private key $\text{O}{\text{K}}_{ID}$ and sends it to the server. When the server returns the calculation results $\text{C}{\text{R}}_{ID}$, we verify the results correct or not, if correct, then calculate the user’s private key $\text{S}{\text{K}}_{ID}$, otherwise return an error $\mathrm{\perp }$.

2.3 Security Model of an $\text{IBE}$ Scheme

We first introduce the full security model against the chosen-plaintext attack (CPA) in an $\text{IBE}$ scheme, and then introduce the security model of an IBE scheme which adds the outsourcing private key generation algorithm. A game between a challenger and an adversary $A$ can describe them.

In the following games, we define the advantage of $A$ and the scheme is secure if the advantage is negligible.

Definition 1:

(IND-ID-CPA) Through the following games, the definition of indistinguishability of an $\text{IBE}$ scheme under the chosen-plaintext attack is given [20]. The game contains 2 participants: challenger and adversary $A$.

Setup: The challenger executes the Setup algorithm to get the public key $PK$ and the master key $MK$, which then sends the public key $PK$ to attacker $A$ while ensuring that $MK$ is secret.

Phase 1: The attacker $A$ adaptively issues.

Private key query: the attacker $A$ sends an identity $ID$ to the challenger, then the challenger runs the KeyGen algorithm, and sends the private key of identity to the attacker $A$.

Challenge: $A$ sends an identity $I{D}^{\ast }$ and two same length messages $M_0,M_1$ to the challenger, in Phase 1, $I{D}^{\ast }$ has not been executed the private key query. The challenger randomly chooses a bit $\beta \in \left\{0,1\right\}$ and forms the ciphertext $C{T}^{\ast }=\text{Encrypt}\left(PK,M_{\beta },I{D}^{\ast }\right)$, and then returns $C{T}^{\ast }$ to $A$.

Phase 2: The adversary $A$ continues to issue private key queries and the challenger responds queries adaptively. However, $I{D}^{\ast }$ will not been executed the private key query.

Guess: $A$ outputs guess ${\beta }^{\mathrm{\prime }}\in \left\{0,1\right\}$.

Definition 2:

(IND-OID-CPA) Through the following games, the definition of indistinguishability of an $\text{IBE}$ scheme under the chosen-plaintext attack is given after adding private key generation algorithm [19]. The game contains two participants: challenger and adversary $A$.

Setup: The challenger executes the Setup algorithm to get the public key $PK$ and the master key $MK$, which then sends the public key $PK$ to attacker $A$ while ensuring that $MK$ is secret.

Phase 1: First the challenger initializes an empty outsourcing list $\text{OL}$ and the adversary $A$ adaptively issues queries.

Private key query: the adversary $A$ sends an identity $ID$ to the challenger, then the challenger runs the KeyGen algorithm, and sends the private key of identity to the adversary $A$.

Outsourcing key query: The adversary $A$ sends $ID$ to the challenger and then the challenger search $\left(ID,O{K}_{ID}\right)$ in $\text{OL}$. If it exists, then returns $O{K}_{ID}$ to $A$, Otherwise, generates $O{K}_{ID}$ and returns it to $A$.

Challenge: $A$ sends an identity $I{D}^{\ast }$ and two same length messages $M_0,M_1$ to the challenger, in Phase 1, $I{D}^{\ast }$ has not been executed the private key query or outsourcing key query. The challenger randomly chooses a bit $\beta \in \left\{0,1\right\}$ and forms the ciphertext $C{T}^{\ast }=\text{Encrypt}\left(PK,M_{\beta },I{D}^{\ast }\right)$, then returns $C{T}^{\ast }$ to the adversary.

Phase 2: The adversary $A$ continues to issue private key queries and the challenger responds queries adaptively. However, $I{D}^{\ast }$ will not been executed the private key query or outsourcing key query.

Guess: $A$ outputs guess ${\beta }^{\mathrm{\prime }}\in \left\{0,1\right\}$.

In the above two games, we define the advantage of $A$ as $|Pr\left[{\beta }^{,}=\beta \right]-\left(1/2\right)|$.

Different from Definition 1, Definition 2 adds the outsourcing private key generation algorithm, and it mainly adds the outsourcing key query in Phase 1. Moreover, in the above two security models, $I{D}^{\ast }$ will not been executed the private key query or outsourcing key query.

3. IDENTITY-BASED ENCRYPTION WITH OUTSOURCED PRIVATE KEY GENERATION

This section proposes an algorithm with verifiable outsourced private key generation based on the $\text{LW}-\text{IBE}$ scheme [20], PKG can verify the correctness of the returned results effectively, but the server cannot obtain the PKG or the private key of any user.

3.1 $\text{LW}-\text{IBE}$ Scheme

In this section, we first review the $\text{LW}-\text{IBE}$ scheme [20].

Setup($\mathit{\lambda }$): PKG runs the Setup algorithm, which selects a bilinear group $G$ of order $N=p_1{p}_2{p}_3$, where $p_1,p_2,p_3$ are three large primes. Let $G_{pi}$ be a subgroup of order $p_i$ in $\text{G}$, where $i\in \left\{1,2,3\right\}$. Then PKG randomly chooses $g,u,h\in G_{p_1}$, $\alpha \in Z_N$, and generates a public key $\text{PK}=\left\{N,g,u,h,e{\left(g,g\right)}^{\alpha }\right\}$, and the master key is $\alpha \in Z_N$ and a generator of $G_{p_3}$.

KeyGen ($\mathbf{M}\mathbf{K},\mathit{I}\mathit{D},\mathit{P}\mathit{K}$): PKG randomly selects $r_{ID}\in Z_N$, $R_{11},R_{12}\in G_{p_3}$ based on identity $ID$, and computes: $K_1=g^{r_{ID}}{R}_{11},K_2=g^{\alpha }(u^{ID}h{)}^{r_{ID}}{R}_{12}.$ Then PKG outputs $S{K}_{ID}=\left(K_1,K_2\right)$ corresponding to $ID$.

Encrypt ($\mathit{M},\mathit{I}\mathit{D},\mathit{P}\mathit{K}$): For an identity $ID$ and a message $M\in G_T$, we randomly choose $s\in Z_N$ and computes: $C_0=Me(g,g{)}^{\alpha s},C_1=(u^{ID}h{)}^s,C_2=g^s.$ Then creates the ciphertext $CT=\left(C_0,C_1,C_2\right)$.

Decrypt ($\mathit{C}\mathit{T},\mathit{S}{\mathit{K}}_{\mathit{I}\mathit{D}},\mathit{P}\mathit{K}$): Take as input an identity $ID$, a private $S{K}_{ID}$ and a ciphertext $CT$, then it decrypts the ciphertext as below: $\begin{array}{rl}& \frac{C_{0}e\left(C_1,K_1\right)}{e\left(C_2,K_2\right)}\\ & =Me(g,g{)}^{\alpha s}\frac{e\left({\left(u_1^{ID}{h}_1\right)}^s,g^{r_{ID}}{R}_{11}\right)}{e\left(g^s,g^{\alpha }{\left(u^{ID}h\right)}^{r_{ID}}{R}_{12}\right)}\\ & =\frac{Me{\left(g,g\right)}^{\alpha s}}{e\left(g^s,g^{\alpha }\right)}\\ & =M.\end{array}$ Since $(u_1^{ID}{h}_1{)}^s$, $g^s\in G_{p_1}$, $R_{11},R_{12}\in G_{p_3}$, then $e\left({\left(u_1^{ID}{h}_1\right)}^s,g^{r_{ID}}{R}_{11}\right)=e\left(g^s,R_{12}\right)=1.$ Thus, the ciphertext can be decrypted successfully.

3.2 The $\text{IBE}$ Scheme with Verifiable Outsourced Key Generation

In this section, we propose an $\text{IBE}$ scheme with verifiable outsourced key generation. The Setup, KeyGen, Encrypt, and Decrypt algorithms are run as the $\text{LW}-\text{IBE}$ scheme, and then we only introduce the identity-based encryption with verifiable outsourced key generation. In [7], a subroutine $\text{Rand}$ is used to generate random tuple with the form of $\left(c,c^{-1},g^c\text{mod}p\right)$, where $c\in Z_q$, so that the computations of the outsourcer can be speeded, and $U$ represents the server.

$\mathit{K}\mathit{e}\mathit{y}\mathit{G}\mathit{e}{\mathit{n}}_{\mathit{O}\mathit{u}\mathit{t}}$($\mathit{I}\mathit{D}$): (1) Firstly PKG computes $g^{\alpha }$ and stores it in the system, then running $\text{Rand}$ sixth to create six blinding pairs: $\begin{array}{rl}& \left(t_1,t_1^{-1},g^{t_1}\right),\left(t_2,t_2^{-1},g^{t_2}\right),\left(t_3,t_3^{-1},g^{t_3}\right),\left(t_4,t_4^{-1},g^{t_4}\right),\\ & \left(t_5,t_5^{-1},g^{t_5}\right)\text{and}\left(t_6,t_6^{-1},g^{t_6}\right).\end{array}$ We denote $v_1=g^{t_1}\text{mod }p$, $v_2=g^{t_2}\text{mod}p$, so that we get the first logical divisions: $\begin{array}{rl}(u^{ID}h{)}^{r_{ID}}& =u^{ID{r}_{ID}}{h}^{r_{ID}}\\ & =(v_{1}m{)}^{ID{r}_{ID}}(v_{2}n{)}^{r_{ID}}\\ & ={v_1}^{ID{r}_{ID}}{v_2}^{r_{ID}}{m}^{ID{r}_{ID}}{n}^{r_{ID}}\\ & ={\text{g}}^{ID{r}_{ID}{t}_1}{g}^{r_{ID}{t}_2}{m}^{ID{r}_{ID}}{n}^{r_{ID}},\end{array}$ where $m=u/v_{1}modp$, $n=h/v_{2}modp$.

Then we get the second logical divisions: $g^{ID{r}_{ID}{t}_1}{g}^{r_{ID}{t}_2}{m}^{ID{r}_{ID}}{n}^{r_{ID}}=g^{t_3}{g}^{t_4}{g}^{r_1}{g}^{r_2}{m}^{ID{r}_{ID}}{n}^{r_{ID}},$ where $\begin{array}{rl}{r}_1& =ID{r}_{ID}{t}_1-t_{3}modq,\\ r_2& =r_{ID}{t}_2-t_{4}modq.\end{array}$

• (2) PKG first selects $t$ random numbers $c_1,c_2\dots \dots c_t,$ then randomly chooses $k\in \left[1,t\right],$ $x_1$ is a small integer [from 1 to 10] and computes: $\begin{array}{rl}{d}_1& =ID{r}_{ID}-\sum _{j=1}^k{c}_j-x_1,\\ d_2& =ID{r}_{ID}-\sum _{j=k+1}^t{c}_j,\end{array}$

Then we set a collection $A=\left\{c_1,c_2\dots \dots c_t,d_1,d_2\right\}$, and use a random permutation function to do the following $A\to A_1=\left\{g_1,g_2\dots \dots g_{t+2}\right\}$.

• (3) Then PKG selects $t$ random numbers $e_1,e_2\dots \dots e_t,$ then randomly chooses $k\in \left[1,t\right],$ $x_2$ is a small integer [from 1 to 10] and computes: $\begin{array}{rl}{d}_3& =r_{ID}-\sum _{j=1}^k{e}_j-x_2,\\ d_4& =r_{ID}-\sum _{j=k+1}^t{e}_j,\end{array}$

Then we set a collection $B=\left\{e_1,e_2\dots \dots e_t,d_3,d_4\right\}$, and use a random permutation function to do the following $B\to B_1=\left\{l_1,l_2\dots \dots l_{t+2}\right\}$.

Then we set $O{K}_{ID}=\left(r_1,r_2,x_1,x_2,A_1,B_1,k,m,n\right)$.

• (4) PKG makes queries to $U$ in random order: $\begin{array}{rl}& U\left(g_i,m\right)\to m^{g_i},i\in \left[1,t+2\right],\\ & U\left(l_i,n\right)\to n^{l_i},i\in \left[1,t+2\right],\\ & U\left(r_1/t_5,g^{t_5}\right)\to g^{r_1},\\ & U\left(r_2/t_6,g^{t_6}\right)\to g^{r_2},\\ & U\left(x_1,m\right)\to m^{x_1},\\ & U\left(x_2,n\right)\to n^{x_2}.\end{array}$

• (5) PKG verifies that the calculation is correct or not:

  1. If $\begin{array}{rl}& g^{-1}\left(i\right)=d_1,\text{then}{s}_1=m^{d_1},\\ & g^{-1}\left(i\right)=d_2,\text{then}{s}_2=m^{d_2},\\ & g^{-1}\left(i\right)\in \left\{c_1,c_2\dots \dots c_k\right\},\text{then}{s}_3=s_3\ast m^{c_i},\\ & g^{-1}\left(i\right)\in \left\{c_{k+1},c_{k+2}\dots \dots c_t\right\}\text{then}{s}_4=s_4\ast m^{c_i},\end{array}$ where $s_3$ and $s_4$ initial value are $1$.

  2. If $\begin{array}{rl}{l}^{-1}\left(i\right)& =d_3,\text{then}{s}_5=n^{d_3},\\ l^{-1}\left(i\right)& =d_4,\text{then}{s}_6=n^{d_4},\\ l^{-1}\left(i\right)& \in \left\{e_1,e_2\dots \dots e_k\right\},\text{then}{s}_7=s_7\ast n^{e_i},\\ l^{-1}\left(i\right)& \in \left\{e_{k+1},e_{k+2}\dots \dots e_t\right\},\text{then}{s}_8=s_8\ast n^{e_i},\end{array}$ where $s_7$ and $s_8$ initial value are $1$.

The verification calculation is as follows: $\begin{array}{rl}{m}^{d_1}\ast \prod _{j=1}^k{m}^{c_j}\ast m^{x_1}& =m^{d_2}\ast \prod _{j=k+1}^t{m}^{c_j},\\ n^{d_3}\ast \prod _{j=1}^k{n}^{e_j}\ast n^{x_2}& =n^{d_4}\ast \prod _{j=k+1}^t{n}^{e_j},\end{array}$ If not, PKG outputs “error”; otherwise, PKG randomly chooses $R_{21}^{\mathrm{\prime }}$, $R_{22}^{\mathrm{\prime }}\in G_{p_3}$, and computes: $\begin{array}{rl}{K}_1& =g^{r_{ID}}{R}_{21}^{\mathrm{\prime }},\\ K_2& =g^{\alpha }{g}^{t_3}{g}^{t_4}{g}^{r_1}{g}^{r_2}{m}^{ID{r}_{ID}}{n}^{r_{ID}}{R}_{22}^{\mathrm{\prime }}\\ & =g^{\alpha }{u}^{ID{r}_{ID}}{h}^{r_{ID}}{R}_{22}^{\mathrm{\prime }}\\ & =g^{\alpha }(u^{ID}h{)}^{r_{ID}}{R}_{22}^{\mathrm{\prime }}.\end{array}$ The private key corresponding to the $ID$ is $S{K}_{ID}=\left(K_1,K_2\right)$.

In the above outsourcing algorithm, the server need not know the relationship between $O{K}_{ID}$ and $ID$, and users only need to perform modular exponentiation operations once in the outsourcing process, which greatly reduces the computational cost of PKG, and the server cannot obtain the PKG or the private key of any user.

4. ANALYSIS OF THE SCHEME

This section analyzes the $\text{IBE}-\text{VOK}$ scheme, including the indistinguishability of the ciphertext and verifiability of the outsourcing results. Then, we show the computation cost comparison of PKG for generating private keys directly and outsourcing the task to a single server, and an efficiency comparison for different schemes with outsourced key generation. Finally, the simulation of the scheme is implemented.

4.1 Security Analysis

When the proposed scheme is under the choice of plaintext attack $\left(\text{CPA}\right)$, Theorem 1 and Theorem 2 prove the indistinguishability of the ciphertext and verifiability of the outsourcing results, respectively.

Theorem 1

(indistinguishability of ciphertext): Assuming that the $\text{LW}-\text{IBE}$ scheme [20] is completely secure under CPA attack, then the $\text{IBE}-\text{VOK}$ scheme is also completely secure under CPA attack.

Proof:

Suppose that an adversary $A$ can distinguish two different plaintexts with a probability of $\epsilon$ under the $\text{CPA}$ security model of the $\text{IBE}-\text{VOK}$ scheme, then the algorithm B can be constructed to distinguish two different plaintexts with the same probability of $\epsilon$ under the $\text{CPA}$ security model of the $\text{LW}-\text{IBE}$ scheme.

Let $C$ represent the challenger who answered $B$ in the $\text{LW}-\text{IBE}$ scheme, $A$ and $B$ perform the following steps:

Setup: $C$ sends $PK=\left\{N,g,u,h,e{\left(g,g\right)}^{\alpha }\right\}$ to $B$ as a public parameter of the $\text{LW}-\text{IBE}$ scheme, and $B$ returns $PK$ to $A$ as a public parameter of the $\text{IBE}-\text{VOK}$ scheme.

Phase1: Firstly, $B$ creates an empty outsourced list $OL$ and then performs the following inquiries.

Private key query: $A$ sends identity $ID$ to $B$, then $B$ sends the $ID$ to $C$ for private key query in the $\text{LW}-\text{IBE}$ scheme and $C$ generates $S{K}_{ID}=\left(K_1,K_2\right)$, where $K_1=g^{r_{ID}^{\mathrm{\prime }}}{R}_{11}$, $K_2=g^{\alpha }(u^{ID}h{)}^{r_{ID}^{\mathrm{\prime }}}{R}_{12}$, which is returned to $B$ and $B$ returns $S{K}_{ID}$ to $A$.

Outsourcing key query: $A$ sends identity $ID$ to $B$, $B$ searches $\left(ID,O{K}_{ID}\right)$ in $OL$ and returns $O{K}_{ID}$ to $A$ if it exists, otherwise randomly selects $r_{ID},a\in Z_N$, and calculates $O{K}_{ID}=\left(r_1,r_2,x_1,x_2,A_1,B_1,k,m,n\right)$, then adds the $\left(ID,O{K}_{ID}\right)$ to the outsourced list $OL$ and returns $O{K}_{ID}$ to $A$.

Challenge: $A$ sends two plaintexts $M_0,M_1$ of the same length and an identity $I{D}^{\ast }$ to $B$, where $I{D}^{\ast }$ does not perform the outsourcing key query or private key query. Then $B$ sends $\text{them}$ to $C$ to complete the challenge phase of the $\text{LW}-\text{IBE}$ scheme. $C$ randomly chooses $\beta \in \left\{0,1\right\}$, then generates ciphertext $C{T}^{\ast }=\left(C_0^{\ast },C_1^{\ast },C_2^{\ast }\right)$ of $M_{\beta }$, and returns $C{T}^{\ast }$ to $B$. At last, $B$ sends $C{T}^{\ast }$ to $A$ as the challenge ciphertext.

Phase2: $A$ continues to ask, and $B$ runs the same operation as Phase1. However, $I{D}^{\ast }$ can not been executed the outsourcing key query or private key query.

Guess: $A$ outputs ${\beta }^{\mathrm{\prime }}\in \left\{0,1\right\}$, $B$ also outputs ${\beta }^{\mathrm{\prime }}$ as a guess for $\beta$.

Then we analyze $B$’s success probability. When $A$ runs the outsourcing key query about identity $ID$, the value of $r_1,r_2,x_1,x_2,A_1,B_1,k,m,n$ can be obtained by $ID$ and $O{K}_{ID}$. If $A$ continues to ask $ID$ for private key query and it can obtain $S{K}_{ID}$. Therefore, if $A$ can break the $\text{IBE}-\text{VOK}$ scheme with a probability of $\epsilon$, then $B$ can also break the $\text{LW}-\text{IBE}$ scheme with the same probability of $\epsilon$.

In the above game, $B$ successfully simulates the full security model under the $\text{CPA}$ attack of the $\text{IBE}-\text{VOK}$ scheme. As in [20], the $\text{LW}-\text{IBE}$ scheme is completely secure under $\text{CPA}$ attack, similarly, the $\text{IBE}-\text{VOK}$ scheme is also completely secure under $\text{CPA}$ attack according to theorem 1.Then the verifiability of the $\text{IBE}-\text{VOK}$ scheme is proved as below.

Theorem 2

(verifiability of outsourcing results): In a malicious model, PKG can detect the error with a probability of $(2t+6)/(2t+8)$ if the server returns incorrect results in the veryfiable $\text{IBE}$ scheme, ($t$ represents the number of random numbers).

Proof:

Assume $U$ is a malicious server, at the end of the algorithm, the PKG verifies the result as below: (1) $m^{d_1}\ast \prod _{j=1}^k{m}^{c_j}\ast m^{x_1}=m^{d_2}\ast \prod _{j=k+1}^t{m}^{c_j},$(1) (2) $n^{d_3}\ast \prod _{j=1}^k{n}^{e_j}\ast n^{x_2}=n^{d_4}\ast \prod _{j=k+1}^t{n}^{e_j},$(2) Since the PKG sends $\left(r_1,r_2,x_1,x_2,A_1,B_1,k,m,n\right)$ to the server, and $U$ must return true values of $m^{g_i},n^{l_i},g^{r_1},g^{r_2},m^{x_1},n^{x_2}$. Otherwise, the Equations (1) and (2) cannot pass the verification successfully.

Therefore, if $U$ returns the error result, the PKG will surely detect this error with a probability of $(2t+6)/(2t+8)$ in the proposed $\text{IBE}-\text{VOK}$ scheme, ($t$ is the number of random numbers).

4.2 Efficiency Comparison

Suppose the system has a total of $m$ users. PKG can precompute $g^{\alpha }$ and store it in the system. The following is a computational comparison of PKG between generating private keys directly and outsourcing the task to a single server, as shown in Table 1.

Table 1: Computation cost comparison of PKG for generating keys directly and outsourcing the task to a single server

		Outsourcing calculation
Algorithm	PKG generates key directly	PKG	$U$
MExp	$3m+1$	1	$2tm+8m$
MM	$4m$	$2tm+15m$	0
Invoke($\text{Rand}$)	0	$6m$	0
Total(MM)	$\approx 4.5mn$	$\approx 1.5n$	$3tmn+12mn$

In Tables 1 and 2, $m$ represents the total number of system users and $n$ is the bit length of $N$. Note that $G$ and $G_T$ are cyclic groups of order $N=p_1{p}_2{p}_3$, where $p_1,p_2,p_3$ are all 512-bit primes. MExp, MM denote the computation of modular exponentiation and modular multiplication, $t$ is the number of random numbers.

Table 2: Computation cost comparison for different schemes with outsourced key generation

PKG calculation	Scheme [19]	This paper
Server	2	1
MExp	$m$+1	1
MM	7$m$	$2tm+15m$
Invoke(Rand)	$m$	$6m$
Total(MM)	$\approx 1.5mn$	$\approx 1.5n$

As we know, using the table-lookup method to invoke the Rand subroutine takes $\text{{O}}\left(1\right)$ MM, and using the square-and-multiply method to execute the modular exponentiation operation takes $1.5n$ MM. In the outsourcing algorithms, we omit other operations such as modular addition.

It can be seen from Table 1, if PKG directly generates the private keys for the users and need to perform $3m+1$ MExp, $4m$ MM operations and the total computation cost is roughly $4.5mn$ MM. Then if PKG outsources the task of generating private keys to a single server, it only needs to execute 1 MExp, $2tm+15m$ MM and $6m$ Rand operations for $m$ users, the total computation cost is roughly $1.5n$ MM. The server $U$ runs $2tm+8m$ MExp operations. Therefore, the cost of the PKG is much smaller than that of generating private keys directly.

As shown in Table 2, the proposed scheme is based on a single server compared with [19], and PKG only needs to perform modular exponentiation operations once during the outsourcing process. Moreover, with the increasing number of users in the system, the computation of PKG remains basically unchanged, and the total computation cost is roughly $1.5n$ MM in this paper. However, in scheme [19], the total computation cost is roughly $1.5mn$ MM and it is much more expensive than this scheme, so the scheme of this paper has more practical advantages.

4.3 Simulation Result

In this section, we provide the experiment evaluation to show the efficiency of the proposed algorithm based on one untrusted server. The PKG and the cloud server are simulated by Intel Core i5 Processor running at 3.2 GHz with 8G memory and Intel Xeon Processor running at 2.2, 2.19 GHz (two processors) with 128G memory, respectively. Note that $G$ and $G_T$ are cyclic groups of order $N=p_1{p}_2{p}_3$, where $p_1,p_2,p_3$ are all 512-bit primes. The programing language is Java.

In Figure 2, we give the time cost of PKG for generating private keys directly and outsourcing the task to the server of the IBE scheme respectively. In the figure, the abscissa represents the total number of users in the system and the ordinate represents the total time cost. It is obvious that the time cost for PKG and the server are less than half of generating private keys directly, with the increasing number of users in the system, the total calculation of the server and PKG is also less than generating private keys directly. For example, when the number of system users is $2^{11}$, the PKG calculation time is about 1100 s and the server is about 1400 s, however, the time cost of direct computation is about 4700 s, obviously, it is far higher than the sum of PKG and the server. Therefore, the algorithm of this paper will become more practical when the number of users is continuously increasing.

Figure 2: Simulation for the proposed IBE scheme with outsourced key generation

5. Conclusion

In this paper, we use combinatorial bilinear groups to propose a verifiable outsourcing algorithm for private key generation based on identity-based encryption. The scheme greatly reduces the time cost of PKG, and the server cannot obtain PKG or the private keys of any user during the outsourcing process. PKG outsources the tasks to a single server, and it can improve security and verify the correctness of outsourced results. Finally, the experimental results show that the total calculation of the server and PKG is far less than generating private keys directly.

Additional information

Funding

This work was supported by the National Natural Science Foundation of China [grant numbers U1736120, 61572309, U1536109], and open project of Shanghai Key Laboratory of Scalable Computing and Systems.

Notes on contributors

Ting Xue

Ting Xue received the BS degree on electrical and information engineering from Changshu Institute of Technology, China, in 2016. Currently, she is a graduate student at the School of Communication and Information Engineering in Shanghai University, Shanghai, China. Her research interests include applied cryptography and secure outsourcing computing. Email: [email protected]

Yanli Ren

Yanli Ren is an associate professor in School of Communication and Information Engineering at Shanghai University, China. She was awarded an MS degree in applied mathematics in 2005 from Shaanxi Normal University, China, and a PhD degree in computer science and technology in 2009 from Shanghai Jiao Tong University, China. Her research interests include applied cryptography, secure outsourcing computing, and network security.

Guorui Feng

Guorui Feng received the BS and MS degree in computational mathematic from Jilin University, China, in 1998 and 2001 respectively. He received PhD degree in electronic engineering from Shanghai Jiaotong University, China, 2005. From January 2006 to December 2006, he was an assistant professor in East China Normal University, China. During 2007, he was a research fellow in Nanyang Technological University, Singapore. Now, he is with the School of Communication and Information Engineering, Shanghai University, China. His current research interests include image processing, image analysis, and computational intelligence. Email: [email protected]