All the results have been produced on a Sun Ultra 10 (440Mhz) with 1Gb of memory running Solaris 8. The program has been built with the help of a BDD management library we wrote in C and compiled with GNU GCC 2.95. (download it). HFE systems have been generated by a C++ program written by Jean-Francis Michon, and then slightly modified, built on top of Shoup's NTL library (with GMP support) (see Victor Shoup).
The following is the algorithm skeleton:
In the first step, the biggest BDD size is remind, as in the second (the index of the biggest is called the inflexion point).
One will be able to find some generated BDDs for some equations with N=10, N=12 and N=14. Black links are representations of the truth assignement of the corresponding variable, red for false assignements. Dotted links are negative links (one must invert the boolean function as the result). Graphs have been generated by dotty. One can find all the BDDs for a full HFE cryptosystem with N=10: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.
One can get a HFE cryptosystem generator: HFEgen.cpp. Written by Jean-Francis Michon and Jean-Baptiste Yunès, it has been slightly modified to provide command line control, it must be easy to use it but an old french documentation is available. One can find a example of a polynomial in the right format (NTL) here: polyHFE.txt. Download all in once.
This version actually support NTL5.4 with GMP and ISO-C++.
HFEgau.cpp is a program which implements the "left" algebraic attack on HFE, it has been written by Jean-Francis Michon and Jean-Baptiste Yunès from Jean-Francis ideas.
Les résultats "standards" suivants (pour N=24, 25, 26, 27, 28, 29) sont obtenus à partir de polynômes quadratiques tirés au hasard et de degré inférieur à 20000.
Tous les degrés inférieurs à 20000 ont été générés, il y en a 118 (selon l'algorithme utilisé par Jean-Francis).
Remarque : la taille du plus grand BDD représentant une équation pour un système à N variables semble être :
On trouvera quelques courbes d'analyse des résultats dans le fichier suivant : resultat. Les données ont été extraites en piochant "au hasard" (choix d'un degré dans les possibles) dans les résultats.
Les résultats "aléatoires" suivants (pour N=24, 25, 26, 27) ont été obtenus par tirage aléatoire de systèmes d'équations quadratiques dans GF(2). Le taux de remplissage correspond à la probabilité qu'un couple de variable apparraisse.
Les résultats "d'élimination des couples distants" suivants (pour N=24) consistent à éliminer dans un système d'équations donné tous les couples de variables dont les indices sont à "distance" supérieure au critère donné.
Les résultats suivants concernent la résolution par BDD du monôme X1+2i (donc X3, X5) "pur" (sans terme constant, sans S ni T et en base NTL).
Les résultats sont disponibles sous forme de courbes (pour X3).