En commun avec François Morain.

Cheng et Wan étudient depuis 2004 comment le logarithme discret sur les corps non premiers se réduit à un certain problème de décodage des codes de Reed-Solomon. Leur objectif est de prouver la difficulté du décodage des codes de Reed-Solomon, en présence d'un grand nombre d'erreurs, sous l'hypothèse que le logarithme discret est difficile. Nous nous sommes proposés d'étudier la réduction dans le sens inverse: utilisation d'algorithmes de décodage connus pour construire un algorithme de calcul de logarithmes discrets sur les corps finis. La méthode est une méthode de calcul d'index, où la découverte de relations repose sur le décodage (des codes de Reed-Solomon). Dans un premier temps, nous avons utilisé des algorithmes de décodage unique, comme celui de Gao, par opposition au décodage en liste. Ces méthodes ont été implantées en Magma et NTL. Bien que cette méthode ne semble pas aussi performante que les méthodes classiques à la Adleman, il y a toutefois de nombreuses thématiques originales qui émergent.

Nous ferons aussi le point sur la difficulté du décodage des codes de Reed-Solomon.

Les automates linéaires de type LFSR (Linear Feedback Shift Register) ou LFSM (Linear Finite State Machine) sont utilisés dans beaucoup de systèmes de chiffrement symétrique, en particulier en chiffrement à flot, mais aussi pour certaines fonctions de hachages de type "lightweight). Nous présenterons l'état de l'art et de récentes avancées sur leur design en vue d'implémentations hardwares et/ou software efficaces.

Nous présenterons aussi la famille plus générale des automates dits algébriques (AFSM) dont les FCSR sont les plus connus. Il s'agit d'automates dont la fonction de transition peut être décrite par une matrice à coefficient dans une algèbre possédant des fonctions de type modulo. Ces automates ne sont pas GF(2)-linéaires et permettent d'introduire de la non-linéarité dans les opérations, tout en ayant une strucutre algébrique garantissant certaines bonnes propriétés de ces automates. Nous verrons également que les récentes avancées sur les LFSR peuvent souvent s'appliquer directement à cette famille plus large d'automates.

Les extensions d'anneau jouent un rôle dans de nombreux tests de (pseudo)-primalité. Je rappellerai quelques définitions et algorithmes concernant ces extensions et j'expliquerai leur rôle dans quelques tests anciens et nouveaux.

Travail commun avec Tony Ezome et Reynald Lercier.

Je donnerai un aperçu de quelques-unes des techniques de cryptanalyse non statistique d'AES proposées à ce jour, en détaillant un peu plus celles à l'étude desquelles j'ai contribué. Les modèles de sécurité considérés seront d'une part le modèle traditionnel, dans lequel l'attaquant dispose d'un accès "en boîte noire" à une instance aléatoire de la primitive et d'autre part le modèle plus paradoxal proposé par Knudsen et Rijmen en 2007, dans lequel l'attaquant dispose d'un accès "en boîte blanche", à clé connue, à une instance aléatoire de la primitive.

Nous exposerons des progrès récents en algèbre linéaires des matrices polynomiales univariées et entières. Une des questions centrales sera la réduction de bases de réseaux.

Dans le cas polynomial les meilleurs algorithmes pour ce problème admettent des bornes de complexités analogues à celle du produit de matrices correspondant. Nous présenterons plusieurs approches essentiellement optimales pour la réduction et leurs liens avec les questions du calcul d'une base minimale de l'espace nul, d'approximants matriciels et de la forme normale d'Hermite.

Dans le cas entier, autour de la réduction de type LLL, nous mettrons en évidence des analogies avec l'algorithmique du cas polynomial. Ces analogies qui seront illustrées en abordant les approches récursives à la Lehmer-Knuth-Schönhage pour LLL, ouvrent des pistes vers des nouvelles améliorations des bornes de complexité.