International Association for Cryptologic Research

International Association
for Cryptologic Research


Efficient Key Recovery for all HFE Signature Variants

Chengdong Tao , Beijing Institute of Mathematical Sciences and Applications
Albrecht Petzoldt , FAU Erlangen-Nuremberg
Jintai Ding , Yau Mathematical Center, Tsinghua University
DOI: 10.1007/978-3-030-84242-0_4 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2021
Award: Honorable mention for best paper
Abstract: The HFE cryptosystem is one of the best known multivariate schemes. Especially in the area of digital signatures, the HFEv- variant offers short signatures and high performance. Recently, an instance of the HFEv- signature scheme called GeMSS was elected as 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. Our attack shows that both the Minus and the Vinegar modifi- cation do not enhance the security of the basic HFE scheme significantly. This shows that it is very difficult to build a secure and efficient signature scheme on the basis of HFE. In particular, we use our attack to show that the proposed parameters of the GeMSS scheme are not as secure as claimed.
Video from CRYPTO 2021
  title={Efficient Key Recovery for all HFE Signature Variants},
  author={Chengdong Tao and Albrecht Petzoldt and Jintai Ding},