[Math] Under what conditions do all the points on an elliptic curve form a cyclic group? (And group cardinality attacks)

cryptographycyclic-groupselliptic-curves

Dear worshipped elliptic curve understanders,

I am currently trying to figure out how cryptosystems with elliptic curves work, particularly the Diffie-Hellman Key exchange on elliptic curves and the discrete logarithm problem. For this purpose I have been studying the book "Understanding Cryptography" by Christof Paar and Jan Pelzl. The book is written more for people who work with this in practice and not so much mathematicians, which is good on the one hand, but sometimes it is a little bit vague on certain details. For example there is one theorem:

The points on an elliptic curve, including $\mathcal{0}$ (point at infinity) have cyclic subgroups. Under certain conditions all points on an EC form a cyclic group.

However, these "certain conditions" are nowhere specified. Maybe someone could explain it to me? It does not have to be super-detailed, just a little bit more than "certain conditions".

Furthermore the book talks about, that it is very important to know the group cardinality, in order to thwart certain attacks regarding the cryptosystems build on the DLP in elliptic curves. But I don't know if by group cardinality they mean the number of points on the elliptic curve or the number of elements in the cyclic group, that we use to formulate the DLP, since the the theorem above states, that not always all points on an elliptic curve form a cyclic group. I would be very greatful if someone could explain some of these things to me 🙂

Kind regards
Likestobegreen

Best Answer

Fix an elliptic curve $E/\Bbb F_q$, where $\Bbb F_q$ is the finite field with $q$ elements. Then the set of points $E(\Bbb F_q)$ form a group, and because $\Bbb F_q$ is finite, $\# E(\Bbb F_q) = n$ is finite. Then $$ E(\Bbb F_q)\subseteq E[n](\overline{\Bbb F}_q) $$ ($E[n](\overline{\Bbb F}_q)$ denotes the set of $n$-torsion points of the elliptic curve in an algebraic closure of $\Bbb F_q$). This follows from Lagrange's theorem, as $E(\Bbb F_q)\subseteq E(\overline{\Bbb F}_q)$ is a subgroup. However, the structure of $E[n](\overline{\Bbb F}_q)$ is well known. For simplicity, let us assume that $n$ and $q$ are relatively prime. Then $$ E[n](\overline{\Bbb F}_q)\cong\Bbb Z/n\Bbb Z\times\Bbb Z/n\Bbb Z. $$ Using this, we get the following more precise version of what you stated:

Theorem: Let $E/\Bbb F_q$ be an elliptic curve, and suppose that $\#E(\Bbb F_q) = n$ is relatively prime to $q$. Then $E(\Bbb F_q)$ is either cyclic or isomorphic to the direct product of two cyclic groups.

In fact, one can even remove the hypothesis that $\#E(\Bbb F_q) = n$ is relatively prime to $q$ above. Of course, you wanted to know when this group is in fact cyclic. I don't know a complete classification, but this will at least provide you with some specific cases in which the group is cyclic.

Theorem: Let $E/\Bbb F_q$ be an elliptic curve, with $q = p^r$ for some prime $p$. Then $E(\Bbb F_q)$ is cyclic if one of the following conditions hold:

  1. $\# E(\Bbb F_q) = p^k$ for some integer $k$. (This is because $\# E[p^k](\overline{\Bbb F_q})$ is either trivial or isomorphic to $\Bbb Z/p^k\Bbb Z$, unlike when you look at $n$-torsion for $n$ prime to the characteristic of the field.)

  2. $E/\Bbb F_q$ is supersingular and $q = p\geq 5$ is prime with $q\equiv 1\pmod{4}$. (This is an exercise in Silverman's "The Arithmetic of Elliptic Curves.")

As for the importance of the cardinality, there are certain types of curves which are particularly vulnerable to attack:

  • Curves over $\Bbb F_{2^m}$ with $m$ composite are vulnerable to Weil descent attacks.
  • Curves such that $n$ divides $p^{B}-1$ (where $p$ is the characteristic of the field your curve lives over) for sufficiently small $B$ are vulnerable to Menezes–Okamoto–Vanstone (MOV) attack which applies usual Discrete Logarithm Problem (DLP) in a small degree extension field of $\mathbb {F} _{p}$ to solve the ECDLP. The bound $B$ should be chosen so that discrete logarithms in the field $\mathbb {F} _{p^{B}}$ are at least as difficult to compute as discrete logs on the elliptic curve $E(\mathbb {F} _{q})$.
  • Curves such that $\#E(\mathbb {F} _{q}) = q$ are vulnerable to the attack that maps the points on the curve to the additive group of $\mathbb {F} _{q}$.

As you can see, the last condition is a condition on the cardinality of $E(\Bbb F_q)$ (which in this case would be cyclic as I noted above, so it's both the cardinality of the group of points and the cyclic group in question). In general, one needs to know the cardinality of both $E(\Bbb F_q)$ and the cyclic subgroup you use, so I think you can assume that both cardinalities are important.

(Note: I'm not an expert in elliptic curve cryptography, and I'm stealing this information from the Wiki page on ECC. I suggest reading that page and the relevant sources for more information on this topic.)

Related Question