Analysis of the gallant-lambert-vanstone method based on efficient endomorphisms: Elliptic and hyperelliptic curves

Francesco Sica; Mathieu Ciet; Jean Jacques Quisquater

doi:10.1007/3-540-36492-7_3

Analysis of the gallant-lambert-vanstone method based on efficient endomorphisms: Elliptic and hyperelliptic curves

Francesco Sica, Mathieu Ciet, Jean Jacques Quisquater

Department of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Chapter

32 Citations (Scopus)

Abstract

In this work we analyse the GLV method of Gallant, Lambert and Vanstone (CRYPTO 2001) which uses a fast endomorphism Φ with minimal polynomial X² + 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 = k₁P + k₂Φ(P), with max{|k₁|,|k₂|} ≤ √1 + |r| + s√n . Next we improve on this bound and give the best constant in the given examples for the quantity sup_k,n max{|k₁|,|k₂|}/√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
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Kaisa Nyberg, Howard Heys
Publisher	Springer Verlag
Pages	21-36
Number of pages	16
ISBN (Print)	9783540006220
DOIs	https://doi.org/10.1007/3-540-36492-7_3
Publication status	Published - 2003

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2595
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Keywords

Algebraic number fields
Efficiently-computable endomorphisms
Elliptic curve cryptography
Fast performance

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-36492-7_3

Fingerprint Dive into the research topics of 'Analysis of the gallant-lambert-vanstone method based on efficient endomorphisms: Elliptic and hyperelliptic curves'. Together they form a unique fingerprint.

Cite this

Sica, F., Ciet, M., & Quisquater, J. J. (2003). Analysis of the gallant-lambert-vanstone method based on efficient endomorphisms: Elliptic and hyperelliptic curves. In K. Nyberg, & H. Heys (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 21-36). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2595). Springer Verlag. https://doi.org/10.1007/3-540-36492-7_3

Analysis of the gallant-lambert-vanstone method based on efficient endomorphisms : Elliptic and hyperelliptic curves. / Sica, Francesco; Ciet, Mathieu; Quisquater, Jean Jacques.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Kaisa Nyberg; Howard Heys. Springer Verlag, 2003. p. 21-36 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2595).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Sica, F, Ciet, M & Quisquater, JJ 2003, Analysis of the gallant-lambert-vanstone method based on efficient endomorphisms: Elliptic and hyperelliptic curves. in K Nyberg & H Heys (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2595, Springer Verlag, pp. 21-36. https://doi.org/10.1007/3-540-36492-7_3

Sica F, Ciet M, Quisquater JJ. Analysis of the gallant-lambert-vanstone method based on efficient endomorphisms: Elliptic and hyperelliptic curves. In Nyberg K, Heys H, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2003. p. 21-36. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-36492-7_3

Sica, Francesco ; Ciet, Mathieu ; Quisquater, Jean Jacques. / Analysis of the gallant-lambert-vanstone method based on efficient endomorphisms : Elliptic and hyperelliptic curves. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Kaisa Nyberg ; Howard Heys. Springer Verlag, 2003. pp. 21-36 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{ba176ff19a5f448db1a4119bed71c02c,

title = "Analysis of the gallant-lambert-vanstone method based on efficient endomorphisms: Elliptic and hyperelliptic curves",

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).",

keywords = "Algebraic number fields, Efficiently-computable endomorphisms, Elliptic curve cryptography, Fast performance",

author = "Francesco Sica and Mathieu Ciet and Quisquater, {Jean Jacques}",

year = "2003",

doi = "10.1007/3-540-36492-7_3",

language = "English",

isbn = "9783540006220",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "21--36",

editor = "Kaisa Nyberg and Howard Heys",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

address = "Germany",

}

TY - CHAP

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

U2 - 10.1007/3-540-36492-7_3

DO - 10.1007/3-540-36492-7_3

M3 - Chapter

AN - SCOPUS:35248862660

SN - 9783540006220

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

SP - 21

EP - 36

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

A2 - Nyberg, Kaisa

A2 - Heys, Howard

PB - Springer Verlag

ER -