## 5 Security Analysis of the New Protocol
### Soundness  
**Theorem 1**. : _In the random oracle model, if a PPT adversary \(A_{1}\) wins Game 1 defined in Section 3 with non-negligible probability \(\epsilon\), then there is an algorithm \(B\) that can solve the \(CDH\) problem._  
**Proof of Theorem 1. ** Algorithm \(B\) is given \((g,g^{a},g^{b})\in G_{1}\); its goal is to output \(g^{ab}\in G_{1}\). Algorithm \(B\) simulates the challenger and interacts with as \(\text{A}_{1}\) follows. **Setup:**\(B\) produces the system parameters \(params\), secret key \(\delta\in Z_{q}^{*}\), and sets \(P=g^{a}\), while \(a\) keeps unknown. **H\({}_{1}\)-Query:** At any time, \(\text{A}_{1}\) can query the random oracle \(\text{H}_{1}\). To respond to these queries, algorithm \(B\) maintains a list of tuples \((ID,k_{1},K)\) as \(\mathit{Tab}_{1}\). When \(\text{A}_{1}\) queries the oracle \(\text{H}_{1}\) at the identity \(ID^{\prime}\), Algorithm \(B\) responds as follows:  
1. If \(ID^{\prime}\in\mathit{Tab}_{1}\), then algorithm \(B\) retrieves the tuple \((ID^{\prime},k_{1}{}^{\prime},K^{\prime})\) and responds with \(K^{\prime}\) to \(\text{A}_{1}\). 2. Otherwise, \(B\) picks a random \(k_{1}{}^{\prime}\in Z_{q}^{*}\) and computes \(K^{\prime}=g^{\text{b}k_{1}{}^{\prime}}\). Then, it adds the tuple \((ID^{\prime},k_{1}{}^{\prime},K^{\prime})\) to \(\mathit{Tab}_{1}\) and responds with \(K^{\prime}\) to \(\text{A}_{1}\). **PartialKey-Query:** At any time, \(\text{A}_{1}\) can query partial key for any identity \(ID^{\prime}\). If \(ID^{\prime}\
otin\mathit{Tab}_{1}\), \(B\) makes the \(H_{1}\)-Query. Otherwise, \(B\) maintains a list of tuples \((ID,\mathit{psk})\) as \(\mathit{Tab}_{2}\). When \(\text{A}_{1}\) queries the oracle PartialKey-Query at the identity, Algorithm \(B\) responds as follows:  
1. If \(ID^{\prime}\in\mathit{Tab}_{2}\), then algorithm \(B\) retrieves the tuple \((ID^{\prime},\mathit{psk}^{\prime})\) and responds \(\mathit{psk}^{\prime}\) to \(\text{A}_{1}\). 2. Otherwise, \(B\) computes \(\mathit{psk}^{\prime}=(K^{\prime})^{a}\). Then, it adds the tuple \((ID^{\prime},\mathit{psk}^{\prime})\) to \(\mathit{Tab}_{2}\) and responds \(\mathit{psk}^{\prime}\) to \(\text{A}_{1}\). **SecretValue-Query:** At any time, \(\text{A}_{1}\) can query secret value for any identity \(ID^{\prime}\), if \(ID^{\prime}\
otin\mathit{Tab}_{1}\) or \(ID^{\prime}\
otin\mathit{Tab}_{2}\). \(B\) firstly makes the \(\text{H}_{1}\)-Query or PartialKey-Query for the identity \(ID^{\prime}\). Then, \(B\) randomly chooses a value \(x^{\prime}\in Z_{q}^{*}\) as response to \(\text{A}_{1}\). **PublicKey-Query:** At any time, \(A_{1}\) can query public key for any identity \(ID^{\prime}\), if \(ID^{\prime}\
otin Tab_{1}\) or \(ID^{\prime}\
otin Tab_{2}\). \(B\) first makes the \(H_{1}\)-Query or PartialKey-Query for the identity \(ID^{\prime}\). Then, \(B\) computes \(PK^{\prime}=g^{x^{\prime}}\), in which \(x^{\prime}\) is the secret value from SecretValue-Query and responds \(PK^{\prime}\) to \(A_{1}\). **H\({}_{2}\)-Query:** At any time, \(A_{1}\) can query the random oracle \(H_{2}\) for \(\omega^{\prime}\). Algorithm \(B\) also maintains a list of tuples \((\omega,W)\) as \(Tab_{3}\). If \(\omega^{\prime}\in Tab_{3}\), then algorithm \(B\) retrieves the tuple \((\omega^{\prime},W^{\prime})\) and responds \(W^{\prime}\) to \(A_{1}\). Otherwise, \(B\) randomly selects \(k_{2}\in Z_{q}^{*}\) and computes \(W^{\prime}=g^{k_{2}}\). Then, it adds the tuple \((\omega^{\prime},W^{\prime})\) to \(Tab_{3}\) and responds \(W^{\prime}\) to \(A_{1}\). **Tag-Query:** At any time, \(A_{1}\) can query tag with \((m^{\prime},ID^{\prime})\). \(B\) first checks whether \(ID^{\prime}\in Tab_{1}\), \(ID^{\prime}\in Tab_{2}\), and \(\omega^{\prime}\in Tab_{3}\). If not, \(B\) will compute corresponding tuple and update \(Tab_{1}\), \(Tab_{2}\), and \(Tab_{3}\). After that, \(B\) can get corresponding information from \(Tab_{1}\), \(Tab_{2}\), and \(Tab_{3}\) and compute the tag \(T^{\prime}\) for \((\omega^{\prime},m^{\prime},ID^{\prime})\) by the algorithm Tag-Gen and returns it to \(A_{1}\).