9
$\begingroup$

For elliptic curve cryptography, I seem to keep coming across curves with either co-factors of 4 or 8 whenever it is a non-prime order group.

Is this a co-incidence? Have we studied ECC for curves which produce cofactor = 3 for example?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
10
$\begingroup$

Having a cofactor $h > 1$ does not inherently provide an advantage; in addition, it has these small disadvantages:

  • It reduces the expected effort of an attacker to solve the ECDLog problem by a factor of $\sqrt{h}$ (over a curve with approximately same size group order, and $h=1$)

  • We then have to worry about "what if the adversary passes us a point that's not in the prime-order subgroup" (and how much of a concern that is depends on where we're using the curve).

Both of these are actually fairly minor; however if we're using the standard Weierstrass curve addition routines, there's no reason to put up with them at all - he can just as easily pick a curve that has $h=1$, and avoid these minor issues.

So, why do we use curves with $h>1$? Well, that's mostly because we want to use curves from more limited curve families (such as Montgomery and Edwards) and use that point addition logic associated with those equations - both Edwards curves and Montgomery curves always have $h$ a multiple of 4 (as they always has a point of order 4); the advantages of the Edwards and Montgomery point addition logic is seen to be a good trade-off (compared to the rather minor disadvantages of having $h>1$).

Have we studied ECC for curves which produce cofactor = 3 for example?

Do you know of a family of elliptic curves that always include a point of order 3? Do those curves have some advantage over other elliptic curves?

Improve this answer
$\endgroup$
4
  • $\begingroup$ This answer is missing something: it is mathematically impossible to produce a prime order curve without compromising somewhat on twist security. Since twist security is valued more highly than prime order, we settle for curves with small cofactors that have uncompromised twist security. $\endgroup$
    – djao
    Jul 6, 2019 at 19:56
  • $\begingroup$ @djao: sorry for my ignorance, but I thought that "twist security" meant "the twist is also a secure elliptic curve" - I didn't think there was anything prohibiting both the curve and the twist from having prime orders. Is there something else that I'm missing (e.g. one of the two must be vulnerable to MOV if they are both prime?) $\endgroup$
    – poncho
    Jul 6, 2019 at 21:44
  • $\begingroup$ Oh yeah, you're right, my bad. What I should have said was something entirely different: we don't really always care about having Edwards curves, but we do always care about having Edwards or Montgomery curves, and this is what precludes prime order. For a Montgomery/Edwards curve, the best you can do is cofactor 4 for one curve and 8 for the twist curve, which is why 4 and 8 always appear. Here is the relevant table: safecurves.cr.yp.to/ladder.html $\endgroup$
    – djao
    Jul 7, 2019 at 15:09
  • $\begingroup$ @djao: fair enough - I shouldn't have limited my answer to imply that Edwards curves were the only family (other than the general Weierstass) that we were interested in... $\endgroup$
    – poncho
    Jul 7, 2019 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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