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

Francesco Sica, Mathieu Ciet, Jean Jacques Quisquater

Research output: Chapter in Book/Report/Conference proceedingChapter

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 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 languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsKaisa Nyberg, Howard Heys
PublisherSpringer Verlag
Pages21-36
Number of pages16
ISBN (Print)9783540006220
DOIs
Publication statusPublished - 2003

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2595
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)

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