Paper 2020/1424

Improved Key Recovery of the HFEv- Signature Scheme

Chengdong Tao, Albrecht Petzoldt, and Jintai Ding


The HFEv- signature scheme is a twenty year old multivariate public key signature scheme. It uses the Minus and the Vinegar modifier on the original HFE scheme. An instance of the HFEv- signature scheme called GeMSS is one of the alternative candidates for signature schemes in the third round of the NIST Post Quantum Crypto (PQC) Standardization Project. In this paper, we propose a new key recovery attack on the HFEv- signature scheme. We show that the Minus modification does not enhance the security of cryptosystems of the HFE family, while the Vinegar modification increases the complexity of our attack only by a polynomial factor. By doing so, we show that the proposed parameters of the GeMSS scheme are not as secure as claimed. Our attack shows that it is very difficult to build a secure and efficient signature scheme on the basis of HFEv-.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Contact author(s)
taochengdong @ bimsa cn
2020-11-15: received
Short URL
Creative Commons Attribution


      author = {Chengdong Tao and Albrecht Petzoldt and Jintai Ding},
      title = {Improved Key Recovery of the HFEv- Signature Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1424},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.