Families of fast elliptic curves from Q-curves

2013/05/23 by Benjamin Smith, Smith, Benjamin · 1 citation
Computer Science · Mathematics · #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #cs.CR #math.NT

paper · pdf · doi:10.48550/arxiv.1305.5400

arxiv created 2013/05/23 · arxiv updated 2013/05/24

Abstract

We construct new families of elliptic curves over \(\FF_p²\) with efficiently computable endomorphisms, which can be used to accelerate elliptic curve-based cryptosystems in the same way as Gallant-Lambert-Vanstone (GLV) and Galbraith-Lin-Scott (GLS) endomorphisms. Our construction is based on reducing \(\QQ\)-curves-curves over quadratic number fields without complex multiplication, but with isogenies to their Galois conjugates-modulo inert primes. As a first application of the general theory we construct, for every \(p > 3\), two one-parameter families of elliptic curves over \(\FF_p²\) equipped with endomorphisms that are faster than doubling. Like GLS (which appears as a degenerate case of our construction), we offer the advantage over GLV of selecting from a much wider range of curves, and thus finding secure group orders when \(p\) is fixed. Unlike GLS, we also offer the possibility of constructing twist-secure curves. Among our examples are prime-order curves equipped with fast endomorphisms, with almost-prime-order twists, over \(\FF_p²\) for \(p = 2¹²⁷-1\) and \(p = 2²⁵⁵-19\).

Cited by

• The Q-curve construction for endomorphism-accelerated elliptic curves

Related

• The Q-curve construction for endomorphism-accelerated elliptic curves
• Four-Dimensional Gallant-Lambert-Vanstone Scalar Multiplication
• Constructing elliptic curves in almost polynomial time
• Faster computation of isogenies of large prime degree
• Efficiently computable endomorphisms for hyperelliptic curves