Improved Key Recovery of the HFEv- Signature Scheme

Chengdong Tao Ding Lab, Beijing Institute of Mathematical Sci. and Applications, Beijing, China Albrecht Petzoldt FAU Erlangen-Nuremberg, Nuremberg, Germany Jintai Ding Yau Mathematical Center, Tsinghua University, Beijing, China; Ding Lab, Beijing Institute of Mathematical Sci. and Applications, Beijing, China; Ding Lab, Beijing Institute of Mathematical Sci. and Applications, Beijing, China

TBD mathscidoc:2207.43128

IACR Cryptol. ePrint Arch., 2020.11
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-.
No keywords uploaded!
[ Download ] [ 2022-07-22 17:35:24 uploaded by dingjt ] [ 41 downloads ] [ 0 comments ]
@inproceedings{chengdong2020improved,
  title={Improved Key Recovery of the HFEv- Signature Scheme},
  author={Chengdong Tao, Albrecht Petzoldt, and Jintai Ding},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220722173524349577712},
  booktitle={IACR Cryptol. ePrint Arch.},
  year={2020},
}
Chengdong Tao, Albrecht Petzoldt, and Jintai Ding. Improved Key Recovery of the HFEv- Signature Scheme. 2020. In IACR Cryptol. ePrint Arch.. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220722173524349577712.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved