## 4 Blind Schnorr Signatures--Results and Discussion
### Linking with the Shared Key \(\mathsf{ak}\)  
We assume that \(\mathcal{D}\) and \(\mathcal{S}\) already share a secret \(\mathsf{ak}\). The goal of the attack described below is to enable linking a Schnorr signature \(\sigma\) derived by \(\mathcal{D}\) with an interaction between \(\mathcal{S}\) and \(\mathcal{D}\). As \(\mathcal{D}\) is not anonymous during this interaction, such linking reveals the User who received \(\sigma\). Thus, the attack aims to break the blindness property. As a side effect of the proposed construction, the device \(\mathcal{D}\) can also create a hidden ciphertext that is readable only by \(\mathcal{S}\).  
The key point for linking is creating a hidden relation between \(\alpha\) and \(\beta\) by \(\mathcal{D}\). Namely, first assume that \(\alpha\) is created at random, as in the original scheme, while \(\beta\) depends on \(\alpha\), the session, and a hidden message \(m^{\prime}\). For example, let \(\mathsf{m}^{\prime}<q/2^{20}\) be a covert message. Then, \(\beta\) is calculated as  
\[\beta=\alpha+\mathsf{PRNG}(0,\mathsf{ak},R)+\mathsf{m}^{\prime}\bmod q\]  
where \(\mathsf{PRNG}\) is a pseudorandom number generator that yields elements of \(\mathbb{Z}_{q}\), and \(R\) is the element sent by \(\mathcal{S}\) as the first message in the current session. So, we use a one-time pad in \(\mathbb{Z}_{q}\), where the key is session-specific and depends on the shared secret \(\mathsf{ak}\). Note that the link between \(\alpha,\beta\) and \(\mathcal{D}\) is witnessed by the fact that  
\[\beta-\alpha-\mathsf{PRNG}(0,\mathsf{ak},R)\bmod q<q/2^{20}\]  
In the case of using a wrong key \(\mathsf{ak}\), the calculated number is a random element of \(\mathbb{Z}_{q}\), so the probability of a false positive is about \(2^{-20}\). Of course, the choice of \(\mathsf{m}^{\prime}<q/2^{20}\) is somewhat arbitrary but seems to be good enough in practice.  
In order to extend the bandwidth of a covert channel, \(\mathcal{D}\) may generate \(\alpha\) not at random but derive it with \(\mathsf{ak},R\) and the second covert message \(\mathsf{m}^{\prime\prime}<q\). Namely,  
\[\alpha=\mathsf{PRNG}(1,\mathsf{ak},R)+\mathsf{m}^{\prime\prime}\bmod q\]  
(note that we use the same arguments \(\mathsf{ak}\) and \(R\) as before, but slightly change the input to obtain a different pseudorandom element).  
The details of the procedure executed by \(\mathcal{D}\) during signature creation are shown in Figure 8. The only difference is that \(\alpha\) and \(\beta\) are generated in a modified way. Note that the change is undetectable by the auditor \(\mathcal{J}\) as long as the output of \(\mathsf{PRNG}\) is not distinguishable from random sampling in \(\mathbb{Z}_{q}\). However, \(\mathsf{ak}\) is not available to \(\mathcal{J}\), so we may use a cryptographically strong generator \(\mathsf{PRNG}\) with this property.  
Now, let us discuss how a signature can be linked with a transcript of a signing procedure. So assume that \(\mathcal{S}\) holds a transcript \((R,c,s)\) of an interaction with \(\mathcal{D}\) and a signature \((s^{\prime},c^{\prime})\) found in the cyberspace. The goal is to check whether \((s^{\prime},c^{\prime})\) corresponds to this interaction (consequently, whether \((s^{\prime},c^{\prime})\) has been used by the owner of \(\mathcal{D}\)). In the positive case, the covert messages \(\mathsf{m}^{\prime}\) and \(\mathsf{m}^{\prime\prime}\) should be retrieved as well. The test details are given in Figure 8. First, \(\alpha,\beta\) are recalculated by computing\(\alpha^{\prime}=s^{\prime}-s\bmod q\),  
2. \(\beta^{\prime}=c-c^{\prime}\bmod q\),  
Then, one can test whether the link is correct by deriving  
\[\mathsf{m}^{\prime}=\beta^{\prime}-\alpha^{\prime}-\mathsf{PRNG}(0,\mathsf{ak},R) \bmod q\]  
and checking that  
\[\mathsf{m}^{\prime}<q/2^{20}\]  
If this is the case, then \(\mathsf{m}^{\prime}\) and \(\mathsf{m}^{\prime\prime}=\beta^{\prime}-\alpha^{\prime}-\mathsf{PRNG}(1, \mathsf{ak},R)\bmod q\) are accepted as covert messages from \(\mathcal{D}\).