Details:
Title  Algebraic cryptanalysis of HFE using Gröbner bases  Author(s)  JeanCharles Faugère  Type  Technical Report, Misc  Abstract  HFE (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.  Keywords  Hidden Field Equations (HFE), Multivariate polynomial equations, Gröbner bases, Algebraic Cryptanalysis, Computer Algebra  Length  22  ISSN  02496399 
File 
 Language  English  Journal  INRIA  Number  4738  Pages  19 p.  Year  2003  Month  February  Edition  0  Translation 
No  Refereed 
No 
