International Association
for Cryptologic Research

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 (Finite Fields Appl 15(2):246–260, 2009 ) had suggested the use of the associated Kummer line to speed up scalar multiplication. In the present 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. It 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 1 : = KL 2519 ( 81 , 20 ) , $$K_2:=\mathsf{KL25519(82,77)}$$ K 2 : = KL 25519 ( 82 , 77 ) and $$K_3:=\mathsf{KL2663(260,139)}$$ K 3 : = KL 2663 ( 260 , 139 ) over the three primes $$2^{251}-9$$ 2 251 - 9 , $$2^{255}-19$$ 2 255 - 19 and $$2^{266}-3$$ 2 266 - 3 , respectively. Implementations of scalar multiplications for all three Kummer lines using Intel intrinsics have been done, and the code is publicly available. Timing results on the Skylake and the Haswell processors of Intel indicate that both fixed base and variable base scalar multiplications for $$K_1$$ K 1 and $$K_2$$ K 2 are faster than those achieved by Sandy2x , which is a highly optimised SIMD implementation in assembly of the well-known Curve25519 . On Skylake, both fixed base and variable base scalar multiplications for $$K_3$$ K 3 are faster than Sandy2x , whereas on Haswell, fixed base scalar multiplication for $$K_3$$ K 3 is faster than Sandy2x while variable base scalar multiplication for both $$K_3$$ K 3 and Sandy2x takes roughly the same time. In practical terms, the particular Kummer lines that are introduced in this work are serious candidates for deployment and standardisation. We further illustrate the usefulness of the proposed Kummer lines by instantiating the quotient Digital Signature Algorithm on all the three Kummer lines.