# zbMATH — the first resource for mathematics

Decoding random linear codes in $$\tilde{\mathcal{O}}(2^{0.054n})$$. (English) Zbl 1227.94055
Lee, Dong Hoon (ed.) et al., Advances in cryptology – ASIACRYPT 2011. 17th international conference on the theory and application of cryptology and information security, Seoul, South Korea, December 4–8, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-25384-3/pbk). Lecture Notes in Computer Science 7073, 107-124 (2011).
Summary: Decoding random linear codes is a fundamental problem in complexity theory and lies at the heart of almost all code-based cryptography. The best attacks on the most prominent code-based cryptosystems such as McEliece directly use decoding algorithms for linear codes. The asymptotically best decoding algorithm for random linear codes of length $$n$$ was for a long time Stern’s variant of information-set decoding running in time $$\tilde{\mathcal{O}}\left(2^{0.05563n}\right)$$. Recently, Bernstein, Lange and Peters proposed a new technique called Ball-collision decoding which offers a speed-up over Stern’s algorithm by improving the running time to $$\tilde{\mathcal{O}}\left(2^{0.05558n}\right)$$.
In this paper, we present a new algorithm for decoding linear codes that is inspired by a representation technique due to Howgrave-Graham and Joux in the context of subset sum algorithms. Our decoding algorithm offers a rigorous complexity analysis for random linear codes and brings the time complexity down to $$\tilde{\mathcal{O}}\left(2^{0.05363n}\right)$$.
For the entire collection see [Zbl 1227.94002].

##### MSC:
 94A60 Cryptography 94B35 Decoding
##### Keywords:
information set decoding; representation technique
Full Text: