Paper 2010/436

Arithmetic of Supersingular Koblitz Curves in Characteristic Three

Roberto Avanzi, Clemens Heuberger, and Helmut Prodinger

Abstract

We consider digital expansions of scalars for supersingular Koblitz curves in characteristic three. These are positional representations of integers to the base of $\tau$, where $\tau$ is a zero of the characteristic polynomial $T^2 \pm 3\,T + 3$ of a Frobenius endomorphism. They are then applied to the improvement of scalar multiplication on the Koblitz curves. A simple connection between $\tau$-adic expansions and balanced ternary representations is given. Windowed non-adjacent representations are considered whereby the digits are elements of minimal norm. We give an explicit description of the elements of the digit set, allowing for a very simple and efficient precomputation strategy, whereby the rotational symmetry of the digit set is also used to reduce the memory requirements. With respect to the current state of the art for computing scalar multiplications on supersingular Koblitz curves we achieve the following improvements: \rm{(i)} speed-ups of up to 40\%, \rm{(ii)} a reduction of memory consumption by a factor of three, \rm{(iii)} our methods apply to all window sizes without requiring operation sequences for the precomputation stage to be determined offline first. Additionally, we explicitly describe the action of some endomorphisms on the Koblitz curve as a scalar multiplication by an explicitly given integer.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
elliptic curve cryptosystemimplementationsupersingular Koblitz curvesscalar multiplication
Contact author(s)
clemens heuberger @ tugraz at
History
2010-08-13: received
Short URL
https://ia.cr/2010/436
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/436,
      author = {Roberto Avanzi and Clemens Heuberger and Helmut Prodinger},
      title = {Arithmetic of Supersingular Koblitz Curves in Characteristic Three},
      howpublished = {Cryptology ePrint Archive, Paper 2010/436},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/436}},
      url = {https://eprint.iacr.org/2010/436}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.