# Families of fast elliptic curves from Q-curves

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$$.
Keywords :
Document type :
Conference papers
Kazue Sako; Palash Sarkar. Advances in Cryptology - ASIACRYPT 2013, Dec 2013, Bangalore, India. Springer, 8269, pp.61-78, 2013, Lecture Notes in Computer Science. 〈10.1007/978-3-642-42033-7_4〉
Domain :

Cited literature [26 references]

https://hal.inria.fr/hal-00825287
Contributor : Benjamin Smith <>
Submitted on : Thursday, May 23, 2013 - 1:13:59 PM
Last modification on : Thursday, May 10, 2018 - 2:06:24 AM
Document(s) archivé(s) le : Saturday, August 24, 2013 - 5:40:09 AM

### Files

qc-hal.pdf
Files produced by the author(s)

### Citation

Benjamin Smith. Families of fast elliptic curves from Q-curves. Kazue Sako; Palash Sarkar. Advances in Cryptology - ASIACRYPT 2013, Dec 2013, Bangalore, India. Springer, 8269, pp.61-78, 2013, Lecture Notes in Computer Science. 〈10.1007/978-3-642-42033-7_4〉. 〈hal-00825287〉

Record views