# Improving Throughput of Mobile Sensors via Certificateless Signature Supporting Batch Verification
## 2 Preliminaries
### Review a CLS Scheme Based on SM2  
The SM2-based CLS scheme designed by [PERSON] et al. [28] is made up of six algorithms.  
* [noitemsep]
* Setup \((1^{\lambda})\): The Setup algorithm receives the security parameter \(1^{\lambda}\) as input and uses the SM2 setup algorithm. It chooses an elliptic curve group \((\mathbb{G},p,P)\) with parameters \(a,b\) and coordinates \(x_{p},y_{P}\). Then, it randomly picks \(\alpha\in\mathbb{Z}_{p}\) and computes \(P_{pub}=[\alpha]P\). It also selects a hash function \(H\), such as the SM3 algorithm. Finally, the algorithm returns the master public and secret key pair as \[mpk=(\mathbb{G},p,P,P_{pub},H),\ msk=\alpha.\]
* KeyExt \((mpk,msk,\mathsf{ID})\): The KeyExt algorithm receives the master key pair \((mpk,msk)\) and an identity ID as inputs. Firstly, it randomly selects \(x\in\mathbb{Z}_{p}\) and computes\(ppk_{\text{ID}}=[x]P\). Then, it concatenates the identity ID and the partial public key \(ppk_{\text{ID}}\). Finally, it runs the SM2 signature algorithm to produce the partial private key.  
1. Compute \(e=H(\text{ID}\parallel ppk_{\text{ID}})\);
2. Pick \(k\in\mathbb{Z}_{p}\) randomly and calculate \([k]P=(x_{1},y_{1}),r=(e+x_{1})\bmod p\);
3. Compute \(s=((1+\alpha)^{-1}\cdot(k-r\cdot\alpha))\bmod p\).  
The partial private key is \(d_{\text{ID}}=(r,s,x,ppk_{\text{ID}})\);
* ScretValue \((mpk,\text{ID})\): The ScretValue algorithm receives the master public key \(mpk\) and an identity ID. Then, it runs the SM2 key generation algorithm. It randomly selects a \(y\in\mathbb{Z}_{p}\) and sets \(sv_{\text{ID}}=(x,y)\) with the random value \(x\) received from the KGC. Next, it outputs the secret value \(sv_{\text{ID}}\);
* PublicKey \((mpk,\text{ID},sv_{\text{ID}})\): The PublicKey algorithm receives the master public key \(mpk\), an identity ID, and a secret value \(sv_{\text{ID}}=(x,y)\). Then, it computes \([y]P\) and generates a noninteractive zero-knowledge proof (NIZKP) \(\pi\) of holding the unique \(y\) with respect to \([y]P\). Next, it sets \(pk_{\text{ID}}=(ppk_{\text{ID}},[y]P,\pi)\) and outputs \(pk_{\text{ID}}\) as the public key;
* Sign \((mpk,d_{\text{ID}},sv_{\text{ID}},m)\): The Sign algorithm receives the master public key \(mpk\), a partial private key \(d_{\text{ID}}=(r,s,x,ppk_{\text{ID}})\), a secret value \(sv_{\text{ID}}=(x,y)\), and a message \(m\). It first concatenates the identity ID and message \(m\). Then, it computes \((x+y)\bmod p\) and runs the SM2 signing algorithm with \((x+y)\) to generate the part signature. In detail,  
1. Compute \(e=H(\text{ID}\parallel m)\);
2. Pick \(k\in\mathbb{Z}_{p}\) randomly and compute \([k]P=(x_{1},y_{1}),r^{\prime}=(e+x_{1})\bmod p\);
3. Compute \(s^{\prime}=((1+(x+y))^{-1}\cdot(k-r^{\prime}\cdot(x+y)))\bmod p\).  
Next, it outputs the signature \(\sigma_{m}=(r,s,r^{\prime},s^{\prime})\);  
* Verify\((mpk,\text{ID},pk_{\text{ID}},m,\sigma_{m})\): The Verify algorithm receives the master public key \(mpk\), an identity ID, a public key \(pk_{\text{ID}}=(ppk_{\text{ID}},[y]P,\pi)\), a message \(m\), and a signature \(\sigma_{m}=(r,s,r^{\prime},s^{\prime})\). Then, it runs the SM2 algorithm to verify \((r,s)\) and \((r^{\prime},s^{\prime})\) and checks whether \(\pi\) is valid. In detail,  
1. Compute \(e_{1}^{\prime}=H(\text{ID}\parallel ppk_{\text{ID}}),e_{2}^{\prime}=H(\text{ID }\parallel m)\);
2. Compute \(t_{1}=(r+s)\bmod p,t_{2}=(r^{\prime}+s^{\prime})\bmod p\);
3. Compute \([s]P+[t_{1}]P_{pub}=(x_{1}^{\prime},y_{1}^{\prime}),[s^{\prime}]P+[t_{2}]( ppk_{\text{ID}}+[y]P)=(x_{2}^{\prime},y_{2}^{\prime})\);
4. Compute \(R=(e_{1}^{\prime}+x_{1}^{\prime}),R^{\prime}=(e_{2}^{\prime}+x_{2}^{\prime})\).  
If the proof \(\pi\) is valid and the equations \(r=R,r^{\prime}=R^{\prime}\) hold, it outputs \"1\". Otherwise, it outputs \"0\".