HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Algebraic cryptanalysis of HFE using Gröbner bases

Jean-Charles Faugère 1
1 SPACES - Solving problems through algebraic computation and efficient software
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : HFE (Hidden Fields Equations) is a public key cryptosystem using (multivariat- e) 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 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. We establish experimentally that the algebraic systems coming from HFE behave not as «random systems» so that they can be solved in polynomial time when the degree d of the univariate polynomial is fixed. For practical value of d we can establish precisely the complexity of this attack: O(n^8) (resp. O(n^10)) when 16
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 6:57:09 PM
Last modification on : Friday, February 4, 2022 - 3:34:38 AM
Long-term archiving on: : Sunday, April 4, 2010 - 8:35:54 PM


  • HAL Id : inria-00071849, version 1



Jean-Charles Faugère. Algebraic cryptanalysis of HFE using Gröbner bases. [Research Report] RR-4738, INRIA. 2003, pp.19. ⟨inria-00071849⟩



Record views


Files downloads