## 5 Tessaro-Zhu Blind Signatures--Results and Discussion
### Linking with No Shared Key
#### 5.4.2 Linkable Signature Creation Details  
Similarly as before, we use random elements of \(\mathbb{Z}_{q}\) from the original scheme to carry the covert data. The elements are specific to the schemes, as well as their recovery when a signature is compared with an interaction transcript: The random elements used are:  
* **Scheme BS3 from [19]: \(r_{1},r_{2},\gamma_{1}\in\mathbb{Z}_{p},\gamma_{2}\in\mathbb{Z}_{p}^{*}\)*
* selected by \(\mathcal{D}\) during execution of \(\mathsf{BS}_{3}\).U\({}_{1}\) (compare page 22 of [19]). They can be recalculated by \(\mathcal{S}\) as follows:
* \(\gamma_{1}=y^{\prime}/y\bmod q\) (compare \(\mathsf{BS}_{3}\).U\({}_{2}\));
* \(\gamma_{2}=c/c^{\prime}\bmod q\) (compare \(\mathsf{BS}_{3}\).U\({}_{1}\)));
* \(r_{1}=s^{\prime}-(\gamma_{1}/\gamma_{2})\cdot s\bmod q\) (compare \(\mathsf{BS}_{3}\).U\({}_{2}\));
* \(r_{2}=t^{\prime}-\gamma_{1}\cdot t\bmod q\) (compare \(\mathsf{BS}_{3}\).U\({}_{2}\)). Note that \(c^{\prime},s^{\prime},y^{\prime},t^{\prime}\) are the components of the signature compared with an interaction with messages containing \(s,y,t\) (message sent by \(\mathcal{S}\) as the output of \(\mathsf{BS}_{3}\).S\({}_{2}\)) and \(c\) (message sent by \(\mathcal{D}\) as the output of \(\mathsf{BS}_{3}\).ISign). * **Scheme BS from [34]**: \(\alpha,\beta,r\in\mathbb{Z}_{q}\) (in some cases, \(\in\mathbb{Z}_{q}^{*}\)) selected by \(\mathcal{D}\) (compare \(\mathsf{BS}[f_{1}]\).I\(\mathsf{Sign}_{1}\) and \(\mathsf{BS}[f_{2}]\).I\(\mathsf{Sign}_{1}\) on page 13 of [34]). They can be recovered by \(\mathcal{S}\) as follows (compare \(\mathsf{BS}[f_{1}]\).I\(\mathsf{Sign}_{1}\), \(\mathsf{BS}[f_{1}]\).I\(\mathsf{Sign}_{2}\) and \(\mathsf{BS}[f_{2}]\).I\(\mathsf{Sign}_{1}\), \(\mathsf{BS}[f_{2}]\).I\(\mathsf{Sign}_{2}\) on page 13 of [34]):
* \(\alpha=g/y\bmod q\),
* \(\beta=c/\bar{c}\bmod q\) (the version with \(f_{2}\)) or \(\beta=c-\bar{c}\alpha^{-5}\bmod q\) (the version with \(f_{1}\)),
* \(r=\bar{z}-\alpha\beta^{-1}z-\alpha b\bmod q\) (the version with \(f_{2}\)) or \(r=\bar{z}-\alpha^{5}z-\alpha b\bmod q\) (the version with \(f_{2}\)). * **Scheme BSr3 from [34]:*
* the elements \(\beta,s\in\mathbb{Z}_{q}\). Note that random \(s\) is sent in clear during blind-signature creation so it can be used to calculate the shared ephemeral secret used to derive \(\beta\). In turn, \(\beta\) can be derived by \(\mathcal{S}\) as \(c/\bar{c}\bmod q\), where \(\bar{c}\) is recalculated according to the regular verification procedure (compare page 14 of [34]):
* **Scheme BS1 from [35]:*
* the elements \(\alpha_{0},\alpha_{1},\gamma_{0},\gamma_{1}\in\mathbb{Z}_{q}\) selected freely by \(\mathcal{D}\) during \(\mathsf{BS}_{1}\).U\({}_{2}\). They can be recalculated by \(\mathcal{S}\) during the linking test as: \(\gamma_{0}=d^{\prime}-d\bmod q\), \(\gamma_{1}=e^{\prime}-e\bmod q\), \(\alpha_{0}=z_{0}^{\prime}-z_{0}\bmod q\), \(\alpha_{1}=z_{1}^{\prime}-z_{1}\bmod q\) (recall that \(d^{\prime},e^{\prime},z_{0}^{\prime},z_{1}^{\prime}\) are components of the blind signature, while \(d,e,z_{0},z_{1}\) are transmitted by \(\mathcal{S}\) in the last step of \(\mathsf{BS}_{1}\).S\({}_{2}\) (compare page 10 of [35]);
* **Scheme BS2 from [35]:*
* the elements \(\alpha_{0},\alpha_{1},\gamma_{0},\gamma_{1}\in\mathbb{Z}_{q}\) selected by \(\mathcal{D}\) during \(\mathsf{BS}_{2}\).U\({}_{1}\) (compare page 19 of [35]). They can be recalculated by \(\mathcal{S}\) during the linking test as: \(\gamma_{0}=d^{\prime}-d\bmod q\), \(\gamma_{1}=e^{\prime}-e\bmod q\), \(\alpha_{0}=z_{0}^{\prime}-z_{0}\bmod q\), \(\alpha_{1}=z_{1}^{\prime}-z_{1}\bmod q\). Recall that \(d^{\prime},e^{\prime},z_{0}^{\prime},z_{1}^{\prime}\) are components of the blind signature, while \(d,e,z_{0},z_{1}\) are transmitted by \(\mathcal{S}\) in the last step of \(\mathsf{BS}_{2}\).S\({}_{3}\).