Décodage par liste des codes de Reed-Muller et application à la cryptanalyse

Collection

Informatique

Citer ce document

Fourquet, Rafaël, “Décodage par liste des codes de Reed-Muller et application à la cryptanalyse,” Bibliothèque numérique Paris 8, consulté le 29 mars 2024, https://octaviana.fr/document/185167993.

À propos

Les codes de Reed-Muller sont des codes historiquement importants pour la correction d'erreurs, et il existe depuis longtemps des algorithmes de décodage efficaces. La thèse traite du "décodage par liste" de ces codes au delà du cadre strict de la communication d'information. Les codes de Reed-Muller ont un lien étroit avec les fonctions booléennes. Celles-ci sont utilisées dans de nombreux systèmes de chiffrement, ce qui rend ces algorithmes de décodage applicables au domaine cryptographique. Le modèle est alors différent: on ne suppose plus que les erreurs sont aléatoires. L'algorithme doit alors être plus robuste, car il doit être capable de corriger des erreurs dont la répartition est arbitraire, comme celles produites par un "adversaire". Les algorithmes présentés dans la thèse correspondent à ce modèle. Ils sont dans la lignée des algorithmes de Kabatiansky-Tavernier pour les ordres un (2004) et deux (2005). Ceux-ci peuvent être déterministes ou probabilistes. Les premiers sont infaillibles (sous certaines conditions), et sont donc particulièrement adaptés à l'étude des fonctions booléennes; ils permettent par exemple d'en calculer la non-linéarité, qui est un paramètre important de résistance cryptographique. Cependant, en raison de leur complexité élevée, ces algorithmes déterministes ne s'appliquent qu'aux codes de petite longueur. Les versions probabilistes prennent alors le relais et corrigent la plupart des erreurs même dans le modèle adversaire. On présente des techniques permettant d'appliquer ces algorithmes probabilistes à la cryptanalyse de certains systèmes de chiffrement par blocs, comme le DES.

Reed-Muller codes are historically important error correcting codes, for which good decoding algorithms were known for a long time. List decoding of these codes is the subject of this thesis, Reed-Muller codes are closely related to Boolean functions, which are themselves widely used in encryption systems, so these decoding algorithm are also useful in cryptography. However, in this case, the settings are different: one can no longer assume that the "errors" are random. Then the algorithm has to be more robust, to be able to correct arbitrary error patterns, for example errors produced by an "adversary". The algorithms shown in this thesis correspond to this setting. They can be either "determinist" or "probabilist". Determinist algorithms are very powerful, as in certain conditions they cannot fail. This property makes them particularly well suited for the study of Boolean functions (for example, they can be used to determine the non-linearity of these functions, which is an important parameter in cryptography). However, because of their high complexity, they can be applied only to a limited class of codes (the "small" ones). On the other hand, probabilist algorithms can be used for much larger codes. Decoding failure is possible, but "most" errors must be corrected, even in the cryptographic setting. We show in this thesis some techniques to apply the probabilist algorithms to the cryptanalysis of a certain class of cryptographic systems (for example the DES).

Sujets

Codes de Reed-Muller Cryptographie Codage

Auteur

Fourquet, Rafaël

Collaborateur

Sarlet, Claude (sous la direction de)

Source

Paris 8, BU - Saint-Denis, Magasin 2, TH3687

Date

2011

Identifiant

185167993

N° national de thèse

2011PA084061

Droits d'accès

Accessible à tous

Conditions d'utilisation

Toute reproduction même partielle est interdite sans accord exprès de l'auteur

Discipline (Thèse)

Informatique

Domaine (Dewey)

004 Traitement des données. Informatique. Généralités. Dictionnaires