## Cryptology ePrint Archive: Report 2013/312

Families of fast elliptic curves from Q-curves

Benjamin Smith

Abstract: We construct new families of elliptic curves over $\FF_{p^2}$ 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^2}$ 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^2}$ for $p = 2^{127}-1$ and $p = 2^{255}-19$.

Category / Keywords: Elliptic curve cryptography, endomorphisms, GLV, GLS, exponentiation, scalar multiplication, Q-curves

Date: received 23 May 2013

Contact author: smith at lix polytechnique fr

Available format(s): PDF | BibTeX Citation

Short URL: ia.cr/2013/312

[ Cryptology ePrint archive ]