Paper 2014/727

The Q-curve Construction for Endomorphism-Accelerated Elliptic Curves

Benjamin Smith

Abstract

We give a detailed account of the use of $\mathbb{Q}$-curve reductions to construct elliptic curves over ${\mathbb{F}}_{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. Like GLS (which is 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 for efficient implementation. Unlike GLS, we also offer the possibility of constructing twist-secure curves. We construct several one-parameter families of elliptic curves over $$ equipped with efficient endomorphisms for every $$, and exhibit examples of twist-secure curves over $$ for the efficient Mersenne prime $$.

Note: This is an extended version of the ASIACRYPT 2013 article "Families of fast elliptic curves from QQ-curves" (eprint 2013/312).