Thesis (Ph. D.)--Auburn University, 2009. / Abstract. Includes bibliographical references (p. 51-52).

Les travaux de cette thèse portent sur la cryptanalyse d'un système de chiffrement simple, mais important : le registre filtré. Ils concernent les deux principales familles d'attaques que sont les attaques algébriques et les attaques probabilistes. Pour les attaques algébriques, il est important de pouvoir calculer efficacement l'immunité algèbrique de la fonction booléenne par laquelle le registre est filtré. Cette quantité est intimement liée au comportement des codes de Reed-Muller sur le canal à effacements et son étude a permis la découverte de plusieurs résultats qui s'expriment naturellement dans le cadre de la théorie des codes correcteurs. Nous avons ainsi construit une nouvelle borne sur la probabilité de pouvoir compenser un nombre d'effacements fixé. Cette borne montre que l'immunité algébrique d'une fonction booléenne aléatoire est presque toujours maximale. Nous avons également explicité une méthode de décodage fondée sur des algorithmes d'algèbre linéaire creuse (comme l'algorithme de Wiedemann) qui donne un des algorithmes les plus efficace pour calculer l'immunité algébrique. Pour les attaques probabilistes, un outil très important est de parvenir à trouver efficacement de nombreux multiples de poids faible du registre à décalage du système. Un nouvel algorithme fondé sur les logarithmes discrets à été proposé. Il est particulièrement interessant pour les multiples de poids 4, améliorant dans de nombreux cas pratiques le meilleur algorithme connu. Ce travail s'est poursuivi par une nouvelle cryptanalyse probabiliste du registre filtré qui utilise ces multiples de poids faible pour reconnaître les entrées nulles de la fonction de filtrage. Cette attaque est l'une des plus efficaces connue à l'heure actuelle.

No description available.

Parmi les différents critères qu'une fonction booléenne doit satisfaire en cryptographie, on s'intéresse à la non-linéarité. Pour une fonction booléenne donnée, cette notion mesure la distance de Hamming qui la sépare des fonctions de degré au plus 1. C'est un critère naturel pour évaluer la complexité d'une fonction cryptographique, celle-ci ne devant pas admettreune approximation qui soit simple, comme par une fonction de degré 1, ou plus généralement une fonction de bas degré. Ainsi, il est important de considérer plus généralement, la non-linéarité d'ordre supérieur, qui pour un ordre donné r, mesure la distance d'une fonction donnée à l'ensemble des fonctions de degré au plus r. Cette notion est également importante pour les fonctions vectorielles, i.e., celles à plusieurs sorties. Quand le nombre de variables est grand, presque toutes les fonctions ont une non-linéarité (d'ordre 1) voisine d'une certaine valeur, assez élevée. Dans un premier travail, on étend ce résultat à l'ordre 2. Cette méthode qui consiste à observer comment les boules de Hamming recouvrent l'hypercube des fonctions booléennes, nous conduit naturellement vers une borne de décodage théorique des codes de Reed-Muller d'ordre 1, coïncidant au même endroit où se concentre la non-linéarité de presque toutes les fonctions ; une approche nouvelle pour un résultat pas entièrement nouveau. On étudie aussi la non-linéarité des fonctions vectorielles. On montre avec une approche différente, que le comportement asymptotique est le même que celui des fonctions booléennes: une concentration de la non-linéarité autour d'une valeur assez élevée. / Among the different criteria that a Boolean function must satisfy in symmetric cryptography, we focus on the nonlinearity of these. This notion measures the Hamming distance between a given function and the set of functions with degree at most 1. It is a natural criterion to evaluate the complexity of a cryptographic function that must not have a simple approximation as by a function of degree 1, or more generally, a function of low degree. Hence, it is important to consider the higher order nonlinearity, which for a given order r, measures the distance between a given function and the set of all functions of degree at most r. This notion is equally important for multi-output Boolean functions. When the number of variables is large enough, almost all Boolean functions have nonlinearities lying in a small neighbourhood of a certain high value. We prove that this fact holds when considering the second-order nonlinearity. Our method which consists in observing how the Hamming balls pack the hypercube of Boolean functions led quite naturally to a theoretical decoding bound for the first-order Reed-Muller code, coinciding with the concentration point of the nonlinearity of almost all functions. This was a new approach for a result which is not entirely new. We also studied the nonlinearity of multi-output functions. We proved with a different approach, that the asymptotic behaviour of multi-output functions is the same as the single-output ones: a concentration of the nonlinearity around a certain large value.

In this thesis some families of linear error correcting codes are presented. The reader will find a general description of binary codes and more specific details about linear codes such as Hamming, repetition codes, Reed-Muller codes, etc. To fully immerse ourselves in the methods of coding and decoding, we will introduce examples in order to contribute to the understanding of the theories.   In these times of much communication through computer technology, our daily lives involve a substantial amount of data transmission. It is essential that these data are transmitted without errors through the communication channels. Therefore, the scientific field of error-correcting codes holds a significant importance in many aspects of todays society.   The main goal of this thesis is to study linear block codes which belong to the class of binary codes. In this case we will attribute a more prominent role to first order Reed-Muller codes. / I den här uppsatsen kommer flera varianter av linjära felrättande koder att presenteras. Läsaren får ta del av en allmän beskrivning av binära koder och en mer detaljerad framställning av linjära koder så som Hamming, repetitionskod, Reed-Muller kod m.m. Tillsammans med en fördjupning i ämnet, avseende metoder för kodning och avkodning, kommer vi att ge exempel för att bidra till förståelsen.   Den digitala eran, som vi lever i, innefattar att datatransmission är en del av vår vardag. Vår frekventa användning av mobila enheter visar på hur viktigt det är att data överförs korrekt via kommunikationskanalerna. Av den anledningen är vetenskapen om felrättande koder högaktuell i dagens samhälle.   Det huvudsakliga syftet med uppsatsen är att studera linjära block-koder som tillhör klassen binära koder. I det här fallet kommer vi att fokusera lite extra på Reed-Muller koder av första ordningen.

Dans cette thèse, nous étudions les codes de Reed-Muller qui constituent une des familles de codes correcteurs les plus étudiées, et les plus utilisées dans la transmission des communications numériques. Grâce à leur rapidité d'encodage et de décodage, ils furent notamment utilisés pour les transmissions satellitaires. Ils ont également un lien très fort avec les notions de fonctions booléennes. L'étude de ces dernières constitue le coeur de la réalisation et de la sécurité des systèmes de chiffrement à clé secrète, tant par blocs que par flot. Depuis l'introduction de ces codes, de très nombreux algorithmes de décodage virent le jour, et aujourd'hui encore étudier leur structure afin de construire des algorithmes de décodage constitue un fructueux domaine de recherche. Ces algorithmes de décodage peuvent être utilisés dans l'étude de la structure de systèmes de chiffrement à clé secrète. Nous exposons un point de vue unificateur à l'ensemble des algorithmes de décodage des codes de Reed-Muller, ce point de vue étant celui de la dérivée discrète. Nous exposons un algorithme performant pour le décodage des codes d'ordre deux, que nous analysons ensuite. Nous discutons les résultats de simulations des algorithmes étudiés pour les petites et moyennes longueurs de code. Ces résultats montrent que l'algorithme proposé décode beaucoup plus loin en pratique que les autres algorithmes.

Solutions to the problem of large peak to average power ratio (PAPR) in orthogonal frequency division multiplexing (OFDM) systems are proposed. Although the design of PAPR reduction codewords has been extensively studied and the existence of asymptotically good codes with low PAPR has been proved, still no reduced PAPR capacity achieving code has been constructed. This is the topic of the current thesis.This goal is achieved by implementing a time-frequency turbo block coded OFDM. In this scheme, we design the frequency domain component code to have a PAPR bounded by a small number. The time domain component code is designed to obtain good performance while the decoding algorithm has reasonable complexity. Through comparative numerical evaluation we show that our method achieves considerable improvement in terms of PAPR with slight performance degradation compared to capacity achieving codes with similar block lengths. For the frequency domain component code, we used the realization of Golay sequences as cosets of the fi rst order Reed-Muller code and the modi cation of dual BCH code. A simple MAP decoding algorithm for the modi ed dual BCH code is also provided. Finally, we provide a flexible and practical scheme based on probabilistic approach to a PAPR problem. This approach decreases the PAPR without any signi cant performance loss and without any adverse impact or required change to the system. / Engineering and Applied Sciences

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / In this work we present the determination of the second Hamming weight of generalized Reed- Muller codes in most cases (see Teorema 4.6). Our main reference is [13], although we have also used results from [3] and [5]. In the first chapter we describe finite fields e we show how they can be constructed. In chapter 2 we present the basics of coding theory. We define what are error correcting codes, the Hamming metric, the parameters of a code, the equivalence of codes through the concept of isometry, and we briefly present generalized Reed-Muller codes and their parameters. In chapter 3 we present some results from Grobner bases theory and the definition of Affine Cartesian codes, which generalize the generalized Reed-Muller codes. we use tools from Grobner bases theory to determine the dimension and the minimum distance of Affine Cartesian codes. We finish our work in chapter 4, with the determination of the second Hamming weight for generalized Reed-Muller codes in most cases. / Nesse trabalho apresentamos o cálculo do segundo peso de Hamming de códigos de Reed-Muller generalizados na maioria dos casos (v. Teorema 4.6). Nossa referência principal sera [13], embora tenhamos utilizado também resultados de [3] e [5]. No primeiro capítulo descrevemos os corpos finitos e mostramos como podem ser construídos. No capítulo 2 apresentamos os conceitos básicos da teoria de códigos. Nele, definimos o que são os códigos corretores de erros, a métrica de Hamming, os parâmetros de um código, a equivalência de códigos através da noção de isometria, bem como uma breve apresentação dos códigos de Reed-Muller generalizados e seus parâmetros. No capítulo 3 sao apresentados alguns resultados da teoria de Bases de Grobner e a definição dos Códigos Cartesianos Afins, que são uma generalização dos códigos de Reed-Muller generalizados. Usamos ferramentas da teoria de bases de Grobner para determinar a dimensão e distância mínima de Códigos Cartesianos Afins. Para finalizar nosso trabalho, no capítulo 4 determinamos o segundo peso de Hamming do Código de Reed-Muller generalizado na maioria dos casos. / Mestre em Matemática

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.

<p>En säker informationskanal med hög överföringskvalitet krävs i dessa dagar när informationsöverföringen ökar för varje år som går. Det finns olika sätt att skapa detta. Antingen genom att se till att överföringsmediet är av mycket hög kvalitet eller att skapa en skyddsmekanism som gör att de överföringsfel som kan uppstå kan detekteras och även korrigeras om man önskar detta. Denna uppsats handlar om detta, att kunna detektera och korrigera fel. Denna gren inom matematiken kallas kodningsteori.</p><p>Uppsatsen presenterar grunden för kodningsteorin, för att sedan presentera några vanligt förekommande kodningsalgoritmer, Hamming koder, BCH koder, Reed-Solomon. Jag går in på djupet av en av de absolut äldsta kodningsalgoritmerna, en kod som presenterades 1954 av David E. Muller, något senare presenterade en annan föregångare inom kodningsteori, Irving S. Reed, en avkodningsalgoritm för Mullers kod. Denna kod blev känd under namnet Reed-Muller kod.</p><p>Jag presenterar teorin bakom Reed-Muller kod och hur ett Reed-Muller kodord skapas med hjälp av teorin. Jag visar också hur man avkodar Reed-Muller kod med hjälp av olika algoritmer där Irving S. Reeds algoritm står i centrum. För att testa kodning och avkodning i simulerad verklighet används datorprogrammet Matlab. Slutligen presenteras hur kodnings- och avkodningsalgoritmer kan skapas med hjälp av grindnät.</p>