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 \(\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\).

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

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
elliptic curve cryptosystemimplementationnumber theory
Contact author(s)
smith @ lix polytechnique fr
History
2014-09-19: received
Short URL
https://ia.cr/2014/727
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/727,
      author = {Benjamin Smith},
      title = {The Q-curve Construction for Endomorphism-Accelerated Elliptic Curves},
      howpublished = {Cryptology ePrint Archive, Paper 2014/727},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/727}},
      url = {https://eprint.iacr.org/2014/727}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.