[Resource Topic] 2024/720: MQ maps are not binding - Revisiting Multivariate Blind Signatures

Welcome to the resource topic for 2024/720

MQ maps are not binding - Revisiting Multivariate Blind Signatures

Authors: Ward Beullens


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. This paper shows that this is not the case. Given any pair of messages, one can 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.

ePrint: https://eprint.iacr.org/2024/720

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .