Algebraic codes to protect digital information
Vincent Herbert (Inria Rocquencourt)
Thursday 3 May 2012, 15.00, b-it 1.25 (cosec meeting room)
Error-correcting codes are used to reconstitute digital data, which are proned to alterations during their storage and their transport. They can also be employed in cryptography. These different aspects are adressed in this talk. First of all, we study the class of cyclic codes defined by the zero set {1, 2i + 1, 2j + 1}, where i and j are distinct positive integers. We focus on the characterization of three-error correcting codes in this class as well as the weight distribution of these codes. We improve the Schaub algorithm, which gives a lower bound on the minimum distance of cyclic codes. We implement this algorithm to compute the spectral immunity of Boolean functions. This quantity is related with the minimum distance of cyclic codes and is important to guarantee the security of certain stream ciphers. Subse quently, we propose a solution to speed up the polynomial roots computation over finite fields of characterisitic two. This computation is the slowest step during the decoding of McEliece-type cryptosystems based on classical binary Goppa codes. We provide a complexity analysis of the underlying algorithm named BTZ.