Cryptology ePrint Archive: Report 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 \(\mathbb{F}_{p^2}\) equipped with efficient endomorphisms for every \(p > 3\), and exhibit examples of twist-secure curves over \(\mathbb{F}_{p^2}\) for the efficient Mersenne prime \(p = 2^{127}-1\).

Category / Keywords: implementation / elliptic curve cryptosystem, implementation, number theory

Date: received 18 Sep 2014

Contact author: smith at lix polytechnique fr

Available format(s): PDF | BibTeX Citation

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

Version: 20140919:211648 (All versions of this report)

Short URL: ia.cr/2014/727

Discussion forum: Show discussion | Start new discussion