Clemens Heuberger: Signed digit expansions in quadratic number fields with applications in cryptography

This is a joint work with Roberto M. Avanzi and Helmut Prodinger.

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, the digit expansions have to be made with respect to a quadratic algebraic integer base. Optimal expansions as well as their analysis will be discussed.

Back to the Index