Technical Program

Paper Detail

Paper Title Speeding up decoding a code with a non-trivial automorphism group up to an exponential factor
Paper IdentifierTH1.R9.4
Authors Rodolfo Canto-Torres, Jean-Pierre Tillich, INRIA, France
Session Algebraic Coding Theory
Location Pontoise, Level 5
Session Time Thursday, 11 July, 09:50 - 11:10
Presentation Time Thursday, 11 July, 10:50 - 11:10
Manuscript  Click here to download the manuscript
Abstract We give an algorithm that is able to speed up the decoding of a code with a non-trivial automorphism group, by summing for the word that has to be decoded, all its entries belonging to a same orbit and decoding the resulting word in a reduced code. For a certain range of parameters, this results in a decoding that is faster by an exponential factor in the codelength when compared to the best algorithms for decoding generic linear codes. This algorithm is then used to break several proposals of public-key cryptosystems based on codes with a non-trivial automorphism group.