A Provably-Secure Unidirectional Proxy Re-encryption Scheme Without Pairing in the Random Oracle Model

Abstract

Proxy re-encryption (PRE) enables delegation of decryption rights by entrusting a proxy server with special information, that allows it to transform a ciphertext under one public key into a ciphertext of the same message under a different public key, without learning anything about the underlying plaintext. In Africacrypt 2010, the first PKI-based collusion resistant CCA secure PRE scheme without pairing was proposed in the random oracle model. In this paper, we point out an important weakness in the security proof of the scheme. We also present a collusion-resistant pairing-free unidirectional PRE scheme which meets CCA security under a variant of the computational Diffie-Hellman hardness assumption in the random oracle model.

S. Sharmila Deva Selvi—Postdoctoral researcher supported by Project No. CCE/CEP/22/VK&CP/CSE/14-15 on Information Security & Awareness(ISEA) Phase-II by Ministry of Electronics & Information Technology, Government of India.

A. Paul and C. Pandurangan—Work partially supported by Project No. CCE/CEP/22/VK&CP/CSE/14-15 on ISEA-Phase II.

1 Introduction

Proxy re-encryption is an important cryptographic primitive that allows a third party termed as proxy server, to transform the ciphertext of a user into a ciphertext of another user without learning anything about the underlying message. As pointed out by Mambo and Okamoto in [7], this is a common situation in practice where a data encrypted under $PK_{Alice}$ is required to be encrypted under $PK_{Bob}$, such as applications like encrypted email forwarding, distributed file systems and outsourced filtering of encrypted spam. Here, Alice provides a secret information to the proxy called Re-Encryption Key (but not her private key $SK_{Alice}$) allowing it to transform $E_{PK_{Alice}}(m)$ to $E_{PK_{Bob}}(m)$ without learning anything about m or $SK_{Alice}$.

Most of the proxy re-encryption schemes in the literature are based on costly bilinear pairing operation [1, 3, 6]. Despite recent advances in implementation techniques, bilinear pairing takes more than twice the time taken by modular exponentiation computation and is an expensive operation. As stated by Chow et al. [4], removing pairing operations from PRE constructions is one of the open problems left by [3]. Weng et al. [5] proposed the first CCA secure pairing-free PRE scheme, which was however shown to be vulnerable to collusion attack [10]. Collusion resistance, also termed as delegator secret security is a desirable property in many practical scenarios such as secure cloud services, which prevents a colluding proxy and malicious delegatees from recovering the private key of the delegator. In 2010, Chow et al. [4] proposed the first construction of a collusion-resistant CCA secure pairing-free PRE scheme. However, in our work, we point out a major weakness in the security proof of the scheme by Chow et al. We also provide a construction of a CCA-secure collusion-resistant pairing-free unidirectional single-hop proxy re-encryption scheme under the Computational Diffie-Hellman (CDH) and the Divisible Computational Diffie-Hellman (DCDH) hardness assumptions in the random oracle model. Prior to our work, Canard et al. [2] exposed a similar flaw in the security proof of the scheme due to Chow et al. [4], and provided a fix to the scheme using NIZKOE (Non-interactive Zero-Knowledge proofs with Online Extractors). We show that our scheme is more efficient than the modified scheme due to Canard et al., providing an efficient pairing-free unidirectional collusion-resistant PRE scheme.

Complexity Assumptions

We define the complexity assumptions used in the security proof of our scheme. Let $\mathbb {G}$ be a cyclic multiplicative group of prime order q.

Definition 1

Computational Diffie Hellman Assumption (CDH): The CDH problem in $\mathbb {G}$ is, given $(g, g^a , g^b ) \in \mathbb {G}^3$, compute $g^{ab}$, where $a, b \leftarrow \mathbb {Z}_q^*$.

Definition 2

Divisible Computational Diffie Hellman Assumption (DCDH): The DCDH problem in $\mathbb {G}$ is, given $(g, g^a , g^b ) \in \mathbb {G}^3$, compute $g^{b/a}$, where $a, b \leftarrow \mathbb {Z}_q^*$.

Definition 3

Discrete Logarithm Assumption (DL): The DL problem in $\mathbb {G}$ is, given $(g, g^a) \in \mathbb {G}^2$, compute a, where $a \leftarrow \mathbb {Z}_q^*$.

2 Analysis of a PRE Scheme by Chow et al. [4]

We review the scheme due to Chow et al. [4] and point out the weakness in the security proof of the scheme in this section.

2.1 Review of the Scheme

• Setup$({\lambda })\mathbf{: }$ Choose two primes p and q such that $q|p-1$ and the security parameter $\lambda$ defines the bit-length of q. Let $\mathbb {G}$ be a subgroup of $\mathbb {Z}_q^*$ with order q and let g be a generator of the group $\mathbb {G}$. Choose four hash functions: $H_1 : \{0, 1\}^{l_0} \times \{0, 1\}^{l_1} \rightarrow \mathbb {Z}_q^* , H_2 : \mathbb {G} \rightarrow \{0, 1\}^{ l_0 + l_1} , H_3 : \{0, 1\}^*\rightarrow \mathbb {Z}_q^*, H_4 : \mathbb {G} \rightarrow \mathbb {Z}_q^*$. The hash functions $H_1,H_2,H_3$ are modelled as random oracles in the security proof reduction. Here $l_0$ and $l_1$ are security parameters determined by $\lambda$, and the message space $\mathcal {M}$ is $\{0, 1\}^{l_0}$. Return the public parameters $PARAM = (q, \mathbb {G}, g, H_1 , H_2 , H_3 , H_4 , l_0 , l_1 )$.

• KeyGen$(U_i, PARAMS)\mathbf{: }$ To generate the private key $(SK_i)$ and the corresponding public key $(PK_i)$ of user $U_i$:

  • Pick $x_{i,1},x_{i,2}\in _R\mathbb {Z}_q^*$ and set $SK_i=(x_{i,1},x_{i,2})$.

  • Compute $PK_i=(PK_{i,1},PK_{i,2})=(g^{x_{i,1}},g^{x_{i,2}})$.

• ReKeyGen$(SK_i,PK_i,PK_j,PARAMS)\mathbf{: }$ On input of the private key $SK_i$ and public key $PK_i$ of user $U_i$ and user j’s public key $PK_j$, generate the re-encryption key $RK_{i\rightarrow j}$ as shown:

  • Pick $h \in _R \{0,1\}^{l_0}$, $\pi \in _R \{0,1\}^{l_1}$.

  • Compute $v=H_1(h,\pi )$, $V=PK_{j,2}^v$ and $W=H_2(g^v)\oplus (h||\pi )$.

  • Define $RK_{i\rightarrow j}^{\langle 1 \rangle }=\frac{h}{x_{i,1}H_4(PK_{i,2})+x_{i,2}}$.

  • Return $RK_{i\rightarrow j}=(RK_{i\rightarrow j}^{\langle 1 \rangle },V,W).$

• Encrypt$(m, PK_i, PARAMS)\mathbf{: }$ To encrypt a message $m\in \mathcal {M}$ under $PK_i$:

  • Pick $u\in _R \mathbb {Z}_q^*$, $\omega \in _R \{0,1\}^{l_1}$.

  • Compute $D=\big (PK_{i,1}^{H_4(PK_{i,2})} PK_{i,2} \big )^u.$

  • Compute $r=H_1(m,\omega )$.

  • Compute $E=\big (PK_{i,1}^{H_4(PK_{i,2})}PK_{i,2} \big )^r$ and $F=H_2(g^r)\oplus (m||\omega )$.

  • Compute $s=u+r\cdot H_3(D,E,F) \mod q$.

  • Output the ciphertext $\sigma _i=(D,E,F,s).$

• ReEncrypt$(\sigma _i, PK_i, PK_j,RK_{i\rightarrow j},PARAMS)\mathbf{: }$ On input of an original ciphertext $\sigma _i=(D,E,F,s)$ encrypted under the public key of the delegator $PK_i$, the public key of the delegatee $PK_j$, the re-encryption key $RK_{i\rightarrow j}$, re-encrypt $\sigma _i$ into a ciphertext $\hat{\sigma _j}$ under $PK_j$ as follows:

  • Check if the following condition holds to satisfy the well-formedness of ciphertexts, otherwise return $\bot$:

    $$\begin{aligned} \big (PK_{i,1}^{H_4(PK_{i,2})}PK_{i,2}\big )^s{\mathop {=}\limits ^{?}}D\cdot E^{H_3(D,E,F)} \end{aligned}$$

    (1)

  • If the condition holds, compute $\hat{E}=E^{RK_{i\rightarrow j}^{\langle 1 \rangle }}=g^{rh}$.

  • Output $\hat{\sigma _j}=(\hat{E},F,V,W)$.

• Encrypt$_1(m, PK_i, PARAMS)\mathbf{: }$ To generate a non-transformable ciphertext under public key $PK_i$ of a message $m\in \mathcal {M}$:

  • Pick $h\in _R \{0,1\}^{l_0}$ and $\pi \in _R\{0,1\}^{l_1}$.

  • Compute $v=H_1(h,\pi )$, $V=PK_{j,2}^{v}$ and $W=H_2(g^v)\oplus (h||\pi )$.

  • Pick $\omega \in _R \{0,1\}^{l_1}$ and compute $r=H_1(m,\omega )$.

  • Compute $\hat{E}=(g^r)^h$ and $F=H_2(g^r)\oplus (m||\omega )$.

  • Output the non-transformable ciphertext $\hat{\sigma _j}=(\hat{E},F,V,W)$.

• Decrypt$(\sigma _i, PK_i, SK_i, PARAMS)\mathbf{: }$ On input of a ciphertext $\sigma _i$, public key $PK_i$ and private key $SK_i=(x_{i,1},x_{i,2})$, decrypt according to two cases:

  • Original Ciphertext ${\sigma _i}=(D,E,F,s)$:

    $*$ :

    If Eq. (1) does not hold, return $\bot$.

    $*$ :

    Otherwise, compute $(m||\omega )=F\oplus H_2(E^{\frac{1}{x_{i,1}H_4(PK_{i,2})+x_{i,2}}}).$

    $*$ :

    Return m if $E{\mathop {=}\limits ^{?}}\big (PK_{i,1}^{H_4(PK_{i,2})}PK_{i,2} \big )^{H_1(m,\omega )}$ holds; else return $\bot$.

  • Transformed /Non-transformable Ciphertext $\hat{\sigma _i}=(\hat{E},F,V,W)$:

    $*$ :

    Compute $(h||\pi )=W\oplus H_2(V^{1/SK_{i,2}})$ and $(m||\omega )=F\oplus H_2(\hat{E}^{1/h})$.

    $*$ :

    Return m if $V{\mathop {=}\limits ^{?}}PK_{i,2}^{H_1(h,\pi )}$, $\hat{E}{\mathop {=}\limits ^{?}}g^{H_1(m,\omega )\cdot h}$ holds; else return $\bot$.

2.2 Weakness in the Security Proof of Chow et al.

In this section, we point out the weakness of the security proof for the PRE scheme by Chow et al. [4]. We show that the simulation of the oracles defined in the security proof of the scheme is not consistent with the real algorithm. This allows the adversary to distinguish the simulation run by the challenger from the real system. We demonstrate this flaw by considering the validity of the ciphertexts with respect to the ReEncrypt and Decrypt algorithm in the real system and the simulation (re-encryption oracle OReE and decryption oracles ODec respectively). To make it simple, we consider $PK_T$ as the public key of the target user in the challenge phase and the attack is posed in Phase-II after the challenge phase is over. We re-encrypt a ciphertext $\sigma _T$ under $PK_T$ into a ciphertext $\hat{\sigma }_j$ under $PK_j$ ($PK_j$ is corrupt) and further decrypt $\hat{\sigma }_{j}$. All the computations hereafter are done using $PK_T$ and $PK_j$.

First, we encrypt a message m under $PK_T$. Let us consider two forms of ciphertext $\sigma _{Real}= \langle D_{Real},E_{Real},F_{Real}, s_{Real} \rangle$ and $\sigma _{Fake}=\langle D_{Fake}, E_{Fake},$ $F_{Rand},s_{Fake} \rangle$. $\sigma _{Real}$ is the ciphertext obtained from the encryption algorithm Encrypt (i.e., encryption of m under $PK_{T}$ by executing the Encrypt$(m,PK_T,PARAMS)$). $\sigma _{Fake}$ is a cooked-up ciphertext that can pass the verification tests of ReEncrypt algorithm but not the Decrypt algorithm. We denote the algorithm for the construction of $\sigma _{Fake}$ as Encrypt$_{Fake}(m,PK_T)$, which is as follows:

• Pick $u_{Fake}\in _R\mathbb {Z}_q^*$.

• Compute $D_{Fake}=\Big ((PK_{T,1})^{H_4(PK_{T,2})}PK_{T,2}\Big )^{u_{Fake}}$.

• Pick $r_{Rand}\in _R\mathbb {Z}_q^*$. Here it should be noted that $r_{Rand}$ does not follow the actual algorithm, instead it is picked at random from $\mathbb {Z}_q^*$.

• Pick $\omega _{Fake}\in _R\{0,1\}^{l_1}$ and compute $r_{Fake}=H_1(m,\omega _{Fake}).$ Note that in the Encrypt algorithm, $r_{Fake}$ is the output of $H_1$ oracle on giving a message and a random string ($\omega _{Fake}$) of size $\{0,1\}^{l_1}$ as input.

• Compute $E_{Fake}=\Big ((PK_{T,1})^{H_4(PK_{T,2})}PK_{T,2}\Big )^{r_{Rand}}$.

• Choose $F_{Rand}\in _R \{0,1\}^{l_0+l_1}$. In the Encrypt algorithm, F is the encryption of the message along with a random string $\omega _{Fake}$ of length $\{0,1\}^{l_1}$. But in the construction of $\sigma _{Fake}$, we note that $F_{Rand}$ is chosen at random.

• Compute $s_{Fake}=u_{Fake}+r_{Rand}H_3(D_{Fake},E_{Fake},F_{Rand})\mod q$.

• Output the ciphertext $\sigma _{Fake}=( D_{Fake}, E_{Fake}, F_{Rand}, s_{Fake})$. Note that, $\sigma _{Fake}$ passes the ciphertext validation test of Eq. (1).

The important properties possessed by $\sigma _{Real}$ and $\sigma _{Fake}$ are:

• 1. Output of Decrypt($\sigma _{Real}, PK_T,SK_T,PARAMS$) is m and the output of $ODec(PK_T,\sigma _{Real})$ is m. This is because $\sigma _{Real}$ is a legitimate ciphertext of m produced by Encrypt algorithm.

• 2. Output of Decrypt($\sigma _{Fake},PK_T,SK_T,PARAMS$) and $ODec(PK_T,\sigma _{Fake})$ is $\bot$ as $\sigma _{Fake}$ fails to satisfy the validity check for the obtained message.

• 3. $\sigma _{Real}$ is a valid ciphertext and $\sigma _{Fake}$ is an invalid ciphertext with respect to both Decrypt algorithm and ODec oracle. Therefore, the simulation of the decryption algorithm is perfect.

• 4. Both $\sigma _{Real}$ and $\sigma _{Fake}$ are valid ciphertexts corresponding to the ReEncrypt algorithm. This is because $\sigma _{Real}$ is a legitimate ciphertext of m produced by the Encrypt algorithm. Again, $\sigma _{Fake}$ passes the ciphertext verification test of Eq. (1) and the algorithm computes the re-encrypted ciphertext $\hat{\sigma }_{Fake}=(\hat{E},F,V,W)$ as per the protocol where $\hat{E}_{Fake}=g^{r_{Fake}h}$.

Next, we re-encrypt both $\sigma _{Real}$ and $\sigma _{Fake}$ under the public key $PK_j$ of a corrupt user. Let us consider the following notations.

• $\hat{\sigma }_{Real}^{(Scheme)}\leftarrow$ ReEncrypt($\sigma _{Real},PK_T,PK_j,RK_{T\rightarrow j},PARAMS$).

• $\hat{\sigma }_{Real}^{(Oracle)}\leftarrow OReE(PK_T,PK_j,\sigma _{Real})$.

• $\hat{\sigma }_{Fake}^{(Scheme)}\leftarrow$ReEncrypt$(\sigma _{Fake},PK_T,PK_j,RK_{T\rightarrow j},PARAMS)$.

• $\hat{\sigma }_{Fake}^{(Oracle)}\leftarrow OReE(PK_T,PK_j,\sigma _{Fake})$.

Observations on $\hat{\sigma }_{Real}^{(Scheme)}$ and $\hat{\sigma }_{Real}^{(Oracle)}:$

• 1. $\hat{\sigma }_{Real}^{(Scheme)}=\hat{\sigma }_{Real}^{(Oracle)}$.

• 2. $\hat{\sigma }_{Fake}^{(Scheme)}\ne \hat{\sigma }_{Fake}^{(Oracle)}$.

The reason for observation 1 follows directly from the fact that $\sigma _{Real}$ is a valid ciphertext. The reason for the violation in observation 2 is that the ReEncrypt algorithm is only a function of the re-encryption key but OReE oracle makes use of the knowledge of $r_{Fake}$ to generate $\hat{\sigma }_{Fake}^{(Oracle)}$. However, in the construction of $\sigma _{Fake}$, $r_{Rand}$ is used in the generation of $\hat{\sigma }_{Fake}^{(Oracle)}$. The question here is, how will the adversary find this difference, that is $\hat{\sigma }_{Fake}^{(Scheme)}\ne \hat{\sigma }_{Fake}^{( Oracle)}$. Let us now demonstrate how the adversary captures this difference shown by the OReE oracle simulation and the ReEncrypt algorithm.

Distinguishing The Oracle From The Real Algorithm:

• 1. $\mathcal {C}$ provides the system parameters PARAMS to $\mathcal {A}$.

• 2. After getting training in Phase-I, $\mathcal {A}$ provides two messages $m_0$ and $m_1$ of equal length and a target public key $PK_T$ to $\mathcal {C}$.

• 3. $\mathcal {C}$ generates the challenge ciphertext $\sigma _T$ and gives as challenge to $\mathcal {A}$.

• 4. $\mathcal {A}$ now does the following:

  • (a) Generate $\sigma _{Fake}\,=\,$Encrypt$_{Fake}(m_0,PK_T)=( D_{Fake}, E_{Fake},F_{Rand},$$s_{Fake} )$. Here $\mathcal {A}$ knows $r_{Rand}$ and $u_{Fake}$.

  • (b) $\mathcal {A}$ queries $OReE(\sigma _{Fake},PK_{T},PK_j,RK_{T\rightarrow j},PARAMS)$. It should noted that $v,V,h,\pi ,W$ are fixed for $T\rightarrow j$ delegation.

  • (c) Test: If $\bot \leftarrow OReE((\sigma _{Fake},PK_{T},PK_j,RK_{T\rightarrow j},PARAMS))$, then $ReEncrypt\ne OReE$ and $\mathcal {A}$ knows that it is not the real system and will abort. Else, $\mathcal {A}$ learns no clue about the simulation.

2.3 Fixing the Flaw

Note that modifying the re-encryption algorithm to fix the flaw is not possible since re-encryption of a valid ciphertext $\sigma _T$ will always require the knowledge of $r=H_1(m,\omega )$ as no other trapdoor exists to obtain a re-encrypted ciphertext $\hat{\sigma }_j$. Again, the knowledge of the private key of the delegator is necessary to generate the re-encryption keys and re-encrypted ciphertexts. Consequently, we cannot provide a trivial fix to the scheme in order to address the problem. As a solution, we propose a new collusion-resistant unidirectional proxy re-encryption scheme without any pairing operation. We have incorporated additional information to the existing Encrypt algorithm along with ciphertext validity checks in both the Re-Encrypt and the Decrypt algorithm.

3 A Unidirectional Proxy Re-encryption Scheme

• Setup$({\lambda })\mathbf{: }$ Choose two primes p and q such that $q|p-1$ and the bit-length of q is the security parameter $\lambda$. Let $\mathbb {G}$ be a subgroup of $\mathbb {Z}_q^*$ with order q. g is a generator of the group $\mathbb {G}$. Choose five hash functions $H_1 : \{0, 1\}^{l_0} \times \{0, 1\}^{l_1} \rightarrow \mathbb {Z}_q^* , H_2 : \mathbb {G} \rightarrow \{0, 1\}^{ l_0 + l_1} , H_3 : \{0, 1\}^* \rightarrow \mathbb {Z}_q^*, H_4 : \mathbb {G} \rightarrow \mathbb {Z}_q^* ,H_5 : \mathbb {G}^4 \times \{0,1\}^{l_0+l_1}\rightarrow \mathbb {G}.$ The hash functions are modelled as random oracles in the security proof reduction. Here $l_0$ and $l_1$ are security parameters determined by $\lambda$, and the message space $\mathcal {M}$ is $\{0, 1\}^{l_0}$. Return the public parameters $PARAM = (q, \mathbb {G}, g, H_1 , H_2 , H_3 , H_4 , H_5, l_0 , l_1 )$.

• KeyGen$(U_i, PARAMS)\mathbf{: }$ To generate the private key $(SK_i)$ and the corresponding public key $(PK_i)$ of user $U_i$:

  • Pick $x_{i,1},x_{i,2}\in _R\mathbb {Z}_q^*$ and set $SK_i=(x_{i,1},x_{i,2})$.

  • Compute $PK_i=(PK_{i,1},PK_{i,2})=(g^{x_{i,1}},g^{x_{i,2}})$.

• ReKeyGen$(SK_i,PK_i,PK_j,PARAMS)\mathbf{: }$ On input of a user i’s private key $SK_i=(x_{i,1},x_{i,2})$ and public key $PK_i=(PK_{i,1},PK_{i,2})$ and user j’s public key $PK_j=(PK_{j,1},PK_{j,2})$, generate the re-encryption key $RK_{i\rightarrow j}$ as shown:

  • Pick $h \in _R \{0,1\}^{l_0}$, $\pi \in _R \{0,1\}^{l_1}$.

  • Compute $v=H_1(h,\pi )$, $V=PK_{j,2}^v$ and $W=H_2(g^v)\oplus (h||\pi )$.

  • Define $RK_{i\rightarrow j}^{\langle 1 \rangle }=\frac{h}{x_{i,1}H_4(PK_{i,2})+x_{i,2}}$.

  • Return $RK_{i\rightarrow j}=(RK_{i\rightarrow j}^{\langle 1 \rangle },V,W).$

• Encrypt$(m,PK_i,PARAMS)\mathbf{: }$ To encrypt a message $m\in \mathcal {M}$:

  • Pick $u\in _R \mathbb {Z}_q^*$, $\omega \in _R \{0,1\}^{l_1}$.

  • Compute $D=\big (PK_{i,1}^{H_4(PK_{i,2})} PK_{i,2} \big )^u$.

  • Compute $\bar{D}=H_5(PK_{i,1},PK_{i,2},D,E,F)^u.$

  • Compute $r=H_1(m,\omega )$.

  • Compute $E=\big (PK_{i,1}^{H_4(PK_{i,2})}PK_{i,2} \big )^r$.

  • Compute $\bar{E}=H_5(PK_{i,1},PK_{i,2},D,E,F)^r.$

  • Compute $F=H_2(g^r)\oplus (m||\omega )$.

  • Compute $s=u+r\cdot H_3(D,\bar{E},F) \mod q$.

  • Output the ciphertext $\sigma _i=(D,\bar{E},F,s).$

• ReEncrypt$(\sigma _i,PK_i,PK_j,RK_{i\rightarrow j},PARAMS)\mathbf{: }$ On input of an original ciphertext $\sigma _i=(E,\bar{E},F,s)$ encrypted under public key $PK_i=(PK_{i,1},$$PK_{i,2})$, the public keys $PK_i$ and $PK_j$, a re-encryption key $RK_{i\rightarrow j}=(RK_{i\rightarrow j}^{\langle 1 \rangle },V,W)$, re-encrypt $\sigma _i$ into a ciphertext $\hat{\sigma _j}$ under the public key $PK_j=(PK_{j,1},PK_{j,2})$ as follows:

  • Compute D and $\bar{D}$ as follows:

    $$\begin{aligned} D&=\big ( PK_{i,1}^{H_4(PK_{i,2})}PK_{i,2}\big )^s\cdot (E^{H_3(E,\bar{E},F)})^{-1}\\ {}&=\big (PK_{i,1}^{H_4(PK_{i,2})} PK_{i,2} \big )^u.\\ \bar{D}&=H_5(PK_{i,1},PK_{i,2},D,E,F)^s\cdot (\bar{E}^{(E,\bar{E},F)})^{-1}\\ {}&=H_5(PK_{i,1},PK_{i,2},D,E,F)^u. \end{aligned}$$

  • Check the well-formedness of the ciphertext by verifying:

    $$\begin{aligned} \big ( PK_{i,1}^{H_4(PK_{i,2})}PK_{i,2}\big )^s{\mathop {=}\limits ^{?}}D\cdot E^{H_3(E,\bar{E},F)} \end{aligned}$$

    (2)
    $$\begin{aligned} \big (H_5(PK_{i,1},PK_{i,2},D,E,F) \big )^s{\mathop {=}\limits ^{?}}\bar{D}\cdot \bar{E}^{H_3(E,\bar{E},F)} \end{aligned}$$

    (3)

  • If the above checks fail, return $\bot$. Else, compute $\bar{E}=E^{RK_{i\rightarrow j}^{\langle 1 \rangle }} = g^{rh}$.

  • Output $\hat{\sigma _j}=(\bar{E},F,V,W)$.

• Encrypt$_1(m,PK_i,PARAMS)\mathbf{: }$ To generate a non-transformable ciphertext under public key $PK_i$ of a message $m\in \mathcal {M}$:

  • Pick $h\in _R \{0,1\}^{l_0}$ and $\pi \in _R\{0,1\}^{l_1}$.

  • Compute $v=H_1(h,\pi )$, $V=PK_{j,2}^{v}$ and $W=H_2(g^v)\oplus (h||\pi )$.

  • Pick $\omega \in _R \{0,1\}^{l_1}$ and compute $r=H_1(m,\omega )$.

  • Compute $\hat{E}=(g^r)^h$ and $F=H_2(g^r)\oplus (m||\omega )$.

  • Output the non-transformable ciphertext $\hat{\sigma _j}=(\hat{E},F,V,W)$.

• Decrypt$(\sigma _i,PK_i,SK_i,PARAMS)\mathbf{: }$ On input a ciphertext $\sigma _i$, public key $PK_i$ and private key $SK_i=(x_{i,1},x_{i,2})$, decrypt according to two cases:

  • Original ciphertext of the form $\sigma _i=(E,\bar{E},F,s)$:

    $*$ :

    Check if the ciphertext is well-formed by computing the values of D and $\bar{D}$ and checking if Eqs. (2) and (3) holds.

    $*$ :

    If the conditions hold, extract $(m||\omega )=F\oplus H_2(E^{\frac{1}{x_{i,1}H_4(PK_{i,2})+x_{i,2}}})$, else return $\bot$.

    $*$ :

    Return m if the following checks hold, else return $\bot$.

    $$\begin{aligned} E&{\mathop {=}\limits ^{?}}\big (PK_{i,1}^{H_4(PK_{i,2})}PK_{i,2} \big )^{H_1(m,\omega )}\\\bar{E}&{\mathop {=}\limits ^{?}}H_5(PK_{i,1},PK_{i,2},D,E,F)^{H_1(m,\omega )} \end{aligned}$$

  • Transformed or non-transformable ciphertext of the form $\sigma _i=(\hat{E},F,V,W)$:

    $*$ :

    Compute $(h||\pi )=W\oplus H_2(V^{1/SK_{i,2}})$, extract $(m||\omega )=F\oplus H_2(\hat{E}^{1/h})$.

    $*$ :

    Return m if $V{\mathop {=}\limits ^{?}}PK_{i,2}^{H_1(h,\pi )}$, $\hat{E}{\mathop {=}\limits ^{?}}g^{H_1(m,\omega )\cdot h}$ holds; else return $\bot$.

3.1 Correctness

Due to space constraints, the correctness of our scheme is given in the full version of the paper [9].

3.2 Security Proof

Original Ciphertext Security:

Theorem 1

The proposed scheme is CCA-secure for the original ciphertext under the DCDH assumption and the $EUF-CMA$ security of Schnorr signature scheme [8]. If a $(t,\epsilon )IND$-PRE-CCA $\mathcal {A}$ with an advantage $\epsilon$ breaks the IND-PRE-CCA security of the given scheme in time t, $\mathcal {C}$ can solve the DCDH problem with advantage $\epsilon '$ within time $t'$ where:

$$\begin{aligned}&\epsilon ' \ge \frac{1}{q_{H_2}}\bigg ( \frac{\epsilon }{e(q_{RK}+1)}-\frac{q_{H_1}}{2^{l_1}}- \frac{q_{H_3}+q_{H_5}}{2^{l_0+l_1}}- q_{d}\Big (\frac{q_{H_1}+q_{H_2}}{2^{l_0+l_1}} + \frac{2}{q}\Big ) -\epsilon _1 -\epsilon _2\bigg ),\\&t'\le t+(q_{H_1}+q_{H_2}+q_{H_3}+q_{H_4}+q_{H_5}+n_h+n_c+q_{RK}+q_{RE}+q_d)O(1)\\&+\,(2n_h+2n_c+2q_{RK}+5q_{RE}+2q_d+q_{H_1}q_{RE}+(2q_{H_2}+2q_{H_1})q_d)t_e, \end{aligned}$$

We note that e is the base of natural logarithm, $\epsilon _1$ denotes the advantage in breaking the CCA security of the hashed Elgamal encryption scheme and $\epsilon _2$ denotes the advantage in breaking the EUF-CMA security of the Schnorr Signature scheme and $t_e$ denotes the time taken for exponentiation in group $\mathbb {G}$.

Proof

Due to space constraints, the proof of the theorem is shown in the full version of the paper [9].

Transformed Ciphertext Security:

Theorem 2

The proposed scheme is CCA-secure for the transformed ciphertext under the CDH assumption and the $EUF-CMA$ security of Schnorr signature scheme [8]. If a $(t,\epsilon )IND$-PRE-CCA $\mathcal {A}$ with an advantage $\epsilon$ breaks the IND-CPRE-CCA security of the given scheme, $\mathcal {C}$ can solve the DCDH problem with advantage $\epsilon '$ within time $t'$ where:

$$\begin{aligned}&\epsilon ' \ge \frac{1}{q_{H_2}}\bigg ( \frac{2 \epsilon }{e(2+q_{RK})^2}-\frac{q_{H_1}}{2^{l_1}}- q_{d}\Big (\frac{q_{H_1}+q_{H_2}}{2^{l_0+l_1}} + \frac{2}{q}\Big )-\epsilon _2 \bigg ),\\&t'\le t+(q_{H_1}+q_{H_2}+q_{H_3}+q_{H_4}+q_{H_5}+n_h+n_c+q_{RK}+q_{RE}+q_d)O(1)\\&+\,(2n_h+2n_c+2q_{RK}+3q_{RE}+2q_d+(2q_{H_2}+2q_{H_1})q_d)t_e, \end{aligned}$$

Proof

The proof of the theorem is shown in the full version of the paper [9].   $\square$

Non-transformable Ciphertext Security:

Theorem 3

The proposed scheme is CCA-secure for the non-transformable ciphertext under the CDH assumption. If a $(t,\epsilon -\epsilon _2)IND$-PRE-CCA $\mathcal {A}$ with an advantage $\epsilon -\epsilon _2$ breaks the IND-PRE-CCA security of the given scheme, $\mathcal {C}$ can solve the CDH problem with advantage $\epsilon '$ within time $t'$ where:

$$\begin{aligned}&\epsilon ' \ge \frac{1}{q_{H_2}}\bigg ( \epsilon -\epsilon _2-\frac{q_{H_1}}{2^{l_1}}- q_{d}\Big (\frac{q_{H_1}+q_{H_2}}{2^{l_0+l_1}} + \frac{2}{q}\Big ) \bigg ),\\&t'\le t+(q_{H_1}+q_{H_2}+q_{H_3}+q_{H_4}+q_{H_5}+n_h+n_c+q_{RK}+q_d)O(1)\\&+\,(2n_h+2n_c+2q_{RK}+2q_d+(2q_{H_2}+2q_{H_1})q_d)t_e, \end{aligned}$$

Proof

The proof of the theorem is shown in the full version of the paper [9].

Delegator Secret Security:

Theorem 4

The proposed scheme is DSK-secure under the DL assumption. If a $(t,\epsilon )DSK$ $\mathcal {A}$ with an advantage $\epsilon$ breaks the DSK security of the given scheme in time t, $\mathcal {C}$ can solve the DL problem with advantage $\epsilon$ within time $t'$ where:

$$\begin{aligned}&t'\le t+O(2q_{RK}+2n_h+2n_c)t_e, \end{aligned}$$

Proof

The proof of the theorem is shown in the full version of the paper [9].    $\square$

4 Efficiency Comparison

We give a comparison of our scheme with the modified scheme of Chow et al. by Canard et al. [2] in Table 1. We show the computational efficiency of our PRE scheme, and use $t_e$ to denote the time for exponentiation operation. Note that $l=O(\log \lambda )$ denotes the number of commitments generated by the signer in the NIZK proof in the encryption protocol in [2]. The comparison shows that our proposed design is more efficient than the existing fix to the pairing-free unidirectional PRE scheme of Chow et al. constructed by Canard et al. [2].

Table 1. Comparative analysis of the modified pairing-free PRE scheme due to Canard et al. and our scheme. Note that $l=O(\log \lambda ).$

5 Conclusion

Although pairing is an expensive operation, only one scheme due to Chow et al. [4] reported the pairing-free unidirectional property with collusion-resistance. In this paper, we point out that the security proof in the scheme is flawed, where the adversary is able to determine that the simulation provided by challenger is not consistent with real system. Also, we present a construction of unidirectional proxy re-encryption scheme without bilinear pairing that provides collusion-resistance, and show that our scheme is more efficient than the modified scheme of Chow et al. constructed by Canard et al. Our scheme is proven CCA-secure under a variant of the computational Diffie-Hellman assumption in the random oracle model.