2005 Reports :  Cryptology ePrint Archive Forum
Discussion forum for Cryptology ePrint Archive reports posted in 2005. Please put the report number in the subject.
2005/077 and HFE inversion attacks
Posted by: ncourtois (IP Logged)
Date: 09 September 2012 12:18

The authors have already integrated my earlier remarks however few details are still not quite right and need to be corrected.
The bottom line is that many inversion attacks were developed much earlier than Faugčre and Joux who brought them to the next level, and Cou01 [in fact written in 1999 and submitted to Crypto 1999 but published in another LNCS volume in 2001]. This paper Cou01 does not only improve KS99 as it is said here but presents powerful inversion attacks which already break the HFE Challenge 1 and already break the general basic HFE in polynomial time. Inversion attacks should not be confused with attacks from Crypto 1999 [KS99] which do recover the key, while inversion attacks are MUCH faster and do not recover the key [Cou01,FJ03].

=======================================

[eprint.iacr.org]

==================================================================
From a cryptanalytic point of view, basic HFE are broken: an efficient key inversion attack, using the MinRank-problem (cf Section 2.6.2), has been demonstrated in [KS99]. An inversion attack which uses both GrÄobner bases and general linearization methods has been shown in [FJ03]. In [SG03] we find an attack which works better if n is not a prime, i.e., we have splitting fields.
A more detailed discussion of HFE can be found in [Pat96b, Cou01, WP04a]. Here, [Pat96b] gives some general considerations of HFE after its development, e.g., a general linearization attack against all
multivariate schemes (cf Section 2.4.5), while [Cou01] summarised the situation of HFE in 2001 and also improves over the attack from [KS99]. The latest such summary of attacks can be found in [WP04a].

Let me correct this text:

From a cryptanalytic point of view, basic HFE are broken: a key recovery attack, using the MinRank-problem (cf Section 2.6.2), has been demonstrated in [KS99] and further discussed in [Cou01]. Then more efficient and more practical inversion attacks with multivariate algebraic input/output relations have been developed in [Cou01]. This paper already shows that HFE Challenge 1 can be broken and that HFE can be broken in in polynomial time if the hidden polynomial degree is fixed. Subsequent inversion attacks allow to enhance and optimize this process of solving through GrÄobner bases [FJ03]. In [SG03] we find an attack which works better if n is not a prime, i.e., we have splitting fields.
A more detailed discussion of HFE can be found in [Pat96b, Cou01, WP04a]. Here, [Pat96b] gives some general considerations of HFE after its development, e.g., a general linearization attack against all
multivariate schemes (cf Section 2.4.5), while [Cou01] summarised the situation of HFE in 2001 and also improves over the attack from [KS99]. The latest summary of attacks can be found in [WP04a].

==============
end of section 4.3.

"In particular,
the attacks from [KS99, FJ03] are no longer effective against this variation."
=>
"In particular,
the attacks from [KS99, Cou01,FJ03] are no longer effective against this variation."

================

"Hidden field equations were mainly used with the minus and the \v" modification so far. The cryptanalysis of [KS99] becomes ineffective if any variation is applied. However, the later work of Faugµere and Joux [FJ03] proves very efficient against HFE, HFE+, and also to some extent against HFEv.

"Hidden field equations were mainly used with the minus and the "v" modification so far. The cryptanalysis of [KS99] becomes ineffective if any variation is applied. The inversion attacks in [Cou01] it also seemed ineffective agaisnt variations, however in [CDF03] it is first (experimentally) shown that some variations can be broken. This is greatly expanded and fully justified in later work by Faugµere and Joux [FJ03] which proves very efficient against HFE, HFE+, and also to some extent against HFEv.

[CDF03]
Nicolas Courtois, Magnus Daum and Patrick Felke:
"On the Security of HFE, HFEv- and Quartz,"
PKC 2003, LNCS 2567, Springer, pp. 337-350.
YG Desmedt, editor. Public Key Cryptography,
PKC 2003, 6th International Workshop on Practice and Theory in Public Key Cryptography

==================

However, the method HFE- proves a very efficient way to counter this attack."
=>
I am NOT so sure about it, but will offer no correction.