## 6 Proof of Safety
\(\mathcal{B}\) randomly picks \(\xi_{1},\xi_{2},\zeta_{1},\zeta_{2}\in Z_{N}\) and generates one private key with the semi-functional form \(\widetilde{SK_{ID_{i}}}=\left(\widetilde{SK_{ID_{i}k,1}},\widetilde{SK_{ID_ {i}k,2}}\right)\), where  
\(\widetilde{SK_{ID_{i}k,1}}=(g_{1}^{r_{i}}R_{1}g_{1}^{\beta_{i}+\ldots+\beta_{i }k}(g_{2}^{r_{i}}g_{3}^{\zeta_{1}},g_{1}^{a}(h_{1}\prod\limits_{j=1}^{d}{u_{j }^{ID_{j}}})^{r_{i}}Q_{1}g_{1}^{\gamma_{i1}+\ldots+\gamma_{i}k}(g_{2}^{u}g_{3} ^{\zeta_{2}}))\) and  
\(\widetilde{SK_{ID_{i}k,2}}=(R_{1}^{\prime}g_{1}^{-\beta_{i},\ldots-\beta_{i }k}(g_{2}^{u}g_{3}^{\zeta_{1}})^{\zeta_{1}},Q_{1}^{\prime}g_{1}^{-\gamma_{i1} -\ldots-\gamma_{i}k}(g_{2}^{u}g_{3}^{\zeta_{2}})^{\zeta_{2}})\). (2) In case \(i>k\), \(\mathcal{B}\) calls the private key generation algorithm to gain one private key with normal form. (3) In case \(i=k\), \(\mathcal{B}\) randomly picks \(\beta_{i,k},\gamma_{i,k}\in Z_{N}\), \(r_{i}\in Z_{N}(i=\{1,\ldots,d\})\) and \(R_{i},Q_{i},R_{i}^{\prime},Q_{i}^{\prime}\in G_{p_{3}}\). \(\mathcal{B}\) generates a private key \(SK_{ID_{i}k}\)= \((SK_{ID_{i}k,1},SK_{ID_{i}k,2})\), where  
\(SK_{ID_{i}k,1}\)= \((SK_{ID_{i}k,1}^{1},SK_{ID_{i}k,1}^{2})=(T^{r_{i}}g_{1}^{\beta_{i}+\ldots+ \beta_{i}k}R_{1},g_{1}^{\alpha}(T^{\sum\limits_{i=1}^{d}{a_{i}ID_{i}+b}})^{r_{ i}}\)\(S_{1}^{\gamma_{i1}+\ldots+\gamma_{i}k}Q_{1})\) and  
\(SK_{ID_{i}k,2}(SK_{ID_{i}k,2}^{1},SK_{ID_{i}k,2}^{2})=(R_{1}^{\prime}g_{1}^{- \beta_{i},1-\ldots-\beta_{i}k},Q_{1}^{\prime}g_{1}^{-\gamma_{i1}-\ldots-\gamma _{i}k})\). Provided \(T\in G_{w_{1}w_{3}}\), this private key is normal. \(\mathcal{B}\) correctly imitates \(\text{EX}_{k-1}\). Provided \(T\in G_{1}\), this private key has a semi-functional form. \(\mathcal{B}\) correctly imitates \(\text{EX}_{k}\). **Challenge. **\(\mathcal{A}\) gives \(\mathcal{B}\) one set \(S^{*}=\{ID_{1}^{*},\ldots,D_{d}^{*}\}\) and two messages, \(M_{0}\) and \(M_{1}\), of equal size. \(\mathcal{B}\) randomly selects \(\beta\in\{0,1\}\) and calculates ciphertext  
\(CT=(C,Hdr)=(C,C_{1},C_{2})=(M_{\beta}e(g_{1},g_{1}^{z}g_{2}^{v})^{\alpha},(g_{ 1}^{z}g_{2}^{v})^{\sum\limits_{i=1}^{d}{a_{i}ID_{i}^{*}}},g_{1}^{z}g_{2}^{v})\)  
**Phase 2**. \(\mathcal{A}\) may query the private key for \(ID_{i}\
otin S^{*}\). **Guess. **\(\mathcal{A}\) output a guess \(\beta^{\prime}\). If \(\beta^{\prime}=\beta\), \(\mathcal{A}\) wins the game. When \(T\in G_{w_{1}w_{3}}\), \(\mathcal{B}\) properly simulates the game \(\text{EX}_{k-1}\). When \(T\in G_{1}\), \(\mathcal{B}\) properly simulates the game \(\text{EX}_{k}\). Thus, \(|\text{Pr}[\mathcal{B}(D,T\in G_{w_{1}w_{3}})=0]-\mathcal{B}(D,T\in G_{1})=0]|=| Ad_{\mathcal{A}}^{\text{EX}_{k-1}}-Ad_{\mathcal{A}}^{\text{EX}_{k}}|\geq\epsilon\). In other words, as long as \(\mathcal{A}\) achieves certain advantages in distinguishing \(\text{EX}_{k-1}\) and \(\text{EX}_{k}\), the challenger has the same advantages in destroying Assumption 2. This is not consistent with assumption 2. So, \(\left|Ad_{\mathcal{A}}^{\text{EX}_{k-1}}(L_{SK})-Ad_{\mathcal{A}}^{\text{EX}_{k }}(L_{SK})\right|<\epsilon\). For the same reason, as for \(i\in[k,q]\), \(\left|Ad_{\mathcal{A}}^{\text{EX}_{k}}(L_{SK})-Ad_{\mathcal{A}}^{\text{EX}_{k +1}}(L_{SK})\right|<\epsilon\),..., and \(\left|Ad_{\mathcal{A}}^{\text{EX}_{q-1}}(L_{SK})-Ad_{\mathcal{A}}^{\text{EX}_{q }}(L_{SK})\right|<\epsilon\). So,  
\[\left|Ad_{\mathcal{A}}^{\text{EX}_{k}}(L_{SK})-Ad_{\mathcal{A}}^{ \text{EX}_{q}}(L_{SK})\right|\] \[= \left|Ad_{\mathcal{A}}^{\text{EX}_{k}}(L_{SK})-Ad_{\mathcal{A}}^{ \text{EX}_{k+1}}(L_{SK})+\ldots+Ad_{\mathcal{A}}^{\text{EX}_{q-1}}(L_{SK})-Ad_{ \mathcal{A}}^{\text{EX}_{q}}(L_{SK})\right|\] \[< \left|Ad_{\mathcal{A}}^{\text{EX}_{k}}(L_{SK})-Ad_{\mathcal{A}}^{ \text{EX}_{k+1}}(L_{SK})\right|+\ldots+\left|Ad_{\mathcal{A}}^{\text{EX}_{q-1}}(L_{SK})- Ad_{\mathcal{A}}^{\text{EX}_{q}}(L_{SK})\right|\] \[< \left(q-k\right)\epsilon\]In addition, \(\big{|}Adv_{\mathcal{A}}^{\text{EXq}}(L_{SK})-Adv_{\mathcal{A}}^{\text{EXr}}(L_{ SK})\big{|}<\varepsilon\) (the proof will be given in Lemma 4).