Speeding up decoding a code with a non-trivial automorphism group up to an exponential factor

Rodolfo Canto-Torres (1) , Jean-Pierre Tillich (1)

1 SECRET - Security, Cryptology and Transmissions

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.

Mots clés: Decoding; Orbits; Linear codes; Complexity theory; Public key; Generators; Nontrivial automorphism group; Exponential factor; Public-key cryptosystems; Generic linear code decoding

Domaines: Théorie de l'information [cs.IT]; Cryptographie et sécurité [cs.CR]

Rodolfo Canto-Torres, Jean-Pierre Tillich. Speeding up decoding a code with a non-trivial automorphism group up to an exponential factor. ISIT 2019 - IEEE International Symposium on Information Theory, Jul 2019, Paris, France. pp.1927-1931, ⟨10.1109/ISIT.2019.8849628⟩. ⟨hal-02424101⟩