Skip to Main content Skip to Navigation

Codes de Reed-Muller et cryptanalyse du registre filtré.

Abstract : This thesis deals with the cryptanalysis of a simple but important stream cipher: the filter generator. A first approach to break such cipher is to use algebraic attacks. For these attacks, it is important to compute efficiently the algebraic immunity of the Boolean function used as a filter. This quantity is closely related to the behavior of Reed-Muller codes over the erasure channel. Using this relation, we discovered new results that are best stated in the error correcting codes framework. We thus build a new bound on the probability to be able to correct a fixed number of erasures. This bound implies that the algebraic immunity of a random function is optimal or close from it. We also detail a new decoding method based on sparse linear algebra algorithm like Wiedemann's one. It leads to one of the most efficient algorithm to compute the algebraic immunity of a given function. A second approach is to use probabilistic attacks. For most of them, we need to compute small weight multiples of the LFSR. We propose a new algorithm that use discrete logarithm and is particularly efficient for multiples of weight 4. We then describe a new attack that use these multiples to detect the time positions for which the inputs of the filter are all zero. At the time being, this attack is one of the most efficient.
Document type :
Complete list of metadatas
Contributor : Ecole Polytechnique <>
Submitted on : Friday, July 23, 2010 - 2:16:17 PM
Last modification on : Friday, May 25, 2018 - 12:02:05 PM
Document(s) archivé(s) le : Monday, October 25, 2010 - 11:20:28 AM


  • HAL Id : pastel-00003579, version 1



Frédéric Didier. Codes de Reed-Muller et cryptanalyse du registre filtré.. Informatique [cs]. Ecole Polytechnique X, 2007. Français. ⟨pastel-00003579⟩



Record views


Files downloads