Paper 2023/1588

M&M'S: Mix and Match Attacks on Schnorr-type Blind Signatures with Repetition

Khue Do, CISPA Helmholtz Center for Information Security
Lucjan Hanzlik, CISPA Helmholtz Center for Information Security
Eugenio Paracucchi, CISPA Helmholtz Center for Information Security

Blind signatures allow the issuing of signatures on messages chosen by the user so that they ensure $\mathit{blindness}$ of the message against the signer. Moreover, a malicious user cannot output $\ell+1$ signatures while only finishing $\ell$ signing sessions. This notion, called $\mathit{one}$-$\mathit{more}$ unforgeability, comes in two flavors supporting either $\mathit{sequential}$ or $\mathit{concurrent}$ sessions. In this paper, we investigate the security of a class of blind signatures constructed from Sigma-protocols with small challenge space $\mathcal{C}_{\Sigma}$ (i.e., polynomial in the security parameter), using $k$ repetitions of the protocol to decrease the chances of a cheating prover. This class of schemes includes, among others, the Schnorr blind signature scheme with bit challenges and the recently proposed isogeny-based scheme CSI-Otter (Crypto'23), as well as potential blind signatures designed from assumptions with the well-known Sigma-protocol for the graph-isomorphism problem (e.g., Lattice Isomorphism Problem). For this class of blind signatures, we show a $\mathit{polynomial}$-$\mathit{time}$ attack that breaks one-more unforgeability for any $\ell \geq k$ concurrent sessions in time $O(k \cdot |\mathcal{C}_{\Sigma}|)$. Contrary to the ROS attack, ours is generic and does not require any particular algebraic structure. We also propose a computational trade-off, where, for any $t \leq k$, our attack works for $\ell = \frac{k}{t}$ in time $O(\frac{k}{t} \cdot |\mathcal{C}_{\Sigma}|^t)$. The consequences of our attack are as follows. Schemes in the investigated class of blind signatures should not be used concurrently without applying specific transformations to boost the security to support more signing sessions. Moreover, for the parameters proposed for CSI-Otter ($k=128$ and $|\mathcal{C}_{\Sigma}|=2$), the scheme becomes forgeable after 128 concurrent signing sessions for the basic attack and with only eight sessions in our optimized attack. We also show that for those parameters, it is even possible to compute two signatures in around 10 minutes with just one signing session using the computation power of the Bitcoin network. Thus, we show that, for sequential security, the parameter $k$ must be at least doubled in the security parameter for any of the investigated schemes.

Available format(s)
Attacks and cryptanalysis
Publication info
Blind SignaturesSigma ProtocolsGroup ActionsCryptanalysis
Contact author(s)
khue do @ cispa de
hanzlik @ cispa de
eugenio paracucchi @ cispa de
2023-10-13: revised
2023-10-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Khue Do and Lucjan Hanzlik and Eugenio Paracucchi},
      title = {M&M'S: Mix and Match Attacks on Schnorr-type Blind Signatures with Repetition},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1588},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.