A No-Pairing Proxy Re-Encryption Scheme for Data Sharing in Untrusted Cloud

Abstract

To protect data sharing from leakage in untrusted cloud, proxy re-encryption is commonly exploited for access control. However, most proposed schemes require bilinear pair to attain secure data sharing, which gives too heavy burden on the data owner. In this paper, we propose a novel lightweight proxy re-encryption scheme without pairing. Our scheme builds the pre-encryption algorithm based on computational Diffie–Hellman problem, and designs a certificateless protocol based on a semi-trusted Key Generation Center. Theoretical analysis proves that our scheme is Chosen-Ciphertext-Attack secure. The performance is also shown to achieve less computation burden for the data owner compared with the state-of-the-art.

Supported by the National Key Research and Development Program of China (No. 2016YFB0801301, No. 2016YFB0800402); the National Natural Science Foundation of China (No. U1405254, No. U1536207).

1 Introduction

Booming cloud computing has been developing very fast for many years, which brings convenience for billions of users all over the world. However, widely used cloud service has also caught the attention of attackers which have conducted many cloud security accidents, especially cloud data leakage. Accumulating data leakage in cloud environment makes cloud service untrusted for users.

To protect cloud data from leakage, encryption access control mechanisms has been introduced for secure data sharing [16], including proxy re-encryption.

The notion of proxy re-encryption (PRE) was first introduced by Blaze et al. [1] in 1998, and they promoted the first bidirectional PRE scheme based on a simple modification of the El Gamal encryption scheme [13]. Proxy re-encryption (PRE) is a cryptographic scheme which efficiently solve the problem of delegation of decryption rights. It allows a semi-trusted proxy with re-encryption keys, generated by the delegator, to transform a ciphertext under a given public key of the delegator into a ciphertext of the same message under a different public key the delegatee, while learning nothing about the encrypted message. PRE schemes have many practical applications due to its transformation property, such as cloud storage [2], distributed file systems, encrypted email forwarding [1], outsourced filtering of encrypted spam and so on.

Most of the PRE schemes in practical applications are constructed based on either traditional Public Key Infrastructure (PKI) or Identity-Based Encryption (IBE) setting. In the PKI setting, the authenticity of a user’s public key is assured by Digital Certificates, which is digitally signed and issued by a trusted third party called the Certification Authority (CA). It is the management of certificates, which is a costly and a cumbersome process including the revocation, storage, distribution of certificates and so on, that inherently makes PRE schemes based on PKI setting inefficient. In the IBE setting, the secret keys of all the users are generated by a third party called the Private Key Generator (PKG), therefore brings the key-escrow problem.

To solve both certificate management problem in the PKI setting and key-escrow problem in the IBE setting, certificateless public key encryption (CLPKE) was first introduced by Al-Riyami and Paterson [4] in 2003. CLPKE combines the advantages of PKI and of IBE, while does not suffer from the aforementioned problems, therefore indicates a new direction for the construction of the PRE schemes. The notion of certificateless proxy re-encryption (CLPRE) was introduced by Sur et al. [5] in 2010.

We propose a lightweight proxy certificateless proxy re-encryption(CLPRE) scheme for data sharing in untrusted cloud. Our scheme builds the pre-encryption algorithm based on computational Diffie–Hellman problem, and designs a certificateless protocol based on a semi-trusted Key Generation Center. Compared with the proxy re-encryption schemes state-of-the-art, our CLPRE scheme can be more lightweight for data owner and achieve same security against Chosen Ciphertext Attack (CCA).

2 Related Work

Since the first bidirectional PRE scheme was promoted by Blaze et al. [1] in 1998, there have been lots of works and promotions about PRE scheme. Ateniese et al. [3] proposed a unidirectional PRE schemes in 2005, which is the first unidirectional PRE scheme based on bilinear pairings and achieves CPA-secure (chosen-plaintext attack, CPA).

Canetti et al. [6] and Libert et al. [7] proposed the first bidirectional multi-hop and the first unidirectional single hop scheme both achieve RCCA-secure (replayable chosen ciphertext attack) in the standard model. For greater security, the construction of CCA-secure (chosen-ciphertext attack, CCA) PRE scheme has become an significant issue. In 2008, Deng et al. [8] proposed a bidirectional CCA secure PRE scheme without the bilinear pairings. Later, Hanaoka et al. [9] proposed a generic construction of CCA secure PRE scheme in the standard model.

All the PRE schemes are constructed based on either traditional Public Key Infrastructure (PKI) or Identity-Based Encryption (IBE) setting. In order to avoid both certificate management problem in the PKI setting and key-escrow problem in the IBE setting, certificateless public key encryption (CLPKE) first introduced by Al-Riyami and Paterson [4] in 2003 is considered in the construction of the PRE schemes. In 2010, Sur et al. [5] first introduced the notion of CLPRE and proposed a CCA secure CLPRE scheme in the random oracle model, which was shown to be vulnerable to chosen ciphertext attack by Zheng et al. [10]. In 2013, a CLPRE scheme using bilinear pairings proposed by Guo et al. [11] satisfies RCCA-security in the random oracle model. A lot of works have been proposed during these years [17]. Unfortunately, construction of CLPRE schemes has so far depended on the costly bilinear pairings.

In 2005, Baek et al. [12] proposed an efficient certificateless public key encryption (CLPKE) scheme that does not rely on the bilinear parings. In 2014, Yang et al. [14] addressed a CLPRE scheme without bilinear pairing, which claimed to be CCA-secure in the random oracle model, yet was shown to be vulnerable to chain collusion attack in by Srinivasan et al. [15] in their work proposed in 2015. In that work, they proposed the first CCA-secure unidirectional certificateless PRE scheme without bilinear pairing under the Computational Diffie-Hellman (CDH) assumption in the random oracle model.

3 Model

In order to describe our lightweight proxy re-encryption scheme for data sharing in untrusted cloud more figurative and in details, Fig. 1 gives an overview of entities and their activities in this framework.

Fig. 1.

Model architecture of our lightweight proxy re-encryption scheme.

Data Owner: Owner encrypts his data and uploads the ciphertext to the Cloud. Owner decides which users are authorized to share data from cloud by generating re-encryption keys for those authorized to transform the ciphertext.

Data User: Authorized users can share data from cloud by download the transformed ciphertext from cloud and decrypt by their own.

Proxy: Proxy is a semi-trusted third party in untrusted cloud. It re-encrypt the ciphertext in cloud under the private key of data owner into a ciphertext of the same message under given private keys of authorized users, while learning nothing about the encrypted data.

KGC: Key Generation Center is a semi-trusted fourth party, which means it is honest but curious. KGC initialize the whole system, and generate partial keys for everyone in the system. Users can generate his own public key and private key from partial keys generated by KGC and secret value chosen by himself. At the same time, KGC does not have any information about the secret value generated by the user and hence cannot decrypt any ciphertext.

4 CLPRE Scheme

The detailed construction of our CLPRE scheme are as follows. User $i$ and user $j$ represent the data owner and the authorized user respectively.

• (1) Setup$\left( {1^{\upkappa } } \right)$: In the setup phase, on input a security parameter $1^{\upkappa }$, the Probabilistic Polynomial Time (PPT) algorithm run by the Key Generation Center (KGC) outputs the public parameters $params$ and master secret key $msk$. The algorithm works as below:

  Generate a $k$-bit prime $q$ and a group ${\mathbb{G}}$ of order $q$. Pick a random generator $g \in {\mathbb{G}}$, and then randomly pick $s \in {\mathbb{Z}}_{q}^{ *}$, compute $h = g^{s}$;

  Choose cryptographic hash functions $H_{1} :\left\{ {0,1} \right\}^{ *}\, \times\, {\mathbb{G}} \to {\mathbb{Z}}_{q}^{ *}$, $H_{2} :\left\{ {0,1} \right\}^{ *} \to {\mathbb{Z}}_{q}^{ *},\, H_{3} :{\mathbb{G}} \to \left\{ {0,1} \right\}^{{l + l_{0} }}$, $H_{4} :{\mathbb{G}} \to {\mathbb{Z}}_{q}^{ *}$, $H_{5} :\left\{ {0,1} \right\}^{ *} \to {\mathbb{Z}}_{q}^{ *}$.

  The public parameters are $params = \left\{ {q,l,l_{0} ,H_{1} ,H_{2} , H_{3} ,H_{4} ,H_{5} } \right\}$, where $l,l_{0}$ denote the bit-length of a message and a randomness respectively, and master secret key is $msk = s$, which is stored secretly. The message space is ${\mathcal{M}} = \left\{ {0,1} \right\}^{l}$.

• (2) PartialKeyExtract $\left( {params,msk,ID_{i} } \right)$: On input public parameters $params$, master secret key $msk$ and the user $i$’s identity $ID_{i}$, this algorithm run by KGC outputs the partial public key $ppk_{i}$ and the partial secret key $psk_{i}$.

  Pick a random $\alpha_{i} \in {\mathbb{Z}}_{q}^{ *}$, and compute $a_{i} = g^{{\alpha_{i} }}$, $x_{i} = \alpha_{i} + sH_{1} \left( {ID_{i} ,a_{i} } \right)$, return $\left( {ppk_{i} ,psk_{i} } \right) = \left( {a_{i} ,x_{i} } \right)$.

• (3) SetSecretValue $\left( {params,ID_{i} } \right)$: On input public parameters $params$, and user $i$’s identity $ID_{i}$, this algorithm run by user $i$ outputs user $i$’s secret value $v_{i}$.

  Pick a random $z_{i} \in {\mathbb{Z}}_{q}^{ *}$, return $v_{i} = z_{i}$.

• (4) SetPrivateKey $\left( {params,psk_{i} ,v_{i} } \right)$: On input public parameters $params$, user $i$’s partial secret key $psk_{i}$, user $i$’s secret value $v_{i}$, this algorithm run by user $i$ outputs user $i$’s secret key $sk_{i}$.

  Return $sk_{i} = \left( {x_{i} ,z_{i} } \right).$

• (5) SetPublicKey $\left( {params,ppk_{i} ,v_{i} } \right)$: On input public parameters $params$, user $i$’s partial public key $ppk_{i}$, user $i$’s secret value $v_{i}$, this algorithm run by user $i$ outputs user $i$’s public key $pk_{i}$.

  Compute $u_{i} = g^{{z_{i} }}$, return $pk_{i} = \left( {a_{i} ,u_{i} } \right)$.

• (6) ReEncryptKey $\left( {params,ID_{i} ,\left( {pk_{i} ,sk_{i} } \right),ID_{j} ,pk_{j} } \right)$: On input public parameters $params$, user $i$’s identity $ID_{i}$, user $i$’s cryptographic key pair $\left( {pk_{i} ,sk_{i} } \right)$, user $j$’s identity $ID_{j}$ and public key $pk_{j}$, this algorithm run by user $i$ outputs a re-encryption key $rk_{i \to j}$ from user $i$ to user $j$.

  Parse $pk_{i}$ as $\left( {a_{i} ,u_{i} } \right)$, $sk_{i}$ as $\left( {x_{i} ,z_{i} } \right)$ and $pk_{j}$ as $\left( {a_{j} ,u_{j} } \right)$, compute $V_{j} = a_{j} h^{{H_{1} \left( {ID_{j} ,a_{j} } \right)}}$, and $W_{ij} = H_{5} \left( {t_{j}^{{z_{i} }} \parallel u_{j}^{{x_{i} }} \parallel ID_{i} \parallel pk_{i} \parallel ID_{j} \parallel pk_{j} } \right)$. Then compute $B_{i} = \left( {x_{i} H_{4} \left( {u_{i} } \right) + z_{i} } \right)$, return $rk_{i \to j} = B_{i} W_{ij}$.

• (7) Encrypt $\left( {params,m,pk_{i} } \right)$: On input public parameters $params$, data $m \in {\mathcal{M} }\left( {{\mathcal{M}} = \left\{ {0,1} \right\}^{l} } \right)$, and user $i$’s public key $pk_{i}$, this algorithm run by user $i$ outputs a second level ciphertext $c_{i}$.

  Parse $pk_{i}$ as $\left( {a_{i} ,u_{i} } \right)$, pick a randomness $\sigma \in \left\{ {0,1} \right\}^{{l_{0} }}$, compute $V_{i} = a_{i} h^{{H_{1} \left( {ID_{i} ,a_{i} } \right)}}$, $r = H_{2} \left( {m\parallel \sigma \parallel ID_{i} \parallel u_{i} } \right)$, then compute $c_{1} = g^{r}$, $c_{2} = \left( {m\parallel \sigma } \right) \oplus H_{3} \left( {A_{i}^{r} } \right)$, in which $A_{i} = V_{i}^{{H_{4} \left( {u_{i} } \right)}} \cdot u_{i}$. Return $c_{i} = \left( {c_{1} ,c_{2} } \right)$.

• (8) ReEncrypt $\left( {params,c_{i} ,rk_{i \to j} } \right)$: On inputs public parameters $params$, a second level ciphertext $c_{i}$, a re-encryption key $rk_{i \to j}$, this algorithm run by proxy outputs a first level ciphertext $c_{j}$.

  Parse $c_{i} = \left( {c_{1} ,c_{2} } \right)$, compute ${\text{c}}_{1}^{ '} = {\rm{c}}_{1}^{{rk_{i \to j} }}$, ${\text{c}}_{2}^{ '}$ = $c_{2}$, in which $rk_{i \to j} = B_{i} W_{ij}$, $B_{i} = \left( {x_{i} H_{4} \left( {u_{i} } \right) + z_{i} } \right)$. Return $c_{j} = \left( {{\text{c}}_{1}^{ '} ,{\rm{c}}_{2}^{ '} } \right)$.

• (9) Decrypt $\left( {params,pk_{i} ,c_{i} } \right)$: On input public parameters $params$, user $i$’s public key $pk_{i}$, and a ciphertext $c_{i}$, this algorithm run by user $i$ outputs either a plaintext $m \in {\mathcal{M}}$ or an error symbol ⊥.

  • i. Decrypt2 $\left( {params,pk_{i} ,c_{i} } \right)$: The algorithm is run by the data owner user $i$.

    Parse $pk_{i}$ as $\left( {a_{i} ,u_{i} } \right)$, $sk_{i}$ as $\left( {x_{i} ,z_{i} } \right)$, $c_{i} = \left( {c_{1} ,c_{2} } \right)$, compute $\left( {m\parallel \sigma } \right) = c_{2} \oplus H_{3} \left( {c_{1}^{{\left( {x_{i} H_{4} \left( {u_{i} } \right) + z_{i} } \right)}} } \right)$, then compute $r = H_{2} \left( {m\parallel \sigma \parallel ID_{i} \parallel u_{i} } \right)$.

    Check if the equation holds: $g^{r} = c_{1}$.

    Return $m$ if it holds: $\left( {m\parallel \sigma } \right) = c_{2} \oplus H_{3} \left( {c_{1}^{{\left( {x_{i} H_{4} \left( {u_{i} } \right) + z_{i} } \right)}} } \right)$.

    Otherwise return ⊥, which implies the ciphertext $c_{i}$ is wrongful.

  • ii. Decrypt1 $\left( {params,pk_{i} ,c_{i} } \right)$: The algorithm is run by the authorized user $j$.

    Parse $pk_{i}$ as $\left( {a_{i} ,u_{i} } \right)$, $sk_{i}$ as $\left( {x_{i} ,z_{i} } \right)$, $c_{i} = \left( {{\text{c}}_{1}^{ '} ,{\rm{c}}_{2}^{ '} } \right)$, compute $V_{j} = a_{j} h^{{H_{1} \left( {ID_{j} ,a_{j} } \right)}}$, $W_{ji} = H_{5} \left( {V_{j}^{{z_{i} }} \parallel u_{j}^{{x_{i} }} \parallel ID_{i} \parallel pk_{i} \parallel ID_{j} \parallel pk_{j} } \right)$ and $\left( {m\parallel \sigma } \right) = c_{2}^{{\prime }} \,{ \oplus }\,H_{3} \left( {c_{1}^{{{\prime }1/W_{ji} }} } \right)$,$r = H_{2} \left( {m\parallel \sigma \parallel ID_{j} \parallel u_{j} } \right)$.

    Check if the equation holds: $\left( {V_{j}^{{H_{4} \left( {u_{j} } \right)}} \cdot u_{j} } \right)^{{r{{W_{ji} }} }} = c_{1}^{'}$.

    Return $m$ if it holds: $\left( {m\parallel \sigma } \right) = c_{2}^{{\prime }} \, \oplus \,H_{3} \left( {c_{1}^{{{\prime }1/W_{ji} }} } \right)$.

    Otherwise return ⊥, which implies the ciphertext $c_{i}$ is wrongful.

5 Correctness

5.1 Correctness of PartialKey

As we can see from the PartialKeyExtract algorithm, $a_{i} = g^{{\alpha_{i} }}$, $x_{i} = \alpha_{i} + sH_{1} \left( {ID_{i} ,a_{i} } \right)$, the equation $g^{{psk_{i} }} = g^{{x_{i} }} = g^{{\alpha_{i} + sH_{1} \left( {ID_{i} ,a_{i} } \right)}} = a_{i} h^{{H_{1} \left( {ID_{i} ,a_{i} } \right)}} = ppk_{i} h^{{H_{1} \left( {ID_{i} ,ppk_{i} } \right)}}$ will hold, if the partial cryptographic key pair $\left( {ppk_{i} ,psk_{i} } \right) = \left( {a_{i} ,x_{i} } \right)$ is properly generated by KGC.

5.2 Correctness of Ciphertext2

As we can see from the Encryt algorithm, $c_{1} = g^{r}$, $c_{2} = \left( {m\parallel \sigma } \right) \oplus H_{3} \left( {A_{i}^{r} } \right)$, the equation $g^{r} = g^{{H_{2} \left( {m\parallel \sigma \parallel ID_{i} \parallel u_{i} } \right)}} = g^{{H_{2} \left( {c_{2} \oplus H_{3} \left( {c_{1}^{{\left( {x_{i} H_{4} \left( {u_{i} } \right) + z_{i} } \right)}} } \right)\parallel ID_{i} \parallel u_{i} } \right)}} = c_{1}$ will hold, if $c_{i} = \left( {c_{1} ,c_{2} } \right)$ is a correctly second level ciphertext generated by user $i$.

5.3 Correctness of Ciphertext1

As we can see from the ReEncryt algorithm, $\text{c}_{1}^{'} = {\rm{c}}_{1}^{{rk_{i \to j} }} = \left( {g^{r} } \right)^{{rk_{i \to j} }}$, in which $rk_{i \to j} = B_{i} W_{ij}$, ${\text{c}}_{2}^{'} = c_{2} = \left( {m\parallel \sigma } \right) \oplus H_{3} \left( {A_{j}^{r} } \right)$, the equation $c_{1}^{'} = g^{{rB_{\varvec{j}} W_{ji} }} = A_{j}^{{rW_{ji} }} = \left( {V_{j}^{{H_{4} \left( {u_{j} } \right)}} \cdot u_{j} } \right)^{{H_{2} \left( {m\parallel \sigma \parallel ID_{j} \parallel u_{i} } \right)W_{ji} }} = \left( {V_{j}^{{H_{4} \left( {u_{j} } \right)}} \cdot u_{j} } \right)^{{H_{2} \left( {c_{2}^{'} \oplus H_{3} \left( {c_{1}^{{{\prime }1/W_{ji} }} } \right)\parallel ID_{j} \parallel u_{i} } \right)W_{ji} }}$ will hold, if $c_{i} = \left( {\text{c}_{1}^{'} ,{\rm{c}}_{2}^{'} } \right)$ is a correctly first level ciphertext generated by the proxy.

5.4 Correctness of Decrypt2

As mentioned above, $c_{1} = g^{r}$, $c_{2} = \left( {m\parallel \sigma } \right) \oplus H_{3} \left( {A_{i}^{r} } \right)$, hence $\left( {m\parallel \sigma } \right) = c_{2} \oplus H_{3} \left( {A_{i}^{r} } \right) = c_{2} \oplus H_{3} \left( {g^{{B_{i} r}} } \right) = c_{2} \oplus H_{3} \left( {c_{1}^{{B_{i} }} } \right) = c_{2} \oplus H_{3} \left( {c_{1}^{{\left( {x_{i} H_{4} \left( {u_{i} } \right) + z_{i} } \right)}} } \right)$, in which $A_{i} = V_{i}^{{H_{4} (u_{i} )}} \cdot u_{i}$, $B_{i} = \left( {x_{i} H_{4} \left( {u_{i} } \right) + z_{i} } \right)$.

5.5 Correctness of Decrypt1

As mentioned above, ${\text{c}}_{1}^{'} = {\rm{c}}_{1}^{{rk_{i \to j} }}$, $c_{2}^{'} = c_{2} = \left( {m\parallel \sigma } \right) \oplus H_{3} \left( {A_{j}^{r} } \right)$, hence $\left( {m\parallel \sigma } \right) = c_{2}^{'} { \oplus }H_{3} \left( {A_{j}^{r} } \right) = c_{2}^{'} { \oplus }H_{3} \left( {g^{{B_{j} r}} } \right) = c_{2}^{'} { \oplus }H_{3} \left( {c_{1}^{{B_{j} }} } \right) = c_{2}^{'} { \oplus }H_{3} \left( {c_{1}^{{'1/W_{ji} }} } \right)$.

5.6 Correctness of the Whole Scheme

For all $m \in {\mathcal{M}}$ and all users’ cryptographic key pair $\left( {pk_{i} ,sk_{i} } \right)$, $\left( {pk_{j} ,sk_{j} } \right)$, these algorithms should satisfy the following conditions of correctness:

• (a) $\text{Decrypt}_{2} \left( {params, sk_{i} ,\text{Encrypt}\left( {params,ID_{i} ,pk_{i} ,m} \right)} \right) = m$

• (b) $\text{Decrypt}_{1} \left( {params, sk_{j} ,\text{ReEncrypt}\left( {params,rk_{i \to j} ,c_{i} } \right)} \right) = m$

  where $c_{i} = \text{Encrypt}\left( {params,ID_{i} ,pk_{i} ,m} \right)$, $rk_{i \to j} = \text{ReEncryptKey}\left( {params,ID_{i} ,\left( {pk_{i} ,sk_{i} } \right),ID_{j} ,pk_{j} } \right)$.

6 Security Proof

Two types of adversaries, Type I adversary $\mathcal{A}_{{\mathbf{I}}}$ and Type II adversary ${\mathcal{A}}_{{\mathbf{II}}}$ are considered for a CL-PRE. ${\mathcal{A}_{{\mathbf{I}}}}$ models an attacker from the outside (i.e. anyone except the KGC) without access to the master secret key ${\text{msk}}$ but may replace public keys of entities (i.e. user ${\text{i}}$ or user ${\text{j}}$) with values of its choice. ${\mathcal{A}_{{\mathbf{II}}}}$ models an honest-but-curious KGC who has access to the master secret key ${\text{msk}}$, but is not allowed to replace public keys of entities. In our model, Type I adversary ${\mathcal{A}_{{\mathbf{I}}}}$ is not considered since

Here we focus on the Type II adversary ${\mathcal{A}_{{\mathbf{II}}}}$ only and prove the chosen ciphertext security of first level ciphertext.

Definition (CLPRE-CCA Security).

We say a CLPRE scheme is CLPRE-CCA secure if the scheme is 1st-IND-CLPRE-CCA secure and 2nd-IND-CLPRE-CCA secure.

Theorem 1 (1st-IND-CLPRE-CCA security).

The proposed CLPRE scheme is 1st-IND-CLPRE-CCA secure against Type-II adversary ${\mathcal{A}_{{\mathbf{II}}}}$ in the random oracle model, if the CDH assumption holds in ${\mathbb{G}}$.

Lemma 1.

Assume that ${\text{H}}_{1} ,{\rm{H}}_{2} , {\text{H}}_{3} ,{\rm{H}}_{4} ,{\text{H}}_{5}$ are random oracles, if there exists a 1st-IND-CLPRE-CPA Type I adversary ${\mathcal{A}}_{{\mathbf{II}}}$ against the proposed CLPRE scheme with advantage $\upepsilon$ when running in time ${\text{t}}$, making at most ${\text{q}}_{\rm{pk}}$ public key request queries, at most ${\text{q}}_{\rm{pak}}$ partial key extract queries, at most ${\text{q}}_{\rm{sk}}$ private key extract queries, at most ${\text{q}}_{\rm{pkr}}$ public key replacement queries, at most ${\text{q}}_{\rm{rk}}$ re-encryption key extract queries, at most ${\text{q}}_{\rm{re}}$ re-encryption queries, ${\text{q}}_{{{\rm{dec}}_{ 2} }}$ decrypt2 queries, ${\text{q}}_{{{\rm{dec}}_{ 1} }}$ decrypt1 queries, and ${\text{q}}_{{{\rm{H}}_{\text{i}} }}$ random oracle queries to ${\text{H}}_{\rm{i}} \left( {1 \le {\text{i}} \le 5} \right)$. Then, for any $0 < v < {\epsilon}$, there exists an algorithm $\mathcal{C}$ to solve the $(\rm{t}{^{\prime}}, {\upepsilon}{^{\prime}} )$-CDH problem in ${\mathbb{G}}$ with

$$\begin{aligned} {\text{t}}^{{\prime }} \le {\text{t}} & + ({\rm{q}}_{\text{H}} + 2{\rm{q}}_{{{\text{H}}_{ 1} }} + 2{\rm{q}}_{{{\text{H}}_{ 2} }} + {\rm{q}}_{{{\text{H}}_{ 3} }} + {\rm{q}}_{{{\text{H}}_{ 4} }} + {\rm{q}}_{{{\text{H}}_{ 5} }} + {\rm{q}}_{\text{pk}} + {\rm{q}}_{\text{pak}} + {\rm{q}}_{\text{sk}} + {\rm{q}}_{\text{rk}} + {\rm{q}}_{\text{re}} \\ &+ {\rm{q}}_{{{\text{dec}}_{ 2} }} + {\rm{q}}_{{{\text{dec}}_{ 1} }} )\,{\mathcal{O}}\left( 1 \right)\, + \,(2{\text{q}}_{\rm{pk}} + {\text{q}}_{\rm{pak}} + 2{\text{q}}_{\rm{sk}} + 5{\text{q}}_{\rm{rk}} + 6{\text{q}}_{\rm{re}} \\ + \,2{\text{q}}_{{{\rm{dec}}_{ 2} }} + 5{\text{q}}_{{{\rm{dec}}_{ 1} }} ){\text{t}}_{\rm{e}} \end{aligned} $$

$$ {\upepsilon}{^{\prime}} \ge \frac{1}{{\mathrm{q}_{\mathrm{{H}_{3} }} }}\left( {\frac{{2\left( {{\upepsilon} - {\rm{v}}} \right)}}{{\mathrm{e}\left( {1 +\mathrm{ q}_\mathrm{pak} + \mathrm{q}_\mathrm{rk} } \right)}} - \uptau } \right) $$

where ${\text{e}}$ is the base of the natural logarithm, we denote the time taken for exponentiation operation in group ${\mathbb{G}}$ as ${\text{t}}_{\rm{e}}$, and $\uptau$ denotes the advantage that ${\mathcal{A}_{{\mathbf{II}}}}$ can distinguish the incorrectly-formed re-encryption keys in our simulation from all correctly-formed re-encryption keys in a “real world” interaction.

Theorem 2 (2nd-IND-CLPRE-CCA security).

The proposed CLPRE scheme is 2nd-IND-CLPRE-CCA secure against Type-II adversary ${\mathcal{A}_{{\mathbf{II}}}}$ in the random oracle model, if the CDH assumption holds in ${\mathbb{G}}$.

Lemma 2.

Assume that ${\text{H}}_{1} ,{\rm{H}}_{2} , {\text{H}}_{3} ,{\rm{H}}_{4} ,{\text{H}}_{5}$ are random oracles, if there exists a 2nd-IND-CLPRE-CPA Type I adversary ${\mathcal{A}}_{{\mathbf{II}}}$ against the proposed CLPRE scheme with advantage $\upepsilon$ when running in time ${\text{t}}$, making at most ${\text{q}}_{\rm{pk}}$ public key request queries, at most ${\text{q}}_{\rm{pak}}$ partial key extract queries, at most ${\text{q}}_{\rm{sk}}$ private key extract queries, at most ${\text{q}}_{\rm{pkr}}$ public key replacement queries, at most ${\text{q}}_{\rm{rk}}$ re-encryption key extract queries, at most ${\text{q}}_{\rm{re}}$ re-encryption queries, ${\text{q}}_{{{\rm{dec}}_{ 2} }}$ decrypt2 queries, ${\text{q}}_{{{\rm{dec}}_{ 1} }}$ decrypt1 queries, and ${\text{q}}_{{{\rm{H}}_{\text{i}} }}$ random oracle queries to ${\text{H}}_{\rm{i}} \left( {1 \le {\text{i}} \le 5} \right)$. Then, for any $0 < v < \epsilon$, there exists an algorithm ${\text{C}}$ to solve the $\left( {\rm{t}}{^{\prime}},\upepsilon {^{\prime}} \right)$-CDH problem in ${\mathbb{G}}$ with

$$\begin{aligned} {\text{t}}^{{\prime }} \le {\rm{t}} & + ({\text{q}}_{\rm{H}} + {\text{q}}_{{{\rm{H}}_{ 1} }} + {\text{q}}_{{{\rm{H}}_{ 2} }} + {\text{q}}_{{{\rm{H}}_{ 3} }} + {\text{q}}_{{{\rm{H}}_{ 4} }} + {\text{q}}_{{{\rm{H}}_{ 5} }} + {\text{q}}_{\rm{pk}} + {\text{q}}_{\rm{pak}} + {\text{q}}_{\rm{sk}} + {\text{q}}_{\rm{rk}} + {\text{q}}_{\rm{re}} \\ &+ \,{\text{q}}_{{{\rm{dec}}_{ 2} }} + {\text{q}}_{{{\rm{dec}}_{ 1} }} )\,{\mathcal{O}}\left( 1 \right) + (2{\text{q}}_{\rm{pk}} + {\text{q}}_{\rm{pak}} + 2{\text{q}}_{\rm{sk}} + 5{\text{q}}_{\rm{rk}} + 6{\text{q}}_{\rm{re}} \\ + \,2{\text{q}}_{{{\rm{dec}}_{ 2} }} + 5{\text{q}}_{{{\rm{dec}}_{ 1} }} ){\text{t}}_{\rm{e}} \end{aligned} $$

$$ {\upepsilon}{^{\prime}} \ge \frac{1}{{\mathrm{q}_{{\mathrm{H}_{3} }} }}\left( {\frac{{2\left( {\upepsilon - {\rm{v}}} \right)}}{{\mathrm{e}\left( {1 + \mathrm{q}_{\mathrm{pak}} + \mathrm{q}_\mathrm{rk} } \right)}} - \uptau } \right) $$

where ${\text{e}}$ is the base of the natural logarithm, we denote the time taken for exponentiation operation in group ${\mathbb{G}}$ as ${\text{t}}_{\rm{e}}$, and $\uptau$ denotes the advantage that ${\mathcal{A}_{{\mathbf{II}}}}$ can distinguish the incorrectly-formed re-encryption keys in our simulation from all correctly-formed re-encryption keys in a “real world” interaction.

Proof.

We show how to construct an algorithm ${\mathcal{C}}$ which can solve the $\left( {\rm{{t}}}{^{\prime}},{\upepsilon} {^{\prime}} \right)$-CDH problem in group ${\mathbb{G}}$.

Suppose ${\mathcal{C}}$ is given a CDH challenge tuple $\left( {{\text{g}},{\rm{g}}^{\text{a}} ,{\rm{g}}^{\text{b}} } \right) \in {\mathbb{G}}^{3}$ with random unknown ${\text{a}},{\rm{b}} \in {\mathbb{Z}}_{\text{q}}^{*}$ as input. The goal of ${\mathcal{C}}$ is to compute the $g^{ab}$. ${ \mathcal{C}}$ act as challenger and play the 2nd-IND-CLPRE-CPA “Game II” with adversary ${\mathcal{A}}_{{\mathbf{II}}}$ as follows.

“Game II”: This is a game between ${\mathcal{A}}_{{\mathbf{II}}}$ and the challenger ${\mathcal{C}}$.

${\mathcal{A}}_{{\mathbf{II}}}$ has access to the master secret key ${\text{msk}}$, but is not allowed to replace public keys of entities.

Setup. ${ \mathcal{C}}$ takes a security parameter $1^{\upkappa }$, runs Setup$\left( {1^{\upkappa } } \right)$ algorithm to generate the system parameter ${\text{params}} = \left\{ {{\rm{q}},{\rm{l}},{\text{l}}_{0} ,{\rm{H}}_{1} ,{\text{H}}_{2} , {\rm{H}}_{3} ,{\text{H}}_{4} ,{\rm{H}}_{5} } \right\}$, and a master secret key ${\text{msk}} = {\rm{s}}$. ${\mathcal{C}}$ gives ${\text{params}}$ to ${\mathcal{A}}_{{\mathbf{II}}}$ while keeping ${\text{msk}}$ secret.

Random Oracle Queries. ${\text{H}}_{1} ,{\rm{H}}_{2} , {\text{H}}_{3} ,{\rm{H}}_{4} ,{\text{H}}_{5}$ are random oracles controlled by ${\mathcal{C}}$, who maintains six hash lists ${\text{Hlist}},\,{\rm{H}}_{ 1} {\text{list}},\,{\rm{H}}_{ 2} {\text{list}},\,{\rm{H}}_{ 3} {\text{list}},\,{\rm{H}}_{ 4} {\text{list}},\,{\rm{H}}_{ 5} {\text{list}}$. Whenever ${\mathcal{A}}_{{\mathbf{II}}}$ request access to any hash function, ${\mathcal{C}}$ responds as follows:

H queries: On receiving a query $\left( { < \rm{Q} > ,\upalpha } \right)$, ${ \mathcal{C}}$ searches ${\text{Hlist}}$ and returns $\upalpha$ as answer if found. Otherwise, chooses $\upalpha \in_{\rm{R}} {\mathbb{Z}}_{\rm{q}}^{*}$ and returns $\upalpha$. ${\mathcal{C}}$ adds $\left( { < \rm{Q} > ,\upalpha } \right)$ to the ${\text{Hlist}}$.

H₁ queries: On receiving a query $\left( { < \text{ID,a} >,{\rm{X}}} \right)$, ${ \mathcal{C}}$ searches ${\text{H}}_{ 1} {\rm{list}}$ and returns ${\text{X}}$ as answer if found. Otherwise, chooses ${\text{X}} \in_{{\rm{R}}} {\mathbb{Z}}_{{\text{q}}}^{*}$ and returns ${\text{X}}$. ${\mathcal{C}}$ adds $\left( { < \text{ID,a} >,\rm{X}} \right)$ to the ${\text{H}}_{ 1} {\rm{list}}$.

H₂ queries: On receiving a query $\left( { < \text{m},\upsigma,{\text{ID,u}} > ,{\rm{R}}} \right)$, ${ \mathcal{C}}$ searches ${\text{H}}_{ 2} {\rm{list}}$ and returns ${\text{R}}$ as answer if found. Otherwise, chooses ${\text{R}} \in_{{\rm{R}}} {\mathbb{Z}}_{{\text{q}}}^{*}$ and returns ${\text{R}}$. ${\mathcal{C}}$ adds $\left( { < {\text{m}},\upsigma ,{\text{ID,u}} > ,{\rm{R}}} \right)$ to the ${\text{H}}_{ 2} {\rm{list}}$.

H₃ queries: On receiving a query $\left( { < {\text{t,u}} > ,{\rm{A}}} \right)$, ${ \mathcal{C}}$ searches ${\text{H}}_{ 3} {\rm{list}}$ and returns ${\text{A}}$ as answer if found. Otherwise, chooses ${\text{A}} \in_{{\rm{R}}} {\mathbb{Z}}_{{\text{q}}}^{*}$ and returns ${\text{A}}$. ${\mathcal{C}}$ adds $\left( { < {\text{t,u}} > ,{\rm{A}}} \right)$ to the ${\text{H}}_{ 3} {\rm{list}}$.

H₄ queries: On receiving a query $\left( { < {\text{u}} > ,{\rm{B}}} \right)$, ${ \mathcal{C}}$ searches ${\text{H}}_{ 4} {\rm{list}}$ and returns ${\text{B}}$ as answer if found. Otherwise, chooses ${\text{B}} \in_{{\rm{R}}} {\mathbb{Z}}_{{\text{q}}}^{*}$ and returns ${\text{B}}$. ${\mathcal{C}}$ adds $\left( { < {\text{u}} > ,{\rm{B}}} \right)$ to the ${\text{H}}_{ 4} {\rm{list}}$.

H₅ queries: On receiving a query $\left( { < {\text{k}}_{ 1} ,{\rm{k}}_{ 2} ,{\text{ID}}_{\rm{i}} ,{\text{pk}}_{\rm{i}} ,{\text{ID}}_{\rm{j}} ,{\text{pk}}_{\rm{j}} > ,{\text{W}}} \right)$, ${ \mathcal{C}}$ searches ${\text{H}}_{ 5} {\rm{list}}$ and returns ${\text{W}}$ as answer if found. Otherwise, chooses ${\text{W}} \in_{\rm{R}} {\mathbb{Z}}_{\text{q}}^{*}$ and returns ${\text{W}}$. ${\mathcal{C}}$ adds $\left( { < {\text{k}}_{ 1} ,{\rm{k}}_{ 2} ,{\text{ID}}_{\rm{i}} ,{\text{pk}}_{\rm{i}} ,{\text{ID}}_{\rm{j}} ,{\text{pk}}_{\rm{j}} > ,{\text{W}}} \right)$ to the ${\text{H}}_{ 5} {\rm{list}}$.

Phase1. ${\mathcal{A}_{{\mathbf{II}}}}$ issues any one of the following queries adaptively.

Partial Key Compute. ${\mathcal{A}_{{\mathbf{II}}}}$ computes the partial private key pair $\left( {{\text{ppk}}_{{{\rm{ID}}_{\text{i}} }} ,{\rm{psk}}_{{{\text{ID}}_{\rm{i}} }} } \right)$ for any ${\text{ID}}_{\rm{i}}$ of its choice, by computing compute ${\text{a}}_{\rm{i}} = {\text{g}}^{{\upalpha_{\text{i}} }}$, ${\text{x}}_{\rm{i}} =\upalpha_{\text{i}} + {\rm{sH}}_{1} \left( {{\text{ID}}_{\rm{i}} ,{\text{a}}_{\rm{i}} } \right)$, $\left( {{\text{ppk}}_{\rm{i}} ,{\text{psk}}_{\rm{i}} } \right){ = }\left( {{\text{a}}_{\rm{i}} ,{\text{x}}_{\rm{i}} } \right)$. ${\mathcal{C}}$ maintains a list of partial keys computed by ${\mathcal{A}_{{\mathbf{II}}}}$ in a partial key list $\left( {{\text{ID}}_{\rm{i}} ,{\text{ppk}}_{{{\rm{ID}}_{\text{i}} }} ,{\rm{psk}}_{{{\text{ID}}_{\rm{i}} }} } \right)$.

Public key request queries. On input ${\text{ID}}$ by ${\mathcal{A}}_{{\mathbf{II}}}$, the challenger ${\mathcal{C}}$ searches whether there exists a tuple $\left( {{\text{ID}},{\rm{pk}}_{\text{ID}} ,{\rm{coin}}} \right) \in {\text{pklist}}$. If not, ${\mathcal{C}}$ runs algorithm SetPublicKey to generate the public key ${\text{pk}}_{\rm{ID}}$ for entity ${\text{ID}}$, then adds the tuple $\left( {{\text{ID}}, {\rm{pk}}_{\text{ID}} ,{\rm{coin}}} \right)$ to the ${\text{pklist}}$ and return ${\text{pk}}_{\rm{ID}}$ to ${\mathcal{A}_{{\mathbf{II}}}}$. Otherwise, ${\mathcal{C}}$ returns ${\text{pk}}_{\rm{ID}}$ to ${\mathcal{A}_{{\mathbf{II}}}}$. The value of ${\text{coin}}$ is decided the challenger ${\mathcal{C}}$’s strategy.

Private key extract queries. On input identity ${\text{ID}}$ by ${\mathcal{A}}_{{{\mathbf{II}}}}$, the challenger ${\mathcal{C}}$ searches whether there exists a tuple $\left( {{\text{ID}}, {\rm{pk}}_{\text{ID}} ,{\rm{coin}}} \right) \in {\text{pklist}}$. If ${\text{coin}} \ne \bot$, ${\mathcal{C}}$ runs algorithm SetPrivateKey to generate the private key ${\text{sk}}_{\rm{ID}}$ for entity ${\text{ID}}$. If ${\text{coin}} = \bot$, ${\mathcal{C}}$ returns “Reject”.

Re-encryption key extract queries. On input $\left( {{\text{ID}}_{\rm{i}} ,{\text{ID}}_{\rm{j}} } \right)$ by ${\mathcal{A}}_{{\mathbf{II}}}$, the challenger ${\mathcal{C}}$ searches whether there exists a tuple $\left( {{\text{ID}}_{\rm{i}} , {\text{pk}}_{{{\rm{ID}}_{\text{i}} }} ,{\rm{coin}}_{\text{i}} } \right) \in {\text{pklist}}$. If ${\text{coin}}_{\rm{i}} \ne \bot$, ${\mathcal{C}}$ responds by running algorithm ReEncryptKey to generate the re-encryption key ${\text{rk}}_{{{\rm{ID}}_{\text{i}} \to {\rm{ID}}_{\text{j}} }}$ for entity ${\text{ID}}_{\rm{i}} ,{\text{ID}}_{\rm{j}}$. Otherwise, ${\mathcal{C}}$ returns “Reject”.

Re-encryption queries. On input $\left( {{\text{ID}}_{\rm{i}} ,{\text{ID}}_{\rm{j}} {\text{C}}_{\rm{IDi}} } \right)$ by ${\mathcal{A}}_{{\mathbf{II}}}$, the challenger ${\mathcal{C}}$ searches whether there exists a tuple $\left( {{\text{ID}}_{\rm{i}} , {\text{pk}}_{{{\rm{ID}}_{\text{i}} }} ,{\rm{coin}}_{\text{i}} } \right) \in {\text{pklist}}$. If ${\text{coin}}_{\rm{i}} \ne \bot$, ${\mathcal{C}}$ responds by running algorithm ReEncrypt to convert the second level ciphertext ${\text{c}}_{{{\rm{ID}}_{\text{i}} }}$ into the first level ciphertext ${\text{c}}_{{{\rm{ID}}_{\text{j}} }}$. Otherwise, returns “Reject”.

Decryption queries for second level ciphertext. On input $\left( {{\text{ID}},{\rm{c}}} \right)$ by ${\mathcal{A}_{{\mathbf{II}}}}$, if ${\text{c}}$ is a second level ciphertext, ${\mathcal{C}}$ responds by running algorithm Decrypt₂ using the related private key to decrypt the C and returns the result to ${\mathcal{A}_{{\mathbf{II}}}}$. Otherwise, returns “Reject”.

Decryption queries for first level ciphertext. On input $\left( {{\text{ID}},{\rm{c}}} \right)$ by ${\mathcal{A}_{{\mathbf{II}}}}$, if ${\text{c}}$ is a first level ciphertext, ${\mathcal{C}}$ responds by running algorithm Decrypt₁ using the related private key to decrypt the ${\text{c}}$ and returns the result to ${\mathcal{A}_{{\mathbf{II}}}}$. Otherwise, returns “Reject”.

Challenge. Once the adversary ${\mathcal{A}_{{\mathbf{II}}}}$ decides that Phase 1 is over, it outputs the challenge identity ${\text{ID}}_{*}$, and two equal length plaintexts ${\text{m}}_{0} ,{\rm{m}}_{1} \in {\mathcal{M}}$. Moreover, ${\mathcal{A}}_{{\mathbf{II}}}$ is restricted to choose a challenge identity ${\text{ID}}_{*}$ that trivial decryption is not possible. ${\mathcal{C}}$ searches a tuple $\left( {{\text{ID}}_{ *} , {\rm{pk}}_{{{\text{ID}}_{ *} }} ,{\rm{coin}}_{ *} } \right) \in {\text{pklist}}$, then picks a random bit $\delta \in \left\{ {0,1} \right\}$, and computes the challenge ciphertext ${\text{c}}_{*}$ = Encrypt $\left( {{\text{params}},{\rm{ID}}_{ *} , {\text{pk}}_{{{\rm{ID}}_{ *} }} ,{\text{m}}_{\updelta} } \right)$, and returns ${\text{c}}_{*}$ to ${\mathcal{A}}_{{\mathbf{II}}}$.

Phase2. The adversary ${\mathcal{A}_{{\mathbf{II}}}}$ continues to query any of the above mentioned oracles with the restrictions defined in the IND-CLPRE-CCA “Game II”.

Guess. Finally, the adversary ${\mathcal{A}_{{\mathbf{II}}}}$ outputs a guess $\updelta^{\prime} \in \left\{ {0,1} \right\}$ and wins the game if $\updelta^{\prime} = \updelta$.

We define the advantage of ${\mathcal{A}_{{\mathbf{II}}}}$ in “Game II” as ${\text{Adv}}_{{{\rm{Game II}}, {\mathcal{A}}_{\text{II}} }}^{{{\rm{IND}} - {\text{CLPRE}} - {\rm{CCA }}}} \left( {\text{k}} \right) = \left| {\Pr \left[ {{\rm{X}}^{'} = {\text{X}}} \right] - \frac{1}{2}} \right|$.

A CLPRE scheme is said to be $\left( {{\text{t}},\upepsilon } \right)$-2nd-IND-CLPRE-CCA secure if for any ${\text{t}}$-time 2nd-IND-CLPRE-CCA Type-II adversary ${\mathcal{A}_{{\mathbf{II}}}}$ we have ${\text{Adv}}_{{{\rm{Game II}}, {\mathcal{A}}_{\text{II}} }}^{{{\rm{IND}} - {\text{CLPRE}} - {\rm{CCA }}}} \left( {\text{k}} \right) = \left| {\Pr \left[ {{\rm{X}}^{\prime} = {\text{X}}} \right]} \right| < \upepsilon$. We simply say that a CLPRE scheme is 2nd-IND-CLPRE-CCA secure if ${\text{t}}$ is polynomial with respect to security parameter ${\text{k}}$ and $\upepsilon$ is negligible.

7 Performance Evaluation

We make comparison between our scheme and Sur et al.’s scheme, Yang et al.’s scheme and Srinivasan et al.’s scheme, in terms of computational cost and ciphertext size. The number of “bignum” operations that CLPRE schemes need to perform are considered, other operations like addition or multiplication in group, XOR operation and conventional hash function evaluation is omitted, since the computation of these operations is efficient and far less than that of exponentiations or pairings. two modular exponentiations and the three modular exponentiations can be computed at a cost of about 1.17 and 1.25 exponentiations respectively, using simultaneous multiple exponentiation algorithm mentioned in [23]. The Map-To-Point hash function is special and far more expensive than conventional hash operation so it cannot be omitted.

From the Tables, we can find that all of our five algorithm listed in the table are much more computation efficient than Sur et al. [5]’s scheme and Yang et al. [14]’s scheme. Our encrypt algorithm and ciphertext size of the first and second level ciphertext are more efficient than those in Srinivasan et al. [15]’s scheme (Table 1).

Table 1. Comparison of CLPRE schemes’ performance.

8 Conclusion

We provide a lightweight proxy certificateless proxy re-encryption (CLPRE) scheme without pairing. We also prove security of our CLPRE scheme against Type II adversary ${\mathcal{A}_{{\mathbf{II}}}}$ under the CDH assumption in the random oracle model, and make comparison with representative CLPRE scheme. The results show that our scheme is much more computational and communicational efficient than Sur et al.’s scheme and Yang et al.’s scheme, and outperform Srinivasan et al.’s scheme in terms of space efficiency.