TY - GEN
T1 - Families of fast elliptic curves from ℚ-curves
AU - Smith, Benjamin
PY - 2013/12/1
Y1 - 2013/12/1
N2 - We construct new families of elliptic curves over Fp2 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 quadratic ℚ-curves (curves defined over quadratic number fields, without complex multiplic'ation, but with isogenies to their Galois conjugates) modulo inert primes. As a first application of the general theory we construct, for every prime p > 3, two one-parameter families of elliptic curves over double-struck Fp2 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 over double-struck Fp2, equipped with fast endomorphisms, and with almost-prime-order twists, for the particularly efficient primes p = 2127 - 1 and p = 2255 - 19.
AB - We construct new families of elliptic curves over Fp2 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 quadratic ℚ-curves (curves defined over quadratic number fields, without complex multiplic'ation, but with isogenies to their Galois conjugates) modulo inert primes. As a first application of the general theory we construct, for every prime p > 3, two one-parameter families of elliptic curves over double-struck Fp2 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 over double-struck Fp2, equipped with fast endomorphisms, and with almost-prime-order twists, for the particularly efficient primes p = 2127 - 1 and p = 2255 - 19.
KW - Elliptic curve cryptography
KW - GLS
KW - GLV
KW - endomorphisms
KW - exponentiation
KW - scalar multiplication
KW - ℚ-curves
UR - https://www.scopus.com/pages/publications/84892374815
U2 - 10.1007/978-3-642-42033-7_4
DO - 10.1007/978-3-642-42033-7_4
M3 - Conference contribution
AN - SCOPUS:84892374815
SN - 9783642420320
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 61
EP - 78
BT - Advances in Cryptology, ASIACRYPT 2013 - 19th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
T2 - 19th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2013
Y2 - 1 December 2013 through 5 December 2013
ER -