# the probability of sampling a group element that falls in the subgroup on elliptic curve

Given an elliptic curve $$E$$ on $$Z_q$$. There is a subgroup $$$$ on $$E$$, and the order of $$$$ is $$p$$, where $$p$$ is a prime. And the discrete log problem on $$$$ is hard. Now we randomly sample a group element $$G_0$$ of $$E$$. Let $$Q$$ be the event that $$G_0$$ falls in $$$$. Can we say that the probability that $$Q$$ happens is negligible?

• Only if $<G>$ is negligibly small compared to $E$. For the elliptic curves used in crypto, the topic here, that is never the case, but for the more general topic of elliptic curves in mathematics it can be. Feb 12, 2021 at 4:11
• But the elliptic curve on $Z_q$ should be isomorphic to a finite cyclic group or direct sum of two finite cyclic subgroups. If the elliptic curve used in crypto is isomorphic to two finite cyclic subgroups and the smaller one is used as the cryptographic group, I think it is possible. Assume here the size of the cryptographic group is $p$, Then the whole size of the elliptic curve should be larger than $p^2$(the size of the smaller sub-group should divide the size of the larger group). Then the probability that $Q$ happens should be smaller than $p/p^2=1/p$, which is negligible. What's wrong? Feb 12, 2021 at 6:02
• (Can't fully explain in comment, see answer.) Feb 12, 2021 at 11:40
• The problem is not random, rather the attacker may control it. See: Curve25519 Key Validation, Lim-Lee small subgroup attack and the twist attack are the cases. Feb 12, 2021 at 16:08
• Got it. Thank you! Feb 13, 2021 at 2:27

Yes, every finite group (including an elliptic curve over a finite field) either is a finite cyclic group or is the product (not sum) of at least two (not exactly two) finite cyclic groups, and in the latter case some (or even all) of those subgroups may be relatively small. But for crypto we only use a prime-order subgroup that is large enough to satisfy a specified security parameter, which in practice is set close to the size of the full group of the curve (and also close to the size of the underlying field, per Hasse's theorem). For example the widely-used X9/NIST/SECG curves over $$F_p$$ were chosen to have prime order, so the only subgroup is the full group and any point chosen as G has that order; this is also stated as having cofactor 1. Bernstein et al's Curve25519 has a full group of order near $$2^{255}$$ and uses a subgroup of order near $$2^{252}$$, also stated as cofactor 8; this is not negligible.