Decoding of Reed-Muller codes and applications to cryptography. - Archive ouverte HAL Access content directly
Theses Year : 2007

Decoding of Reed-Muller codes and applications to cryptography.

Etude du décodage des codes de Reed-Muller et application à la cryptographie.

(1)
1

Abstract

In this thesis, we study the Reed-Muller codes which constitute one of the classes of error correcting codes the most studied, and most used in numerical communications. Thanks to their speed of encoding and decoding, they were in particular used for the satellite transmissions. They also have a strong bond with the concepts of Boolean functions. The study of Boolean functions constitutes the heart of the realization and the safety of secret key cryptography. Since the introduction of these codes, many decoding algorithms were introduced, and even today the study of their structure! in order to build decoding algorithms constitutes an interested field of research in coding theory and in cryptography for finding good linear, quadratic etc approximations to Boolean functions used in cryptography We expose a unifying point of view to all known decoding algorithms of this codes, this point of view is that of the discrete derivative. We expose a powerful algorithm for the decoding of the codes of order two, which we analyze then. We discuss the results of simulations of the algorithms studied for the small and average lengths of code. Simulation results show that the proposed algorithm decodes in practice much further that the other algorithms.
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.
Fichier principal
Vignette du fichier
Sakkour.pdf (1.1 Mo) Télécharger le fichier

Dates and versions

pastel-00002412 , version 1 (28-07-2010)

Identifiers

  • HAL Id : pastel-00002412 , version 1

Cite

Bassem Sakkour. Etude du décodage des codes de Reed-Muller et application à la cryptographie.. Informatique [cs]. Ecole Polytechnique X, 2007. Français. ⟨NNT : ⟩. ⟨pastel-00002412⟩
704 View
265 Download

Share

Gmail Facebook Twitter LinkedIn More