# Improving Throughput of Mobile Sensors via Certificateless Signature Supporting Batch Verification
## 4 Performance Analyses
### Batch Verification  
This scheme requires the pairing operations in the verification algorithm, which consumes a lot of resources. To accelerate the algorithm, we can batch process a large number of signatures from the same user. For example, when multiple signatures from the same user are received consecutively, the received \(r,s,X,Y\) must all be consistent. Therefore, the verification equations can be performed once. The following is a simplified validation algorithm:  
Batch-Verify\((mpk,\text{ID},pk_{\text{ID}},\{m_{1},m_{2},\dots,m_{n}\},\{\sigma_{1},\sigma_{ 2},\dots,\sigma_{n}\})\): The verification algorithm inputs the master public key \(mpk\), a user's identity ID, a public key \(pk_{ID}\), n messages \(\{m_{1},m_{2},\dots,m_{n}\}\), and n signatures \(\{\sigma_{1},\sigma_{2},\dots,\sigma_{n}\}\). The \(\{\sigma_{i}\}_{i\in\{1\dots n\}}\) is denoted as \(\{r_{i},s_{i},r_{i}^{\prime},s_{i}^{\prime}\}\) and the \(pk_{ID}\) is denoted as \(\{[x],[y]P,[xy]P\}\). 1. Compute \(e_{i,1}^{\prime}=H(\text{ID}\parallel ppk_{\text{ID}})\), \(t_{i,1}=(r_{i}+s_{i})\bmod p\), \([s_{i}]P+[t_{i,1}]P_{pub}=(x_{i,1}^{\prime},y_{i,1}^{\prime})\), \(R_{i}=(e_{i,1}^{\prime}+x_{i,1}^{\prime})\). Then, check if the equations \(R_{i}=r_{i}\) holds. For n signatures coming from the same user, the \(\{r_{i},s_{i},[x]P\}\) are the same so that this step only needs to be calculated once for n signatures;
2. Compute \(e_{i,2}^{\prime}=H(\text{ID}\parallel m_{i})\), \(t_{i,2}=(r_{i}^{\prime}+s_{i}^{\prime})\bmod p\), \([s_{i}^{\prime}]P+[t_{i,2}]([xy]P)=(x_{i,2}^{\prime},y_{i,2}^{\prime})\), \(R_{i}^{\prime}=(e_{i,2}^{\prime}+x_{i,2}^{\prime})\). Then, check if the equation \(R_{i}^{\prime}=r_{i}^{\prime}\) holds. This step must to be executed for each signature;
3. Check if the equation \(e([x]P,[y]P)=e([xy]P,P)\) holds. This step only needs to be calculated once for n signatures. If all three equations hold, it outputs \"1\". Otherwise, it outputs \"0\". In this way, when verifying n signatures from the same user, step 1 and 3 only need to be performed once and step 2 needs to be performed n times. Thus, the expensive pairing operation only needs to be performed twice. Multi-User-Batch-Verify\((mpk,\{1D_{1},ID_{2},\dots,ID_{m}\},\{pk_{ID_{1}},pk_{ID_{2}},\dots,pk_{ID_{m}}\},\{m_{1,1}, \dots,m_{1,n},m_{1,2},\dots,m_{n,n}\},\{\sigma_{1,1},\sigma_{1,2},\dots,\sigma_ {1,n},\dots,\sigma_{m,n}\})\): The verification algorithm inputs the master public key \(mpk\), m identities \(\{\text{ID}_{1},\text{ID}_{2},\dots,\text{ID}_{m}\}\), and m public keys \(\{pk_{\text{ID}_{1}},pk_{\text{ID}_{2}},\dots,pk_{\text{ID}_{m}}\}\). The \(m_{i,j}\) and \(\sigma_{i,j}\) denote the j-th message and signature for i-th user, respectively. The \(\sigma_{i,j}\) is denoted as \((r_{i,j},s_{i,j},r_{i,j}^{\prime},s_{i,j}^{\prime})\) and the \(pk_{\text{ID}_{i}}\) is denoted as \(([x_{i}]P,[y_{i}]P,[xy_{i}]P)\). 1. Compute \(e_{i,1}^{\prime}=H(\text{ID}_{i}\parallel[x_{i}]P)\), \(t_{i,j,1}=(r_{i,j}+s_{i,j})\bmod p\), \([s_{i,j}]P+[t_{i,j,1}]P_{pub}=(x_{i,j,1}^{\prime},y_{i,j,1}^{\prime})\), \(R_{i,j}=(e_{i,1}^{\prime}+x_{i,j,1}^{\prime})\). Then, check if the equation \(R_{i,j}=r_{i,j}\) holds. This step needs to be calculated once for each user;
2. Compute \(e_{i,j,2}^{\prime}=H(\text{ID}_{i}\parallel m_{i,j})\), \(t_{i,j,2}=(r_{i,j}^{\prime}+s_{i,j}^{\prime})\bmod p\), \([s_{i,j}^{\prime}]P+[t_{i,j,2}]([xy_{i}]P)=(x_{i,j,2}^{\prime},y_{i,j,2}^{\prime})\), \(R_{i,j}^{\prime}=(e_{i,j,2}^{\prime}+x_{i,j,2}^{\prime})\). Then, check if the equation \(R_{i,j}^{\prime}=r_{i,j}^{\prime}\) holds. This step must to be calculated for each signature;
3. For all m public keys, calculate \(\pi_{1}=\prod_{i=1,j=1,i=j}^{m}e([x_{i}]P,[y_{i}]P)\)=\(\prod_{i=1}^{m}(\prod_{j=1,j=i}^{m}(e([x_{i}]P,[y_{j}]P))\). This calculation can be completed by a third-party assistant and the results