Four-dimensional Gallant-Lambert-Vanstone scalar multiplication

Patrick Longa, Francesco Sica

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

    37 Citations (Scopus)

    Abstract

    The GLV method of Gallant, Lambert and Vanstone (CRYPTO 2001) computes any multiple kP of a point P of prime order n lying on an elliptic curve with a low-degree endomorphism Φ (called GLV curve) over double-struck F p as kP = k1P + k2Φ(P), with max{|k 1|, |k2|} ≤ C1√n, for some explicit constant C1 > 0. Recently, Galbraith, Lin and Scott (EUROCRYPT 2009) extended this method to all curves over double-struck Fp2 which are twists of curves defined over double-struck Fp. We show in this work how to merge the two approaches in order to get, for twists of any GLV curve over double-struck Fp2 , a four-dimensional decomposition together with fast endomorphisms Φ, Ψ over double-struck Fp2 acting on the group generated by a point P of prime order n, resulting in a proven decomposition for any scalar k ∈ [1, n] given by kP = k1P + k2Φ(P) + k3Ψ(P) + k4ΨΦ(P) with maxi(|ki|) <C2 n1/4, for some explicit C2 <0. Remarkably, taking the best C1, C2, we obtain C2/C1 <412, independently of the curve, ensuring in theory an almost constant relative speedup. In practice, our experiments reveal that the use of the merged GLV-GLS approach supports a scalar multiplication that runs up to 50% times faster than the original GLV method. We then improve this performance even further by exploiting the Twisted Edwards model and show that curves originally slower may become extremely efficient on this model. In addition, we analyze the performance of the method on a multicore setting and describe how to efficiently protect GLV-based scalar multiplication against several side-channel attacks. Our implementations improve the state-of-the-art performance of point multiplication for a variety of scenarios including side-channel protected and unprotected cases with sequential and multicore execution.

    Original languageEnglish
    Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Pages718-739
    Number of pages22
    Volume7658 LNCS
    DOIs
    Publication statusPublished - 2012
    Event18th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2012 - Beijing, China
    Duration: Dec 2 2012Dec 6 2012

    Publication series

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

    Other

    Other18th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2012
    CountryChina
    CityBeijing
    Period12/2/1212/6/12

    Fingerprint

    Scalar multiplication
    Decomposition
    Curve
    P-point
    Twist
    Decompose
    Side Channel Attacks
    Experiments
    Endomorphism
    Endomorphisms
    Elliptic Curves
    Multiplication
    Speedup
    Scalar
    Scenarios
    Model
    Experiment
    Side channel attack

    Keywords

    • Elliptic curves
    • GLV-GLS method
    • Multicore computation
    • Scalar multiplication
    • Side-channel protection
    • Twisted Edwards curve

    ASJC Scopus subject areas

    • Computer Science(all)
    • Theoretical Computer Science

    Cite this

    Longa, P., & Sica, F. (2012). Four-dimensional Gallant-Lambert-Vanstone scalar multiplication. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 7658 LNCS, pp. 718-739). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7658 LNCS). https://doi.org/10.1007/978-3-642-34961-4_43

    Four-dimensional Gallant-Lambert-Vanstone scalar multiplication. / Longa, Patrick; Sica, Francesco.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 7658 LNCS 2012. p. 718-739 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7658 LNCS).

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

    Longa, P & Sica, F 2012, Four-dimensional Gallant-Lambert-Vanstone scalar multiplication. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). vol. 7658 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7658 LNCS, pp. 718-739, 18th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2012, Beijing, China, 12/2/12. https://doi.org/10.1007/978-3-642-34961-4_43
    Longa P, Sica F. Four-dimensional Gallant-Lambert-Vanstone scalar multiplication. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 7658 LNCS. 2012. p. 718-739. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-34961-4_43
    Longa, Patrick ; Sica, Francesco. / Four-dimensional Gallant-Lambert-Vanstone scalar multiplication. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 7658 LNCS 2012. pp. 718-739 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
    @inproceedings{8a4854dfb3774151afe5e3dade57f4e8,
    title = "Four-dimensional Gallant-Lambert-Vanstone scalar multiplication",
    abstract = "The GLV method of Gallant, Lambert and Vanstone (CRYPTO 2001) computes any multiple kP of a point P of prime order n lying on an elliptic curve with a low-degree endomorphism Φ (called GLV curve) over double-struck F p as kP = k1P + k2Φ(P), with max{|k 1|, |k2|} ≤ C1√n, for some explicit constant C1 > 0. Recently, Galbraith, Lin and Scott (EUROCRYPT 2009) extended this method to all curves over double-struck Fp2 which are twists of curves defined over double-struck Fp. We show in this work how to merge the two approaches in order to get, for twists of any GLV curve over double-struck Fp2 , a four-dimensional decomposition together with fast endomorphisms Φ, Ψ over double-struck Fp2 acting on the group generated by a point P of prime order n, resulting in a proven decomposition for any scalar k ∈ [1, n] given by kP = k1P + k2Φ(P) + k3Ψ(P) + k4ΨΦ(P) with maxi(|ki|) <C2 n1/4, for some explicit C2 <0. Remarkably, taking the best C1, C2, we obtain C2/C1 <412, independently of the curve, ensuring in theory an almost constant relative speedup. In practice, our experiments reveal that the use of the merged GLV-GLS approach supports a scalar multiplication that runs up to 50{\%} times faster than the original GLV method. We then improve this performance even further by exploiting the Twisted Edwards model and show that curves originally slower may become extremely efficient on this model. In addition, we analyze the performance of the method on a multicore setting and describe how to efficiently protect GLV-based scalar multiplication against several side-channel attacks. Our implementations improve the state-of-the-art performance of point multiplication for a variety of scenarios including side-channel protected and unprotected cases with sequential and multicore execution.",
    keywords = "Elliptic curves, GLV-GLS method, Multicore computation, Scalar multiplication, Side-channel protection, Twisted Edwards curve",
    author = "Patrick Longa and Francesco Sica",
    year = "2012",
    doi = "10.1007/978-3-642-34961-4_43",
    language = "English",
    isbn = "9783642349607",
    volume = "7658 LNCS",
    series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
    pages = "718--739",
    booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

    }

    TY - GEN

    T1 - Four-dimensional Gallant-Lambert-Vanstone scalar multiplication

    AU - Longa, Patrick

    AU - Sica, Francesco

    PY - 2012

    Y1 - 2012

    N2 - The GLV method of Gallant, Lambert and Vanstone (CRYPTO 2001) computes any multiple kP of a point P of prime order n lying on an elliptic curve with a low-degree endomorphism Φ (called GLV curve) over double-struck F p as kP = k1P + k2Φ(P), with max{|k 1|, |k2|} ≤ C1√n, for some explicit constant C1 > 0. Recently, Galbraith, Lin and Scott (EUROCRYPT 2009) extended this method to all curves over double-struck Fp2 which are twists of curves defined over double-struck Fp. We show in this work how to merge the two approaches in order to get, for twists of any GLV curve over double-struck Fp2 , a four-dimensional decomposition together with fast endomorphisms Φ, Ψ over double-struck Fp2 acting on the group generated by a point P of prime order n, resulting in a proven decomposition for any scalar k ∈ [1, n] given by kP = k1P + k2Φ(P) + k3Ψ(P) + k4ΨΦ(P) with maxi(|ki|) <C2 n1/4, for some explicit C2 <0. Remarkably, taking the best C1, C2, we obtain C2/C1 <412, independently of the curve, ensuring in theory an almost constant relative speedup. In practice, our experiments reveal that the use of the merged GLV-GLS approach supports a scalar multiplication that runs up to 50% times faster than the original GLV method. We then improve this performance even further by exploiting the Twisted Edwards model and show that curves originally slower may become extremely efficient on this model. In addition, we analyze the performance of the method on a multicore setting and describe how to efficiently protect GLV-based scalar multiplication against several side-channel attacks. Our implementations improve the state-of-the-art performance of point multiplication for a variety of scenarios including side-channel protected and unprotected cases with sequential and multicore execution.

    AB - The GLV method of Gallant, Lambert and Vanstone (CRYPTO 2001) computes any multiple kP of a point P of prime order n lying on an elliptic curve with a low-degree endomorphism Φ (called GLV curve) over double-struck F p as kP = k1P + k2Φ(P), with max{|k 1|, |k2|} ≤ C1√n, for some explicit constant C1 > 0. Recently, Galbraith, Lin and Scott (EUROCRYPT 2009) extended this method to all curves over double-struck Fp2 which are twists of curves defined over double-struck Fp. We show in this work how to merge the two approaches in order to get, for twists of any GLV curve over double-struck Fp2 , a four-dimensional decomposition together with fast endomorphisms Φ, Ψ over double-struck Fp2 acting on the group generated by a point P of prime order n, resulting in a proven decomposition for any scalar k ∈ [1, n] given by kP = k1P + k2Φ(P) + k3Ψ(P) + k4ΨΦ(P) with maxi(|ki|) <C2 n1/4, for some explicit C2 <0. Remarkably, taking the best C1, C2, we obtain C2/C1 <412, independently of the curve, ensuring in theory an almost constant relative speedup. In practice, our experiments reveal that the use of the merged GLV-GLS approach supports a scalar multiplication that runs up to 50% times faster than the original GLV method. We then improve this performance even further by exploiting the Twisted Edwards model and show that curves originally slower may become extremely efficient on this model. In addition, we analyze the performance of the method on a multicore setting and describe how to efficiently protect GLV-based scalar multiplication against several side-channel attacks. Our implementations improve the state-of-the-art performance of point multiplication for a variety of scenarios including side-channel protected and unprotected cases with sequential and multicore execution.

    KW - Elliptic curves

    KW - GLV-GLS method

    KW - Multicore computation

    KW - Scalar multiplication

    KW - Side-channel protection

    KW - Twisted Edwards curve

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

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

    U2 - 10.1007/978-3-642-34961-4_43

    DO - 10.1007/978-3-642-34961-4_43

    M3 - Conference contribution

    SN - 9783642349607

    VL - 7658 LNCS

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

    SP - 718

    EP - 739

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

    ER -