Abstract
In this work we analyse the GLV method of Gallant, Lambert and Vanstone (CRYPTO 2001) which uses a fast endomorphism Φ with minimal polynomial X2 + rX + s to compute any multiple kP of a point P of order n lying on an elliptic curve. First we fill in a gap in the proof of the bound of the kernel K vectors of the reduction map f: (i,j) → i + λj (mod n). In particular, we prove the GLV decomposition with explicit constant kP = k1P + k2Φ(P), with max{|k1|,|k2|} ≤ √1 + |r| + s√n . Next we improve on this bound and give the best constant in the given examples for the quantity supk,n max{|k1|,|k2|}/√n. Independently Park, Jeong, Kim, and Lim (PKC 2002) have given similar but slightly weaker bounds. Finally we provide the first explicit bounds for the GLV method generalised to hyperelliptic curves as described in Park, Jeong and Lim (EUROCRYPT 2002).
| Original language | English |
|---|---|
| Pages (from-to) | 21-36 |
| Number of pages | 16 |
| Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| Volume | 2595 |
| Publication status | Published - 2003 |
| Externally published | Yes |
Fingerprint
Keywords
- Algebraic number fields
- Efficiently-computable endomorphisms
- Elliptic curve cryptography
- Fast performance
ASJC Scopus subject areas
- Computer Science(all)
- Biochemistry, Genetics and Molecular Biology(all)
- Theoretical Computer Science
Cite this
Analysis of the gallant-lambert-vanstone method based on efficient endomorphisms : Elliptic and hyperelliptic curves. / Sica, Francesco; Ciet, Mathieu; Quisquater, Jean Jacques.
In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 2595, 2003, p. 21-36.Research output: Contribution to journal › Article
}
TY - JOUR
T1 - Analysis of the gallant-lambert-vanstone method based on efficient endomorphisms
T2 - Elliptic and hyperelliptic curves
AU - Sica, Francesco
AU - Ciet, Mathieu
AU - Quisquater, Jean Jacques
PY - 2003
Y1 - 2003
N2 - In this work we analyse the GLV method of Gallant, Lambert and Vanstone (CRYPTO 2001) which uses a fast endomorphism Φ with minimal polynomial X2 + rX + s to compute any multiple kP of a point P of order n lying on an elliptic curve. First we fill in a gap in the proof of the bound of the kernel K vectors of the reduction map f: (i,j) → i + λj (mod n). In particular, we prove the GLV decomposition with explicit constant kP = k1P + k2Φ(P), with max{|k1|,|k2|} ≤ √1 + |r| + s√n . Next we improve on this bound and give the best constant in the given examples for the quantity supk,n max{|k1|,|k2|}/√n. Independently Park, Jeong, Kim, and Lim (PKC 2002) have given similar but slightly weaker bounds. Finally we provide the first explicit bounds for the GLV method generalised to hyperelliptic curves as described in Park, Jeong and Lim (EUROCRYPT 2002).
AB - In this work we analyse the GLV method of Gallant, Lambert and Vanstone (CRYPTO 2001) which uses a fast endomorphism Φ with minimal polynomial X2 + rX + s to compute any multiple kP of a point P of order n lying on an elliptic curve. First we fill in a gap in the proof of the bound of the kernel K vectors of the reduction map f: (i,j) → i + λj (mod n). In particular, we prove the GLV decomposition with explicit constant kP = k1P + k2Φ(P), with max{|k1|,|k2|} ≤ √1 + |r| + s√n . Next we improve on this bound and give the best constant in the given examples for the quantity supk,n max{|k1|,|k2|}/√n. Independently Park, Jeong, Kim, and Lim (PKC 2002) have given similar but slightly weaker bounds. Finally we provide the first explicit bounds for the GLV method generalised to hyperelliptic curves as described in Park, Jeong and Lim (EUROCRYPT 2002).
KW - Algebraic number fields
KW - Efficiently-computable endomorphisms
KW - Elliptic curve cryptography
KW - Fast performance
UR - http://www.scopus.com/inward/record.url?scp=35248862660&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=35248862660&partnerID=8YFLogxK
M3 - Article
VL - 2595
SP - 21
EP - 36
JO - Lecture Notes in Computer Science
JF - Lecture Notes in Computer Science
SN - 0302-9743
ER -