Skip to Main content Skip to Navigation

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

Morgan Barbier 1 
1 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : 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.
Complete list of metadata

Cited literature [82 references]  Display  Hide  Download
Contributor : Morgan Barbier Connect in order to contact the contributor
Submitted on : Thursday, March 8, 2012 - 11:45:09 AM
Last modification on : Friday, February 4, 2022 - 3:16:11 AM
Long-term archiving on: : Monday, November 26, 2012 - 10:31:02 AM


  • HAL Id : pastel-00677421, version 1



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. ⟨pastel-00677421⟩



Record views


Files downloads