Christiane Peters (Eindhoven): Optimizing double-base elliptic-curve single-scalar multiplication

Many algorithms in Elliptic Curve Cryptography (ECC) require fast computation of a multiple of a given point. Speeding up single-scalar multiplication is therefore one of the most important research topics in ECC. In our work (to appear at Indocrypt 2007) we investigate several speed-up techniques such as choosing curve shapes and coordinate systems allowing fast arithmetic, using double-base chains as well as sliding-window methods and we show how those different techniques interact. Double-base chains are intended to speed up scalar multiplication by representing the scalar as a sum of weighted products of powers of 2 and 3. We consider various coordinate systems with fast addition, doubling and tripling formulas and we show how to choose the highest powers of 2 and 3 in the double-base representation in order to minimize the overall costs. In particular, in this talk we will give a brief overview on Edwards curves which were recently introduced as a representation of elliptic curves and provide very fast addition, doubling and tripling formulas.