Kummer for Genus One over Prime Order Fields

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 in 2009 had suggested the use of the associated Kummer line to speed up scalar multiplication. In this work, we explore this idea in detail. The first task is to obtain an elliptic curve in 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 ladder step on the Kummer line supports parallelism and can be implemented very efficiently in constant time using the single-instruction multiple-data (SIMD) operations available in modern processors. For the 128-bit security level, this work presents three Kummer lines denoted as \(K_1:=\mathsf{KL2519(81,20)}\), \(K_2:=\mathsf{KL25519(82,77)}\) and \(K_3:=\mathsf{KL2663(260,139)}\) over the three primes \(2^{251}-9\), \(2^{255}-19\) and \(2^{266}-3\) respectively. Implementations of scalar multiplications for all the three Kummer lines using Intel intrinsics have been done and the code is publicly available. Timing results on the recent Skylake and the earlier Haswell processors of Intel indicate that both fixed base and variable base scalar multiplications for \(K_1\) and \(K_2\) are faster than those achieved by Sandy2x which is a highly optimised SIMD implementation in assembly of the well known Curve25519; for example, on Skylake, variable base scalar multiplication on \(K_1\) is faster than Curve25519 by about 25%. On Skylake, both fixed base and variable base scalar multiplication for \(K_3\) are faster than Sandy2x; whereas on Haswell, fixed base scalar multiplication for \(K_3\) is faster than Sandy2x while variable base scalar multiplication for both \(K_3\) and Sandy2x take roughly the same time. In fact, on Skylake, \(K_3\) is both faster and also offers about 5 bits of higher security compared to Curve25519. In practical terms, the particular Kummer lines that are introduced in this work are serious candidates for deployment and standardisation.