## 3 Identity-Based Short Digital Signature
### IBS-1 Signature Scheme  
In this section we describe the IBS-1 scheme. It consists in a quadruple of probabilistic polynomial time (PPT) algorithms (Setup, KeyGen, Sign, Vrf).  
* Setup takes a security parameter \(1^{k}\) as input (here, \(1^{k}\) is the unary notation for the security parameter, _i.e._, key material is \(k\) bits long), and returns the master (signing) key \(s\) plus a set of system parameters _params_ that includes the system public key \(P_{pub}\);
* KeyGen takes as inputs the master key \(s\) and an identity \(id\in\{0,1\}^{*}\), and returns a secret signature key \(S_{id}\);
* Sign takes as inputs the secret signature key \(S_{id}\) and a message \(m\in\{0,1\}^{*}\), and returns the signature \(\sigma\) of \(m\);
* Vrf takes as inputs \(P_{pub},id,msg\) and \(\sigma\). It returns 1 if \(\sigma\) is a valid signature of \(m\) related to \(id\), and 0 otherwise.  
The PKG runs Setup algorithm which defines the elliptic curve \(E(\mathbb{F}_{q})\) to be used, and a generator point \(P\in E(\mathbb{F}_{q})\) of prime order \(l\). It also initializes public system parameters for the intended service.  
* Choice of an elliptic curve \(E(\mathbb{F}_{q})\), and a point \(P\in E\) of prime order \(l\) with \(\gcd(l,q-1)=1\).
* Selection of a point \(P\in E(\mathbb{F}_{q^{k}})\) of order \(l\) and definition of the bilinear pairing \(e\)
* Choice of a pseudo-random integer \(s\in\mathbb{Z}_{l}^{*}\) as its master key, and computation of its public verification key \(P_{pub}=sP\).
* Publication of \(E,e,l,P,P_{pub}\) and of the two hash functions: \[H:\ \{0,1\}^{*}\rightarrow\mathbb{G}\,\quad h:\ \{0,1\}^{*}\to Z_{l}^{*}\]  
**Algorithm 1** Setup algorithm  
The KeyGen algorithm extracts the private keys for a set of registered users. The PKG does the following:  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Signature scheme** & **Signature size** & **Public key size** & **Private key size** \\ \hline ECDSA & 320 & 160 & 160 \\ IBS-1 & 160 & 160 & 160 \\ \hline \hline \end{tabular}
\end{table}
Table 1: IBS-1 and ECDSA signature size comparison, considering an MNT (Miyaji, Nakabayashi and Takano) elliptic curve over a prime field with 80 bits security level.  
```
* For each binary string \(id\) in a suitable finite set: \[\text{ Computation of digests }H(id)\text{ and }h(id).\] \[\text{ Computation of the elements of }\mathbb{G}(+)=\langle P\rangle\text{:}\] \[S_{id}=s\,H(id)\] (1)

which represent private key corresponding to the identity \(id\).
```  
**Algorithm 2** KeyGen algorithm  
In the IBS-1 scheme, illustrated in Algorithm 3, the signer \(id\) uses its private key \(S_{id}\) given by Equation (1) and the public parameters returned by the Setup algorithm in order to compute the signature \((\Sigma,R)\in\mathbb{G}\times\mathbb{G}\) of message \(m\). The verifier can check the signature due to the knowledge of the signer identifier \(id\) and the public parameters returned by the Setup algorithm.  
```
* Sign: the signer \(id\) does the following
* Choice of a pseudo-random integer \(r\in\mathbb{Z}_{l}^{*}\), and computation of the public element \(R=rP\).
* Computation of the element of \(\mathbb{G}(+)=\langle P\rangle\): \[\Sigma=\frac{S_{1}(id)}{r+h(m)}\] (2) The couple \((\Sigma,R)\) represents the signature by user \(id\) for message \(m\).
* Vrf: the verifier does the following
* Computation of digests \(H(id)\), \(h(m)\) and point \(R+h(m)P\).
* Check of the equality \[e(\Sigma,R+h(m)P)=e(H(id),P_{pub})\] (3) and acceptance of the signature only if Equation (3) is true.
```  
**Algorithm 3** IBS-1 signature scheme  
It the following theorem we verify the correctness of the IBS-1 signature scheme. Substituting the value \(S_{1}(id)\) given by Equation (1) in the Equation (2) of \(\Sigma\), from the Bilinearity of \(e\).  
**Theorem 1**.: _Suppose that no adversaries interfere with the execution of signature scheme. By virtue of Equation (3), the scheme is correct:_  
\[e(\Sigma,R+h(m)P)=e\left(\frac{sH(id)}{r+h(m)},(r+h(m))P\right)=e(sH(id),P)=e( H(id),P_{pub})\]