Multivariate Blind Signatures Revisited

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 R: Fq^m -> Fq^m and a collision-resistant hash function H: {0,1}^* -> Fq^m, the function Com(m;r) := H(m) - R(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.