Paper 2013/705

Symmetric Digit Sets for Elliptic Curve Scalar Multiplication without Precomputation

Clemens Heuberger and Michela Mazzoli

Abstract

We describe a method to perform scalar multiplication on two classes of ordinary elliptic curves, namely $E: y^2 = x^3 + Ax$ in prime characteristic $p\equiv 1$ mod~4, and $E: y^2 = x^3 + B$ in prime characteristic $p\equiv 1$ mod 3. On these curves, the 4-th and 6-th roots of unity act as (computationally efficient) endomorphisms. In order to optimise the scalar multiplication, we consider a width-$w$-NAF (non-adjacent form) digit expansion of positive integers to the complex base of $\tau$, where $\tau$ is a zero of the characteristic polynomial $x^2 - tx + p$ of the Frobenius endomorphism associated to the curve. We provide a precomputationless algorithm by means of a convenient factorisation of the unit group of residue classes modulo $\tau$ in the endomorphism ring, whereby we construct a digit set consisting of powers of subgroup generators, which are chosen as efficient endomorphisms of the curve.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
elliptic curve cryptosystemimplementationnumber theoryscalar multiplicationFrobenius endomorphisminteger digit expansionsdigit sets$\tau$-adic expansionwidth-$w$ non-adjacent formGaussian integersEisenstein integers
Contact author(s)
clemens heuberger @ aau at
History
2013-11-03: received
Short URL
https://ia.cr/2013/705
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/705,
      author = {Clemens Heuberger and Michela Mazzoli},
      title = {Symmetric Digit Sets for Elliptic Curve Scalar Multiplication without Precomputation},
      howpublished = {Cryptology ePrint Archive, Paper 2013/705},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/705}},
      url = {https://eprint.iacr.org/2013/705}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.