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 metadatas

Cited literature [82 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/pastel-00677421
Contributor : Morgan Barbier <>
Submitted on : Thursday, March 8, 2012 - 11:45:09 AM
Last modification on : Wednesday, March 27, 2019 - 4:41:29 PM
Long-term archiving on : Monday, November 26, 2012 - 10:31:02 AM

Identifiers

  • HAL Id : pastel-00677421, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

856

Files downloads

1363