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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Multivariate Blind Signatures Revisited

  • 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 \(\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.