Décodage des codes algébriques et cryptographie

I discuss the decoding problem of two important families of algebraiccodes: binary cyclic codes and $q$-ary Reed-Solomon codes (and alsoalgebraic geometry codes). Concerning cyclic codes, they do not have ageneric decoding algorithm, except for the case of the BCH codes andrelated codes (Hartmann-Tzeng, Roos bound). Among these codes are thequadratic residue codes, for which there is no generic decodingalgorithm, but which have good parameters. I present and study asystem of equations related the syndrom decoding of cyclic codes.These equations can be solved by Gröbner tools. We thus obtaindecoding algorithms with good complexity for these codes. This workwas a part of the PHD thesis of Magali Bardet.Regarding Reed-Solomon codes, they can be seen as {\em evaluation codes}, and the associated decoding problem amounts to findingapproximations of a function by low degree polynomials. A majorprogress has been achieved by Guruswami and Sudan, who have producedan algorithm which can decode much more errors than classical ones, byrelaxing the hypothesis that the solution be unique. I have foundimprovements of this algorithm, which speed it, and make itdeterministic (notably by removing a fectorization over finitefields), either in the Reed-Solomon case, or in the algebraic geometrycase. This achievements were made when I directed Lancelot Pecquet PHDthesis.From the theoretical point of view, I have studied mutlivariategeneralizations, which correspond either to products of Reed-Solomoncodes, or to Reed-Muller codes. I then obtain a good decoding radius,for codes with small rate. In the case of Reed-Muller codes over thebinary field, Cédric Tavernier, in his PHD thesis under my direction,has found and implemented an efficient algorithm, more than thealgorithms based on the Guruswami-Sudan method.I have also studied the negative aspects of syndrom decoding ofgeneral linear codes, and of the the decoding of Reed-Solomon codes,when the number of errors is high, aiming at applications incryptography. In the first case, I have built a cryptographic hashfunction with a security reduction, that is to say, to find an attackon the hash function is equivalent to solve a difficult codingproblem. I have also built a new primitive for public key encryption,relying on the difficulty of decoding Reed-Solomon codes.In a more applied domain, I have proposed, with Raghav Bhaskar, a newprotocol for multiusers group key agreement, founded on the discretelogarithm problem. Raghav Bhaskar has given a security proof of thisprotocol, in his PHD thesis under my direction. We have also discussedhow to adapt the protocol to messages losses, since our protocol isamong the few which can resist such losses.Je traite du décodage de deux grandes familles de codes algébriques :les codes cycliques binaires et les codes de Reed-Solomon sur unalphabet $q$-aire (ainsi que les codes géométriques). En ce quiconcerne les codes cycliques, ceux-ci n'ont pas d'algorithme génériquede décodage, mis à part les codes BCH ou assimilés (bornes deHartman-Tzeng, de Roos). Au premier rang des codes intéressants pourlesquels on ne connaît pas d'algorithme de décodage {\em générique}figurent les {\em codes à résidus quadratiques}, qui ont de bonsparamètres. J'étudie une mise en équation du problème du décodage parsyndrôme de ces codes, que l'on peut résoudre avec des outils de basede Gröbner. On obtient ainsi des algorithmes de décodage de complexitéraisonnable pour ces codes. Ces travaux ont fait l'objet d'une partiede la thèse de Magali Bardet.En ce qui concerne les codes de Reed-Solomon, ceux-ci peuvent être vuscomme des {\em codes d'évaluation}, et le problème de décodage associérevient à approcher une fonction par des polynômes de base degré. Degrands progrès ont été réalisés par Guruswami et Sudan, qui ont trouvéun algorithme qui décode bien au delà des rayons classiques dedécodage, en relaxant l'hypothèse que la solution doit être unique. Jepropose d'améliorer certaines étapes de cet algorithme, en le rendantplus rapide et déterministe (notamment en évitant une factorisation depolynôme sur un corps fini), dans le cas des codes Reed-Solomon, etdans le cas des codes géométriques. Ces travaux ont été effectués enencadrant Lancelot Pecquet.Du point de vue théorique, j'ai étudié des généralisationsmultivariées, qui correspondent à certains codes: les codes produitsde Reed-Solomon, et les codes de Reed-Muller. On obtient ainsi un bonrayon de décodage, dans le cas des codes de petit taux. Dans le cas decodes de Reed-Muller sur l'alphabet binaire, Cédric Tavernier, dans sathèse sous ma direction, a produit et implanté un algorithme efficace,plus que ceux basés sur l'algorithme de Guruswami-Sudan.J'ai étudié les aspects négatifs du problème de décodage par syndrômedes codes linéaires, et du décodage des codes de Reed-Solomon, quandle nombre d'erreurs est élevé, en but d'application en cryptographie.Dans le premier cas, j'ai construit une fonction de hachagecryptographique à réduction de sécurité, c'est-à-dire que trouver unefaiblesse dans le fonction de hachage revient à résoudre un problèmeréputé difficile de codage. J'ai aussi construit une nouvelleprimitive de chiffrement à clé publique, reposant sur la difficulté dedécoder les codes de Reed-Solomon.Dans un domaine plus appliqué, j'ai proposé avec Raghav Bhaskar unnouvel algorithme d'échange de clé multi-utilisateurs, fondé sur leproblème du logarithme discret. Raghav Bhaskar a fourni une preuve desécurité de ce protocole, pendant sa thèse sous ma direction. Nousavons aussi étudié comment adapter ce protocole aux pertes demessages, car notre protocole est un des seuls qui est robuste à cespertes