Paper 2016/938

Kummer for Genus One over Prime Order Fields

Sabyasachi Karati and Palash Sarkar

Abstract

This work considers the problem of fast and secure scalar multiplication using curves of genus one defined over a field of prime order. Previous work by Gaudry and Lubicz had suggested the use of the associated Kummer line to speed up scalar multiplication. In this work, we explore this idea in details. The first task is to obtain an elliptic curve in the Legendre form which satisfies necessary security conditions such that the associated Kummer line has small parameters and a base point with small coordinates. In turns out that the Kummer ladder supports parallelism and can be implemented very eficiently in constant time using the single-instruction multiple-data (SIMD) operations available in modern processors. This work presents appropriate Kummer lines over three primes, namely, $2^{251}-9$, $2^{255}-19$ and $2^{266}-3$ all of which are targeted at the 128-bit level. Implementation of scalar multiplication for all three Kummer lines using Intel intrinsics have been done. Timing results indicate that scalar multiplication using all three of these Kummer lines are faster than the best known highly optimised assembly implementation of the well known Curve25519. In fact, the Kummer line over $2^{266}-3$ is both faster and others about 6 bits of higher security compared to Curve25519. As part of our work, we describe a new multiplication algorithm modulo $2^{255}-19$ which, given the importance of Curve25519, should be of some independent interest.