@inproceedings{7a1f42b0fbd14bd2aa752d67295abfa2,
title = "Simplified high-speed high-distance list decoding for alternant codes",
abstract = "This paper presents a simplified list-decoding algorithm to correct any number w of errors in any alternant code of any length n with any designed distance t+1 over any finite field F\_q ; in particular, in the classical Goppa codes used in the McEliece and Niederreiter public-key cryptosystems. The algorithm is efficient for w close to, and in many cases slightly beyond, the F\_q Johnson bound J'=n' - sqrt\{n'(n'-t-1)\} where n'¿=¿n(q-1)/q, assuming t+1¿=¿n'. In the typical case that qn/t in (lg n)\textasciicircum{}O(1) and that the parent field has (lg n)\textasciicircum{}O(1) bits, the algorithm uses n(lg n)\textasciicircum{}O(1) bit operations for w = J' - n/(lg n)\textasciicircum{}O(1); O(n\textasciicircum{} 4.5) bit operations for w = J' + o((lg lg n); and n\textasciicircum{}O(1) bit operations for w = J' + O((lgn)/lg lg n).",
author = "D.J. Bernstein",
year = "2011",
doi = "10.1007/978-3-642-25405-5\_13",
language = "English",
isbn = "978-3-642-25404-8",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "200--216",
editor = "B.Y. Yang",
booktitle = "Post-Quantum Cryptography (4th International Workshop, PQCrypto 2011, Taipei, Taiwan, November 29-December 2, 2011. Proceedings)",
address = "Germany",
}