## 5 Security Analysis of the New Protocol
### Soundness
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\({}_{2}\). Otherwise, \(B\) randomly selects \(l_{3}\in Z_{q}^{*}\) and computes \(W^{\prime}=g^{bl_{3}}\). Then, it adds the tuple \((\omega^{\prime},W^{\prime})\) to \(Tab_{3}\) and responds with \(W^{\prime}\) to A\({}_{2}\). **Tag-Query:** At any time, A\({}_{2}\) can query tag with \((m^{\prime},ID^{\prime},\omega^{\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 updates \(Tab_{1}\), \(Tab_{2}\), and \(Tab_{3}\). After that, \(B\) can get corresponding information from \(Tab_{1}\), \(Tab_{2}\), and \(Tab_{3}\), and computes the tag \(T^{\prime}\) for \((\omega^{\prime},m^{\prime},ID^{\prime})\) using the algorithm Tag-Gen and returns it to A\({}_{2}\). **Forge:** Eventually, A\({}_{2}\) outputs \((T^{\prime},\omega^{\prime},m^{\prime},ID^{\prime})\). \(T^{\prime}\) is the forged tag of the data block \(m^{\prime}\) on the identity \(ID^{\prime}\). **Analysis:** If A\({}_{2}\) wins Game 2, on the one hand, \(B\) can get  
\[e(T^{\prime},g)=e(H_{1}(ID^{\prime}\ +\ \delta)^{m^{\prime}},P)\cdot e(H_{2}( \omega^{\prime}),Y^{\prime})\]  
according to the verification Equation (1). On the other hand, \(B\) can retrieve \(H_{1}(ID^{\prime}\ +\ \delta)=g^{l_{1}{}^{\prime}}\) from \(Tab_{1}\), \(Y^{\prime}=g^{a\mu_{2}{}^{\prime}}\) from \(Tab_{2}\), and \(H_{2}(\omega^{\prime})=g^{bl_{3}}\) from \(Tab_{3}\). Thus, \(B\) gets \(e(T^{\prime},g)=e(g^{l_{1}{}^{\prime}m^{\prime}},P)\cdot e(g^{bl_{3}},g^{a\mu_ {2}})\). Finally, we can derive that  
\[g^{ab}=\big{(}T^{\prime}\big{)}^{\frac{1}{l_{1}^{\prime}l_{2}}l_{3}^{\text{ sgn}^{\prime}}}\]  
which means that \(B\) can solve the CDH problem with non-negligible probability \(\varepsilon\). However, according to CDH assumption, the advantage for \(B\) to solve the CDH problem in \(G_{1}\) is negligible. Thus, [PERSON]\({}_{2}\) cannot win Game 2. This completes the proof. **Theorem 3**. : _If the DL assumption holds, the adversary \(A_{3}\) wins Game 3 only at negligible probability._  
Proof of Theorem 3.: Let the challenge information be \(\mathit{chal}=\{Q,T_{1},T_{2}\}\). If [PERSON]\({}_{3}\) outputs \(\mathit{proof}^{\prime}\) and wins Game 3 at non-negligible probability, we can get the verification equation:  
\[\mathit{proof}^{\prime}=H_{3}(e(\sigma^{\prime},T_{1})\cdot\mu^{\prime-1})=H_ {3}(\prod_{j\in I}e(H_{2}\left(j||\mathit{frame}\right)^{v_{j}},Y_{ID_{j}}^{t }))\]  
in which \(\sigma^{\prime}\) is the forged tag for the forged data block \(m^{\prime}\) and \(\mu^{\prime}\) is produced by A\({}_{3}\). Assume the real proof is \(\mathit{proof}\) and the corresponding information is \((\sigma,\mu)\). We also get the verification equation:  
\[\mathit{proof}=H_{3}(e(\sigma,T_{1})\cdot\mu^{-1})=H_{3}(\prod_{j\in I}e(H_{2} \left(j||\mathit{frame}\right)^{v_{j}},Y_{ID_{j}}^{t}))\]  
Thus, we can derive from the above two verification equations that  
\[\frac{e(\sigma,T_{1})}{e(\sigma^{\prime},T_{1})}=\frac{\mu}{\mu^{\prime}}\]  
Because [PERSON]\({}_{3}\) wins the Game 3, there exists \(\sigma=\sigma^{\prime}\) and at least one data block \(m_{j}\
eq m_{j}{}^{\prime}\). Suppose \(m_{j}-m_{j}{}^{\prime}=\Delta m_{j}\). Then, we get \(\frac{\mu}{\mu^{\prime}}=1\), which is \(\frac{\prod\limits_{j\in I}T_{2j}^{v_{j}m_{j}}}{\prod\limits_{j\in I}T_{2j}^{ v_{j}m_{j}}}=1\). We can get \(\prod\limits_{j\in I}T_{2j}^{v_{j}\Delta m_{j}}=1\). Based on this conclusion, the DL problem can be solved as follows: Given two elements \(g,y\in G_{1}\) in which \(y=g^{a}\), we will compute \(a\in{Z_{q}}^{*}\). We randomly select \(\alpha_{j},\beta_{j}\in Z_{q}^{*}\) and let \({T_{2j}}^{v_{j}}\)= \(X_{j}=g^{a_{j}}y^{\beta_{j}}\).