Gröbner bases and application to HFE
Résumé
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}