# Improving Throughput of Mobile Sensors via Certificateless Signature Supporting Batch Verification
## 3 A Certificateless Signature Scheme Supporting Batch Verification
### Construction  
Next, we describe our new certificateless signature scheme with batch verification based on SM2. Our scheme also consists of six algorithms.  
* Setup \((1^{\lambda})\): The Setup algorithm receives a security parameter \(1^{\lambda}\). It generates an elliptic curve group \((\mathbb{G},p,P)\) with parameters \(a,b\) and coordinates \(x_{p},y_{p}\). Then, it picks \(\alpha\in\mathbb{Z}_{p}\) randomly and sets \(P_{pub}=[\alpha]P\). Next, it chooses a hash function \(H\), such as the SM3 algorithm. Finally, it outputs the master key pair as \[mpk=(\mathbb{G},p,P,P_{pub},H),\ msk=\alpha.\]
* KeyExt \((mpk,msk,\text{ID})\): The KeyExt algorithm receives the master key pair \((mpk,msk)\) and an identity ID as inputs. It first picks \(x\in\mathbb{Z}_{p}\) randomly and calculates \(ppk_{\text{ID}}=[x]P\). Then, it concatenates ID with \(ppk_{\text{ID}}\). Next, it runs the SM2 algorithm to generate a partial private key. 1. Compute \(e=H(\text{ID}\parallel ppk_{\text{ID}})\); 2. Pick \(k\in\mathbb{Z}_{p}\) randomly and compute \([k]P=(x_{1},y_{1}),r=(e+x_{1})\text{ mod }p\); 3. Compute \(s=((1+\alpha)^{-1}\cdot(k-r\cdot\alpha))\text{ mod }p\). It transmits the partial private key \(d_{\text{ID}}=(r,s,x,ppk_{\text{ID}})\) to the user safely;
* \(\text{\sc{Scr}Value}\ (mpk,\text{ID})\): The \(\text{\sc{Scr}Value}\) algorithm receives the master public key \(mpk\) and an identity ID as inputs. Then, it runs the SM2 key generation algorithm. It selects \(y\in\mathbb{Z}_{p}\) randomly and sets \(sv_{\text{ID}}=(x,y)\) with the random value \(x\) received from 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\), a user identity ID, and a secret value \(sv_{\text{ID}}=(x,y)\) of the user as inputs. Then, it computes \([y]P\) and \([xy]P\). Next, it sets \(pk_{\text{ID}}=(ppk_{\text{ID}},[y]P,[xy]P)\) and produces the public key \(pk_{\text{ID}}\);
* Sign \((mpk,d_{\text{ID}},sv_{\text{ID}},m)\): The Sign algorithm inputs the master public key \(mpk\), a user 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 the message \(m\). Then, it computes \(xy\text{ mod }p\) and runs the SM2 signing algorithm with \(xy\) to generate the part signature. In detail, 1. Compute \(e=H(\text{ID}\parallel m)\); 2. Pick \(k^{\prime}\in\mathbb{Z}_{p}\) randomly and compute \([k^{\prime}]P=(x_{2},y_{2}),r^{\prime}=(e+x_{2})\text{ mod }p\); 3. Compute \(s^{\prime}=((1+xy)^{-1}\cdot(k^{\prime}-r^{\prime}\cdot xy)\text{ mod }p\). Next, it outputs the signature \(\sigma=(r,s,r^{\prime},s^{\prime})\);
* Verify \((mpk,\text{ID},pk_{\text{ID}},m,\sigma)\): The Verify algorithm receives the master public key \(mpk\), an identity ID, public key \(pk_{\text{ID}}=([x]P,[y]P,[xy]P)\), a message \(m\), and a signature \(\sigma=(r,s,r^{\prime},s)\). It first checks if \(e([x]P,[y]P)=e([xy]P,P)\) holds. Then, it runs the SM2 verification algorithm to check the validity of \(\sigma_{\text{ID}}\) and \(\sigma_{m}\). In detail, 1. Compute \(e_{1}^{\prime}=H(\text{ID}\parallel ppk_{\text{ID}}),t_{1}=(r+s)\text{ mod }p,[s]P+[t_{1}]P_{pub}\ =\ (x_{1}^{\prime},y_{1}^{\prime})\), \(R=(e_{1}^{\prime}+x_{1}^{\prime})\). Then check if the equations \(R=r\) holds; 2. Compute \(e_{2}^{\prime}=H(\text{ID}\parallel m),t_{2}=(r^{\prime}+s^{\prime})\text{ mod }p,[s^{\prime}]P+[t_{2}]([xy]P)=(x_{2}^{\prime},y_{2}^{\prime})\), \(R^{\prime}=(e_{2}^{\prime}+x_{2}^{\prime})\).Then check if the equations \(R^{\prime}=r^{\prime}\) holds; 3. Check if the equations \(e([x]P,[y]P)=e([xy]P,P)\) holds If all three equations hold, it outputs \"1\". Otherwise, it outputs \"0\".