Analysis of the gallant-lambert-vanstone method based on efficient endomorphisms

Elliptic and hyperelliptic curves

Francesco Sica, Mathieu Ciet, Jean Jacques Quisquater

Research output: Contribution to journalArticle

30 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
Pages (from-to)21-36
Number of pages16
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2595
Publication statusPublished - 2003
Externally publishedYes

Fingerprint

Hyperelliptic Curves
Endomorphisms
Elliptic Curves
Protein Kinase C
P-point
Minimal polynomial
Best Constants
Explicit Bounds
Polynomials
Endomorphism
Decomposition
kernel
Decompose
First Fill

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

@article{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",
language = "English",
volume = "2595",
pages = "21--36",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Springer Verlag",

}

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 -