Welcome to the resource topic for
**2016/938**

**Title:**

Kummer for Genus One over Prime Order Fields

**Authors:**
Sabyasachi Karati, 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 in 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:={\sf KL2519(81,20)}, K_2:={\sf KL25519(82,77)} and K_3:={\sf KL2663(260,139)} over the three primes 2^{251}-9, 2^{255}-19 and 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 and K_2 are faster than those achieved by {\sf Sandy2x}, which is a highly optimised SIMD implementation in assembly of the well known {\sf Curve25519}; for example, on Skylake, variable base scalar multiplication on K_1 is faster than {\sf Curve25519} by about 30%. On Skylake, both fixed base and variable base scalar multiplication for K_3 are faster than {\sf Sandy2x}; whereas on Haswell, fixed base scalar multiplication for K_3 is faster than {\sf Sandy2x} while variable base scalar multiplication for both K_3 and {\sf 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 {\sf Curve25519}. 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 (qDSA) on all the three Kummer lines.

**ePrint:**
https://eprint.iacr.org/2016/938

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .