Cryptology ePrint Archive: Report 2020/1424
Improved Key Recovery of the HFEv- Signature Scheme
Chengdong Tao Albrecht Petzoldt Jintai Ding
Abstract: 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-.
Category / Keywords: public-key cryptography / Multivariate Cryptography · HFEv- · Key Recovery · MinRank
Date: received 13 Nov 2020
Contact author: taochengdong at bimsa cn
Available format(s): PDF | BibTeX Citation
Version: 20201115:074410 (All versions of this report)
Short URL: ia.cr/2020/1424
[ Cryptology ePrint archive ]