Paper 2024/720

Multivariate Blind Signatures Revisited

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\to {\mathbb{F}}_q^m$ and a collision-resistant hash function $H:\{0,1{\}}^{\ast }\to {\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.