International Association for Cryptologic Research

International Association
for Cryptologic Research


Helmut Prodinger


Arithmetic of Supersingular Koblitz Curves in Characteristic Three
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.
Redundant $\tau$-adic Expansions I: Non-Adjacent Digit Sets and their Applications to Scalar Multiplication
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 non-adjacent 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+i-1}=\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$ non-adjacent 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\'opez-Dahab coordinates. The second set is suitable for low-memory 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.
Minimality of the Hamming Weight of the \tau-NAF for Koblitz Curves and Improved Combination with Point Halving
In order to efficiently perform scalar multiplications on elliptic Koblitz curves, expansions of the scalar to a complex base associated with the Frobenius endomorphism are commonly used. One such expansion is the $\tau$-adic NAF, introduced by Solinas. Some properties of this expansion, such as the average weight, are well known, but in the literature there is no proof of its {\em optimality}, i.e.~that it always has minimal weight. In this paper we provide the first proof of this fact. Point halving, being faster than doubling, is also used to perform fast scalar multiplications on generic elliptic curves over binary fields. Since its computation is more expensive than that of the Frobenius, halving was thought to be uninteresting for Koblitz curves. At PKC 2004, Avanzi, Ciet, and Sica combined Frobenius operations with one point halving to compute scalar multiplications on Koblitz curves using on average 14\% less group additions than with the usual $\tau$-and-add method without increasing memory usage. The second result of this paper is an improvement over their expansion, that is simpler to compute, and optimal in a suitable sense, i.e.\ it has minimal Hamming weight among all $\tau$-adic expansions with digits $\{0,\pm1\}$ that allow one halving to be inserted in the corresponding scalar multiplication algorithm. The resulting scalar multiplication requires on average 25\% less group operations than the Frobenius method, and is thus 12.5\% faster than the previous known combination.