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 language | English |
|---|---|
| Pages (from-to) | 248-283 |
| Number of pages | 36 |
| Journal | Journal of Cryptology |
| Volume | 27 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - 2014 |
Fingerprint
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 journal › Article
}
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 -