Skip to Main content Skip to Navigation
Conference papers

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

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.
Complete list of metadata

https://hal.inria.fr/hal-02424101
Contributor : Jean-Pierre Tillich <>
Submitted on : Thursday, December 26, 2019 - 4:58:28 PM
Last modification on : Thursday, January 7, 2021 - 3:38:03 PM

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

85