## 6 Performance Analysis
### Computational Complexity Analysis
#### 6.1.2 Computational Complexity in the Batch Authentication Scenario  
Considering the large number of UEs in some scenarios, it is necessary to reduce the amount of authentication data and the processing time of authentication requests [16]. The batch authentication scenario in the proposed scheme can provide efficient services for these UE and lighten the LEOs' burden. We evaluated the cost of the first batch authentication and the rebatch authentication. We also estimated the computational complexity of the rebatch authentication. In the evaluation of first batch verification, we compared the proposed scheme with the related works of [PERSON] et al. [11] and [PERSON] et al. [12]. In order to contrast with the unlinkable authentication scenario, we compared with the work of [PERSON] et al. [12], based on a batch group signature (BGS). The cost of signing and verifying are shown in Table 4. Although the computational complexity of the signature of the proposed scheme was higher than that of [PERSON] et al. 's work, [PERSON] et al. [11] used a UE private key to complete the signature, and the LEO needs to use the UE's public key to verify the signature. This is detrimental to the privacy protection of the UE, as attackers can easily trace the UE through its public key. Therefore, based on security and privacy considerations, our scheme is more suitable for the proposed SGIN scenario. Additionally, Figure 8 shows that the verification cost of the three schemes varies with the increase in the number of authentication requests. It can be seen that the cost of the proposed scheme is significantly less than that required for BGS and the work of [PERSON] et al. [11]. \begin{table}
\begin{tabular}{l c c} \hline \hline \multirow{2}{*}{**Scheme**} & \multicolumn{2}{c}{**Computational Overload (ms)**} \\ \cline{2-3}  & \multicolumn{2}{c}{**Signing**} & **Verifying** \\ \hline [PERSON] et al. [11] & \(T_{Mul_{1}}+T_{Hash_{3}}=0.912675\) & \((n+2)T_{Mul_{1}}+3 nT_{Hash_{3}}\) \\ \hline [PERSON] et al. [12] & \(11T_{Mul_{1}}+2T_{Pairing}+T_{Exp}=12.068067\) & \((6n+7)T_{Mul_{1}}+2T_{Pairing}\) \\ \hline Proposed & \(3T_{Mul_{1}}+T_{Exp}=2.794541\) & \(nT_{Exp}+T_{Pairing}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Computational overload in the batch authentication scenario. \begin{table}
\begin{tabular}{l c c} \hline \hline \multirow{2}{*}{**Scheme**} & \multicolumn{2}{c}{**Computational Overload (ms)**} \\ \cline{2-3}  & \multicolumn{2}{c}{**Signing**} & **Verifying** \\ \hline [PERSON] et al. [37] & \(9T_{Mul_{1}}+5T_{Exp}=8.680483\) & \(13T_{Mul_{1}}+3T_{Pairing}+2T_{Exp}=15.089186\) \\ \hline [PERSON] [24] & \(12T_{Mul_{1}}+2T_{Pairing}+2T_{Exp}+T_{Hash_{1}}=15.075187\) & \(8T_{Mul_{1}}+3T_{Pairing}+5T_{Exp}+T_{Hash_{2}}=13.100944\) \\ \hline [PERSON] et al. [12] & \(11T_{Mul_{1}}+2T_{Pairing}+T_{Exp}=12.068067\) & \(10T_{Mul_{1}}+2T_{Pairing}+3T_{Exp}=11.48289\) \\ \hline Proposed & \(9T_{Mul_{1}}+4T_{Exp}=8.532053\) & \(10T_{Mul_{1}}+2T_{Pairing}+3T_{Exp}=11.48289\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Computational overloads in the unlinkable authentication scenario. In terms of rebatch authentication, it is assumed that there is at most a 1% vulnerable UE in a group containing 1000 UE for batch authentication, then the maximum number of UEs breached in this group is \(N_{ckd}=N_{all}\times 1\%=1000\times 1\%=10\). Given that the number of request messages in a batch is \(N_{req}\), the probability that \(N_{req}\) requests contain exactly \(i\) invalid requests can be expressed using the hypergeometric distribution as  
\[Pr\{X=i\}=\frac{ \begin{pmatrix}N_{all}-N_{ckd}\\ N_{req}-i\end{pmatrix}\begin{pmatrix}N_{ckd}\\ i\end{pmatrix} }{ \begin{pmatrix}N_{all}\\ N_{req}\end{pmatrix} } \tag{2}\]  
Assuming that event \(A\) means rebatch authentication is required to successfully verify valid requests, the probability of event \(A\) can be expressed as  
\[