2
$\begingroup$

I am currently trying to implement a cryptographic scheme. For this purpose I need a group of prime order in which the discrete logarithm problem is hard.

For now, I have been using a subgroup of prime order q over the Integers mod p, where p=2q+1, p prime, q prime. (p about 2048-4096 bits) The parameters for the groups are based on the primes given in RFC3526.

I would like to also try the scheme over elliptic curves. I'm aware of https://safecurves.cr.yp.to which lists and classifies a lot of different curves. However the information of whether the curve is of prime order is missing there. I've tried some of the popular curves like Curve25519 with Sagemath, however e. g. Curve25519 appears not to be of prime order, only the NIST curve (which have uncertain seed origin) are working.

So my question is basically: Are there any 'safe' and well-established elliptic curves of prime order? (If the answer is yes then where to find them? And if the answer is no, then why not and what's so special about the NIST curves then).

Thanks for your help in advance. I'm quite new to the topic, please don't hesitate asking if anything is unclear.

$\endgroup$
4
  • 5
    $\begingroup$ While the curves may not have prime order, certain points can generate subgroups of prime order which would suite your needs. $\endgroup$
    – SEJPM
    Mar 3, 2017 at 17:02
  • 2
    $\begingroup$ The safecurves website is quite misleading. Prime order curves are not always unsafe, which the website claims to be the case. $\endgroup$ Mar 4, 2017 at 0:07
  • $\begingroup$ Prime order curves have important uses in distributed homomorphic computing and shamir schemes. I suspect they will be the dominant curves in time. $\endgroup$ Jun 4, 2018 at 14:30
  • $\begingroup$ @ErikAronesty could you point me at the sort of ECC your talking about? My googling failed to turn it up. $\endgroup$
    – qbt937
    Jan 15, 2020 at 7:09

2 Answers 2

6
$\begingroup$

Are there any 'safe' and well-established elliptic curves of prime order?

Depends on what you mean by 'safe'. If you use Dan Bernstein's definition of "safe curve", no; the curves they list as safe are Edwards curve, which always have a point of order 2 (and hence can't be of prime order).

As for proposed curves that are of prime order, there's the NIST curves that you know about, there's the Brainpool curves, and there are the Weierstrass flavor of the NUMS curves. Whether they are 'well-established' is questionable; they each certainly have their proponents.

Also, it's not clear that you really need a prime order curve. The multiplicative group $Z^*_p$ you're using isn't of prime order either, you manage to work in a prime order subgroup. The elliptic curves we use for cryptography have large prime order subgroups (to make the discrete log program hard), perhaps you can use the same trick to use, say, Curve25519.

$\endgroup$
4
  • 1
    $\begingroup$ Thanks for your answer, now I understand. In fact I'm not using the multiplicative group Zp* but rather a multiplicative subgroup of prime order q over Zp (e.g. { 1, g, g^2, ... g^(q-1) mod p } with g=2. I've just checked, the same trick should work for Curve25519. $\endgroup$
    – raisyn
    Mar 3, 2017 at 23:08
  • 2
    $\begingroup$ Small clarification: the NIST/Certicom Fp curves are prime order; the wildly unpopular F2^m curves have cofactor 2 or 4. $\endgroup$ Mar 4, 2017 at 11:53
  • $\begingroup$ @dave_thompson_085: thanks for the correction; I never remember about those... $\endgroup$
    – poncho
    Mar 4, 2017 at 14:03
  • $\begingroup$ There are lots of applications that require prime order groups, like dPRF's. most of Bernsteins 'safe curves' are not very useful for distributed homomorphic computation, encrypted search, and a basically a whole slew of techniques. $\endgroup$ Jun 4, 2018 at 14:18
1
$\begingroup$

The family of Barreto-Naehrig curves (described in this paper) have prime order if you choose the parameters properly, and the group consisting of the roots of unity (which are guaranteed to lie in the degree twelve extension of the field) is large enough for the discrete log problem to be hard. The curves are also "pairing-friendly".

Subsequent papers by Naehrig et al. and Beuchat et al. describe parameter choices that yield particular curves of prime order. They also describe fast implementations of the optimal Ate pairing for those curves, in case that might be of interest.

$\endgroup$

Your Answer

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

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