## 3 Preliminaries
### Cryptographic Building Blocks  
As our building blocks, we adopt a certificateless proxy re-encryption (CL-PRE) scheme [27] and an id-based signature (ID-SIG) scheme [28] described in the followings. * _Setup_(): A private key generator chooses bilinear map groups \((\mathbb{G}_{1},\mathbb{G}_{2})\) of the same prime order \(q\), random generators \(g,h\in\mathbb{G}_{1}\), and hash functions \(H_{1}:\{0,1\}^{*}\to\mathbb{G}_{1}\), \(H_{2}:\{0,1\}^{*}\to Z_{q}^{*}\), \(H_{3}:G_{2}\times G_{2}\to\{0,1\}^{n+k_{0}}\). It also chooses a random \(s\in Z_{q}^{*}\) as a master secret then computes \(g_{1}=g^{s}\), \(g_{2}=\hat{e}(g,g)\), \(g_{3}=\hat{e}(g,h)\). Public system parameters are set as \(params:=\langle\mathbb{G}_{1},\mathbb{G}_{2},q,\hat{e},g,h,g_{1},\mathbb{g}_{2},g_{3},H_{1},H_{2},H_{3}\rangle\). * _idKeyGen_(\(s\), _id_): Given an identity _id_, this algorithm outputs an id-based private key \(d_{id}=g^{1/(s+H_{2}(id))}\) under the master secret key \(s\) of a private key generator. * _SetPreKey_(\(d_{id}\)): Given a \(d_{id}\) generated by _idKeyGen_ for an _id_, this algorithm chooses random values \(a,b\in Z_{q}^{*}\) and sets \(sk_{id}=(d_{id},a,b)\) as a private key for CL-PRE for a user of the _id_. * _SetPubKey_(\(sk_{id}\)): This algorithm returns a public key \(pk_{id}=(g_{3}^{a},g^{b})\) corresponding to \(sk_{id}\) for CL-PRE. * _clEnc_(\(m\), _id_, \(pk_{id}\)): Certificateless encryption algorithm generates a ciphertext for a given message \(m\) under the _id_ and \(pk_{id}\) as follows: 1. Choose a random \(\alpha\in\{0,1\}^{\kappa_{0}}\) for a security parameter \(\kappa_{0}\). 2. Compute \(\beta=H_{2}(m|\alpha|id|pk_{id})\). 3. Compute \(c_{1}=(g^{H_{2}(id)}\cdot g_{1})^{\beta}\), \(c_{2}=h^{\beta}\), \(c_{3}=(m|\alpha)\oplus H_{3}(g_{2}^{\beta}|(g_{3}^{a})^{\beta})\), and \(c_{4}=u^{\beta}\) where \(u=H_{1}(id|pk_{id}|c_{1}|c_{2}|c_{3})\). 4. Output the ciphertext \(C=(c_{1},c_{2},c_{3},c_{4})\). * _clReKeyGen_(\(sk_{id_{i}}\), \(id_{i}\), \(id_{j}\), \(pk_{id_{i}}\), \(pk_{id_{j}}\)): Re-encryption key generation algorithm returns a proxy re-encryption key \(rk_{id_{i}\to id_{j}}\) as follows: 1. Choose a random \(\gamma\in Z_{q}^{*}\) and compute \(\mu=H_{2}(g_{2}^{\gamma}|id_{i}|pk_{id_{i}}|id_{j}|pk_{id_{j}})\). 2. Compute \(rk^{(1)}=g^{\mu/(s+H_{2}(id_{i}))}\), \(rk^{(2)}=(g^{H_{2}(id_{i})}\cdot g_{1})^{\gamma}\), and \(rk^{(3)}=(g^{b_{j}})^{a_{i}}\) where \(a_{i}\in sk_{id_{i}}\) and \(g^{b_{j}}\in pk_{id_{j}}\), respectively. 3. Output the re-encryption key \(rk_{id_{i}\to id_{j}}=(rk^{(1)},rk^{(2)},rk^{(3)})\). * _clReEnc_(\(id_{i}\), \(pk_{id_{i}}\), \(C\), \(rk_{i\to j}\)): Given a ciphertext \(C\) under the identity \(id_{i}\) and public key \(pk_{id_{i}}\), this algorithm outputs a re-encrypted ciphertext \(C_{j}\) delegated to \(id_{j}\) under the \(rk_{id_{i}\to id_{j}}\) as follows: 1. Parse \(C\) as \(C=(c_{1},c_{2},c_{3},c_{4})\)Compute \(u=H_{1}(id_{i}|pk_{id_{i}}|c_{1}|c_{2}|c_{3})\) and \(y_{i}=H_{2}(id_{i})\). 3. If \(\hat{e}(c_{1},u)\doteq\hat{e}((g^{y_{i}}\cdot g_{1}),c_{4})\) and \(\hat{e}(c_{2},u)\doteq\hat{e}(h,c_{4})\) holds,
4. Set the re-encrypted ciphertext \(C_{j}=(c_{1}^{\prime},c_{2}^{\prime},c_{3}^{\prime},c_{4}^{\prime},id_{i},pk_{ id_{i}})\), where \(c_{1}^{\prime}=\hat{e}(c_{1},rk^{(1)})\), \(c_{2}^{\prime}=rk^{(2)}\), \(c_{3}^{\prime}=\hat{e}(c_{2},rk^{(3)})\), and \(c_{4}^{\prime}=c_{3}\). * \(clReDec(sk_{id_{i}}\), \(C_{j})\): Given a re-encrypted ciphertext \(C_{j}\) delegated to \(id_{j}\) from \(id_{i}\), decryption algorithm outputs the message \(m\) as follows: 1. Parse \(C_{j}\) as \(C_{j}=(c_{1}^{\prime},c_{2}^{\prime},c_{3}^{\prime},c_{4}^{\prime},id_{i},pk_{ id_{i}})\). 2. Compute \(\rho=\hat{e}(c_{2}^{\prime},id_{id_{i}})\) where \({id_{i}}_{j}\in sk_{id_{i}}\), and \(\mu=H_{2}(\rho|id_{i}|pk_{id_{i}}|id_{j}|pk_{id_{j}})\). 3. Compute \((m|\alpha)=c_{4}^{\prime}\oplus H_{3}(c_{1}^{\prime\,1/\mu}|c_{3}^{\prime\,1/ \hat{b}_{j}})\). 4. Compute \(\beta=H_{2}(m|\alpha|id_{i}|pk_{id_{i}})\). 5. If \(c_{1}^{\prime}\stackrel{{?