Skip to Main content Skip to Navigation
Conference papers

Families of fast elliptic curves from Q-curves

Benjamin Smith 1, 2 
1 GRACE - Geometry, arithmetic, algorithms, codes and encryption
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
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\).
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : Benjamin Smith Connect in order to contact the contributor
Submitted on : Thursday, May 23, 2013 - 1:13:59 PM
Last modification on : Thursday, January 20, 2022 - 5:28:41 PM
Long-term archiving on: : Saturday, August 24, 2013 - 5:40:09 AM


Files produced by the author(s)




Benjamin Smith. Families of fast elliptic curves from Q-curves. Advances in Cryptology - ASIACRYPT 2013, Dec 2013, Bangalore, India. pp.61-78, ⟨10.1007/978-3-642-42033-7_4⟩. ⟨hal-00825287⟩



Record views


Files downloads