Gröbner bases and application to HFE

Jean-Charles Faugère 1, 2
1 CALFOR - Calcul formel
LIP6 - Laboratoire d'Informatique de Paris 6
2 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 polynomial operations over finite fields. It has been proposed by Jacques Patarin at Eurocrypt 96 following the ideas of Matsumoto and Imai. It has long been regarded as a very promising cryptosystem because it can be used to produce signatures as short as 128, 100 and even 80 bits. HFE gives the shortest (unbroken) signatures known except with the recent McEliece signature scheme. To study HFE it is necessary to study and to solve polynomial system of equations. One of the most efficient tool for solving algebraic system is Gröbner bases (Buchberger). In this conference we present 3 new results: \begin{itemize} \item we discribe briefly a new efficient algorithm for computing $V$ called $F_5/2$. This algorithm is several order of magnitude faster than any other algorithms (at least $500$ times faster than the Singular program for instance). \item For a fixed value $d$ of the univariate polynomial we report the CPU time taken by the $F_5/2$ algorithm to solve the HFE problem. For instance, when $d=96$, we found experimentally that the time for solving the HFE problem is only $n^8$. We were able to solve the {\em first HFE Challenge} (n=16,d=96) in 96 hours. \item We present accurate {\em theoretical} results concerning the complexity of solving a {\em random} system in $GF(2)$. The complexity of computing a Gröbner basis of a random system of $n$ equations of degree $2$ in $n$ variables is essentially equivalent to solve a $N\times N$ matrix with $$ N \approx 1.5 \frac{1.35^n}{\sqrt{n}}\ {\rm when}\ n\rightarrow\infty $$ This show that that HFE system {\em are not random system}. The difference with a random system for the challenge 1 can be detected after $12$ hours. \end{itemize}
Keywords : hfe crypto groebner
Type de document :
Communication dans un congrès
YACC 2002 - Conference on Cryptography, 2002, Porquerolles, France. 2002
Liste complète des métadonnées
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 14:53:24
Dernière modification le : jeudi 11 janvier 2018 - 06:27:20


  • HAL Id : inria-00100998, version 1



Jean-Charles Faugère. Gröbner bases and application to HFE. YACC 2002 - Conference on Cryptography, 2002, Porquerolles, France. 2002. 〈inria-00100998〉



Consultations de la notice