Algorithmes

Séquences Pseudo-Aléatoires

Les séquences qui imitent le hasard par des méthodes déterministes constituent si l'on peut dire un thème récurrent en Télécommunications. En chiffrement par flot (streamcipher) elles permettent d'engendrer des clés trés longues et donc trés sûres.
En codage à accés multiple elles permettent de discerner dans une situation de partage de canal qui a parlé et quand. La technique de CDMA (Code Division Multiple Access) est d'usage constant en téléphonie mobile.
En étalement de spectre (Spread Spectrum, une contre-mesure courante en communications militaires) elles permettent de prémunir le signal contre un brouillage passe-bande.
S 'il est vrai que les récurrences linéaires par leur linéarité même présentent des faiblesses cryptographiques elles sont néammoins la brique de base de nombreux systèmes que l'ajout d'un ou plusieurs étages de transformations non-linéaires permet de "durcir".
L' expérience acquise à l'I3S dans le domaine des codes cycliques sur les anneaux finis admet des retombées dans le domaine des récurrences linéaires et de la génération de séquences pseudo-aléatoires. Par exemple le résultat primé [18] (Best paper in Information Theory IEEE award, 94) de P. Solé sur la dualité formelle des codes de Kerdock et Preparata repose sur l'utilisation de récurrences linéaires sur ${\bf Z}_4.$ Ces récurrences linéaires sur l'anneau de définition sont essentiellement quadratiques sur le corps à deux éléments.

A noter que la future norme de téléphonie mobile UMTS doit utiliser des récurrences linéaires sur ${\bf Z}_4.$
Les experts internationaux dans ces domaines susceptibles de séjourner au projet sont Tor Helleseth (Bergen), Guang Gong (Waterloo), P. Udaya (Melbourne).

Réseaux Arithmétiques

Les réseaux arithmétiques constituent un domaine à la frontière de l'algorithmique et de la théorie des nombres. Le cassage de certains systèmes cryptographiques (le "knapsack" dûà Merkle Hellman [21] par Shamir [26] dans les années 80) a nécéssité l'étude fine de certains algorithmes (LLL par exemple) de calcul de vecteurs de petit poids dans les réseaux. Nous pensons que le dictionnaire trés profond qui existe entre les codes et les réseaux n'a pas été exploité de facçon systématique. Les analogue naturels des systèmes existants à base de codes en blocs (McEliece, Niedereiter) conduisent-par ce dictionnaire-à des systèmes originaux et qui ont des forces et des faiblesses différentes [14,4].

De plus, un système récent NTRU [23,24,25] développé à Brown University en 1996 par deux mathématiciens bien connus (Jeff Hoffstein et J. Silverman) qui ont monté une start up ([23]) sur ce thème utilise deux des spécialités du projet : Les réseaux arithmétiques et les anneaux finis. Ce cryptosystème à clé publique est nouveau et performant (plus rapide en encryption-décryption et moins encombrant en taille de clés) que ne le sont des systèmes La motivation de base pour revisiter les réseaux aprés le fiasco du Knapsack étant que la clé publique étant proportionnelle à la dimension du réseau (et non pas à son carré) il devient faisable d'utiliser des réseaux de dimension beaucoup plus grande, trop grande pour que LLL soit efficace. Nous comptons poursuivre ces recherches avec l'équipe de l'A2X de Bordeaux (et notamment Martinet et Bachoc que nous connaissons depuis 91) et à l'étranger Chris Charnes (Melbourne).

Problème du Log discret

De nombreux protocoles cryptographiques arithmétiques nécessitent la construction de grands groupes finis abéliens à la structure "cachée" [16]. Par exemple le cardinal d'un tel groupe ne doit pas être "friable" c'est à dire être le produit d' un grand nombre de petits diviseurs. L'idée de base est la suivante : si g est un générateur dudit groupe G alors on definit de log de base g d'un élément x comme l'unique entier n<O(g) s'il existe tel que gⁿ=x. Le desiderata du cryptographe -et la hantise du cryptanaliste- est que x étant donné, l'entier n doit être difficile à calculer. On sait depuis les travaux de Koblitz dans les années 80 que les points sur une courbe elliptique sur un corps fini (munis de la loi d'addition canonique) constituent un candidat possible. De nombreuses attaques ultérieures ont mis en évidence l'existence d'instances faibles d'un tel problème. Les chercheurs se sont tournés alors vers des situations géometriques plus compliquées: par exemple la Jacobienne d'une variété abélienne sur un corps fini. C'est à la construction de tels exemples qu' Yves Aubry travaille actuellement. Alexandre Temkine (candidat CR2) de par ses travaux sur l'arithmétique algébrique a la culture mathématique nécessaire pour se reconvertir et devenir opérationnel trés vite dans ce domaine.

Applications des bases de Gröbner

Rappelons que la théorie des bases standards permet de construire des générateurs d'idéaux dans des anneaux de polynômes à plusieurs variables. Malgré un résultat de complexité négatif (temps de calcul doublement exponentiel en les données!) elles demeurent, lorsque le nombre de variables n'est pas trop grand d'une grande utilité pratique. Elle constituent toujours un sujet actuel en calcul formel (deux sessions au congrés IMACS-ACA 2001) et peuvent constituer une nouvelle collaboration avec GALAAD.

Codes dans les algèbres de groupe

Une construction classique de codes sur des corps ou sur des anneaux finis consiste à considérer des idéaux dans un anneau de polynômes [20]. L'intérêt d'une telle construction est de construire des codes ayant au départ une certaine symétrie ce qui peut par la suite être exploité de manière algorithmique. Un bon exemple est la circuiterie d'encodage des codes cycliques par des registres à décalage.
Les bases standards peuvent intervenir pour classifier certains codes [22] ou aussi comme technique de décodage. Un bon exemple est le cas des codes cycliques[15]. La structure polynomiale multivariée des codes géométriques se prête naturellement à l'utilisation des bases standards [19].

Systèmes de cryptographie combinatoires

Dans sa discussion des problèmes algorithmiquement durs sur lesquels fonder un système de cryptographie à clé publique Koblitz [16, p.111] mentionne "Ideal membership" c'est à dire le problème originel pour lequel les bases standards ont été conçues. De même que les problèmes à base de réseaux arithmétiques évoqués plus haut elles constituent un essai d'alternative aux systèmes fondés sur l'arithmétique des entiers naturels comme RSA.