Super-Isolated Elliptic Curves and Abelian Surfaces in Cryptography

ABSTRACT

We call a simple abelian variety over ${\mathbb{F}}_p$ super-isolated if its (${\mathbb{F}}_p$-rational) isogeny class contains no other varieties. The motivation for considering these varieties comes from concerns about isogeny-based attacks on the discrete log problem. We heuristically estimate that the number of super-isolated elliptic curves over ${\mathbb{F}}_p$ with prime order and p ⩽ N is roughly $\tilde{\Theta }\left(\sqrt{N}\right)$. In contrast, we prove that there are only two super-isolated surfaces of cryptographic size and near-prime order.

KEYWORDS:

• number theory
• elliptic curve cryptography
• abelian varieties

2010 AMS SUBJECT CLASSIFICATION:

• 11T71
• 94A60
• 11G10

Acknowledgments

I would like to thank my advisor Neal Koblitz for all of his inspiration and guidance while working on this paper. I would also like to acknowledge the support from my graduate student peers, for which I am especially grateful.

Notes

3 In this paper, we use simple to mean simple over the base field. Other sources sometimes use the term to mean simple over the algebraic closure.

4 The statement of [Waterhouse 69, Thm. 3.5] refers to an order in ${End}_{{\mathbb{F}}_p}A\otimes \mathbb{Q}$, but this is the same as K since the base field is prime, see [Waterhouse 69, Ch. 2].

5 Cryptosystems usually use jacobians of hyperelliptic curves rather than arbitrary varieties because they provide efficient representations necessary for practical use [Koblitz 89].

6 There are a total of eight choices of signs we could use to define A. These come from the three choices of signs: one in equation (3–5(3--5) $$f_2(x_3,x_4)=\pm 1$$(3--5) ), one in equation (3–6(3--6) $$f_1(x_2,x_3,x_4)=\pm 1.$$(3--6) ), and one from the quadratic formula when solving equation (3–5(3--5) $$f_2(x_3,x_4)=\pm 1$$(3--5) ) for x₃. Every solution to equations (3–5(3--5) $$f_2(x_3,x_4)=\pm 1$$(3--5) )–(3–7(3--7) $$P_0(x_1,x_2,x_3,x_4)=0.$$(3--7) ) lies in one of these eight sets.