La dérégulation des marchés électriques modifie en profondeur l'approche technico-économique dans l'exploitation et l'optimisation des réseaux électriques. C'est dans ce nouveau contexte que les spécialistes des réseaux électriques se voient confrontés à de nombreux défis. Ainsi, les grands réseaux électriques sont utilisés de plus en plus près de leur limite de stabilité. Cependant, faire fonctionner un réseau trop près de ses limites créer des oscillations de puissance entre les centrales de différentes régions des réseaux. Ces oscillations sont appelées oscillations <

Les applications du traitement du signal (TDSI) sont maintenant largement utilisées dans des domaines variés allant de l'automobile aux communications sans fils, en passant par les applications multimédias et les télécommunications. La complexité croissante des algorithmes implémentés et l'augmentation continue des volumes de données et des débits applicatifs requièrent souvent la conception de circuits intégrés dédiés (ASIC). Typiquement l'architecture d'un composant complexe du TDSI utilise (1) des éléments de calculs de plus en plus complexes, (2) des mémoires et des modules de brassage de données (entrelaceur/désentrelaceur pour les TurboCodes, blocs de redondance spatio-temporelle dans les systèmes OFDM1/MIMO, ...). Aujourd'hui, la complexité et le coût de ces systèmes sont très élevés; les concepteurs doivent pourtant parvenir à minimiser la consommation et la surface total du circuit, tout en garantissant les performances temporelles requises. Sur cette problématique globale, nous nous intéressons à l'optimisation des architectures des modules de brassage de données (réseau d'interconnexion, contrôleur...) devant réaliser une règle d'entrelacement définie par l'application et ayant pour objectif d'utiliser un réseau d'interconnexion défini par le concepteur. L'architecture que nous ciblons se compose d'éléments de calculs (PE0,...PEn), de mémoires de données utilisées pour stocker les opérandes et les résultats produits par les éléments de calculs (Mem0,...Memm), d'un réseau d'interconnexion reliant les éléments de calculs aux mémoires et d'une unité de contrôle. Le réseau d'interconnexion est défini par l'utilisateur et peut être basé sur différent modèles : cross-bar, réseaux de Benes, réseau de Bruinj, barrière de multiplexeurs, barrel-shifters (barillets), papillons... L'unité de contrôle est composée de deux parties : un contrôleur de réseau et un contrôleur de mémoires. Ces contrôleurs sont basés sur un ensemble de mémoires de contrôle (une ROM de contrôle par banc mémoire Mem dans l'architecture cible) contenant les mots de commande relatifs au fonctionnement du système. L'approche que nous proposons est à même d'optimiser cette partie de contrôle de l'architecture. Nous proposons plusieurs méthodologies d'exploration et de conception permettant de générer automatiquement une architecture d'entrelacement optimisée réalisant une règle de brassage de données, ou entrelacement, tel que définie par exemple dans un standard de communication. Les approches que nous proposons prennent en entrée (1) des diagrammes temporels (générés à partir de la règle d'entrelacement et de contraintes spécifiant les séquences d'accès parallèles aux données) et (2) une contrainte utilisateur sur le réseau d'interconnexion que doit utiliser l'architecture. Ce flot formalise ensuite ces contraintes de brassage des données sous la forme (1) d'un modèle matriciel des séquences de données qui devront être traitées par chaque processeur et (2) d'un Graphe de Conflit d'Adressage (ACG), dont les propriétés permettent une exploration efficace de l'espace des solutions architecturales. L'objectif est ensuite de générer une architecture cible, en garantissant un fonctionnement sans conflit d'accès mémoire (lorsque plusieurs processeurs veulent accéder en même temps à un même banc mémoire mais pour traiter des données différentes), en respectant la contrainte de réseau et en optimisant l'architecture obtenue (notamment concernant l'architecture de son contrôleur). Cette approche a été mise en oeuvre au sein d'un d'outil et appliquée sur plusieurs cas d'étude : High Speed Packet Access (HSPA), Ultra-WideBand (UWB) et une application Wimax. Ces expériences montrent qu'en comparaison aux approches de l'état de l'art nos approches permettent d'atteindre des gains en surface significatifs. Notamment, pour des applications Turbo Codes pour lesquels les gains sont très importants.

Ce travail permet de résoudre des problemes d'optimisation LMI dependant rationnellement d'un ou plusieurs parametres. Ce resultat est fondamental car il ouvre une solution efficace a la classe extremement large des problemes se formulant comme un probleme d'optimisation LMI dependant de parametres. En Automatique, une telle classe de problemes comprend celle de la conception de cor- recteurs dependant de parametres. Un cas particulier important est celui de la commande des systµemes non lineaires par sequencement de gains. Au depart, cette classe de problemes d'Automatique a ete motive par une nouvelle application possible : la conception de correcteurs dont les gains sont une fonction explicite du cahier des charges, baptises " correcteurs rereglables ". L'interet est de permettre un rereglage aise sur site d'exploitation par un utilisateur neophyte en Automatique, voire un rereglage automatique. Ce travail a permis de formaliser ce problµeme de rereglage, d'en proposer une solution complete et de la valider.

Successivement veuve de Berthold Rembolt et de Claude Chevallon, Charlotte Guillard hérite en 1537 du plus ancien atelier typographique français, le Soleil d'Or, dont elle conduit l'activité durant près de vingt années. Sous sa direction, l'atelier parvient à accaparer deux marchés spécifiques : textes de droit savant et ouvrages des Pères de l'Église. La thèse vise à interroger les conditions de réalisation de ce programme éditorial. On y présente les modalités matérielles de production et de commercialisation des ouvrages. On met ainsi en évidence la forte implication de la parentèle de Charlotte Guillard à tous les niveaux de la chaîne éditoriale, et la coexistence de réseaux de collaborateurs qui, en dépit de motivations intellectuelles et idéologiques parfois divergentes, parviennent à faire œuvre commune. À travers une enquête mobilisant à la fois les sources archivistiques, l'analyse matérielle des ouvrages imprimés et la lecture des préfaces et épîtres liminaires, la monographie permet d'écrire une histoire concrète de l'activité intellectuelle qui tienne compte des conditions idéologiques, sociales et économiques de sa mise en œuvre / Widow of Berthold Rembolt first, then of Claude Chevallon, Charlotte Guillard became in 1537 heiress of France's oldest typography workshop. With Charlotte Guillard at its head, the Soleil d'Or managed to monopolise two specific markets, the law texts and the works of the Church Fathers. The purpose of our thesis is to investigate the practical conditions which made these publications possible. It will highlight the material arrangements of the production and selling of those books, and focus at the people who stayed at Charlotte Guillard's side. This will allow us to demonstrate the importance of her relatives at every step of the process, and to show the coexistence of various networks of collaborators who manage to work on a common basis despite, at times, opposite intellectual and ideological motivations. Calling on manuscript archives, physical bibliography, and an analysis of the prefaces and liminary epistles, this monograph allows us to write a holistic history of the intellectual endeavour, taking into account all the ideological, social and economic conditions entering in its construction

Un code correcteur d'erreur ajoute de la redondance à un message afin de pouvoir corriger celui-ci lorsque des erreurs se sont introduites pendant la transmission. Les codes convolutifs sont des codes performants, et par conséquent, souvent utilisés. Le principe d'un code convolutif consiste à se fixer une fonction de transfert définie sur le groupe des entiers relatifs et à effectuer la convolution d'un message avec cette fonction de transfert. Ces codes ne protègent pas le message d'une interception par une tierce personne. C'est pourquoi nous proposons dans cette thèse, des codes convolutifs avec des propriétés cryptographiques, définis sur des groupes non-commutatifs. Nous avons tout d'abord étudié les codes définis sur le groupe diédral infini, qui, malgré de bonnes performances, n'ont pas les propriétés cryptographiques recherchées. Nous avons donc étudié ensuite des codes convolutifs en bloc sur des groupes finis, avec un encodage variable dans le temps. Nous avons encodé chaque message sur un sous-ensemble du groupe différent à chaque encodage. Ces sous-ensembles sont générés de façon chaotique à partir d'un état initial, qui est la clé du cryptosystème symétrique induit par le code. Nous avons étudié plusieurs groupes et plusieurs méthodes pour définir ces sous-ensembles chaotiques. Nous avons étudié la distance minimale des codes que nous avons conçus et montré qu'elle est légèrement plus petite que la distance minimale des codes en blocs linéaires. Cependant, nous avons, en plus, un cryptosystème symétrique associé à ces codes. Ces codes convolutifs non-commutatifs sont donc un compromis entre correction d'erreur et sécurité. / An error correcting code adds redundancy to a message in order to correct it when errors occur during transmission.Convolutional codes are powerful ones, and therefore, often used. The principle of a convolutional code is to perform a convolution product between a message and a transfer function, both defined over the group of integers. These codes do not protect the message if it is intercepted by a third party. That is why we propose in this thesis, convolutional codes with cryptographic properties defined over non-commutative groups. We first studied codes over the infinite dihedral group, which despite good performance, do not have the desired cryptographic properties. Consequently, we studied convolutional block codes over finite groups with a time-varying encoding. Every time a message needs to be encoded, the process uses a different subset of the group. These subsets are chaotically generated from an initial state. This initial state is considered as the symmetric key of the code-induced cryptosystem. We studied many groups and many methods to define these chaotic subsets. We examined the minimum distance of the codes we conceived and we showed that it is slightly smaller than the minimum distance of the linear block codes. Nevertheless, our codes have, in addition, cryptographic properties that the others do not have. These non-commutative convolutional codes are then a compromise between error correction and security.

La sécurité de l’information repose sur la bonne interaction entre différents niveaux d’abstraction : les composants matériels, systèmes d’exploitation, algorithmes, et réseaux de communication. Cependant, protéger ces éléments a un coût ; ainsi de nombreux appareils sont laissés sans bonne couverture. Cette thèse s’intéresse à ces différents aspects, du point de vue de la sécurité et de la cryptographie. Nous décrivons ainsi de nouveaux algorithmes cryptographiques (tels que des raffinements du chiffrement de Naccache–Stern), de nouveaux protocoles (dont un algorithme d’identification distribuée à divulgation nulle de connaissance), des algorithmes améliorés (dont un nouveau code correcteur et un algorithme efficace de multiplication d’entiers),ainsi que plusieurs contributions à visée systémique relevant de la sécurité de l’information et à l’intrusion. En outre, plusieurs de ces contributions s’attachent à l’amélioration des performances des constructions existantes ou introduites dans cette thèse. / Information security relies on the correct interaction of several abstraction layers: hardware, operating systems, algorithms, and networks. However, protecting each component of the technological stack has a cost; for this reason, many devices are left unprotected or under-protected. This thesis addresses several of these aspects, from a security and cryptography viewpoint. To that effect we introduce new cryptographic algorithms (such as extensions of the Naccache–Stern encryption scheme), new protocols (including a distributed zero-knowledge identification protocol), improved algorithms (including a new error-correcting code, and an efficient integer multiplication algorithm), as well as several contributions relevant to information security and network intrusion. Furthermore, several of these contributions address the performance of existing and newly-introduced constructions.

Contrairement aux protocoles cryptographiques fondés sur la théorie des nombres, les systèmes de chiffrement basés sur les codes correcteurs d’erreurs semblent résister à l’émergence des ordinateurs quantiques. Un autre avantage de ces systèmes est que le chiffrement et le déchiffrement sont très rapides, environ cinq fois plus rapide pour le chiffrement, et 10 à 100 fois plus rapide pour le déchiffrement par rapport à RSA. De nos jours, l’intérêt de la communauté scientifique pour la cryptographie basée sur les codes est fortement motivé par la dernière annonce de la “National Institute of Standards and Technology" (NIST), qui a récemment initié le projet intitulé “Post-Quantum cryptography Project". Ce projet vise à définir de nouveaux standards pour les cryptosystèmes résistants aux attaques quantiques et la date limite pour la soumission des cryptosystèmes à clé publique est fixée pour novembre 2017. Une telle annonce motive certainement à proposer de nouveaux protocoles cryptographiques basés sur les codes, mais aussi à étudier profondément la sécurité des protocoles existants afin d’écarter toute surprise en matière de sécurité. Cette thèse suit cet ordre d’idée en étudiant la sécurité de plusieurs protocoles cryptographiques fondés sur la théorie des codes correcteurs d’erreurs. Nous avons commencé par l’étude de la sécurité d’une version modifiée du cryptosystème de Sidelnikov, proposée par Gueye et Mboup [GM13] et basée sur les codes de Reed-Muller. Cette modification consiste à insérer des colonnes aléatoires dans la matrice génératrice (ou de parité) secrète. La cryptanalyse repose sur le calcul de carrés du code public. La nature particulière des codes de Reed-Muller qui sont définis au moyen de polynômes multivariés binaires, permet de prédire les valeurs des dimensions des codes carrés calculés, puis permet de récupérer complètement en temps polynomial les positions secrètes des colonnes aléatoires. Notre travail montre que l’insertion de colonnes aléatoires dans le schéma de Sidelnikov n’apporte aucune amélioration en matière de sécurité. Le résultat suivant est une cryptanalyse améliorée de plusieurs variantes du cryptosystème GPT qui est un schéma de chiffrement en métrique rang utilisant les codes de Gabidulin. Nous montrons qu’en utilisant le Frobenius de façon appropriée sur le code public, il est possible d’en extraire un code de Gabidulin ayant la même dimension que le code de Gabidulin secret mais avec une longueur inférieure. Le code obtenu corrige ainsi moins d’erreurs que le code secret, mais sa capacité de correction d’erreurs dépasse le nombre d’erreurs ajoutées par l’expéditeur et par conséquent, un attaquant est capable de déchiffrer tout texte chiffré, à l’aide de ce code de Gabidulin dégradé. Nos résultats montrent qu’en fin de compte, toutes les techniques existantes visant à cacher la structure algébrique des codes de Gabidulin ont échoué. Enfin, nous avons étudié la sécurité du système de chiffrement de Faure-Loidreau [FL05] qui est également basé sur les codes de Gabidulin. Inspiré par les travaux précédents et, bien que la structure de ce schéma diffère considérablement du cadre classique du cryptosystème GPT, nous avons pu montrer que ce schéma est également vulnérable à une attaque polynomiale qui récupère la clé privée en appliquant l’attaque d’Overbeck sur un code public approprié. Comme exemple, nous arrivons en quelques secondes à casser les paramètres qui ont été proposés comme ayant un niveau de sécurité de 80 bits. / Contrary to the cryptosystems based on number theory, the security of cryptosystems based on error correcting codes appears to be resistant to the emergence of quantum computers. Another advantage of these systems is that the encryption and decryption are very fast, about five times faster for encryption, and 10 to 100 times faster for decryption compared to RSA cryptosystem. Nowadays, the interest of scientific community in code-based cryptography is highly motivated by the latest announcement of the National Institute of Standards and Technology (NIST). They initiated the Post-Quantum cryptography Project which aims to define new standards for quantum resistant cryptography and fixed the deadline for public key cryptographic algorithm submissions for November 2017. This announcement motivates to study the security of existing schemes in order to find out whether they are secure. This thesis thus presents several attacks which dismantle several code-based encryption schemes. We started by a cryptanalysis of a modified version of the Sidelnikov cryptosystem proposed by Gueye and Mboup [GM13] which is based on Reed-Muller codes. This modified scheme consists in inserting random columns in the secret generating matrix or parity check matrix. The cryptanalysis relies on the computation of the square of the public code. The particular nature of Reed-Muller which are defined by means of multivariate binary polynomials, permits to predict the values of the dimensions of the square codes and then to fully recover in polynomial time the secret positions of the random columns. Our work shows that the insertion of random columns in the Sidelnikov scheme does not bring any security improvement. The second result is an improved cryptanalysis of several variants of the GPT cryptosystem which is a rank-metric scheme based on Gabidulin codes. We prove that any variant of the GPT cryptosystem which uses a right column scrambler over the extension field as advocated by the works of Gabidulin et al. [Gab08, GRH09, RGH11] with the goal to resist Overbeck’s structural attack [Ove08], are actually still vulnerable to that attack. We show that by applying the Frobeniusoperator appropriately on the public key, it is possible to build a Gabidulin code having the same dimension as the original secret Gabidulin code, but with a lower length. In particular, the code obtained by this way corrects less errors than thesecret one but its error correction capabilities are beyond the number of errors added by a sender, and consequently an attacker is able to decrypt any ciphertext with this degraded Gabidulin code. We also considered the case where an isometrictransformation is applied in conjunction with a right column scrambler which has its entries in the extension field. We proved that this protection is useless both in terms of performance and security. Consequently, our results show that all the existingtechniques aiming to hide the inherent algebraic structure of Gabidulin codes have failed. To finish, we studied the security of the Faure-Loidreau encryption scheme [FL05] which is also a rank-metric scheme based on Gabidulin codes. Inspired by our precedent work and, although the structure of the scheme differs considerably from the classical setting of the GPT cryptosystem, we show that for a range of parameters, this scheme is also vulnerable to a polynomial-time attack that recovers the private key by applying Overbeck’s attack on an appropriate public code. As an example we break in a few seconds parameters with 80-bit security claim.

Le traitement de signal optique est une pierre angulaire de la prochaine génération de systèmes de communications optiques avancées. En raison de son comportement non-linéaire, l'amplificateur optique à semi-conducteur (SOA) constitue un élément essentiel du traitement de signal optique. Afin de concevoir et d'optimiser de tels systèmes, des outils d'analyses ultra performants sont nécessaires. Dans la présente thèse, un simulateur basé sur l'algorithme de Monte Carlo Multi Canonique (MMC) a été développé et utilisé afin d'analyser une importante fonctionnalité du traitement de signaux optiques, à savoir la suppression du bruit d'intensité du SOA dans les spectrum-sliced wavelength division multiplexed passive optical networks (SS-WDM PON). L'algorithme de MMC a été introduit au début des années 90 en physique statistique. Depuis 2003, il est utilisé par les chercheurs dans la communauté des communications optiques. Dans le premier chapitre de cette thèse, une brève introduction de la suppression du bruit d'intensité du SOA dans les SS-WDM, ainsi que l'algorithme MMC et la modélisation du SOA seront présentés. Dans le second chapitre, l'algorithme MMC a été utilisé pour la première fois, afin d'estimer les fonctions de densités de probabilités conditionnelles (PDF) des "0" et des "1" logiques au niveau du récepteur d'un lien SS-WDM, avec un utilisateur, assisté par un SOA. En exploitant les PDF, le taux d'erreur binaire (BER) a été estimé à la fois pour les systèmes SS-WDM classiques, les systèmes SS-WDM avec suppression de bruit d'intensité d'un SOA, et finalement les systèmes SS-WDM assisté par SOA, et ce, en tenant compte de l'effet des filtres sélecteurs de canaux. Une nouvelle technique de pattern warping est aussi introduite, et ce, afin de traiter l'interférence inter-symboles (ISI) dû a la mémoire du canal de communication. Les estimations des PDF et des BER sont validées par des mesures expérimentales. Résumé v Le chapitre trois est entièrement consacré à la question de l'ISI, en particulier l'effet dû à la dynamique du SOA, qui est aussi appelé l'effet de patterning. Pour ce faire, un lien avec une source laser à 10 Gb/s est considéré. L'objectif principal est de montrer la fiabilité du simulateur pour l'estimation des PDF conditionnelles des "0" et des "1" logiques reçus en présence de l'effet de patterning. De plus, une nouvelle méthode pour mesurer directement les PDF est proposée. Les PDF conditionnelles et les BER simulées sont comparés avec les mesures expérimentales. Le chapitre 4 porte sur les systèmes SS-WDM, toujours avec des SOA, comprenant plusieurs canaux. L'objectif est d'étudier l'impact des filtres optiques sur la performance du système et de montrer comment choisir leurs caractéristiques (bande passante, forme et espacement inter-canal) afin de maximiser l'efficacité spectrale. Dans cette étude, la suppression du bruit d'intensité du SOA et les codes correcteur d'erreurs sont considérés. Ces deux problèmes sont abordés pour la première fois dans cette thèse. On montre aussi pour la première fois que la parallélisasion de l'algorithme MMC peut facilement être utilisé, et ce, contrairement aux affirmations précédentes dans la littérature. Le prix à payer est la perte d'une petite fraction d'échantillons par cycle MMC par noeud de calcul. Les résultats de simulation des BER sont validés à l'aide de résultats publié par d'autres groupes de recherche. Dans le dernier chapitre, les performances des spectral amplitude coded optical division multiple access (SAC-OCDMA), avec et sans la suppression de bruit d'intensité du SOA, sont analysées pour la première fois. Les résultats simulés pour le cas de 2 et 3 utilisateurs actifs sont validés par rapport aux mesures déjà réalisées et publiés par notre groupe de recherche.

Dans ce mémoire, nous nous pencherons tout particulièrement sur une primitive cryptographique connue sous le nom de partage de secret. Nous explorerons autant le domaine classique que le domaine quantique de ces primitives, couronnant notre étude par la présentation d’un nouveau protocole de partage de secret quantique nécessitant un nombre minimal de parts quantiques c.-à-d. une seule part quantique par participant. L’ouverture de notre étude se fera par la présentation dans le chapitre préliminaire d’un survol des notions mathématiques sous-jacentes à la théorie de l’information quantique ayant pour but primaire d’établir la notation utilisée dans ce manuscrit, ainsi que la présentation d’un précis des propriétés mathématique de l’état de Greenberger-Horne-Zeilinger (GHZ) fréquemment utilisé dans les domaines quantiques de la cryptographie et des jeux de la communication. Mais, comme nous l’avons mentionné plus haut, c’est le domaine cryptographique qui restera le point focal de cette étude. Dans le second chapitre, nous nous intéresserons à la théorie des codes correcteurs d’erreurs classiques et quantiques qui seront à leur tour d’extrême importances lors de l’introduction de la théorie quantique du partage de secret dans le chapitre suivant. Dans la première partie du troisième chapitre, nous nous concentrerons sur le domaine classique du partage de secret en présentant un cadre théorique général portant sur la construction de ces primitives illustrant tout au long les concepts introduits par des exemples présentés pour leurs intérêts autant historiques que pédagogiques. Ceci préparera le chemin pour notre exposé sur la théorie quantique du partage de secret qui sera le focus de la seconde partie de ce même chapitre. Nous présenterons alors les théorèmes et définitions les plus généraux connus à date portant sur la construction de ces primitives en portant un intérêt particulier au partage quantique à seuil. Nous montrerons le lien étroit entre la théorie quantique des codes correcteurs d’erreurs et celle du partage de secret. Ce lien est si étroit que l’on considère les codes correcteurs d’erreurs quantiques étaient de plus proches analogues aux partages de secrets quantiques que ne leur étaient les codes de partage de secrets classiques. Finalement, nous présenterons un de nos trois résultats parus dans A. Broadbent, P.-R. Chouha, A. Tapp (2009); un protocole sécuritaire et minimal de partage de secret quantique a seuil (les deux autres résultats dont nous traiterons pas ici portent sur la complexité de la communication et sur la simulation classique de l’état de GHZ). / In this thesis, we will focus on a cryptographic primitive known as secret sharing. We will explore both the classical and quantum domains of such schemes culminating our study by presenting a new protocol for sharing a quantum secret using the minimal number of possible quantum shares i.e. one single quantum share per participant. We will start our study by presenting in the preliminary chapter, a brief mathematical survey of quantum information theory (QIT) which has for goal primarily to establish the notation used throughout the manuscript as well as presenting a précis of the mathematical properties of the Greenberger-Horne-Zeilinger (GHZ)-state, which is used thoroughly in cryptography and in communication games. But as we mentioned above, our main focus will be on cryptography. In chapter two, we will pay a close attention to classical and quantum error corrections codes (QECC) since they will become of extreme importance when we introduce quantum secret sharing schemes in the following chapter. In the first part of chapter three, we will focus on classical secret shearing, presenting a general framework for such a primitive all the while illustrating the abstract concepts with examples presented both for their historical and analytical relevance. This first part (chapters one and two) will pave the way for our exposition of the theory of Quantum Secret Sharing (QSS), which will be the focus of the second part of chapter three. We will present then the most general theorems and definitions known to date for the construction of such primitives putting emphasis on the special case of quantum threshold schemes. We will show how quantum error correction codes are related to QSS schemes and show how this relation leads to a very solid correspondence to the point that QECC’s are closer analogues to QSS schemes than are the classical secret sharing primitives. Finally, we will present one of the three results we have in A. Broadbent, P.-R. Chouha, A. Tapp (2009) in particular, a secure minimal quantum threshold protocol (the other two results deal with communication complexity and the classical simulation of the GHZ-state).

Je traite du décodage de deux grandes familles de codes algébriques :<br />les codes cycliques binaires et les codes de Reed-Solomon sur un<br />alphabet $q$-aire (ainsi que les codes géométriques). En ce qui<br />concerne les codes cycliques, ceux-ci n'ont pas d'algorithme générique<br />de décodage, mis à part les codes BCH ou assimilés (bornes de<br />Hartman-Tzeng, de Roos). Au premier rang des codes intéressants pour<br />lesquels on ne connaît pas d'algorithme de décodage {\em générique}<br />figurent les {\em codes à résidus quadratiques}, qui ont de bons<br />paramètres. J'étudie une mise en équation du problème du décodage par<br />syndrôme de ces codes, que l'on peut résoudre avec des outils de base<br />de Gröbner. On obtient ainsi des algorithmes de décodage de complexité<br />raisonnable pour ces codes. Ces travaux ont fait l'objet d'une partie<br />de la thèse de Magali Bardet.<br /><br /><br />En ce qui concerne les codes de Reed-Solomon, ceux-ci peuvent être vus<br />comme des {\em codes d'évaluation}, et le problème de décodage associé<br />revient à approcher une fonction par des polynômes de base degré. De<br />grands progrès ont été réalisés par Guruswami et Sudan, qui ont trouvé<br />un algorithme qui décode bien au delà des rayons classiques de<br />décodage, en relaxant l'hypothèse que la solution doit être unique. Je<br />propose d'améliorer certaines étapes de cet algorithme, en le rendant<br />plus rapide et déterministe (notamment en évitant une factorisation de<br />polynôme sur un corps fini), dans le cas des codes Reed-Solomon, et<br />dans le cas des codes géométriques. Ces travaux ont été effectués en<br />encadrant Lancelot Pecquet.<br /><br />Du point de vue théorique, j'ai étudié des généralisations<br />multivariées, qui correspondent à certains codes: les codes produits<br />de Reed-Solomon, et les codes de Reed-Muller. On obtient ainsi un bon<br />rayon de décodage, dans le cas des codes de petit taux. Dans le cas de<br />codes de Reed-Muller sur l'alphabet binaire, Cédric Tavernier, dans sa<br />thèse sous ma direction, a produit et implanté un algorithme efficace,<br />plus que ceux basés sur l'algorithme de Guruswami-Sudan.<br /><br /><br /><br />J'ai étudié les aspects négatifs du problème de décodage par syndrôme<br />des codes linéaires, et du décodage des codes de Reed-Solomon, quand<br />le nombre d'erreurs est élevé, en but d'application en cryptographie.<br />Dans le premier cas, j'ai construit une fonction de hachage<br />cryptographique à réduction de sécurité, c'est-à-dire que trouver une<br />faiblesse dans le fonction de hachage revient à résoudre un problème<br />réputé difficile de codage. J'ai aussi construit une nouvelle<br />primitive de chiffrement à clé publique, reposant sur la difficulté de<br />décoder les codes de Reed-Solomon.<br /><br />Dans un domaine plus appliqué, j'ai proposé avec Raghav Bhaskar un<br />nouvel algorithme d'échange de clé multi-utilisateurs, fondé sur le<br />problème du logarithme discret. Raghav Bhaskar a fourni une preuve de<br />sécurité de ce protocole, pendant sa thèse sous ma direction. Nous<br />avons aussi étudié comment adapter ce protocole aux pertes de<br />messages, car notre protocole est un des seuls qui est robuste à ces<br />pertes.