Quartz is a signature scheme based on an HFEv- trapdoor function published at Eurocrypt 1996. In this paper we study “inversion”
attacks for Quartz, i.e. attacks that solve the system of multivariate equations used in Quartz. We do not cover some special
attacks that forge signatures without inversion.
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 [27], Shamir-Kipnis- Courtois [8], Courtois [8], and attacks related to Gröbner bases such as the F5/2 attack by Jean Charles Faugére [15], [16].
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.
Keywords asymmetric cryptography - finite fields - multivariate cryptanalysis - Gröbner bases - Hidden Field Equation - HFE problem - Quartz - Nessie project
The work described in this paper has been partially supported by the French Ministry of Research under RNRT Project “Turbo-signatures”.