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 \(\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 \(\textsf{Com}(m;\textbf{r}) := H(m) - \mathcal {R}(\textbf{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.