The Q-curve construction for endomorphism-accelerated elliptic curves
This work addresses the need for secure and efficient elliptic curve cryptography by enabling a wider selection of curves and twist-secure options, representing an incremental improvement over existing methods like GLV and GLS.
The paper tackles the problem of constructing elliptic curves with efficiently computable endomorphisms to accelerate cryptosystems, resulting in one-parameter families of such curves over finite fields and examples of twist-secure curves for a specific Mersenne prime.
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 $\mathbb{F}\_{p^2}$ equipped with efficient endomorphisms for every $p \textgreater{} 3$, and exhibit examples of twist-secure curves over $\mathbb{F}\_{p^2}$ for the efficient Mersenne prime $p = 2^{127}-1$.