Elliptic curves with j = 0,1728 and low embedding degree

Abstract

Elliptic curves over a finite field ${\mathbb{F}}_q$ with j-invariant 0 or 1728, both supersingular and ordinary, whose embedding degree k is low are studied. In the ordinary case we give conditions characterizing such elliptic curves with fixed embedding degree with respect to a subgroup of prime order ℓ. For $k=1,2$, these conditions give parameterizations of q in terms of ℓ and two integers m, n. We show several examples of families with infinitely many curves. Similar parameterizations for $k\ge 3$ need a fixed kth root of the unity in the underlying field. Moreover, when the elliptic curve admits distortion maps, an example is provided.

Keywords:

• elliptic curves
• embedding degree
• distortion maps
• pairing-based Cryptography
• Bateman-Horn's conjecture

2010 AMS Subject Classifications:

• 14H52
• 94A60

Acknowledgments

We thank the anonymous referee for the helpful comments and suggestions. An extended abstract including some results of this manuscript (only for elliptic curves with j-invariant 1728) was previously presented at the conference Recsi 2014, [18].

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work has been partially supported by the Spanish Ministerio de Ciencia e Innovacion under grants MTM2010-16051 and MTM2013-46949-P and MTM2014-55421-P.