1 Introduction
1.1 Motivation
1.2 Related Work
Table 1
Schemes  Signers  Decrypters  Additional property 
Xiong et al.’s scheme (Xiong et al., 2021)  PKIPKS  IDPKS  Equality test functionality 
Hou et al.’s scheme (Hou et al., 2021)  PKIPKS  CLPKS  Equality test functionality 
Xiong et al.’s scheme (Xiong et al., 2022)  IDPKS  PKIPKS  Equality test functionality 
Ali et al.’s scheme (Ali et al., 2020)  IDPKS  PKIPKS  Suitable for VANET environments 
Elkhalil et al.’s scheme (Elkhalil et al., 2021)  CLPKS  PKIPKS  Suitable for VANET environments 
Pan et al.’s scheme (Pan et al., 2022)  IDPKS  PKIPKS  Suitable for VANET environments 
Niu et al.’s scheme (Niu et al., 2023)  IDPKS  CLPKS  Suitable for IIoT environments 
Our scheme  PKIPKS  CLPKS  Leakageresilient property 
1.3 Contribution
1.4 Paper Structure
2 Preliminaries
2.1 Bilinear Groups and GBG Model
2.2 Security Assumptions and Entropy

– Discrete logarithm (DL) assumption: In $\{G,{G_{1}},\hat{e},Q,{Q_{1}},q\}$, for given $u\cdot Q\in G$ or ${Q_{1}^{u}}\in {G_{1}}$, without knowing $u\in {Z_{q}^{\ast }}$, it is hard to discover u.

– Secure hash function (SH) assumption: Let $\textit{SH}:{\{0,1\}^{\ast }}\to {\{0,1\}^{t}}$ be a secure hash function, where t is a fixed length. Then it is hard to discover any two random bit strings ${\textit{RBS}_{1}}$ and ${\textit{RBS}_{2}}$ such that $\textit{SH}({\textit{RBS}_{1}})=\textit{SH}({\textit{RBS}_{2}})$.
Lemma 1.
Lemma 2.
3 Framework and Adversary Games
Table 2
Notation  Meaning 
CA  A certificate authority in the PKIPKS 
KGC  A key generation centre in the CLPKS 
${\textit{SK}_{\textit{CA}}}$/${\textit{PK}_{\textit{CA}}}$  CA’s secret/public key pair 
${\textit{SK}_{\textit{KGC}}}$/${\textit{PK}_{\textit{KGC}}}$  KGC’s secret/public key pair 
${\textit{ID}_{\textit{PKI}}}$  The identity of a user in the PKIPKS 
${\mathit{PKISK}_{\textit{ID}}}$/${\mathit{PKIPK}_{\textit{ID}}}$  The secret/public key pair of the user ${\textit{ID}_{\textit{PKI}}}$ 
${\textit{CRT}_{\textit{ID}}}$  The certificate of the user ${\textit{ID}_{\textit{PKI}}}$ 
${\textit{ID}_{\textit{CL}}}$  The identity of a user in the CLPKS 
${\mathit{CLSK}_{\textit{ID}}}$/${\mathit{CLPK}_{\textit{ID}}}$  The secret/public key pair of the user ${\textit{ID}_{\textit{CL}}}$ 
${\mathit{CLISK}_{\textit{ID}}}$/${\mathit{CLIPK}_{\textit{ID}}}$  The identity secret/public key pair of the user ${\textit{ID}_{\textit{CL}}}$ 
M  A message 
$\textit{CT}$  A ciphertext 
$\textit{SP}$  The system parameters 
$\textit{HSE}$  The Hybrid signcryption in the LRHSCHPKS scheme 
$\textit{HUSE}$  The Hybrid unsigncryption in the LRHSCHPKS scheme 
3.1 Framework
Fig. 2
Definition 1.

– System setup: Firstly, the system parameters ($\textit{SP}$) are initially set. The heterogeneous publickey systems consist of the PKIPKS and the CLPKS. The CA in the PKIPKS and the KGC in the CLPKS, respectively, set their secret keys and the associated public keys as follows.

♦ PKIPKS: The CA sets a secret/public key pair (${\textit{SK}_{\textit{CA}}},{\textit{PK}_{\textit{CA}}}$). Initially, the CA partitions ${\textit{SK}_{\textit{CA}}}$ into (${\textit{SK}_{\textit{CA},0,0}},{\textit{SK}_{\textit{CA},0,1}}$).

♦ CLPKS: The KGC sets a secret/public key pair (${\textit{SK}_{\textit{KGC}}},{\textit{PK}_{\textit{KGC}}}$). Initially, the KGC partitions ${\textit{SK}_{\textit{KGC}}}$ into (${\textit{SK}_{\textit{KGC},0,0}},{\textit{SK}_{\textit{KGC},0,1}}$).


– User key generation: For signers in the PKIPKS and decrypters in the CLPKS, two key generating procedures are presented as follows.

♦ PKIPKS: A signer with identity ${\textit{ID}_{\textit{PKI}}}$ and the CA cooperatively run the following two algorithms.

• Signer secret key generation: The signer ${\textit{ID}_{\textit{PKI}}}$ sets a secret/public key pair $({\mathit{PKISK}_{\textit{ID}}},{\mathit{PKIPK}_{\textit{ID}}})$. Initially, the signer ${\textit{ID}_{\textit{PKI}}}$ partitions ${\mathit{PKISK}_{\textit{ID}}}$ into $({\mathit{PKISK}_{\mathit{ID},0,0}},{\mathit{PKISK}_{\mathit{ID},0,1}})$. Also, the signer ${\textit{ID}_{\textit{PKI}}}$ sends $({\textit{ID}_{\textit{PKI}}},{\mathit{PKIPK}_{\textit{ID}}})$ to the CA.

• Signer certificate generation: For this algorithm’s ith running and giving $({\textit{ID}_{\textit{PKI}}},{\mathit{PKIPK}_{\textit{ID}}})$, the CA first updates the old secret key $({\textit{SK}_{\textit{CA},i1,0}},{\textit{SK}_{\textit{CA},i,1,1}})$ to the new secret key $({\textit{SK}_{\textit{CA},i,0}},{\textit{SK}_{\textit{CA},i,1}})$, such that ${\textit{SK}_{\textit{CA}}}={\textit{SK}_{\textit{CA},0,0}}+{\textit{SK}_{\textit{CA},0,1}}={\textit{SK}_{\textit{CA},1,0}}+{\textit{SK}_{\textit{CA},1,1}}=\cdots ={\textit{SK}_{\textit{CA},i,0}}+{\textit{SK}_{\textit{CA},i,1}}$. Subsequently, the CA uses $({\textit{SK}_{\textit{CA},i,0}},{\textit{SK}_{\textit{CA},i,1}})$ to compute and return the certificate ${\textit{CRT}_{\textit{ID}}}$ to the signer ${\textit{ID}_{\textit{PKI}}}$.


♦ CLPKS: A decrypter with identity ${\textit{ID}_{\textit{CL}}}$ and the KGC cooperatively run the following four algorithms.

• Decrypter secret key generation: The decrypter ${\textit{ID}_{\textit{CL}}}$ sets a secret/public key pair $({\mathit{CLSK}_{\textit{ID}}},{\mathit{CLPK}_{\textit{ID}}})$. Also, the decrypter ${\textit{ID}_{\textit{CL}}}$ sends ${\textit{ID}_{\textit{CL}}}$ to the KGC.

• Decrypter identity secret key generation: For this algorithm’s ith running and giving ${\textit{ID}_{\textit{CL}}}$, the KGC first updates the old secret key $({\textit{SK}_{\textit{KGC},i1,0}},{\textit{SK}_{\textit{KGC},i1,1}})$ to the new secret key $({\textit{SK}_{\textit{KGC},i,0}},{\textit{SK}_{\textit{KGC},i,1}})$ such that ${\textit{SK}_{\textit{KGC}}}={\textit{SK}_{\textit{KGC},0,0}}+{\textit{SK}_{\textit{KGC},0,1}}={\textit{SK}_{\textit{KGC},1,0}}+{\textit{SK}_{\textit{KGC},1,1}}=\cdots ={\textit{SK}_{\textit{KGC},i,0}}+{\textit{SK}_{\textit{KGC},i,1}}$. Subsequently, the KGC uses $({\textit{SK}_{\textit{KGC},i,0}},{\textit{SK}_{\textit{KGC},i,1}})$ to compute and return the identity secret/public key pair $({\mathit{CLISK}_{\textit{ID}}},{\mathit{CLIPK}_{\textit{ID}}})$ to the decrypter ${\textit{ID}_{\textit{CL}}}$.

• Decrypter secret key combination: $({\mathit{CLSK}_{\textit{ID}}},{\mathit{CLISK}_{\textit{ID}}})$ is the decrypter ${\textit{ID}_{\textit{CL}}}$’s secret key pair. Initially, the decrypter ${\textit{ID}_{\textit{CL}}}$ partitions ${\mathit{CLSK}_{\textit{ID}}}$ and ${\mathit{CLISK}_{\textit{ID}}}$ into $({\mathit{CLSK}_{\mathit{ID},0,0}},{\mathit{CLSK}_{\mathit{ID},0,1}})$ and $({\mathit{CLISK}_{\mathit{ID},0,0}},{\mathit{CLISK}_{\mathit{ID},0,1}})$, respectively.

• Decrypter public key combination: $({\mathit{CLPK}_{\textit{ID}}},{\mathit{CLIPK}_{\textit{ID}}})$ is the decrypter ${\textit{ID}_{\textit{CL}}}$’s public key pair.



– Hybrid signcryption ($\textit{HSE}$): For the $\textit{HSE}$ algorithm’s jth running and giving $(M,{\textit{ID}_{\textit{CL}}},{\mathit{CLPK}_{\textit{ID}}},{\mathit{CLIPK}_{\textit{ID}}})$, the signer ${\textit{ID}_{\textit{PKI}}}$ first updates the old secret key $({\mathit{PKISK}_{\mathit{ID},j1,0}},{\mathit{PKISK}_{\mathit{ID},j1,1}})$ to the new secret key $({\mathit{PKISK}_{\mathit{ID},j,0}},{\mathit{PKISK}_{\mathit{ID},j,1}})$. Then, the signer ${\textit{ID}_{\textit{PKI}}}$ generates a ciphertext $\textit{CT}=\textit{HSE}(M,{\textit{ID}_{\textit{CL}}},{\mathit{CLPK}_{\textit{ID}}},{\mathit{CLIPK}_{\textit{ID}}},({\mathit{PKISK}_{\mathit{ID},j,0}},{\mathit{PKISK}_{\mathit{ID},j,1}}))$ and returns $\textit{CT}$ to the decrypter ${\textit{ID}_{\textit{CL}}}$.

– Hybrid unsigncryption ($\textit{HUSE}$): For the Hybrid unsigncryption ($\textit{HUSE}$) algorithm’s kth running and giving $\textit{CT}$, the decrypter ${\textit{ID}_{\textit{CL}}}$, respectively, updates the old secret key $({\mathit{CLSK}_{\mathit{ID},k1,0}},{\mathit{CLSK}_{\mathit{ID},k1,1}})$ and the identity secret key $({\mathit{CLISK}_{\mathit{ID},k1,0}},{\mathit{CLISK}_{\mathit{ID},k1,1}})$ to the new secret key $({\mathit{CLSK}_{\mathit{ID},k,0}},{\mathit{CLSK}_{\mathit{ID},k,1}})$ and the new identity secret key $({\mathit{CLISK}_{\mathit{ID},k,0}},{\mathit{CLISK}_{\mathit{ID},k,1}})$, and gets the message $M=\textit{HUSE}(\textit{CT},{\textit{ID}_{\textit{PKI}}},{\mathit{PKIPK}_{\textit{ID}}},{\textit{CRT}_{\textit{ID}}},({\mathit{CLSK}_{\mathit{ID},k,0}},{\mathit{CLSK}_{\mathit{ID},k,1}})$, $({\mathit{CLISK}_{\mathit{ID},k,0}},{\mathit{CLISK}_{\mathit{ID},k,1}}))$.
3.2 Adversary Games

– $\Delta {f_{\textit{SCG},i}}={f_{\textit{SCG},i}}({\textit{SK}_{\textit{CA},i,0}})$.

– $\Delta {h_{\textit{SCG},i}}={h_{\textit{SCG},i}}({\textit{SK}_{\textit{CA},i,1}})$.

– $\Delta {f_{\textit{ISKG},i}}={f_{\textit{ISKG},i}}({\textit{SK}_{\textit{KGC},i,0}})$.

– $\Delta {h_{\textit{ISKG},i}}={h_{\textit{ISKG},i}}({\textit{SK}_{\textit{KGC},i,1}})$.

– $\Delta {f_{\textit{HS},j}}={f_{\textit{HS},j}}({\mathit{PKISK}_{\mathit{ID},j,0}})$.

– $\Delta {h_{\textit{HS},j}}={h_{\textit{HS},j}}({\mathit{PKISK}_{\mathit{ID},j,1}})$.

– $\Delta {f_{\textit{HUS},k}}={f_{\textit{HUS},k}}({\mathit{CLSK}_{\mathit{ID},k,0}},{\mathit{CLISK}_{\mathit{ID},k,0}})$.

– $\Delta {h_{\textit{HUS},k}}={h_{\textit{HUS},k}}({\mathit{CLSK}_{\mathit{ID},k,1}},{\mathit{CLISK}_{\mathit{ID},k,1}})$.

– Illegitimate member (${A_{I}}$): ${A_{I}}$ is used to model the attacking abilities of an illegitimate member as follows.

• ${A_{I}}$ may obtain any signer ${\textit{ID}_{\textit{PKI}}}$’s secret key ${\mathit{PKISK}_{\textit{ID}}}$, except for the target signer ${{\textit{ID}^{\ast }}_{\textit{PKI}}}$. Also ${A_{I}}$ may obtain any decrypter ${\textit{ID}_{\textit{CL}}}$’s secret key ${\mathit{CLSK}_{\textit{ID}}}$ and identity secret key ${\mathit{CLISK}_{\textit{ID}}}$, except for the identity secret key ${\mathit{CLISK}_{{\textit{ID}^{\ast }}}}$ of the target decrypter ${{\textit{ID}^{\ast }}_{\textit{CL}}}$.

• ${A_{I}}$ may obtain a portion about ${\mathit{PKISK}_{{\textit{ID}^{\ast }}}}=({\mathit{PKISK}_{{\textit{ID}^{\ast }},j,0}},{\mathit{PKISK}_{{\textit{ID}^{\ast }},j,1}})$ and ${\mathit{CLISK}_{{\textit{ID}^{\ast }}}}=({\mathit{CLISK}_{{\textit{ID}^{\ast }},k,0}},{\mathit{CLISK}_{{\textit{ID}^{\ast }},k,1}})$ by two pairs of leak functions $({f_{\textit{HS},j}},{h_{\textit{HS},j}})$ and $({f_{\textit{HUS},k}},{h_{\textit{HUS},k}})$, respectively.

• ${A_{I}}$ may obtain a portion of ${\textit{SK}_{\textit{CA}}}=({\textit{SK}_{\textit{CA},i,0}},{\textit{SK}_{\textit{CA},i,1}})$ and ${\textit{SK}_{\textit{KGC}}}=({\textit{SK}_{\textit{KGC},i,0}},{\textit{SK}_{\textit{KGC},i,1}})$ by two pairs of leak functions $({f_{\textit{SCG},i}},{h_{\textit{SCG},i}})$ and $({f_{\textit{ISKG},i}},{h_{\textit{ISKG},i}})$, respectively.


– Malicious CA/KGC (${A_{\textit{II}}}$): ${A_{\textit{II}}}$ is used to model the attacking abilities of a malicious CA/KGC who has both ${\textit{SK}_{\textit{CA}}}$ and ${\textit{SK}_{\textit{KGC}}}$.

• ${A_{\textit{II}}}$ may obtain any signer ${\textit{ID}_{\textit{PKI}}}$’s secret key ${\mathit{PKISK}_{\textit{ID}}}$ and any decrypter ${\textit{ID}_{\textit{CL}}}$’s secret key ${\mathit{CLSK}_{\textit{ID}}}$, except for the target signer ${{\textit{ID}^{\ast }}_{\textit{PKI}}}$ and decrypter ${{\textit{ID}^{\ast }}_{\textit{CL}}}$.

• ${A_{\textit{II}}}$ may obtain a portion of ${\mathit{PKISK}_{{\textit{ID}^{\ast }}}}=({\mathit{PKISK}_{{\textit{ID}^{\ast }},j,0}},{\mathit{PKISK}_{{\textit{ID}^{\ast }},j,1}})$ by the pair of leak functions (${f_{\textit{HS},j}},{h_{\textit{HS},j}}$).

• ${A_{\textit{II}}}$ may obtain a portion of ${\mathit{CLSK}_{{\textit{ID}^{\ast }}}}=({\mathit{CLSK}_{{\textit{ID}^{\ast }},k,0}},{\mathit{CLSK}_{{\textit{ID}^{\ast }},k,1}})$ by the pair of leak functions (${f_{\textit{HUS},k}},{h_{\textit{HUS},k}}$).

Definition 2 ($\mathbf{\mathbf{Gam}{e_{1}}}$).

– Initialization phase: The challenger B runs the System setup in Definition 1 to generate the CA’s secret/public key pair $({\textit{SK}_{\textit{CA}}},{\textit{PK}_{\textit{CA}}})$ and the KGC’s secret/public key pair $({\textit{SK}_{\textit{KGC}}},{\textit{PK}_{\textit{KGC}}})$. Also, B sets the system parameters ($\textit{SP}$). In the meantime, B partitions ${\textit{SK}_{\textit{CA}}}$ and ${\textit{SK}_{\textit{KGC}}}$ into $({\textit{SK}_{\textit{CA},0,0}},{\textit{SK}_{\textit{CA},0,1}})$ and $({\textit{SK}_{\textit{KGC},0,0}},{\textit{SK}_{\textit{KGC},0,1}})$, respectively. Additionally, if A is an ${A_{\textit{II}}}$, both ${\textit{SK}_{\textit{CA}}}$ and ${\textit{SK}_{\textit{KGC}}}$ are sent to ${A_{\textit{II}}}$.

– Query phase: A (${A_{I}}$ or ${A_{\textit{II}}}$) may adaptively request various kinds of queries (oracles) to B as follows.

• Signer secret key query (${\textit{ID}_{\textit{PKI}}}$): The signer ${\textit{ID}_{\textit{PKI}}}$’s secret key ${\mathit{PKISK}_{\textit{ID}}}$ is returned.

• Signer certificate query (${\textit{ID}_{\textit{PKI}}},{\mathit{PKIPK}_{\textit{ID}}}$). For the ith request of this query, B first updates the old secret key $({\textit{SK}_{\textit{CA},i1,0}},{\textit{SK}_{\textit{CA},i1,1}})$ to the new secret key $({\textit{SK}_{\textit{CA},i,0}},{\textit{SK}_{\textit{CA},i,1}})$. By $({\textit{ID}_{\textit{PKI}}},{\mathit{PKIPK}_{\textit{ID}}})$, B uses $({\textit{SK}_{\textit{CA},i,0}},{\textit{SK}_{\textit{CA},i,1}})$ to generate and return the signer ${\textit{ID}_{\textit{PKI}}}$’s certificate ${\textit{CRT}_{\textit{ID}}}$.

• Signer certificate leak query $(i,{f_{\textit{SCG},i}},{h_{\textit{SCG},i}})$. For the ith request of the Signer certificate query, the leak query can only be requested once. B returns $\Delta {f_{\textit{SCG},i}}={f_{\textit{SCG},i}}({\textit{SK}_{\textit{CA},i,0}})$ and $\Delta {h_{\textit{SCG},i}}={h_{\textit{SCG},i}}({\textit{SK}_{\textit{CA},i,1}})$.

• Decrypter identity secret key query (${\textit{ID}_{\textit{CL}}}$). For the ith request of this query, B first updates the old secret key $({\textit{SK}_{\textit{KGC},i1,0}},{\textit{SK}_{\textit{KGC},i1,1}})$ to the new secret key $({\textit{SK}_{\textit{KGC},i,0}},{\textit{SK}_{\textit{KGC},i,1}})$. By ${\textit{ID}_{\textit{CL}}}$, B uses $({\textit{SK}_{\textit{KGC},i,0}},{\textit{SK}_{\textit{KGC},i,1}})$ to generate and return the identity secret/public key pair $({\mathit{CLISK}_{\textit{ID}}},{\mathit{CLIPK}_{\textit{ID}}})$.

• Decrypter identity secret key leak query $(i,{f_{\textit{ISKG},i}},{h_{\textit{ISKG},i}})$. For the ith request of the Decrypter identity secret key query, the leak query can only be requested once. B returns $\Delta {f_{\textit{ISKG},i}}={f_{\textit{ISKG},i}}({\textit{SK}_{\textit{KGC},i,0}})$ and $\Delta {h_{\textit{ISKG},i}}={h_{\textit{ISKG},i}}({\textit{SK}_{\textit{KGC},i,1}})$.

• Decrypter public key replace query $({\textit{ID}_{\textit{CL}}},({\textit{CLPK}^{\prime }_{\textit{ID}}},{\textit{CLIPK}^{\prime }_{\textit{ID}}}))$. The decrypter ${\textit{ID}_{\textit{CL}}}$’s public key is replaced with $({\textit{CLPK}^{\prime }_{\textit{ID}}},{\textit{CLIPK}^{\prime }_{\textit{ID}}})$.

• Decrypter secret key query (${\textit{ID}_{\textit{CL}}}$). If the Decrypter public key replace query $({\textit{ID}_{\textit{CL}}},({\textit{CLPK}^{\prime }_{\textit{ID}}},{\textit{CLIPK}^{\prime }_{\textit{ID}}}))$ is never requested, the decrypter ${\textit{ID}_{\textit{CL}}}$’s secret key ${\mathit{CLSK}_{\textit{ID}}}$ is returned.

• Hybrid signcryption query $(M,{\textit{ID}_{\textit{PKI}}},{\textit{ID}_{\textit{CL}}})$: B first updates the signer ${\textit{ID}_{\textit{PKI}}}$’s old secret key $({\mathit{PKISK}_{\mathit{ID},j1,0}},{\mathit{PKISK}_{\mathit{ID},j1,1}})$ to the new secret key $({\mathit{PKISK}_{\mathit{ID},j,0}},{\mathit{PKISK}_{\mathit{ID},j,1}})$, and runs the Hybrid signcryption to return $\textit{CT}$.

• Hybrid signcryption leak query $({\textit{ID}_{\textit{PKI}}},j,{f_{\textit{HS},j}},{h_{\textit{HS},j}})$: For the signer ${\textit{ID}_{\textit{PKI}}}$’s jth request of the Decrypter identity secret key query, the leak query can only be requested once. B returns $\Delta {f_{\textit{HS},j}}={f_{\textit{HS},j}}({\mathit{PKISK}_{\mathit{ID},j,0}})$ and $\Delta {h_{\textit{HS},j}}={h_{\textit{HS},j}}({\mathit{PKISK}_{\mathit{ID},j,1}})$.

• Hybrid unsigncryption query $(\textit{CT},{\textit{ID}_{\textit{PKI}}},{\textit{ID}_{\textit{CL}}})$: B first updates the decrypter ${\textit{ID}_{\textit{CL}}}$’s old secret key $({\mathit{CLSK}_{\mathit{ID},k1,0}},{\mathit{CLSK}_{\mathit{ID},k1,1}})$ and identity secret key $({\mathit{CLISK}_{\mathit{ID},k1,0}},{\mathit{CLISK}_{\mathit{ID},k1,1}})$ to the new secret key $({\mathit{CLSK}_{\mathit{ID},k,0}},{\mathit{CLSK}_{\mathit{ID},k,1}})$ and identity secret key $({\mathit{CLISK}_{\mathit{ID},k,0}},{\mathit{CLISK}_{\mathit{ID},k,1}})$, respectively. B runs the Hybrid unsigncryption to return M.

• Hybrid unsigncryption leak query (${\textit{ID}_{\textit{CL}}},k,{f_{\textit{HUS},k}},{h_{\textit{HUS},k}}$: For the decrypter ${\textit{ID}_{\textit{CL}}}$’s kth request of the Decrypter identity secret key query, the leak query can only be requested once. B returns $\Delta {f_{\textit{HUS},k}}={f_{\textit{HUS},k}}({\mathit{CLSK}_{\mathit{ID},k,0}},{\mathit{CLSK}_{\mathit{ID},k,1}})$ and $\Delta {h_{\textit{HUS},k}}={h_{\textit{HUS},k}}({\mathit{CLISK}_{\mathit{ID},k,0}},{\mathit{CLISK}_{\mathit{ID},k,1}})$.


– Forgery phase: Assume that A forges a ciphertext ${\textit{CT}^{\ast }}=({{T^{\ast }}_{0}},{{T^{\ast }}_{1}},{{T^{\ast }}_{2}},{{\textit{ID}^{\ast }}_{\textit{PKI}}},{{\textit{ID}^{\ast }}_{\textit{CL}}})$ for the message ${M^{\ast }}$. We say that A wins ${\textit{Game}_{1}}$ if the following three provisions are true.
Definition 3 ($\mathbf{\mathbf{Gam}{e_{2}}}$).

– Initialization phase. The phase is the same with the Initialization phase in Definition 2.

– Query phase. The phase is the same with the Query phase in Definition 2.

– Challenge phase. A selects a target decrypter ${{\textit{ID}^{\ast }}_{\textit{CL}}}$ and a message pair (${M_{0}},{M_{1}}$) as a challenge objective. B randomly selects $c\in \{0,1\}$ and generates a challenge ciphertext ${\textit{CT}^{\ast }}$ by running the Hybrid signcryption with (${M_{c}},{\textit{ID}_{\textit{PKI}}},{{\textit{ID}^{\ast }}_{\textit{CL}}}$). Also, B sends ${\textit{CT}^{\ast }}$ to A. Note that the following two provisions are true.

1. If A is an ${A_{I}}$, the Decrypter identity secret key query (${{\textit{ID}^{\ast }}_{\textit{CL}}}$) is never issued.

2. If A is an ${A_{\textit{II}}}$, neither the Decrypter public key replace query $({{\textit{ID}^{\ast }}_{\textit{CL}}},({\textit{CLPK}^{\prime }_{{ID^{\ast }}}},{\textit{CLIPK}^{\prime }_{{ID^{\ast }}}}))$ nor the Decrypter secret key query (${{\textit{ID}^{\ast }}_{\textit{CL}}}$) is issued.


– Guessing phase. A outputs ${c^{\prime }}\in \{0,1\}$ and wins ${\textit{Game}_{2}}$ if ${c^{\prime }}=c$. Meanwhile, A’s advantage is defined as $\textit{Adv}(A)=\text{Pb}[{c^{\prime }}=c]1/2$.
4 Our LRHSCHPKS Scheme

– System setup: The system sets a bilinear group set $\{G,{G_{1}},\hat{e},Q,{Q_{1}},q\}$ defined in Section 2.1. Moreover, the system publishes $SP=\{G,{G_{1}},\hat{e},Q,{Q_{1}},q,W,T,\textit{SE}/\textit{SD},{\textit{SH}_{0}},{\textit{SH}_{1}}\}$, where W and T are random elements in G, $\textit{SE}$ and $\textit{SD}$ are respectively symmetric encryption and decryption functions, and ${\textit{SH}_{0}}:{\{0,1\}^{\ast }}\times G\to {\{0,1\}^{t}}$ and ${\textit{SH}_{1}}:G\times {\{0,1\}^{\ast }}\to {\{0,1\}^{t}}$ are two secure hash functions. The heterogeneous publickey systems consist of the PKIPKS and the CLPKS. The CA in the PKIPKS and the KGC in the CLPKS, respectively, set their secret/public key pairs as follows.

♦ PKIPKS: The CA randomly selects $r\in {{Z_{q}}^{\ast }}$ and then sets a secret/public key pair $({\textit{SK}_{\textit{CA}}},{\textit{PK}_{\textit{CA}}})$, where ${\textit{SK}_{\textit{CA}}}=r\cdot Q$ and ${\textit{PK}_{\textit{CA}}}=\hat{e}(Q,r\cdot Q)$. Also, the CA randomly selects $w\in {{Z_{q}}^{\ast }}$ and partitions ${\textit{SK}_{\textit{CA}}}$ into ${\textit{SK}_{\textit{CA}}}=({\textit{SK}_{\textit{CA},0,0}},{\textit{SK}_{\textit{CA},0,1}})=(w\cdot Q,{\textit{SK}_{\textit{CA}}}w\cdot Q)$.

♦ CLPKS: The KGC randomly selects $t\in {{Z_{q}}^{\ast }}$ and then sets a secret/public key pair $({\textit{SK}_{\textit{KGC}}},{\textit{PK}_{\textit{KGC}}})$, where ${\textit{SK}_{\textit{KGC}}}=t\cdot Q$ and ${\textit{PK}_{\textit{KGC}}}=\hat{e}(Q,t\cdot Q)$. Also, the KGC randomly selects $s\in {{Z_{q}}^{\ast }}$ and partitions ${\textit{SK}_{\textit{KGC}}}$ into ${\textit{SK}_{\textit{KGC}}}=({\textit{SK}_{\textit{KGC},0,0}},{\textit{SK}_{\textit{KGC},0,1}})=(s\cdot Q,{\textit{SK}_{\textit{KGC}}}s\cdot Q)$.


– User key generation: For signers in the PKIPKS and decrypters in the CLPKS, two key generating procedures are presented as follows.

♦ PKIPKS: A signer with identity ${\textit{ID}_{\textit{PKI}}}$ and the CA cooperatively run the following two algorithms.

• Signer secret key generation: The signer ${\textit{ID}_{\textit{PKI}}}$ randomly selects $x\in {{Z_{q}}^{\ast }}$ and then sets a secret/public key pair (${\mathit{PKISK}_{\textit{ID}}},{\mathit{PKIPK}_{\textit{ID}}}$), where ${\mathit{PKISK}_{\textit{ID}}}=x\cdot Q$ and ${\mathit{PKIPK}_{\textit{ID}}}=\hat{e}(Q,x\cdot Q)$. Also, the signer ${\textit{ID}_{\textit{PKI}}}$ randomly selects ${w_{i}}\in {{Z_{q}}^{\ast }}$ and partitions ${\mathit{PKISK}_{\textit{ID}}}$ into ${\mathit{PKISK}_{\textit{ID}}}=({\mathit{PKISK}_{\mathit{ID},0,0}},{\mathit{PKISK}_{\mathit{ID},0,1}})=({w_{i}}\cdot Q,{\mathit{PKISK}_{\textit{ID}}}{w_{i}}\cdot Q)$.

• Signer certificate generation: For this algorithm’s ith running and giving (${\textit{ID}_{\textit{PKI}}},{\mathit{PKIPK}_{\textit{ID}}}$), the CA randomly selects $w\in {{Z_{q}}^{\ast }}$ and updates the old secret key $({\textit{SK}_{\textit{CA},i1,0}},{\textit{SK}_{\textit{CA},i,1,1}})$ to the new secret key $({\textit{SK}_{\textit{CA},i,0}},{\textit{SK}_{\textit{CA},i,1}})=({\textit{SK}_{\textit{CA},i1,0}}+w\cdot Q,{\textit{SK}_{\textit{CA},i1,1}}w\cdot Q)$, such that ${\textit{SK}_{\textit{CA}}}={\textit{SK}_{\textit{CA},0,0}}+{\textit{SK}_{\textit{CA},0,1}}={\textit{SK}_{\textit{CA},1,0}}+{\textit{SK}_{\textit{CA},1,1}}=\cdots ={\textit{SK}_{\textit{CA},i,0}}+{\textit{SK}_{\textit{CA},i,1}}$. Also, the CA uses $({\textit{SK}_{\textit{CA},i,0}},{\textit{SK}_{\textit{CA},i,1}})$ to compute and return the certificate ${\textit{CRT}_{\textit{ID}}}$ to the signer ${\textit{ID}_{\textit{PKI}}}$.


♦ CLPKS: A decrypter with identity ${\textit{ID}_{\textit{CL}}}$ and the KGC cooperatively run the following four algorithms.

• Decrypter secret key generation: The decrypter ${\textit{ID}_{\textit{CL}}}$ randomly selects $l\in {{Z_{q}}^{\ast }}$ and then sets a secret/public key pair (${\mathit{CLSK}_{\textit{ID}}},{\mathit{CLPK}_{\textit{ID}}}$), where ${\mathit{CLSK}_{\textit{ID}}}=l\cdot Q$ and ${\mathit{CLPK}_{\textit{ID}}}=\hat{e}(Q,l\cdot Q)$. Also, the decrypter ${\textit{ID}_{\textit{CL}}}$ sends ${\textit{ID}_{\textit{CL}}}$ to the KGC.

• Decrypter identity secret key generation: For this algorithm’s ith running and giving ${\textit{ID}_{\textit{CL}}}$, the KGC randomly selects ${t_{i}}\in {{Z_{q}}^{\ast }}$ and updates the old secret key $({\textit{SK}_{\textit{KGC},i1,0}},{\textit{SK}_{\textit{KGC},i1,1}})$ to the new secret key $({\textit{SK}_{\textit{KGC},i,0}},{\textit{SK}_{\textit{KGC},i,1}})=({\textit{SK}_{\textit{KGC},i1,0}}+{t_{i}}\cdot Q,{\textit{SK}_{\textit{KGC},i1,1}}{t_{i}}\cdot Q)$, such that ${\textit{SK}_{\textit{KGC}}}={\textit{SK}_{\textit{KGC},0,0}}+{\textit{SK}_{\textit{KGC},0,1}}={\textit{SK}_{\textit{KGC},1,0}}+{\textit{SK}_{\textit{KGC},1,1}}=\cdots ={\textit{SK}_{\textit{KGC},i,0}}+{\textit{SK}_{\textit{KGC},i,1}}$. Also, the KGC randomly selects $f\in {{Z_{q}}^{\ast }}$ and uses (${\textit{SK}_{\textit{KGC},i,0}},{\textit{SK}_{\textit{KGC},i,1}}$) to compute and return the identity secret/public key pair (${\mathit{CLISK}_{\textit{ID}}},{\mathit{CLIPK}_{\textit{ID}}}$) of the decrypter ${\textit{ID}_{\textit{CL}}}$ as follows:

(1) ${\mathit{CLIPK}_{\textit{ID}}}=f\cdot Q$.

(2) $\rho ={\textit{SH}_{0}}({\textit{ID}_{\textit{CL}}},{\mathit{CLIPK}_{\textit{ID}}})$.

(3) ${\textit{TK}_{i}}={\textit{SK}_{\textit{KGC},i,1}}+f\cdot (W+\rho \cdot T)$.

(4) ${\mathit{CLISK}_{\textit{ID}}}={\textit{SK}_{\textit{KGC},i,0}}+{\textit{TK}_{i}}$.


• Decrypter secret key combination: The decrypter ${\textit{ID}_{\textit{CL}}}$’s secret key pair is (${\mathit{CLSK}_{\textit{ID}}},{\mathit{CLISK}_{\textit{ID}}}$). The ${\textit{ID}_{\textit{CL}}}$ randomly selects δ,$\xi \in {{Z_{q}}^{\ast }}$, and partitions ${\mathit{CLSK}_{\textit{ID}}}$ and ${\mathit{CLISK}_{\textit{ID}}}$ into (${\mathit{CLSK}_{\mathit{ID},0,0}},{\mathit{CLSK}_{\mathit{ID},0,1}})=(\delta \cdot Q,{\mathit{CLSK}_{\textit{ID}}}\delta \cdot Q)$ and $({\mathit{CLISK}_{\mathit{ID},0,0}},{\mathit{CLISK}_{\mathit{ID},0,1}})=(\xi \cdot Q,{\mathit{CLISK}_{\textit{ID}}}\xi \cdot Q)$, respectively.

• Decrypter public key combination: The decrypter ${\textit{ID}_{\textit{CL}}}$’s public key pair is (${\mathit{CLPK}_{\textit{ID}}},{\mathit{CLIPK}_{\textit{ID}}}$).



– Hybrid signcryption ($\textit{HSE}$): Assume that the signer ${\textit{ID}_{\textit{PKI}}}$ wants to send a message M to the decrypter ${\textit{ID}_{\textit{CL}}}$. For the $\textit{HSE}$ algorithm’s jth running, the signer ${\textit{ID}_{\textit{PKI}}}$ runs the following steps to generate a ciphertext $\textit{CT}$.

(1) Randomly select $h\in {{Z_{q}}^{\ast }}$ and update the old secret key (${\mathit{PKISK}_{\mathit{ID},j1,0}},{\mathit{PKISK}_{\mathit{ID},j1,1}}$) into the new secret key $({\mathit{PKISK}_{\mathit{ID},j,0}},{\mathit{PKISK}_{\mathit{ID},j,0}})=({\mathit{PKISK}_{\mathit{ID},j1,0}}+h\cdot Q,{\mathit{PKISK}_{\mathit{ID},j1,1}}h\cdot Q)$.

(2) Randomly select $n\in {{Z_{q}}^{\ast }}$, and compute ${T_{1}}=n\cdot Q$, ${\textit{EK}_{1}}={({\mathit{CLPK}_{\textit{ID}}})^{n}}$, ${\textit{EK}_{2}}={({\textit{PK}_{\textit{KGC}}}\cdot \hat{e}({\mathit{CLIPK}_{\textit{ID}}},(W+\rho \cdot T)))^{n}}$, where $\rho ={\textit{SH}_{0}}({\textit{ID}_{\textit{CL}}},{\mathit{CLIPK}_{\textit{ID}}})$.

(3) Generate ${T_{2}}={\textit{SE}_{\textit{EK}}}(M)$, where $EK={\textit{EK}_{1}}\oplus {\textit{EK}_{2}}$ is an encryption key.

(4) Compute $\textit{TS}={\mathit{PKISK}_{\mathit{ID},j,0}}+(n\cdot (W+\beta \cdot T))$, where $\beta ={\textit{SH}_{1}}({T_{1}},{T_{2}},{\textit{ID}_{\textit{PKI}}},{\textit{ID}_{\textit{CL}}},M)$.

(5) Generate a signature ${T_{0}}={\mathit{PKISK}_{\mathit{ID},j,1}}+\textit{TS}$.

(6) Set $\textit{CT}=({T_{0}},{T_{1}},{T_{2}},{\textit{ID}_{\textit{PKI}}},{\textit{ID}_{\textit{CL}}})$.


– Hybrid unsigncrypion ($\textit{HUSE}$): For the Hybrid unsigncryption ($\textit{HUSE}$) algorithm’s kth running and giving $\textit{CT}$, the decrypter ${\textit{ID}_{\textit{CL}}}$ runs the following steps to get the message M.

(1) Randomly select $v\in {{Z_{q}}^{\ast }}$, and update the old secret key $({\mathit{CLSK}_{\mathit{ID},k1,0}},{\mathit{CLSK}_{\mathit{ID},k1,1}})$ and the old identity secret key $({\mathit{CLISK}_{\mathit{ID},k1,0}},{\mathit{CLISK}_{\mathit{ID},k1,1}})$ to the new secret key $({\mathit{CLSK}_{\mathit{ID},k,0}},{\mathit{CLSK}_{\mathit{ID},k,1}})=({\mathit{CLSK}_{\mathit{ID},k1,0}}+v\cdot Q,{\mathit{CLSK}_{\mathit{ID},k1,1}}v\cdot Q)$ and the new identity secret key $({\mathit{CLISK}_{\mathit{ID},k,0}},{\mathit{CLISK}_{\mathit{ID},k,1}})=({\mathit{CLISK}_{\mathit{ID},k1,0}}+v\cdot Q,{\mathit{CLISK}_{\mathit{ID},k1,1}}v\cdot Q)$, respectively.

(2) Generate ${\textit{TEK}_{1}}=\hat{e}({T_{1}},{\mathit{CLSK}_{\mathit{ID},k,0}})$ and ${\textit{TEK}_{2}}=\hat{e}({T_{1}},{\mathit{CLISK}_{\mathit{ID},k,0}})$.

(3) Compute ${\textit{EK}^{\prime }_{1}}={\textit{TEK}_{1}}\cdot \hat{e}({T_{1}},{\mathit{CLSK}_{\mathit{ID},k,1}})$ and ${\textit{EK}^{\prime }_{2}}={\textit{TEK}_{2}}\cdot \hat{e}({T_{1}},{\mathit{CLISK}_{\mathit{ID},k,1}})$.

(4) Recover $M={\textit{SD}_{{\textit{EK}^{\prime }}}}({T_{2}})$, where ${\textit{EK}^{\prime }}={\textit{EK}^{\prime }_{1}}\oplus {\textit{EK}^{\prime }_{2}}$.

(5) Set ${\beta ^{\prime }}={\textit{SH}_{1}}({T_{1}},{T_{2}},{\textit{ID}_{\textit{PKI}}},{\textit{ID}_{\textit{CL}}},M)$.

(6) Output M if $\hat{e}(Q,{T_{0}})={\mathit{PKIPK}_{\textit{ID}}}\cdot \hat{e}({T_{1}},(W+{\beta ^{\prime }}\cdot T))$ is true.


√ $\begin{array}[t]{r@{\hskip4.0pt}c@{\hskip4.0pt}l}E{K^{\prime }}& =& {\textit{EK}^{\prime }_{1}}\oplus {\textit{EK}^{\prime }_{2}}\\ {} & =& {\textit{TEK}_{1}}\cdot \hat{e}({T_{1}},{\mathit{CLSK}_{\mathit{ID},k,1}})\oplus {\textit{TEK}_{2}}\cdot \hat{e}({T_{1}},{\mathit{CLISK}_{\mathit{ID},k,1}})\\ {} & =& \hat{e}({T_{1}},{\mathit{CLSK}_{\mathit{ID},k,0}})\cdot \hat{e}({T_{1}},{\mathit{CLSK}_{\mathit{ID},k,1}})\oplus \hat{e}({T_{1}},{\mathit{CLISK}_{\mathit{ID},k,0}})\\ {} & & \cdot \hat{e}({T_{1}},{\mathit{CLISK}_{\mathit{ID},k,1}})\\ {} & =& \hat{e}({T_{1}},{\mathit{CLSK}_{\textit{ID}}})\oplus \hat{e}({T_{1}},{\mathit{CLISK}_{\textit{ID}}})\\ {} & =& \hat{e}(n\cdot Q,{\mathit{CLSK}_{\textit{ID}}})\oplus \hat{e}(n\cdot Q,{\mathit{CLISK}_{\textit{ID}}})\\ {} & =& \hat{e}{(Q,{\mathit{CLSK}_{\textit{ID}}})^{n}}\oplus \hat{e}\big(n\cdot Q,{\textit{SK}_{\textit{KGC}}}+\big(f\cdot (W+\rho \cdot T)\big)\big)\\ {} & =& \hat{e}{(Q,{\mathit{CLSK}_{\textit{ID}}})^{n}}\oplus \hat{e}(n\cdot Q,{\textit{SK}_{\textit{KGC}}})\cdot \hat{e}\big(n\cdot Q,\big(f\cdot (W+\rho \cdot T)\big)\big)\\ {} & =& \hat{e}{(Q,{\mathit{CLSK}_{\textit{ID}}})^{n}}\oplus \hat{e}{(Q,{\textit{SK}_{\textit{KGC}}})^{n}}\cdot \hat{e}\big(f\cdot Q,\big(n\cdot (W+\rho \cdot T)\big)\big)\\ {} & =& {({\mathit{CLPK}_{\textit{ID}}})^{n}}\oplus {\big({\textit{PK}_{\textit{KGC}}}\cdot \hat{e}\big({\mathit{CLIPK}_{\textit{ID}}},(W+\rho \cdot T)\big)\big)^{n}}\\ {} & =& {\textit{EK}_{1}}\oplus {\textit{EK}_{2}}.\end{array}$

√ $\begin{array}[t]{r@{\hskip4.0pt}c@{\hskip4.0pt}l}\hat{e}(Q,{T_{0}})& =& \hat{e}(Q,{\mathit{PKISK}_{\mathit{ID},j,1}}+TS)\\ {} & =& \hat{e}(Q,{\mathit{PKISK}_{\mathit{ID},j,1}}+\big({\mathit{PKISK}_{\mathit{ID},j,0}}+\big(n\cdot (W+\beta \cdot T)\big)\big)\\ {} & =& \hat{e}\big(Q,{\mathit{PKISK}_{\textit{ID}}}+\big(n\cdot (W+\beta \cdot T)\big)\big)\\ {} & =& \hat{e}(Q,{\mathit{PKISK}_{\textit{ID}}})\cdot \hat{e}\big(Q,\big(n\cdot (W+\beta \cdot T)\big)\big)\\ {} & =& {\mathit{PKIPK}_{\textit{ID}}}\cdot \hat{e}\big(n\cdot Q,(W+\beta \cdot T)\big)\\ {} & =& {\mathit{PKIPK}_{\textit{ID}}}\cdot \hat{e}\big({T_{1}},\big(W+{\beta ^{\prime }}\cdot T\big)\big).\end{array}$
5 Security Analysis
Theorem 1.
Proof.

– Initialization phase. B runs the System setup in Definition 1 to generate $\textit{SP}=\{G,{G_{1}},\hat{e},Q,{Q_{1}},q,W,T,\textit{SE}/\textit{SD},{\textit{SH}_{0}},{\textit{SH}_{1}}\}$, the CA’s secret/public key pair (${\textit{SK}_{\textit{CA}}},{\textit{PK}_{\textit{CA}}}$) and the KGC’s secret/public key pair $({\textit{SK}_{\textit{KGC}}},{\textit{PK}_{\textit{KGC}}})$. Additionally, if A is an ${A_{\textit{II}}}$, both ${\textit{SK}_{\textit{CA}}}$ and ${\textit{SK}_{\textit{KGC}}}$ are sent to ${A_{\textit{II}}}$. Also, six initially empty lists ${\textit{LT}_{a}}$, ${\textit{LT}_{b}}$, ${\textit{LT}_{\textit{SK}}}$, ${\textit{LT}_{\textit{ISK}}}$, ${\textit{LT}_{\textit{HSE}}}$ and ${\textit{LT}_{\textit{SH}}}$ are constructed as follows.

• ${\textit{LT}_{a}}$: Each element of G is recorded as a pair of (multivariate polynomial, bitstring) in ${\textit{LT}_{a}}$, represented as ($\Psi {G_{x,y,z}},\Omega {G_{x,y,z}}$), where the three x, y and z, denote typex query, yth query and zth item, respectively. Also, B records ($\Psi Q,\Omega {G_{S,0,1}}$), ($\Psi W,\Omega {G_{S,0,2}}$), ($\Psi T,\Omega {G_{S,0,3}}$), $(\Psi {\textit{SK}_{\textit{CA}}},\Omega {G_{S,0,4}})$ and $(\Psi {\textit{SK}_{\textit{KGC}}},\Omega {G_{S,0,5}})$ in ${\textit{LT}_{a}}$. In the subsequent Query phase, there is an autotransformation process that can transform $\Psi {G_{x,y,z}}$ (or $\Omega {G_{x,y,z}}$) to $\Omega {G_{x,y,z}}$ (or $\Psi {G_{x,y,z}}$).

• ${\textit{LT}_{b}}$: Each element of ${G_{1}}$ is recorded as a pair of (multivariate polynomial, bitstring) in ${\textit{LT}_{b}}$, represented as $(\Psi {G_{1,x,y,z}},\Omega {G_{1,x,y,z}})$, where x, y and z are identical with those in ${\textit{LT}_{a}}$. Additionally, B records $(\Psi {\textit{PK}_{\textit{CA}}},\Omega {G_{1,S,0,1}})$ and ($\Psi {\textit{PK}_{\textit{KGC}}},\Omega {G_{1,S,0,1}}$) in ${\textit{LT}_{b}}$. Also, there is an autotransformation process that can transform $\Psi {G_{1,x,y,z}}$ (or $\Omega {G_{1,x,y,z}}$) to $\Omega {G_{1,x,y,z}}$ (or $\Psi {G_{1,x,y,z}}$).

• ${\textit{LT}_{\textit{SK}}}$: A secret/public key pair of ${\textit{ID}_{\textit{PKI}}}/{\textit{ID}_{\textit{CL}}}$ is recorded as a tuple $({\textit{ID}_{\textit{PKI}}}/{\textit{ID}_{\textit{CL}}},\Psi {\mathit{PKISK}_{\textit{ID}}}/\Psi {\mathit{CLSK}_{\textit{ID}}},\Psi {\mathit{PKIPK}_{\textit{ID}}}/\Psi {\mathit{CLPK}_{\textit{ID}}})$ in ${\textit{LT}_{\textit{SK}}}$.

• ${\textit{LT}_{\textit{ISK}}}$: An identity secret/public key pair of ${\textit{ID}_{\textit{CL}}}$ is recorded as a tuple $({\textit{ID}_{\textit{CL}}},\Psi {\mathit{CLISK}_{\textit{ID}}},\Psi {\mathit{CLIPK}_{\textit{ID}}})$ in ${\textit{LT}_{\textit{ISK}}}$.

• ${L_{\textit{HSE}}}$: The related contents of requesting the Hybrid signcryption query $(M,{\textit{ID}_{\textit{PKI}}},{\textit{ID}_{\textit{CL}}})$ are recorded as a tuple $(M,\Psi {T_{0}},\Psi {T_{1}},{T_{2}},\Psi {\textit{EK}_{1}},\Psi {\textit{EK}_{2}},\Psi \beta ,{\textit{ID}_{\textit{PKI}}},{\textit{ID}_{\textit{CL}}})$ in ${L_{\textit{HSE}}}$.

• ${\textit{LT}_{\textit{SH}}}$: The related contents of requesting ${\textit{SH}_{1}}()$ are recorded as a pair $(\Omega {T_{1}}{T_{2}}{\textit{ID}_{\textit{PKI}}}{\textit{ID}_{\textit{CL}}}M,\Omega \beta )$.


– Query phase: A (${A_{I}}$ or ${A_{\textit{II}}}$) may adaptively request various kinds of queries (oracles) to B at most p times as follows.

• ${O_{a}}$ query ($\Omega {G_{O,r,i}},\Omega {G_{O,r,j}},\textit{OP}$): B first transforms $(\Omega {G_{O,r,i}},\Omega {G_{O,r,j}})$ to $(\Psi {G_{O,r,i}},\Psi {G_{O,r,j}})$. B computes $\Psi {G_{O,r,k}}=\Psi {G_{O,r,i}}+\Psi {G_{O,r,j}}$ if $\textit{OP}$ is “addition”. Otherwise, B computes $\Psi {G_{O,l,k}}=\Psi {G_{O,r,i}}\Psi {G_{O,r,j}}$. Also, B records ($\Psi {G_{O,r,k}},\Omega {G_{O,r,k}}$) in ${\textit{LT}_{a}}$.

• ${O_{m}}$ query $(\Omega {G_{1,O,r,i}},\Omega {G_{1,O,r,j}},\textit{OP})$: B first transforms $(\Omega {G_{1,O,r,i}},\Omega {G_{1,O,r,j}})$ to $(\Psi {G_{1,O,r,i}},\Psi {G_{1,O,r,j}})$. B computes $\Psi {G_{1,O,r,k}}=\Psi {G_{1,O,r,i}}+\Psi {G_{1,O,r,j}}$ if $\textit{OP}$ is “multiplication”. Otherwise, B computes $\Psi {G_{1,O,r,k}}=\Psi {G_{1,O,r,i}}\Psi {G_{1,O,r,j}}$. Also, B records ($\Psi {G_{1,O,r,k}},\Omega {G_{1,O,r,k}}$) in ${\textit{LT}_{b}}$.

• ${O_{\hat{e}}}$ query ($\Omega {G_{O,l,i}},\Omega {G_{O,l,j}}$): B first transforms $(\Omega {G_{O,r,i}},\Omega {G_{O,l,j}})$ to $(\Psi {G_{O,r,i}},\Psi {G_{O,r,j}})$. B computes $\Psi {G_{1,O,r,k}}=\Psi {G_{O,r,i}}\cdot \Psi {G_{O,r,j}}$ and records $(\Psi {G_{1,O,r,k}},\Omega {G_{1,O,r,k}})$ in ${\textit{LT}_{b}}$.

• Signer secret key query $({\textit{ID}_{\textit{PKI}}})$: B uses ${\textit{ID}_{\textit{PKI}}}$ to find $({\textit{ID}_{\textit{PKI}}},\Psi {\mathit{PKISK}_{\textit{ID}}},\Psi {\mathit{PKIPK}_{\textit{ID}}})$ in ${\textit{LT}_{\textit{SK}}}$. If found, B transforms $\Psi {\mathit{PKISK}_{\textit{ID}}}$ to return $\Omega {\mathit{PKISK}_{\textit{ID}}}$. Otherwise, B chooses $\Psi \textit{GR}$ in G and computes $\Psi \textit{PKR}=\Psi Q\cdot \Psi \textit{GR}$. B records $({\textit{PKI}_{\textit{ID}}},\Psi {\mathit{PKISK}_{\textit{ID}}}=\Psi \textit{GR},\Psi {\mathit{PKIPK}_{\textit{ID}}}=\Psi \textit{PKR})$ in ${\textit{LT}_{\textit{SK}}}$. Also, B respectively records ($\Psi \textit{GR},\Omega \textit{GR}$) and ($\Psi \textit{PKR},\Omega \textit{PKR}$) in ${\textit{LT}_{a}}$ and ${\textit{LT}_{b}}$, and returns $\Omega \textit{GR}$ and $\Omega \textit{PKR}$.

• Signer certificate query (${\textit{ID}_{\textit{PKI}}},\Omega {\mathit{PKIPK}_{\textit{ID}}}$): For the ith request of this query, B first updates the old secret key $\Psi {\textit{SK}_{\textit{CA}}}=(\Psi {\textit{SK}_{\textit{CA},i1,0}},\Psi {\textit{SK}_{\textit{CA},i1,1}}$) to the new secret key $\Psi {\textit{SK}_{\textit{CA}}}=(\Psi {\textit{SK}_{\textit{CA},i,0}},\Psi {\textit{SK}_{\textit{CA},i,1}}$), and uses ($\Psi {\textit{SK}_{\textit{CA},i,0}},\Psi {\textit{SK}_{\textit{CA},i,1}}$) to generate and return the signer ${\textit{ID}_{\textit{PKI}}}$’s certificate ${\textit{CRT}_{\textit{ID}}}$.

• Signer certificate leak query $(i,{f_{\textit{SCG},i}},{h_{\textit{SCG},i}})$: For the ith request of the Signer certificate query, the leak query can only be requested once. B returns $\Delta {f_{\textit{SCG},i}}={f_{\textit{SCG},i}}({\textit{SK}_{\textit{CA},i,0}}$) and $\Delta {h_{\textit{SCG},i}}={h_{\textit{SCG},i}}({\textit{SK}_{\textit{CA},i,1}}$).

• Decrypter identity secret key query (${\textit{ID}_{\textit{CL}}}$). For the ith request of this query, B first updates the old secret key $\Psi {\textit{SK}_{\textit{KGC}}}=(\Psi {\textit{SK}_{\textit{KGC},i1,0}},\Psi {\textit{SK}_{\textit{KGC},i1,1}}$) to the new secret key $\Psi {\textit{SK}_{\textit{KGC}}}=(\Psi {\textit{SK}_{\textit{KGC},i,0}},\Psi {\textit{SK}_{\textit{KGC},i,1}}$). B chooses $\Psi \textit{GT}$ and $\Psi \rho $ in G, and generates the $\textit{decrypter}$ ${\textit{ID}_{\textit{CL}}}$’s identity secret/public key pair ($\Psi {\mathit{CLISK}_{\textit{ID}}}=\Psi {\textit{SK}_{\textit{KGC}}}+\Psi \textit{GT}\cdot (\Psi W+\Psi \rho \cdot \Psi T),\Psi {\mathit{CLIPK}_{\textit{ID}}}=\Psi \textit{GT})$. B records ($\Psi {\mathit{CLISK}_{\textit{ID}}},\Omega {\mathit{CLISK}_{\textit{ID}}}$), ($\Psi {\mathit{CLIPK}_{\textit{ID}}},\Omega {\mathit{CLIPK}_{\textit{ID}}}$) and ($\Psi \rho ,\Omega \rho ={\textit{ID}_{\textit{CL}}}\Omega {\mathit{CLIPK}_{\textit{ID}}}$) in ${\textit{LT}_{a}}$. Also, B records (${\textit{ID}_{\textit{CL}}},\Psi {\mathit{CLISK}_{\textit{ID}}},\Psi {\mathit{CLIPK}_{\textit{ID}}}$) in ${\textit{LT}_{\textit{ISK}}}$, and returns both $\Omega {\mathit{CLISK}_{\textit{ID}}}$ and $\Omega {\mathit{CLIPK}_{\textit{ID}}}$.

• Decrypter identity secret key leak query $(i,{f_{\textit{ISKG},i}},{h_{\textit{ISKG},i}})$. For the ith request of the Decrypter identity secret key query, the leak query can only be requested once. B returns $\Delta {f_{\textit{ISKG},i}}={f_{\textit{ISKG},i}}({\textit{SK}_{\textit{KGC},i,0}})$ and $\Delta {h_{\textit{ISKG},i}}={h_{\textit{ISKG},i}}({\textit{SK}_{\textit{KGC},i,1}})$.

• Decrypter public key replace query $({\textit{ID}_{\textit{CL}}},(\Omega {\textit{CLPK}^{\prime }_{\textit{ID}}},\Omega {\textit{CLIPK}^{\prime }_{\textit{ID}}}))$. B transforms $(\Omega {\textit{CLPK}^{\prime }_{\textit{ID}}},\Omega {\textit{CLIPK}^{\prime }_{\textit{ID}}})$ to $(\Psi {\textit{CLPK}^{\prime }_{\textit{ID}}},\Psi {\textit{CLIPK}^{\prime }_{\textit{ID}}})$. B modifies $({\textit{CL}_{\textit{ID}}},,\Psi {\textit{CLPK}^{\prime }_{\textit{ID}}})$ in ${\textit{LT}_{\textit{SK}}}$ and $(C{L_{\textit{ID}}},,\Psi {\textit{CLIPK}^{\prime }_{\textit{ID}}})$ in ${\textit{LT}_{\textit{ISK}}}$.

• Decrypter secret key query (${\textit{ID}_{\textit{CL}}}$). B uses ${\textit{ID}_{\textit{CL}}}$ to find $({\textit{ID}_{\textit{CL}}},\Psi {\mathit{CLSK}_{\textit{ID}}},\Psi {\mathit{CLPK}_{\textit{ID}}})$ in ${\textit{LT}_{\textit{SK}}}$. If found, B transforms $\Psi {\mathit{CLSK}_{\textit{ID}}}$ to return $\Omega {\mathit{CLSK}_{\textit{ID}}}$. Otherwise, B chooses $\Psi GR$ in G and computes $\Psi \textit{PKR}=\Psi Q\cdot \Psi \textit{GR}$. B records $({\textit{ID}_{\textit{CL}}},\Psi {\mathit{CLSK}_{\textit{ID}}}=\Psi \textit{GR},\Psi {\mathit{CLPK}_{\textit{ID}}}=\Psi \textit{PKR})$ in ${\textit{LT}_{\textit{SK}}}$. Also, B respectively records ($\Psi \textit{GR},\Omega \textit{GR}$) and $(\Psi \textit{PKR},\Omega \textit{PKR})$ in ${\textit{LT}_{a}}$ and ${\textit{LT}_{b}}$, and returns both $\Omega \textit{GR}$ and $\Omega \textit{PKR}$.

• Hybrid signcryption query ($M,{\textit{ID}_{\textit{PKI}}},{\textit{ID}_{\textit{CL}}}$): B first updates the signer ${\textit{ID}_{\textit{PKI}}}$’s old secret key $\Psi {\mathit{PKISK}_{\textit{ID}}}=(\Psi {\mathit{PKISK}_{\mathit{ID},j1,0}},\Psi {\mathit{PKISK}_{\mathit{ID},j1,1}})$ to the new secret key $\Psi {\mathit{PKISK}_{\textit{ID}}}=(\Psi {\mathit{PKISK}_{\mathit{ID},j,0}},\Psi {\mathit{PKISK}_{\mathit{ID},j,1}})$. B performs the following detailed processes to return $\textit{CT}$.

(1) By ${\textit{ID}_{\textit{CL}}}$, find (${\textit{ID}_{\textit{CL}}},\Psi {\mathit{CLIPK}_{\textit{ID}}},\Psi {\mathit{CLISK}_{\textit{ID}}}$) in ${\textit{LT}_{\textit{ISK}}}$ and (${\textit{ID}_{\textit{CL}}},\Psi {\mathit{CLPK}_{\textit{ID}}},\Psi {\mathit{CLSK}_{\textit{ID}}}$) in ${\textit{LT}_{\textit{SK}}}$. Meanwhile, transform $\Psi {\mathit{CLIPK}_{\textit{ID}}}$ to $\Omega {\mathit{CLIPK}_{\textit{ID}}}$.

(2) Select $\Psi \rho $ and $\Psi n$ in G and record ($\Psi \rho ,{\textit{ID}_{\textit{CL}}}\Omega {\mathit{CLIPK}_{\textit{ID}}}$) in ${\textit{LT}_{a}}$.

(3) Compute $\Psi {\textit{EK}_{1}}=\Psi {\mathit{CLPK}_{\textit{ID}}}\cdot \Psi n$ and $\Psi {\textit{EK}_{2}}=(\Psi {\textit{PK}_{\textit{KGC}}}+(\Psi {\mathit{CLIPK}_{\textit{ID}}}\cdot (\Psi W+\Psi \rho \cdot \Psi T)))\cdot \Psi n$.

(4) Transform $\Psi n$, $\Psi {\textit{EK}_{1}}$ and $\Psi {\textit{EK}_{2}}$ to $\Omega n$, $\Omega {\textit{EK}_{1}}$ and $\Omega {\textit{EK}_{2}}$, respectively.

(5) Compute $\Omega EK=\Omega {\textit{EK}_{1}}\oplus \Omega {\textit{EK}_{2}}$ and ${T_{2}}={\textit{SE}_{\Omega EK}}(M)$.

(6) Compute $\Omega \beta ={\textit{SH}_{1}}(\Omega n,{T_{2}},{\textit{ID}_{\textit{PKI}}},{\textit{ID}_{\textit{CL}}},M)$, select $\Omega \beta $ in G, and record ($\Phi \beta ,\Omega \beta $) in ${\textit{LT}_{a}}$.

(7) Compute $\Psi {T_{0}}=\Psi {\mathit{PKISK}_{\textit{ID}}}+(\Psi n\cdot (\Psi W+\Psi T\cdot \Psi \beta ))$ and transform $\Psi {T_{0}}$ to $\Omega {T_{0}}$.

(8) Record ($M,\Psi {T_{0}},\Psi n,{T_{2}},\Psi {\textit{EK}_{1}},\Psi {\textit{EK}_{2}},\Psi \beta ,{\textit{ID}_{\textit{PKI}}},{\textit{ID}_{\textit{CL}}}$) in ${L_{\textit{HSE}}}$.

(9) Return $\textit{CT}=(\Omega {T_{0}},\Omega n,{T_{2}},{\textit{ID}_{\textit{PKI}}},{\textit{ID}_{\textit{CL}}})$.


• Hybrid signcryption leak query (${\textit{ID}_{\textit{PKI}}},j,{f_{\textit{HS},j}},{h_{\textit{HS},j}}$): For the signer ${\textit{ID}_{\textit{PKI}}}$’s jth request of the Decrypter identity secret key query, the leak query can only be requested once. B returns $\Delta {f_{\textit{HS},j}}={f_{\textit{HS},j}}({\mathit{PKISK}_{\mathit{ID},j,0}})$ and $\Delta {h_{\textit{HS},j}}={h_{\textit{HS},j}}({\mathit{PKISK}_{\mathit{ID},j,1}})$.

• Hybrid unsigncryption query ($\textit{CT},{\textit{ID}_{\textit{PKI}}},{\textit{ID}_{\textit{CL}}}$): B first updates the decrypter ${\textit{ID}_{\textit{CL}}}$’s old secret key (${\mathit{CLSK}_{\mathit{ID},k1,0}},{\mathit{CLSK}_{\mathit{ID},k1,1}}$) and identity secret key (${\mathit{CLISK}_{\mathit{ID},k1,0}},{\mathit{CLISK}_{\mathit{ID},k1,1}}$) to $\Psi {\mathit{CLSK}_{\textit{ID}}}=(\Psi {\mathit{CLSK}_{\mathit{ID},k,0}},\Psi {\mathit{CLSK}_{\mathit{ID},k,1}})$ and $\Psi {\mathit{CLISK}_{\textit{ID}}}=(\Psi {\mathit{CLISK}_{\mathit{ID},k,0}},\Psi {\mathit{CLISK}_{\mathit{ID},k,1}})$, respectively. B performs the following detailed processes to return M.

(1) By ${\textit{ID}_{\textit{PKI}}}$, find (${\textit{ID}_{\textit{PKI}}},\Psi {\mathit{PKIPK}_{\textit{ID}}}$) in ${\textit{LT}_{\textit{SK}}}$ and transform $\Psi {\mathit{PKIPK}_{\textit{ID}}}$ to $\Omega {\mathit{PKIPK}_{\textit{ID}}}$.

(2) Transform $\Omega {T_{0}}$ and $\Omega n$ to $\Psi {T_{0}}$ and $\Psi n$, respectively.

(3) Compute $\Psi {\textit{EK}_{1}}=\Psi n\cdot \Psi {\mathit{CLSK}_{\textit{ID}}}$ and $\Psi {\textit{EK}_{2}}=\Psi n\cdot \Psi {\mathit{CLISK}_{\textit{ID}}}$.

(4) Set $\Omega \beta ={\textit{SH}_{1}}(\Omega n,{T_{2}},{\textit{ID}_{\textit{PKI}}},{\textit{ID}_{\textit{CL}}},M)$ and transform $\Omega \beta $ to $\Psi \beta $.

(5) Use ($\Psi {T_{0}},\Psi n,{T_{2}},\Psi n,\Psi {\textit{EK}_{1}},\Psi n,\Psi {\textit{EK}_{2}},\Psi \beta ,{\textit{ID}_{\textit{PKI}}},{\textit{ID}_{\textit{CL}}}$) to find ($M,\Psi {T_{0}},\Psi {T_{1}},{T_{2}},\Psi {\textit{EK}_{1}},\Psi {\textit{EK}_{2}},\Psi \beta ,{\textit{ID}_{\textit{PKI}}},{\textit{ID}_{\textit{CL}}}$) in ${L_{\textit{HSE}}}$.

(6) If found, return M. Otherwise, return “invalid”.


• Hybrid unsigncryption leak query (${\textit{ID}_{\textit{CL}}},k,{f_{\textit{HUS},k}},{h_{\textit{HUS},k}}$): For the decrypter ${\textit{ID}_{\textit{CL}}}$’s kth request of the Decrypter identity secret key query, the leak query can only be requested once. B returns $\Delta {f_{\textit{HUS},k}}={f_{\textit{HUS},k}}({\mathit{CLSK}_{\mathit{ID},k,0}},{\mathit{CLSK}_{\mathit{ID},k,1}})$ and $\Delta {h_{\textit{HUS},k}}={h_{\textit{HUS},k}}({\mathit{CLISK}_{\mathit{ID},k,0}},{\mathit{CLISK}_{\mathit{ID},k,1}})$.


– Forgery phase: Assume that A forges a ciphertext ${\textit{CT}^{\ast }}=({T_{0}^{\ast }},{{T^{\ast }}_{1}},{{T^{\ast }}_{2}},{{\textit{ID}^{\ast }}_{\textit{PKI}}},{{\textit{ID}^{\ast }}_{\textit{CL}}})$ for the message ${M^{\ast }}$, we say that A wins ${\textit{Game}_{1}}$ when three provisions mentioned in the Forgery phase of Definition 2 (i.e. ${\textit{Game}_{1}}$) are true.

■ The evaluation of ${\textbf{Adv}_{\textbf{1}}}({\textbf{A}_{\textbf{I}\textbf{wo}}})$: In the GBG model, if adversaries can find collisions in G and ${G_{1}}$, the discrete logarithm problem in G and ${G_{1}}$ will be resolved. The total number of elements in both ${\textit{LT}_{a}}$ and ${\textit{LT}_{b}}$ is first counted. In the Query phase, ${A_{I}}$ may request various kinds of queries (oracles) to B at most p times while the number of the added elements in a query (i.e. the Hybrid signcryption query) is at most 6. Therefore, we have ${\textit{LT}_{a}}+{\textit{LT}_{b}}\leqq 6p$. Also, the maximal degrees of polynomials in ${\textit{LT}_{a}}$ and ${\textit{LT}_{b}}$ are 3 and 6, respectively. Moreover, ${\textit{Adv}_{1}}({A_{Iwo}})$ includes two cases’ probabilities as evaluated below.

(1) $\text{Pb}[\textit{Forgery}]$: Let $\text{Pb}[\textit{Forgery}]$ denote the probability that ${A_{I}}$ forges a ciphertext ${\textit{CT}^{\ast }}=({{T^{\ast }}_{0}},{{T^{\ast }}_{1}},{{T^{\ast }}_{2}},{{\textit{ID}^{\ast }}_{\textit{PKI}}},{{\textit{ID}^{\ast }}_{\textit{CL}}})$ for a message ${M^{\ast }}$ that satisfies $\hat{e}(Q,{{T^{\ast }}_{0}})={\mathit{PKIPK}_{{\textit{ID}^{\ast }}}}\cdot \hat{e}({{T^{\ast }}_{1}},(W+{\beta ^{\prime }}\cdot T))$ in the Hybrid unsigncryption. That is, we have $\Psi Q\cdot \Psi {{T^{\ast }}_{0}}=\Psi {\mathit{PKIPK}_{ID\ast }}+\Psi {{T^{\ast }}_{1}}\cdot (\Psi W+\Psi {\beta ^{\prime }}\cdot \Psi T)$ and set $\Psi f=\Psi Q\cdot \Psi {{T^{\ast }}_{0}}(\Psi {\mathit{PKIPK}_{ID\ast }}+\Psi {{T^{\ast }}_{1}}\cdot (\Psi W+\Psi {\beta ^{\prime }}\cdot \Psi T))$ that has degree 3. By Lemma 2, we have $\text{Pb}[\textit{Forgery}]=3/q$ because the probability of $\Psi f=0$ is $3/q$.

(2) $\text{Pb}[\textit{Collision}]$: Let $\text{Pb}[\textit{Collision}]$ denote the probability that ${A_{I}}$ may find collisions in ${\textit{LT}_{a}}$ or ${\textit{LT}_{b}}$. Assume that the polynomials in ${\textit{LT}_{a}}$ have s variates, represented by using s random integers ${u_{i}}\in {{Z_{q}}^{\ast }}$, for $i=1,2,\dots ,s$. Let ($\Psi {G_{j}},\Psi {G_{k}}$) denote a pair of two different polynomials in ${\textit{LT}_{a}}$ so that there are $\left(\genfrac{}{}{0pt}{}{{\textit{LT}_{a}}}{2}\right)$ pairs of ($\Psi {G_{j}},\Psi {G_{k}}$). For each pair, we set $\Psi {G_{l}}({u_{1}},{u_{2}},\dots ,{u_{s}})=\Psi {G_{j}}\Psi {G_{k}}$. If there exists any $\Psi {G_{l}}=0$, a collision in ${\textit{LT}_{a}}$ has occurred. Since there are $\left(\genfrac{}{}{0pt}{}{{\textit{LT}_{a}}}{2}\right)$ pairs of ($\Psi {G_{j}},\Psi {G_{k}}$) and the maximal degree of polynomials in ${\textit{LT}_{a}}$ is 3, we have that $\text{Pb}[\textit{Collision}]$ in ${\textit{LT}_{a}}$ is $(3/q)\left(\genfrac{}{}{0pt}{}{{\textit{LT}_{a}}}{2}\right)$. By similar arguments, we have that $\text{Pb}[\textit{Collision}]$ in ${\textit{LT}_{b}}$ is $(6/q)\left(\genfrac{}{}{0pt}{}{{\textit{LT}_{b}}}{2}\right)$. Since ${\textit{LT}_{a}}+{\textit{LT}_{b}}\leqq 6p$, we have\[\begin{aligned}{}\text{Pb}[\textit{Collision}]& \leqq (3/q)\left(\genfrac{}{}{0pt}{}{{\textit{LT}_{a}}}{2}\right)+(6/q)\left(\genfrac{}{}{0pt}{}{{\textit{LT}_{b}}}{2}\right)\\ {} & \leqq (6/q){\big({\textit{LT}_{a}}+{\textit{LT}_{b}}\big)^{2}}\\ {} & \leqq 216{p^{2}}/q=O\big({p^{2}}/q\big).\end{aligned}\]


■ The evaluation of ${\textbf{Adv}_{\textbf{1}}}({\textbf{A}_{\textbf{I}}})$: By ${\textit{Adv}_{1}}({A_{Iwo}})$, we evaluate the advantage ${\textit{Adv}_{1}}({A_{I}})$ of ${A_{I}}$ with requesting all leak queries in ${\textit{Game}_{1}}$. These leak queries include Signer certificate leak query, Decrypter identity secret key leak query, Hybrid signcryption leak query and Hybrid unsigncryption leak query. Due to the key updating process, any two leaked portions of a secret key are mutually independent. Therefore, ${A_{I}}$ could gain at most $2\tau $ bits of ${\textit{SK}_{\textit{CA}}}$, $2\tau $ bits of ${\textit{SK}_{\textit{KGC}}}$, $2\tau $ bits of ${\mathit{PKISK}_{\textit{ID}}}$, and $2\tau $ bits of both ${\mathit{CLSK}_{\textit{ID}}}$ and ${\mathit{CLISK}_{\textit{ID}}}$. Hence, we have\[ {\textit{Adv}_{1}}({A_{I}})\leqq {\textit{Adv}_{1}}({A_{Iwo}})\cdot {2^{2\tau }}=O\big(\big({p^{2}}/q\big)\cdot {2^{2\tau }}\big).\]It is obvious that ${\textit{Adv}_{1}}({A_{I}})=O(({p^{2}}/q)\cdot {2^{2\tau }})$ is negligible if $p=poly(\log q)$ by Lemma 2.

■ The evaluation of ${\textbf{Adv}_{\textbf{1}}}({\textbf{A}_{\textbf{II}}})$: ${A_{\textit{II}}}$ is used to model the attacking ability of a malicious CA/KGC who has both ${\textit{SK}_{\textit{CA}}}$ and ${\textit{SK}_{\textit{KGC}}}$. Therefore, ${A_{\textit{II}}}$ could gain at most $2\tau $ bits of ${\mathit{PKISK}_{\textit{ID}}}$, and $2\tau $ bits of ${\mathit{CLSK}_{\textit{ID}}}$ or ${\mathit{CLISK}_{\textit{ID}}}$. By similar analysis of ${\textit{Adv}_{1}}({A_{I}})$, we also have ${\textit{Adv}_{1}}({A_{\textit{II}}})=O(({p^{2}}/q)\cdot {2^{2\tau }})$, that is negligible if $p=\textit{poly}(\log q)$ by Lemma 2.
Theorem 2.
Proof.

– Initialization phase: It is exactly the same as the Initialization phase in the proof of Theorem 1.

– Query phase: It is exactly like the Query phase of Theorem 1.

– Challenge phase: A selects a target decrypter ${{\textit{ID}^{\ast }}_{\textit{CL}}}$ and a message pair (${M_{0}},{M_{1}}$) as a challenge objective. B randomly selects $c\in \{0,1\}$ and generates a challenge ciphertext ${\textit{CT}^{\ast }}$ by running the Hybrid signcryption with (${M_{c}},{\textit{ID}_{\textit{PKI}}},{{\textit{ID}^{\ast }}_{\textit{CL}}}$). Also, B sends ${\textit{CT}^{\ast }}$ to A. Note that two provisions mentioned in the Challenge phase of Definition 3 (i.e. ${\textit{Game}_{2}}$) must be satisfied.

– Guessing phase: A outputs ${c^{\prime }}\in \{0,1\}$ and wins ${\textit{Game}_{2}}$ if ${c^{\prime }}=c$. Meanwhile, A’s advantage is defined as $Adv(A)=\text{Pb}[{c^{\prime }}=c]1/2$.

■ The evaluation of ${\textbf{Adv}_{\textbf{2}}}({\textbf{A}_{\textbf{I}\textbf{wo}}})$: ${\textit{Adv}_{2}}({A_{Iwo}})$ includes two cases’ probabilities as evaluated below.

(1) Pb[Guessing]: Since ${A_{Iwo}}$ is not permitted to request any leak query, there is no useful information about secret keys. Therefore, the probability of guessing ${c^{\prime }}=c$ is $1/2$, namely, $\text{Pb}[\textit{Guessing}]=1/2$.

(2) Pb[Collision]: The probability is identical to the probability Pb[Collision] in the proof of Theorem 1, namely, $\text{Pb}[\textit{Collision}]=O({p^{2}}/q)$.
\[\begin{aligned}{}{\textit{Adv}_{2}}({A_{Iwo}})& =\text{Pb}\big[{c^{\prime }}=c\big]1/2\big\\ {} & =\big\text{Pb}[\textit{Guessing}]1/2\big+\big\text{Pb}[\textit{Collision}]\big\\ {} & =O\big({p^{2}}/q\big).\end{aligned}\]
■ The evaluation of ${\textbf{Adv}_{\textbf{2}}}({\textbf{A}_{\textbf{I}}})$: By ${\textit{Adv}_{2}}({A_{Iwo}})$, we evaluate the advantage ${\textit{Adv}_{2}}({A_{I}})$ of ${A_{I}}$ with requesting all leak queries in ${\textit{Game}_{2}}$. By the same evaluation as ${\textit{Adv}_{1}}({A_{I}})$ in the proof of Theorem 1, ${A_{I}}$ could gain at most $2\tau $ bits of ${\textit{SK}_{\textit{CA}}}$, $2\tau $ bits of ${\textit{SK}_{\textit{KGC}}}$, $2\tau $ bits of ${\mathit{PKISK}_{\textit{ID}}}$, and $2\tau $ bits of both ${\mathit{CLSK}_{\textit{ID}}}$ and ${\mathit{CLISK}_{\textit{ID}}}$. Hence, we also have
\[ {\textit{Adv}_{2}}({A_{I}})\leqq {\textit{Adv}_{2}}({A_{Iwo}})\cdot {2^{2\tau }}=O\big(\big({p^{2}}/q\big)\cdot {2^{2\tau }}\big).\]It is obvious that ${\textit{Adv}_{2}}({A_{I}})=O(({p^{2}}/q)\cdot {2^{2\tau }})$ is negligible if $p=\textit{poly}(\log q)$ by Lemma 2. 

■ The evaluation of ${\textbf{Adv}_{\textbf{2}}}({\textbf{A}_{\textbf{II}}})$: ${A_{\textit{II}}}$ is used to model the attacking abilities of a malicious CA/KGC who has both ${\textit{SK}_{\textit{CA}}}$ and ${\textit{SK}_{\textit{KGC}}}$. Therefore, ${A_{\textit{II}}}$ could gain at most $2\tau $ bits of ${\mathit{PKISK}_{\textit{ID}}}$, and $2\tau $ bits of ${\mathit{CLSK}_{\textit{ID}}}$ or ${\mathit{CLISK}_{\textit{ID}}}$. By similar analysis of ${\textit{Adv}_{2}}({A_{I}})$, we also have ${\textit{Adv}_{2}}({A_{\textit{II}}})=O(({p^{2}}/q)\cdot {2^{2\tau }})$, that is negligible if $p=\textit{poly}(\log q)$ by Lemma 2.
6 Performance Analysis
Table 3
Devices  ${T_{bil}}$  ${T_{mul}}$  ${T_{exp}}$ 
PDA  ≈96 ms  ≈30 ms  ≈30 ms 
PC  ≈20 ms  ≈6 ms  ≈6 ms 
Table 4
Algorithms  Computational complexities  Costs on a PDA  Costs on a PC 
System setup  ${T_{bil}}+2{T_{mul}}$  156 ms  32 ms 
User key generation for the PKIPKS  ${T_{bil}}+3{T_{mul}}$  186 ms  38 ms 
User key generation for the CLPKS  ${T_{bil}}+7{T_{mul}}$  306 ms  62 ms 
Hybrid signcryption  ${T_{bil}}+5{T_{mul}}+2{T_{exp}}$  306 ms  62 ms 
Hybrid unsigncryption  $6{T_{bil}}+2{T_{mul}}$  636 ms  132 ms 