Four-dimensional Gallant-Lambert-Vanstone scalar multiplication

Patrick Longa, Francesco Sica

    Research output: Contribution to journalArticle

    14 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 Fp kP = k 1P+ k2Φ(P) with max {|k1|,|k2|} ≤ C1 √n for some explicit constant C1>0. Recently, Galbraith, Lin, and Scott (EUROCRYPT 2009) extended this method to all curves over Fp2 which are twists of curves defined over F p2. We show in this work how to merge the two approaches in order to get, for twists of any GLV curve over Fp2, a four-dimensional decomposition together with fast endomorphisms Φ,Ψ over 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,C 2, we obtain C2/C1

    Original languageEnglish
    Pages (from-to)248-283
    Number of pages36
    JournalJournal of Cryptology
    Volume27
    Issue number2
    DOIs
    Publication statusPublished - 2014

    Fingerprint

    Scalar multiplication
    Decomposition
    P-point
    Curve
    Twist
    Decompose
    Endomorphism
    Endomorphisms
    Elliptic Curves
    Scalar

    Keywords

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

    ASJC Scopus subject areas

    • Applied Mathematics
    • Computer Science Applications
    • Software

    Cite this

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

    In: Journal of Cryptology, Vol. 27, No. 2, 2014, p. 248-283.

    Research output: Contribution to journalArticle

    @article{70ed4dcf851746bdb670e0e516892087,
    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 Fp kP = k 1P+ k2Φ(P) with max {|k1|,|k2|} ≤ C1 √n for some explicit constant C1>0. Recently, Galbraith, Lin, and Scott (EUROCRYPT 2009) extended this method to all curves over Fp2 which are twists of curves defined over F p2. We show in this work how to merge the two approaches in order to get, for twists of any GLV curve over Fp2, a four-dimensional decomposition together with fast endomorphisms Φ,Ψ over 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,C 2, we obtain C2/C1",
    keywords = "Elliptic curves, GLV-GLS method, Multicore computation, Scalar multiplication, Side-channel protection, Twisted Edwards curve",
    author = "Patrick Longa and Francesco Sica",
    year = "2014",
    doi = "10.1007/s00145-012-9144-3",
    language = "English",
    volume = "27",
    pages = "248--283",
    journal = "Journal of Cryptology",
    issn = "0933-2790",
    publisher = "Springer New York",
    number = "2",

    }

    TY - JOUR

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

    AU - Longa, Patrick

    AU - Sica, Francesco

    PY - 2014

    Y1 - 2014

    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 Fp kP = k 1P+ k2Φ(P) with max {|k1|,|k2|} ≤ C1 √n for some explicit constant C1>0. Recently, Galbraith, Lin, and Scott (EUROCRYPT 2009) extended this method to all curves over Fp2 which are twists of curves defined over F p2. We show in this work how to merge the two approaches in order to get, for twists of any GLV curve over Fp2, a four-dimensional decomposition together with fast endomorphisms Φ,Ψ over 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,C 2, we obtain C2/C1

    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 Fp kP = k 1P+ k2Φ(P) with max {|k1|,|k2|} ≤ C1 √n for some explicit constant C1>0. Recently, Galbraith, Lin, and Scott (EUROCRYPT 2009) extended this method to all curves over Fp2 which are twists of curves defined over F p2. We show in this work how to merge the two approaches in order to get, for twists of any GLV curve over Fp2, a four-dimensional decomposition together with fast endomorphisms Φ,Ψ over 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,C 2, we obtain C2/C1

    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=84896402349&partnerID=8YFLogxK

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

    U2 - 10.1007/s00145-012-9144-3

    DO - 10.1007/s00145-012-9144-3

    M3 - Article

    VL - 27

    SP - 248

    EP - 283

    JO - Journal of Cryptology

    JF - Journal of Cryptology

    SN - 0933-2790

    IS - 2

    ER -