Paper 2008/148
Redundant $\tau$adic Expansions I: NonAdjacent Digit Sets and their Applications to Scalar Multiplication
Roberto M. Avanzi, Clemens Heuberger, and Helmut Prodinger
Abstract
This paper investigates some properties of $\tau$adic expansions of scalars. Such expansions are widely used in the design of scalar multiplication algorithms on Koblitz Curves, but at the same time they are much less understood than their binary counterparts. Solinas introduced the width$w$ $\tau$adic nonadjacent form for use with Koblitz curves. This is an expansion of integers $z=\sum_{i=0}^\ell z_i\tau^i$, where $\tau$ is a quadratic integer depending on the curve, such that $z_i\ne 0$ implies $z_{w+i1}=\ldots=z_{i+1}=0$, like the sliding window binary recodings of integers. It uses a redundant digit set, i.e., an expansion of an integer using this digit set need not be uniquely determined if the syntactical constraints are not enforced. We show that the digit sets described by Solinas, formed by elements of minimal norm in their residue classes, are uniquely determined. Apart from this digit set of minimal norm representatives, other digit sets can be chosen such that all integers can be represented by a width$w$ nonadjacent form using those digits. We describe an algorithm recognizing admissible digit sets. Results by Solinas and by Blake, Murty, and Xu are generalized. In particular, we introduce two new useful families of digit sets. The first set is syntactically defined. As a consequence of its adoption we can also present improved and streamlined algorithms to perform the precomputations in $\tau$adic scalar multiplication methods. The latter use an improvement of the computation of sums and differences of points on elliptic curves with mixed affine and LópezDahab coordinates. The second set is suitable for lowmemory applications, generalizing an approach started by Avanzi, Ciet, and Sica. It permits to devise a scalar multiplication algorithm that dispenses with the initial precomputation stage and its associated memory space. A suitable choice of the parameters of the method leads to a scalar multiplication algorithm on Koblitz Curves that achieves sublinear complexity in the number of expensive curve operations.
Metadata
 Available format(s)
 Category
 Implementation
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 publickey cryptographyKoblitz curvesFrobenius endomorphismScalar Multiplication$tau$adic expansionsNonAdjacentFormsDigit SetsPoint halving
 Contact author(s)
 clemens heuberger @ tugraz at
 History
 20080408: received
 Short URL
 https://ia.cr/2008/148
 License

CC BY
BibTeX
@misc{cryptoeprint:2008/148, author = {Roberto M. Avanzi and Clemens Heuberger and Helmut Prodinger}, title = {Redundant $\tau$adic Expansions I: NonAdjacent Digit Sets and their Applications to Scalar Multiplication}, howpublished = {Cryptology ePrint Archive, Paper 2008/148}, year = {2008}, note = {\url{https://eprint.iacr.org/2008/148}}, url = {https://eprint.iacr.org/2008/148} }