Étude de divers problèmes lies aux graphes de Hamming

Cette thèse étudie deux approches différentes visant à réduire la taille de la clé publique des cryptosystèmes à base de codes correcteurs. Une première idée en ce sens est l'utilisation de familles de codes à haute capacité de correction, comme les codes géométriques. Depuis l'attaque de Sidelnikov et Shestakov, on sait qu'un attaquant peut retrouver la structure d'un code de Reed-Solomon utilisé dans la clé publique. Nous avons réussi à adapter aux courbes hyperelliptiques la méthode d'attaque développée par Minder contre les codes elliptiques. Nous sommes notamment en mesure d'attaquer en temps polynomial le système de Janwa et Moreno développé sur des codes géométriques de genre 2 ou plus. Une seconde idée est l'utilisation de codes correcteurs pour la métrique rang. Celle-ci complique énormément les attaques par décodage, qui ne peuvent plus utiliser une fenêtre d'information pour tenter de décoder. On peut ainsi se prémunir des attaques par décodage en utilisant une clé publique de faible taille. Dans cette optique, nous présentons un cryptosystème à clé publique basé sur le problème de reconstruction de polynômes linéaires. Nous montrons que notre système est rapide, utilise des clés de taille raisonnable, et résiste à toutes les attaques connues dans l'état de l'art.

Depuis 20 ans, l'information quantique a profondément changé notre façon d'appréhender la physique atomique, ainsi que la nature des ressources utiles au calcul. Cette thèse aborde trois aspects relatifs à l'information quantique: - Le phénomène de décohérence -- responsable de la transition quantique-classique -- est décrit quantitativement grâce à l'analyse de l'information mutuelle entre deux systèmes quantiques ; - Une nouvelle classe de codes correcteurs d'erreurs quantiques -- les codes convolutifs -- est introduite en detail et il est montré qu'elle partage les propriétés des codes convolutifs classiques (codage et décodage en ligne, algorithme efficace d'estimation d'erreurs au maximum de vraisemblance, existence de condition nécessaire et suffisante pour l'absence d'erreur catastrophique, etc.) ; - Quelques propositions expérimentales de manipulation d'information quantique sont décrites (porte de Toffoli et clonage universel pour l'électrodynamique quantique en cavité).

Nous proposons et développons un modèle original de mémoires associatives s'appuyant sur des réseaux de neurones codés. Les mémoires associatives sont des dispositifs capables d'apprendre des messages binaires puis de les reproduire à partir de fractions de leurs contenus. L'état de l'art est le réseau proposé par Hopfield, dont la diversité de mémorisation - le nombre de messages qu'il peut n mémoriser - est inférieure à 2 log(n) où n est le nombre de neurones dans le réseau. Notre travail a consisté à tirer parti des techniques de codage et de déco- dage correcteur d'erreur, plus précisément celle des codes distribués, afin d'ac- croître considérablement les performances des mémoires associatives. Pour ce faire, nous avons introduit des codes originaux dont les mots de code sont portés par des cliques neurales. Nous montrons que, combinées à des codes locaux par- cimonieux, ces cliques neurales offrent une diversité d'apprentissage qui évolue comme le carré du nombre de neurones. Les gains observés viennent de l'utilisation de la parcimonie à plusieurs é- chelles : d'une part les messages appris sont de longueur bien inférieure à n, d'autre part ils n'utilisent qu'une partie du matériel disponible, que ce soit au niveau des neurones ou de leurs connexions. L'apprentissage est donc localisé, au contraire des réseaux de Hopfield. De plus, ces mémoires bénéficient d'une efficacité - rapport du nombre de bits appris au nombre de bits utilisés - presque maximale. Elles se présentent donc comme une alternative intéressante aux mé- moires indexées classiques. Au delà de l'aspect quantitatif, le modèle que nous proposons offre une plau- sibilité biologique fortement accrue par rapport au modèle de Hopfield. Les con- cepts de cliques neurales, de winner take all, ou encore de synchronisation tem- porelle que ce modèle exploite rejoignent les observations récentes rapportées par la littérature neurobiologique. Par ailleurs, elles pourraient ouvrir la voie à la conception de machines cognitives capables de croiser des informations pour en produire de nouvelles car les cliques neurales sont recouvrantes, par leurs som- mets ou par leurs arêtes.

Dans la plupart des entreprises de fabrication mécanique, le réglage des machines-outils est une tâche déléguée au régleur qui cherche à garantir les tolérances. Cela a pour conséquence d'augmenter le temps de réglage pour une qualité qui n'est pas au niveau souhaité. Au cours de ces six dernières années, le laboratoire SYMME a élaboré des méthodes de pilotage (Copilot-Pro®et Pilotage inertiel) pour résoudre le problème de réglage des machines-outils. Fondés sur ces deux méthodes, les travaux présentés en font une synthèse et présentent des nouvelles avancées dans le pilotage de commande numériques afin d'obtenir la meilleure qualité possible quelle que soit la complexité de la pièce. L'apport de ce travail est présenté en cinq chapitres. Le premier chapitre présente le contexte général des travaux de recherche et fait un état de l'art des travaux existants, d'une part sur le pilotage et d'autre part sur la conformité. Le pilotage consiste à réduire la variabilité autour de la cible des produits et la conformité consiste à s'assurer que la dispersion d'une caractéristique est contenue dans l'intervalle de tolérance de celle-ci. Le second chapitre revient sur les méthodes de pilotage qui consistent à établir les relations entre les caractéristiques de la pièce et les correcteurs et propose dessolutions pour améliorer le calcul de la correction en tenant compte à la fois des tolérances et des nombres de points palpés sur les surfaces de la pièce. Le troisième chapitre présente les stratégies de pilotage et met en évidence les limites des méthodes classiques de détection des situations hors contrôle qui sont la carte de contrôle de Shewhart et la carte T² de Hotelling. Le quatrième chapitre fait une synthèse des méthodologies pour faciliter le déploiement des méthodes dans l'industrie. Le cinquième chapitre présente une application expérimentale du pilotage inertiel et un témoignage de l'utilisation du pilotage matriciel dans une entreprise d'horlogerie. Une conclusion rappelle les principaux apports de ce travail.

Mass., Massachusetts Inst. of Technology, Diss.--Cambridge, 2001. / Literaturverz. S. [337] - 347.

Thèse (Ph. D.)--Université Laval, 2008. / Bibliogr.: f. [130]-144. Publié aussi en version électronique dans la Collection Mémoires et thèses électroniques.

Dans la plupart des entreprises de fabrication mécanique, le réglage des machines-outils est une tâche déléguée au régleur qui cherche à garantir les tolérances. Cela a pour conséquence d’augmenter le temps de réglage pour une qualité qui n’est pas au niveau souhaité. Au cours de ces six dernières années, le laboratoire SYMME a élaboré des méthodes de pilotage (Copilot-Pro®et Pilotage inertiel) pour résoudre le problème de réglage des machines-outils. Fondés sur ces deux méthodes, les travaux présentés en font une synthèse et présentent des nouvelles avancées dans le pilotage de commande numériques afin d’obtenir la meilleure qualité possible quelle que soit la complexité de la pièce. L’apport de ce travail est présenté en cinq chapitres. Le premier chapitre présente le contexte général des travaux de recherche et fait un état de l'art des travaux existants, d’une part sur le pilotage et d’autre part sur la conformité. Le pilotage consiste à réduire la variabilité autour de la cible des produits et la conformité consiste à s'assurer que la dispersion d'une caractéristique est contenue dans l'intervalle de tolérance de celle-ci. Le second chapitre revient sur les méthodes de pilotage qui consistent à établir les relations entre les caractéristiques de la pièce et les correcteurs et propose dessolutions pour améliorer le calcul de la correction en tenant compte à la fois des tolérances et des nombres de points palpés sur les surfaces de la pièce. Le troisième chapitre présente les stratégies de pilotage et met en évidence les limites des méthodes classiques de détection des situations hors contrôle qui sont la carte de contrôle de Shewhart et la carte T² de Hotelling. Le quatrième chapitre fait une synthèse des méthodologies pour faciliter le déploiement des méthodes dans l’industrie. Le cinquième chapitre présente une application expérimentale du pilotage inertiel et un témoignage de l'utilisation du pilotage matriciel dans une entreprise d'horlogerie. Une conclusion rappelle les principaux apports de ce travail. / In most mechanical manufacturing companies, setting machine-tools is a task delegated to the setter who seeks to ensure tolerances. This has the consequence of increasing the adjustment time with a quality that is not at the desired level. Over the past six years, the SYMME laboratory has developed steering methods (Copilot -Pro ® and inertial steering) to solve the problem of setting machine tools. Based on these methods, the works presented make a synthesis and presents new advances in steering of digital controls (CNC) to obtain the best quality regardless of the complexity of the part. The contribution of this workis presented in five chapters. The first chapter presents the general context of the research and makes a state of the art of existing works, on the one hand on the steering and on the other hand on the conformity. The steering consists in reducing the variability around the target products and the conformity consists in verifyingthat the dispersion of a characteristic is inside its tolerance interval. The second chapter discusses the methods of steering which consist in establishing the relationship between the characteristics of the workpiece and thetool-offsets and propose solutions to improve the calculation of the correction taking into account both tolerances and number of points probed on the surfaces of the workpiece. The third chapter presents the steering strategies and highlights the limitations of conventional methods for detecting out of control situations which are the Shewhart's control card and the T² Hotelling’s card. The fourth chapter is a synthesis of methodologies to facilitate the deployment of the methods in the industry. The fifth chapter presents an experimental application of inertial steering and a debriefing on the matrix steering used in a watch manufacturer company. Conclusion reiterates the main contributions of this work

De nos jours, l’architecture du réseau mobile est en pleine évolution pour assurer la montée en débit entre les Centraux (CO) (réseaux coeurs) et différents terminaux comme les mobiles, ordinateurs, tablettes afin de satisfaire les utilisateurs. Pour faire face à ces défis du futur, le réseau C-RAN (Cloud ou Centralized-RAN) est connu comme une solution de la 5G. Dans le contexte C-RAN, toutes les BBUs (Base Band Units) sont centralisées dans le CO, seules les RRH (Remote Radio Head) restent situées à la tête de la station de base (BS). Un nouveau segment entre les BBUs et RRHs apparait nommé « fronthaul ». Il est basé sur des transmissions D-ROF (digital radio-overfiber) et transporte le signal radio numérique à un débit binaire élevé en utilisant le protocole CPRI (Common Public Radio Interface). En prenant en compte le CAPEX et l’OPEX, le projet ANR LAMPION a proposé la technologie RSOA (Reflective Semiconductor Optical Amplifier) auto alimenté afin de rendre la solution plus flexible et s’affranchir d’émetteurs/récepteurs colorés dans le cadre de transmission WDM-PON (Wavelength Division Multiplexing Passive Optical Network). Néanmoins, il est nécessaire d’ajouter un FEC (forward error corrector) dans la transmission pour assurer la qualité de service. Donc l’objectif de cette thèse est de trouver le FEC le plus adéquat à appliquer dans le contexte C-RAN. Nos travaux se sont focalisés sur l’utilisation de codes LDPC, choisis après comparaisons des performances avec les autres types de codes. Nous avons précisé les paramètres (rendement du code, taille de la matrice, cycle, etc.) nécessaires pour les codes LDPC afin d'obtenir les meilleures performances. Les algorithmes LDPC à décisions dures ont été choisis après considération du compromis entre complexités de circuit et performance. Parmi ces algorithmes à décision dures, le GDBF (gradient descent bit-flipping) était la meilleure solution. La prise en compte d’un CAN 2-Bit dans le canal nous a amené à proposer une variante : le BWGDBF (Balanced weighted GDBF). Des optimisations ont également été faites en regard de la convergence de l'algorithme et de la latence. Enfin, nous avons réussi à implémenter notre propre algorithme sur le FPGA Spartan 6 xc6slx16. Plusieurs méthodes ont été proposées pour atteindre une latence de 5 μs souhaitée dans le contexte C-RAN. Cette thèse a été soutenue par le projet ANR LAMPION (Lambada-based Access and Metropolitan Passive Optical networks). / Nowadays, the architecture of the mobile network is in full evolution to ensure the increase in terms of bit rate between the Central (CO) (core networks) and various terminals such as mobiles, computers, tablets in order to satisfy the users. To address these challenges of the future, the C-RAN (Cloud or Centralized-RAN) network is known as a 5G solution. In the C-RAN context, all BBUs (Base Band Units) are centralized in the CO, only the RRH (Remote Radio Head) remain at the head of the base station (BS). A new segment between BBUs and RRHs appears called "fronthaul". It is based on D-ROF (digital radio-overfiber) transmissions and carries the digital radio signal at a high bit rate using the Common Public Radio Interface (CPRI) protocol. Taking into account CAPEX and OPEX, the ANR LAMPION project has proposed the Self-seeded Reflective Semiconductor Optical Amplifier (RSOA) technology in order to make the solution more flexible and overcome the need for colored transmitters / receivers in the context of PON-WDM (Wavelength Division Multiplexing Passive Optical Network). Nevertheless, it is necessary to add a FEC (forward error corrector) in the transmission to ensure the quality of service. So the objective of this thesis is to find the most suitable FEC to apply in the C-RAN context. Our work has focused on the use of LDPC codes, chosen after performance comparisons with other types of codes. We have specified the parameters (code performance, matrix size, cycle, etc.) required for LDPC codes to obtain the best performance. Hard-decision LDPC algorithms were chosen after considering the tradeoff between circuit complexities and performance. Among these hard-decision algorithms, the GDBF (gradient descent bit-flipping) was the best solution. Taking into account a CAN 2-Bit in the channel led us to propose a variant: the BWGDBF (Balanced weighted GDBF). Optimizations have also been made with respect to the convergence of the algorithm and latency. Finally, we managed to implement our own algorithm on the Spartan FPGA 6 xc6slx16. Several methods have been proposed to achieve a latency of 5 μs desired in the C-RAN context. This thesis was supported by the project ANR LAMPION (Lambada-based Access and Metropolitan Passive Optical Networks).

Cette thèse aborde différents aspects de la cryptologie, subsumant des champs aussi variés que la conception de protocoles, l’amélioration d’outils algorithmiques et les attaques. Les deux principales focales de cette étude sont : un protocole de co-signature prouvé irréfragable et un système de chiffrement authentifié à sécurité prouvée. Notre protocole de co-signature permet l’équité légale. L’équité légale est une nouvelle variante de la notion d’équité, ne reposant pas sur des tiers. Notre instanciation d’équité légale est construite à l’aide des signatures de Schnorr. Nous présenterons également un protocole d’authentification distribué de type Fiat-Shamir. La deuxième partie de cette thèse est consacrée aux améliorations algorithmiques. Nous introduisons une méthode permettant de doubler la vitesse de l’algorithme de Barrett en utilisant des modules composites spécifiques et un nouvel algorithme de multiplication à retour sur trace, particulièrement adapté aux microprocesseurs bon marché. Nous nous intéresserons ensuite à la sécurité des composants en étudiant la régulation du débit des correcteurs de von Neumann et les attaques en fautes sur des implémentations de cryptographie à courbes elliptiques. Enfin, un des actes novatoires incidents notre travail sera d’adapter aux codes correcteurs d’erreurs deux techniques empruntées à la cryptographie : un premier résultat améliore l’efficacité calculatoire des codes BCH grâce à une version de l’algorithme de Barrett étendue aux polynômes. Le second est un nouveau code correcteur d’erreurs basé sur la théorie des nombres. / This thesis addresses various topics in cryptology, namely protocol design, algorithmic improvements and attacks. In addition, we venture out of cryptography and propose two new applications of cryptographic techniques to error correcting codes. Our main results comprise a provably secure co-signature protocol and a provably secure authenticated encryption scheme. Our co-signature protocol achieves legal fairness, a novel fairness variant that does not rely on third parties. Legal fairness is implemented using Schnorr signatures. We also present a distributed Fiat-Shamir authentication protocol. The second part of the thesis is devoted to computational improvements, we discuss a method for doubling the speed of Barrett’s algorithm by using specific composite moduli, devise new BCH speed-up strategies using polynomial extensions of Barrett’s algorithm, describe a new backtracking-based multiplication algorithm suited for lightweight microprocessors and present a new number theoretic error-correcting code. Fault injection attacks are further overviewed and a new fault attack on ECC implementations is proposed.