Faster scalar multiplication on koblitz curves combining point halving with the frobenius endomorphism

Roberto Maria Avanzi, Mathieu Ciet, Francesco Sica

Research output: Contribution to journalArticle

19 Citations (Scopus)

Abstract

Let E be an elliptic curve defined over F2n. The inverse operation of point doubling, called point halving, can be done up to three times as fast as doubling. Some authors have therefore proposed to perform a scalar multiplication by an "halve-and-add" algorithm, which is faster than the classical double-and-add method. If the coefficients of the equation defining the curve lie in a small subfield of F2n, one can use the Frobenius endomorphism τ of the field extension to replace doublings. Since the cost of τ is negligible if normal bases are used, the scalar multiplication is written in "base τ" and the resulting "τ-and-add" algorithm gives very good performance. For elliptic Koblitz curves, this work combines the two ideas for the first time to achieve a novel decomposition of the scalar. This gives a new scalar multiplication algorithm which is up to 14.29% faster than the Frobenius method, without any additional precomputation.

Original languageEnglish
Pages (from-to)28-40
Number of pages13
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2947
Publication statusPublished - 2004
Externally publishedYes

Fingerprint

Scalar multiplication
Endomorphism
Doubling
Frobenius
Elliptic Curves
Curve
Halve
Normal Basis
Field extension
Subfield
Scalar
Decomposition
Costs and Cost Analysis
Decompose
Costs
Coefficient

Keywords

  • τ-adic expansion
  • Integer decomposition
  • Koblitz curves
  • Point halving
  • Scalar multiplication

ASJC Scopus subject areas

  • Computer Science(all)
  • Biochemistry, Genetics and Molecular Biology(all)
  • Theoretical Computer Science

Cite this

@article{47b6ed4645914a9c829ad7a95c6641bc,
title = "Faster scalar multiplication on koblitz curves combining point halving with the frobenius endomorphism",
abstract = "Let E be an elliptic curve defined over F2n. The inverse operation of point doubling, called point halving, can be done up to three times as fast as doubling. Some authors have therefore proposed to perform a scalar multiplication by an {"}halve-and-add{"} algorithm, which is faster than the classical double-and-add method. If the coefficients of the equation defining the curve lie in a small subfield of F2n, one can use the Frobenius endomorphism τ of the field extension to replace doublings. Since the cost of τ is negligible if normal bases are used, the scalar multiplication is written in {"}base τ{"} and the resulting {"}τ-and-add{"} algorithm gives very good performance. For elliptic Koblitz curves, this work combines the two ideas for the first time to achieve a novel decomposition of the scalar. This gives a new scalar multiplication algorithm which is up to 14.29{\%} faster than the Frobenius method, without any additional precomputation.",
keywords = "τ-adic expansion, Integer decomposition, Koblitz curves, Point halving, Scalar multiplication",
author = "Avanzi, {Roberto Maria} and Mathieu Ciet and Francesco Sica",
year = "2004",
language = "English",
volume = "2947",
pages = "28--40",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Springer Verlag",

}

TY - JOUR

T1 - Faster scalar multiplication on koblitz curves combining point halving with the frobenius endomorphism

AU - Avanzi, Roberto Maria

AU - Ciet, Mathieu

AU - Sica, Francesco

PY - 2004

Y1 - 2004

N2 - Let E be an elliptic curve defined over F2n. The inverse operation of point doubling, called point halving, can be done up to three times as fast as doubling. Some authors have therefore proposed to perform a scalar multiplication by an "halve-and-add" algorithm, which is faster than the classical double-and-add method. If the coefficients of the equation defining the curve lie in a small subfield of F2n, one can use the Frobenius endomorphism τ of the field extension to replace doublings. Since the cost of τ is negligible if normal bases are used, the scalar multiplication is written in "base τ" and the resulting "τ-and-add" algorithm gives very good performance. For elliptic Koblitz curves, this work combines the two ideas for the first time to achieve a novel decomposition of the scalar. This gives a new scalar multiplication algorithm which is up to 14.29% faster than the Frobenius method, without any additional precomputation.

AB - Let E be an elliptic curve defined over F2n. The inverse operation of point doubling, called point halving, can be done up to three times as fast as doubling. Some authors have therefore proposed to perform a scalar multiplication by an "halve-and-add" algorithm, which is faster than the classical double-and-add method. If the coefficients of the equation defining the curve lie in a small subfield of F2n, one can use the Frobenius endomorphism τ of the field extension to replace doublings. Since the cost of τ is negligible if normal bases are used, the scalar multiplication is written in "base τ" and the resulting "τ-and-add" algorithm gives very good performance. For elliptic Koblitz curves, this work combines the two ideas for the first time to achieve a novel decomposition of the scalar. This gives a new scalar multiplication algorithm which is up to 14.29% faster than the Frobenius method, without any additional precomputation.

KW - τ-adic expansion

KW - Integer decomposition

KW - Koblitz curves

KW - Point halving

KW - Scalar multiplication

UR - http://www.scopus.com/inward/record.url?scp=26444444315&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=26444444315&partnerID=8YFLogxK

M3 - Article

VL - 2947

SP - 28

EP - 40

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -