• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Decoding random linear codes in 0.091n

Krouk E., Abramov A.

Decoding random linear codes is one of the central problems in coding theory and code-based cryptography. In this paper a new algorithm for decoding random long linear codes is proposed. It has a lower decoding complexity exponent than other known algorithms for the codes with rates in a range from 0 to 0.6. This impromevent comes from two key ideas - one is a new approach to lower the dimension of decoding problem which is in some sense opposite to the concept that was proposed by Finiasz and Sendrier; and the second one is to use supercodes decoding algorithm proposed by Barg, Krouk and Van-Tilborg to solve that problem.