Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal

Details:

   
TitleAlgebraic cryptanalysis of HFE using Gröbner bases
Author(s) Jean-Charles Faugère
TypeTechnical Report, Misc
AbstractHFE (Hidden Fields Equations) is a public key cryptosystem using (multivariate) polynomial operations over finite fields. It has been proposed by Jacques Patarin following the ideas of Matsumoto and Imai. In this paper we present a new and efficient attack of this cryptosystem based on fast algorithms for computing Gröbner basis. The attack consists simply in computing a Gröbner basis of the public key. Of course the efficiency of this attack depends strongly on the choice of the algorithm for computing the Gröbner basis: while the corresponding algebraic systems are completely far beyond the capacity of any implementation of the Buchberger algorithm, it was possible to break the first HFE challenge (80 bits) in only two days of CPU time by using the new algorithm F5 implemented in C.
KeywordsHidden Field Equations (HFE), Multivariate polynomial equations, Gröbner bases, Algebraic Cryptanalysis, Computer Algebra
Length22
ISSN0249-6399
File
LanguageEnglish
JournalINRIA
Number4738
Pages19 p.
Year2003
MonthFebruary
Edition0
Translation No
Refereed No
Webmaster