A secure family of composite finite fields suitable for fast implementation of elliptic curve cryptography

Mathieu Ciet, Jean Jacques Quisquater, Francesco Sica

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    13 Citations (Scopus)

    Abstract

    In 1999 Silverman [21] introduced a family of binary finite fields which are composite extensions of F2 and on which arithmetic operations can be performed more quickly than on prime extensions of F2 of the same size. We present here a fast approach to elliptic curve cryptography using a distinguished subset of the set of Silverman fields F2N = Fhn. This approach leads to a theoretical computation speedup over fields of the same size, using a standard point of view (cf. [7]). We also analyse their security against prime extension fields F2p, where p is prime, following the method of Menezes and Qu [12]. We conclude that our fields do not present any significant weakness towards the solution of the elliptic curve discrete logarithm problem and that often the Weil descent of Galbraith-Gaudry-Hess-Smart (GGHS) does not offer a better attack on elliptic curves defined over F2N than on those defined over F2p, with a prime p of the same size as N. A noteworthy example is provided by F2226: a generic elliptic curve Y2 + XY = X3 + αX2 + β defined over F2226 is as prone to the GGHS Weil descent attack as a generic curve defined on the NIST field F2233.

    Original languageEnglish
    Title of host publicationProgress in Cryptology - INDOCRYPT 2001 - 2nd International Conference on Cryptology in India, Proceedings
    PublisherSpringer Verlag
    Pages108-116
    Number of pages9
    Volume2247
    ISBN (Print)9783540453116
    Publication statusPublished - 2001
    Event2nd International Conference on Cryptology in India, INDOCRYPT 2001 - Chennai, India
    Duration: Dec 16 2001Dec 20 2001

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume2247
    ISSN (Print)03029743
    ISSN (Electronic)16113349

    Other

    Other2nd International Conference on Cryptology in India, INDOCRYPT 2001
    CountryIndia
    CityChennai
    Period12/16/0112/20/01

    Fingerprint

    Cryptography
    Elliptic Curves
    Galois field
    Composite
    Composite materials
    Descent
    Attack
    Discrete Logarithm Problem
    Field extension
    Speedup
    Binary
    Curve
    Subset
    Family

    Keywords

    • Elliptic curve cryptography
    • Fast performance
    • Finite fields
    • Weil descent

    ASJC Scopus subject areas

    • Computer Science(all)
    • Theoretical Computer Science

    Cite this

    Ciet, M., Quisquater, J. J., & Sica, F. (2001). A secure family of composite finite fields suitable for fast implementation of elliptic curve cryptography. In Progress in Cryptology - INDOCRYPT 2001 - 2nd International Conference on Cryptology in India, Proceedings (Vol. 2247, pp. 108-116). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2247). Springer Verlag.

    A secure family of composite finite fields suitable for fast implementation of elliptic curve cryptography. / Ciet, Mathieu; Quisquater, Jean Jacques; Sica, Francesco.

    Progress in Cryptology - INDOCRYPT 2001 - 2nd International Conference on Cryptology in India, Proceedings. Vol. 2247 Springer Verlag, 2001. p. 108-116 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2247).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Ciet, M, Quisquater, JJ & Sica, F 2001, A secure family of composite finite fields suitable for fast implementation of elliptic curve cryptography. in Progress in Cryptology - INDOCRYPT 2001 - 2nd International Conference on Cryptology in India, Proceedings. vol. 2247, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2247, Springer Verlag, pp. 108-116, 2nd International Conference on Cryptology in India, INDOCRYPT 2001, Chennai, India, 12/16/01.
    Ciet M, Quisquater JJ, Sica F. A secure family of composite finite fields suitable for fast implementation of elliptic curve cryptography. In Progress in Cryptology - INDOCRYPT 2001 - 2nd International Conference on Cryptology in India, Proceedings. Vol. 2247. Springer Verlag. 2001. p. 108-116. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
    Ciet, Mathieu ; Quisquater, Jean Jacques ; Sica, Francesco. / A secure family of composite finite fields suitable for fast implementation of elliptic curve cryptography. Progress in Cryptology - INDOCRYPT 2001 - 2nd International Conference on Cryptology in India, Proceedings. Vol. 2247 Springer Verlag, 2001. pp. 108-116 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
    @inproceedings{ba7cde2759814f11a1268f8a30fb9028,
    title = "A secure family of composite finite fields suitable for fast implementation of elliptic curve cryptography",
    abstract = "In 1999 Silverman [21] introduced a family of binary finite fields which are composite extensions of F2 and on which arithmetic operations can be performed more quickly than on prime extensions of F2 of the same size. We present here a fast approach to elliptic curve cryptography using a distinguished subset of the set of Silverman fields F2N = Fhn. This approach leads to a theoretical computation speedup over fields of the same size, using a standard point of view (cf. [7]). We also analyse their security against prime extension fields F2p, where p is prime, following the method of Menezes and Qu [12]. We conclude that our fields do not present any significant weakness towards the solution of the elliptic curve discrete logarithm problem and that often the Weil descent of Galbraith-Gaudry-Hess-Smart (GGHS) does not offer a better attack on elliptic curves defined over F2N than on those defined over F2p, with a prime p of the same size as N. A noteworthy example is provided by F2226: a generic elliptic curve Y2 + XY = X3 + αX2 + β defined over F2226 is as prone to the GGHS Weil descent attack as a generic curve defined on the NIST field F2233.",
    keywords = "Elliptic curve cryptography, Fast performance, Finite fields, Weil descent",
    author = "Mathieu Ciet and Quisquater, {Jean Jacques} and Francesco Sica",
    year = "2001",
    language = "English",
    isbn = "9783540453116",
    volume = "2247",
    series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
    publisher = "Springer Verlag",
    pages = "108--116",
    booktitle = "Progress in Cryptology - INDOCRYPT 2001 - 2nd International Conference on Cryptology in India, Proceedings",
    address = "Germany",

    }

    TY - GEN

    T1 - A secure family of composite finite fields suitable for fast implementation of elliptic curve cryptography

    AU - Ciet, Mathieu

    AU - Quisquater, Jean Jacques

    AU - Sica, Francesco

    PY - 2001

    Y1 - 2001

    N2 - In 1999 Silverman [21] introduced a family of binary finite fields which are composite extensions of F2 and on which arithmetic operations can be performed more quickly than on prime extensions of F2 of the same size. We present here a fast approach to elliptic curve cryptography using a distinguished subset of the set of Silverman fields F2N = Fhn. This approach leads to a theoretical computation speedup over fields of the same size, using a standard point of view (cf. [7]). We also analyse their security against prime extension fields F2p, where p is prime, following the method of Menezes and Qu [12]. We conclude that our fields do not present any significant weakness towards the solution of the elliptic curve discrete logarithm problem and that often the Weil descent of Galbraith-Gaudry-Hess-Smart (GGHS) does not offer a better attack on elliptic curves defined over F2N than on those defined over F2p, with a prime p of the same size as N. A noteworthy example is provided by F2226: a generic elliptic curve Y2 + XY = X3 + αX2 + β defined over F2226 is as prone to the GGHS Weil descent attack as a generic curve defined on the NIST field F2233.

    AB - In 1999 Silverman [21] introduced a family of binary finite fields which are composite extensions of F2 and on which arithmetic operations can be performed more quickly than on prime extensions of F2 of the same size. We present here a fast approach to elliptic curve cryptography using a distinguished subset of the set of Silverman fields F2N = Fhn. This approach leads to a theoretical computation speedup over fields of the same size, using a standard point of view (cf. [7]). We also analyse their security against prime extension fields F2p, where p is prime, following the method of Menezes and Qu [12]. We conclude that our fields do not present any significant weakness towards the solution of the elliptic curve discrete logarithm problem and that often the Weil descent of Galbraith-Gaudry-Hess-Smart (GGHS) does not offer a better attack on elliptic curves defined over F2N than on those defined over F2p, with a prime p of the same size as N. A noteworthy example is provided by F2226: a generic elliptic curve Y2 + XY = X3 + αX2 + β defined over F2226 is as prone to the GGHS Weil descent attack as a generic curve defined on the NIST field F2233.

    KW - Elliptic curve cryptography

    KW - Fast performance

    KW - Finite fields

    KW - Weil descent

    UR - http://www.scopus.com/inward/record.url?scp=84974687517&partnerID=8YFLogxK

    UR - http://www.scopus.com/inward/citedby.url?scp=84974687517&partnerID=8YFLogxK

    M3 - Conference contribution

    SN - 9783540453116

    VL - 2247

    T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

    SP - 108

    EP - 116

    BT - Progress in Cryptology - INDOCRYPT 2001 - 2nd International Conference on Cryptology in India, Proceedings

    PB - Springer Verlag

    ER -