Digital expansions in quadratic algebraic number fields and their applications in cryptography

Clemens Heuberger

Technische Universität Graz, Austria

Elliptic curve cryptography relies on the fact that multiples $nP$ of a point $P$ can be computed easily, whereas the inverse problem (discrete logarithm on elliptic curves) seems to be hard. Since subtraction on elliptic curves is as cheap as addition, scalar multiplication can be done using a double, add and subtract algorithm using a binary expansion with digits 0, $\pm 1$. On special Koblitz curves, the doublings can be avoided by using the Frobenius endomorphism. In that case, digital expansions have to a quadratic algebraic integer base replace the binary expansion.

We introduce several digit sets that are useful in this context and discuss their properties. We also investigate the effect of using number systems with a rather large set of digits, where uniqueness is achieved by imposing additional syntactical properties.

Supported by the Austrian Science Foundation FWF, project S9606, that is part of the Austrian National Research Network ``Analytic Combinatorics and Probabilistic Number Theory.''