List decoding for binary Goppa codes

D.J. Bernstein

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    13 Citations (Scopus)

    Abstract

    This paper presents a Patterson-style list-decoding algorithm for classical irreducible binary Goppa codes. The algorithm corrects, in polynomial time, approximately $n - \sqrt{n(n-2t-2)}$ errors in a length-n classical irreducible degree-t binary Goppa code. Compared to the best previous polynomial-time list-decoding algorithms for the same codes, the new algorithm corrects approximately $t^2/2n$ extra errors.
    Original languageEnglish
    Title of host publicationCoding and Cryptology (Third International Workshop, IWCC 2011, Qingdao, China, May 30-June 3, 2011. Proceedings)
    EditorsY.M. Chee
    Place of PublicationBerlin
    PublisherSpringer
    Pages62-80
    ISBN (Print)978-3-642-20900-0
    DOIs
    Publication statusPublished - 2011

    Publication series

    NameLecture Notes in Computer Science
    Volume6639
    ISSN (Print)0302-9743

    Fingerprint

    Binary codes
    Decoding
    Polynomials

    Cite this

    Bernstein, D. J. (2011). List decoding for binary Goppa codes. In Y. M. Chee (Ed.), Coding and Cryptology (Third International Workshop, IWCC 2011, Qingdao, China, May 30-June 3, 2011. Proceedings) (pp. 62-80). (Lecture Notes in Computer Science; Vol. 6639). Berlin: Springer. https://doi.org/10.1007/978-3-642-20901-7_4
    Bernstein, D.J. / List decoding for binary Goppa codes. Coding and Cryptology (Third International Workshop, IWCC 2011, Qingdao, China, May 30-June 3, 2011. Proceedings). editor / Y.M. Chee. Berlin : Springer, 2011. pp. 62-80 (Lecture Notes in Computer Science).
    @inproceedings{badc16d036e74ab98992b9cf62188710,
    title = "List decoding for binary Goppa codes",
    abstract = "This paper presents a Patterson-style list-decoding algorithm for classical irreducible binary Goppa codes. The algorithm corrects, in polynomial time, approximately $n - \sqrt{n(n-2t-2)}$ errors in a length-n classical irreducible degree-t binary Goppa code. Compared to the best previous polynomial-time list-decoding algorithms for the same codes, the new algorithm corrects approximately $t^2/2n$ extra errors.",
    author = "D.J. Bernstein",
    year = "2011",
    doi = "10.1007/978-3-642-20901-7_4",
    language = "English",
    isbn = "978-3-642-20900-0",
    series = "Lecture Notes in Computer Science",
    publisher = "Springer",
    pages = "62--80",
    editor = "Y.M. Chee",
    booktitle = "Coding and Cryptology (Third International Workshop, IWCC 2011, Qingdao, China, May 30-June 3, 2011. Proceedings)",
    address = "Germany",

    }

    Bernstein, DJ 2011, List decoding for binary Goppa codes. in YM Chee (ed.), Coding and Cryptology (Third International Workshop, IWCC 2011, Qingdao, China, May 30-June 3, 2011. Proceedings). Lecture Notes in Computer Science, vol. 6639, Springer, Berlin, pp. 62-80. https://doi.org/10.1007/978-3-642-20901-7_4

    List decoding for binary Goppa codes. / Bernstein, D.J.

    Coding and Cryptology (Third International Workshop, IWCC 2011, Qingdao, China, May 30-June 3, 2011. Proceedings). ed. / Y.M. Chee. Berlin : Springer, 2011. p. 62-80 (Lecture Notes in Computer Science; Vol. 6639).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    TY - GEN

    T1 - List decoding for binary Goppa codes

    AU - Bernstein, D.J.

    PY - 2011

    Y1 - 2011

    N2 - This paper presents a Patterson-style list-decoding algorithm for classical irreducible binary Goppa codes. The algorithm corrects, in polynomial time, approximately $n - \sqrt{n(n-2t-2)}$ errors in a length-n classical irreducible degree-t binary Goppa code. Compared to the best previous polynomial-time list-decoding algorithms for the same codes, the new algorithm corrects approximately $t^2/2n$ extra errors.

    AB - This paper presents a Patterson-style list-decoding algorithm for classical irreducible binary Goppa codes. The algorithm corrects, in polynomial time, approximately $n - \sqrt{n(n-2t-2)}$ errors in a length-n classical irreducible degree-t binary Goppa code. Compared to the best previous polynomial-time list-decoding algorithms for the same codes, the new algorithm corrects approximately $t^2/2n$ extra errors.

    U2 - 10.1007/978-3-642-20901-7_4

    DO - 10.1007/978-3-642-20901-7_4

    M3 - Conference contribution

    SN - 978-3-642-20900-0

    T3 - Lecture Notes in Computer Science

    SP - 62

    EP - 80

    BT - Coding and Cryptology (Third International Workshop, IWCC 2011, Qingdao, China, May 30-June 3, 2011. Proceedings)

    A2 - Chee, Y.M.

    PB - Springer

    CY - Berlin

    ER -

    Bernstein DJ. List decoding for binary Goppa codes. In Chee YM, editor, Coding and Cryptology (Third International Workshop, IWCC 2011, Qingdao, China, May 30-June 3, 2011. Proceedings). Berlin: Springer. 2011. p. 62-80. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-20901-7_4