Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Groebner bases

Jean-Charles Faugère 1 Antoine Joux
1 SPACES - Solving problems through algebraic computation and efficient software
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this paper, we review and explain the existing algebraic cryptanalysis of multivariate cryptosystems from the hidden field equation (HFE) family. These cryptanalysis break cryptosystems in the HFE family by solving multivariate systems of equations. In this paper we present a new and efficient attack of this cryptosystem based on fast algorithms for computing Gröbner basis. In particular 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. From a theoretical point of view we study the algebraic properties of the equations produced by instance of the HFE cryptosystems and show why they yield systems of equations easier to solve than random systems of quadratic equations of the same sizes. Moreover we are able to bound the maximal degree occuring in the Gröbner basis computation. As a consequence, we gain a deeper understanding of the algebraic cryptanalysis against these cryptosystems. We use this understanding to devise a specific algorithm based on sparse linear algebra. In general, we conclude that the cryptanalysis of HFE can be performed in polynomial time. We also revisit the security estimates for existing schemes in the HFE family.
Type de document :
Communication dans un congrès
Dan Boneh. 23rd Annual International Cryptology Conference - CRYPTO 03, 2003, Santa Barbara USA, Springer, 2729, pp.44-60, 2003, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00099731
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 09:40:43
Dernière modification le : mercredi 9 mai 2018 - 15:46:12

Identifiants

  • HAL Id : inria-00099731, version 1

Collections

Citation

Jean-Charles Faugère, Antoine Joux. Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Groebner bases. Dan Boneh. 23rd Annual International Cryptology Conference - CRYPTO 03, 2003, Santa Barbara USA, Springer, 2729, pp.44-60, 2003, Lecture Notes in Computer Science. 〈inria-00099731〉

Partager

Métriques

Consultations de la notice

123