## CryptoDB

### Clemens Heuberger

#### Publications

**Year**

**Venue**

**Title**

2011

PKC

2010

EPRINT

Arithmetic of Supersingular Koblitz Curves in Characteristic Three
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.

2008

EPRINT

Unbalanced Digit Sets and the Closest Choice Strategy for Minimal Weight Integer Representations
Abstract

An online algorithm is presented that produces an optimal radix-2 representation of an input integer $n$ using digits from the set $D_{\ell,u}=\{a\in\Z:\ell\le a\le u\}$, where $\ell \leq 0$ and $u \geq 1$. The algorithm works by scanning the digits of the binary representation of $n$ from left-to-right (\ie from most-significant to least-significant). The output representation is optimal in the sense that, of all radix-2 representations of $n$ with digits from $D_{\ell,u}$, it has as few nonzero digits as possible (\ie it has \emph{minimal weight}). Such representations are useful in the efficient implementation of elliptic curve cryptography. The strategy the algorithm utilizes is to choose an integer of the form $d 2^i$, where $d \in D_{\ell,u}$, that is closest to $n$ with respect to a particular distance function. It is possible to choose values of $\ell$ and $u$ so that the set $D_{\ell,u}$ is unbalanced in the sense that it contains more negative digits than positive digits, or more positive digits than negative digits. Our distance function takes the possible unbalanced nature of $D_{\ell,u}$ into account.

2008

EPRINT

Redundant $\tau$-adic Expansions I: Non-Adjacent Digit Sets and their Applications to Scalar Multiplication
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 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.

2008

EPRINT

Redundant $\tau$-adic Expansions II: Non-Optimality and Chaotic Behaviour
Abstract

When computing scalar multiples on Koblitz curves, the Frobenius endomorphism can be used to replace the usual doublings on the curve. This involves digital expansions of the scalar to the complex base $\tau=(\pm 1\pm \sqrt{-7})/2$ instead of binary expansions. As in the binary case, this method can be sped up by enlarging the set of valid digits at the cost of precomputing some points on the curve. In the binary case, it is known that a simple syntactical condition (the so-called $w$-NAF-condition) on the expansion ensures that the number of curve additions is minimised. The purpose of this paper is to show that this is not longer true for the base $\tau$ and $w\in\{4,5,6\}$. Even worse, it is shown that there is no longer an online algorithm to compute an optimal expansion from the digits of some standard expansion from the least to the most significant digit, which can be interpreted as chaotic behaviour. The proofs heavily depend on symbolic computations involving transducer automata.

2006

EPRINT

Minimal Weight and Colexicographically Minimal Integer Representations
Abstract

Redundant number systems (e.g. signed binary representations) have
been utilized to efficiently implement algebraic operations required
by public-key cryptosystems, especially those based on elliptic
curves. Several families of integer representations have been
proposed that have a minimal number of nonzero digits (so-called
\emph{minimal weight} representations). We observe that many of the
constructions for minimal weight representations actually work by
building representations which are minimal in another sense. For a
given set of digits, these constructions build
\emph{colexicographically minimal} representations; that is, they
build representations where each nonzero digit is positioned as far
left (toward the most significant digit) as possible. We utilize
this strategy in a new algorithm which constructs a very general
family of minimal weight dimension-$d$ \emph{joint} representations
for any $d \geq 1$. The digits we use are from the set $\{a \in
\ZZ: \ell \leq a \leq u\}$ where $\ell \leq 0$ and $u \geq 1$ are
integers. By selecting particular values of $\ell$ and $u$, it is
easily seen that our algorithm generalizes many of the minimal
weight representations previously described in the literature. From
our algorithm, we obtain a syntactical description of a particular
family of dimension-$d$ joint representations; any representation
which obeys this syntax must be both colexicographically minimal and
have minimal weight; moreover, every vector of integers has exactly
one representation that satisfies this syntax. We utilize this
syntax in a combinatorial analysis of the weight of the
representations.

2005

EPRINT

Minimality of the Hamming Weight of the \tau-NAF for Koblitz Curves and Improved Combination with Point Halving
Abstract

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.

#### Coauthors

- Roberto Maria Avanzi (4)
- James A. Muir (2)
- Helmut Prodinger (3)