Paper 2024/720

Multivariate Blind Signatures Revisited

Ward Beullens, IBM Research - Zurich
Abstract

In 2017, Petzoldt, Szepieniec, and Mohamed proposed a blind signature scheme, based on multivariate cryptography. This construction has been expanded on by several other works. This short paper shows that their construction is susceptible to an efficient polynomial-time attack. The problem is that the authors implicitly assumed that for a random multivariate quadratic map $\mathcal{R}:\mathbb{F}_q^m \rightarrow \mathbb{F}_q^m$ and a collision-resistant hash function $H: \{0,1\}^* \rightarrow \mathbb{F}_q^m$, the function $\mathsf{Com}(m;\mathbf{r}) := H(m) - \mathcal{R}(\mathbf{r})$ is a binding commitment, which is not the case. There is a "folklore" algorithm that can be used to, given any pair of messages, efficiently produce a commitment that opens to both of them. We hope that by pointing out that multivariate quadratic maps are not binding, similar problems can be avoided in the future.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
multivariate cryptographyattackspost-quantum cryptography
Contact author(s)
wbe @ zurich ibm com
History
2024-05-13: revised
2024-05-10: received
See all versions
Short URL
https://ia.cr/2024/720
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/720,
      author = {Ward Beullens},
      title = {Multivariate Blind Signatures Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2024/720},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/720}},
      url = {https://eprint.iacr.org/2024/720}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.