0
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Feb 12 at 4:11
  • $\begingroup$ 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? $\endgroup$
    – user77340
    Feb 12 at 6:02
  • $\begingroup$ (Can't fully explain in comment, see answer.) $\endgroup$ Feb 12 at 11:40
  • $\begingroup$ 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. $\endgroup$
    – kelalaka
    Feb 12 at 16:08
  • $\begingroup$ Got it. Thank you! $\endgroup$
    – user77340
    Feb 13 at 2:27
1
$\begingroup$

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.

If a cryptographic scheme (or implementation of one) that intends to use such a sufficiently-large but proper subgroup fails to ensure or verify that elements (for EC points) purported to be in the subgroup actually are, an attacker may be able to cause it to use values constrained to one of the small subgroups, and thereby gain an advantage; these are generically called small-subgroup attacks and you will find quite a few existing Qs and As about them. 25519 makes privatekeys a multiple of 8 to block this.

That's why your question makes sense for EC mathematics, but not for EC crypto as practiced.

$\endgroup$
2
  • $\begingroup$ Ok, I understood. Thank you so much! $\endgroup$
    – user77340
    Feb 12 at 13:28
  • $\begingroup$ You claim "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". But I think it is just exactly two finite cyclic groups, if not one. It will not be more than two. It is due to a theorem 4.1 in the book 《Elliptic Curves Number Theory and Cryptography》, Washington $\endgroup$
    – user77340
    Feb 20 at 3:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.