Decoding random linear codes in 0.091n
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.