Décodage en liste et application à la sécurité de l'information - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Thèse Année : 2011

List Decoding and application to information security

Décodage en liste et application à la sécurité de l'information

Morgan Barbier

Résumé

This thesis studies some aspects of error-correcting codes and their applications to information security. We focused more specifically on the maximum-likelyhood and list decoding problems. A new notion was proposed by relating a code family and a decoding algorithm, thus underlining the codes for which the maximum-likelyhood decoding problem is solvable in polynomial time. We then present an alternative formulation of Koetter and Vardy's decoding algorithm for alternant codes and study its complexity. Using this method, we were able to introduce a key size reduction for the McEliece cryptosystem, leading to a gain of up to 21\% for the dyadic variant. We were also interested in code-based steganography. We proposed several bounds to characterize stegosystems using linear codes, ensuring that the embedding problem with locked positions is always solvable. One of these bounds shows that the lower the MDS rank of the used code is, the more efficient a stegosystem relying on this code will be. Moreover, we proved that non-linear systematic codes are also candidates. Finally, we reformulated the bounded embedding problem with locked positions so as to always obtain a solution, and showed that binary Hamming codes satisfy all exhibited constraints.
Cette thèse porte sur l'étude de certains aspects des codes correcteurs d'erreurs et leurs applications à la sécurité de l'information. Plus spécifiquement, on s'est intéressé aux problèmes de décodage complet et de décodage en liste. Une nouvelle notion de codes a été introduite en liant une famille de codes et un algorithme de décodage, mettant ainsi en évidence les codes pour lesquels le décodage complet est réalisable en un temps polynomial. On présente ensuite une reformulation de l'algorithme de Koetter et Vardy pour le décodage en liste pour les codes alternant et analysons sa complexité. Cette méthode a permit de présenter une réduction de la taille de la clé du cryptosystème de McEliece, allant jusqu'à 21\% pour la variante dyadique. On s'est également intéressé à la stéganographie basée sur les codes. On propose différentes bornes caractérisant les stégosystèmes utilisant des codes linéaires, de façon à assurer la solvabilité du problème d'insertion avec des positions verrouillées. Une de ces bornes permet d'affirmer que plus le rang MDS du code utilisé est bas, plus ce code permettra de concevoir un stégosystème efficace. On montre également que les codes non-linéaires systématiques sont également de bons candidats. Enfin, on reformule le problème d'insertion bornée avec des positions verrouillées rendant ainsi l'insertion toujours possible, et on démontre que les codes de Hamming binaires permettent de satisfaire à toutes les contraintes exhibées.
Fichier principal
Vignette du fichier
these.pdf (1.2 Mo) Télécharger le fichier
Loading...

Dates et versions

pastel-00677421 , version 1 (08-03-2012)

Identifiants

  • HAL Id : pastel-00677421 , version 1

Citer

Morgan Barbier. Décodage en liste et application à la sécurité de l'information. Cryptographie et sécurité [cs.CR]. Ecole Polytechnique X, 2011. Français. ⟨NNT : ⟩. ⟨pastel-00677421⟩
719 Consultations
1621 Téléchargements

Partager

Gmail Facebook X LinkedIn More