2004 Reports :  Cryptology ePrint Archive Forum
Discussion forum for Cryptology ePrint Archive reports posted in 2004. Please put the report number in the subject.  
Goto Thread: PreviousNext
Goto: Forum ListMessage ListNew TopicSearchLog In
Posted by: ncourtois (IP Logged)
Date: 09 September 2012 13:25

This paper ignores major historical contributions to the cryptanalysis of HFE, pre-Grobner basis inversion attacks (essentially the same but simpler, there is no fixed ordering of monomials, but the same operations are done). A small correction:

In 2002 Faugère reported to have broken the HFE Challenge 1 in 96 hours.


In 2001 Courtois introduces a first inversion attack on HFE and shows that it is frequently much faster than even an impvoed version of the Kipnis-Shamir attack, cf. [Cou01]. These inversion attacks with multivariate algebraic input/output relations are claimed to break HFE in polynomial time if the hidden polynomial degree is an arbitrary fixed value. This paper also outlines a first attack on HFE Challenge 1. Subsequent inversion attacks allow to enhance and optimize this process of solving equations in the ideal of polynomials spanned by the initial equations through GrÄobner bases [FJ03]. In 2002 Faugère reported a first experimental attack on HFE Challenge 1 whcih takes 96 hours which was substantially faster than $2^{60}$-like attack from [Cou01].

Please log in for posting a message. Only registered users may post in this forum.