We are interested in methods to invert the HFEv- trapdoor function or at least to distinguish it from a random system of the same size. There are 4 types of attacks known on HFE: Shamir-Kipnis, Shamir-Kipnis-Courtois, Courtois, and attacks related to Gr\"{o}bner bases such as the F5/2 attack by Jean Charles Faugère.
No attack has been published so far on HFEv- and it was believed to be more secure than HFE. In this paper we show that even modified HFE systems can be successfully attacked. It seems that the complexity of the attack increases by at least a factor of $q^{tot}$ with $tot$ being the total number of perturbations in HFE. From this and all the other known attacks we will estimate what is the complexity of the best "inversion" attack for Quartz.
Category / Keywords: public-key cryptography / asymmetric cryptography, finite fields, multivariate cryptanalysis, Gr\"{o}bner bases, Hidden Field Equation, HFE problem, Quartz, Nessie project Publication Info: - Date: received 12 Sep 2002, last revised 17 Sep 2002 Contact author: Magnus Daum at ruhr-uni-bochum de Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20020917:144330 (All versions of this report) Short URL: ia.cr/2002/138 Discussion forum: Show discussion | Start new discussion