Curve25519 vs "Million Dollar Curve"

Question

Quoting from the Million Dollar Curve website:

By using publicly verifiable randomness produced in February 2016 by many national lotteries from all around the world, we propose to generate a cryptographically secure elliptic curve for the ECDH cryptosystem as an alternative to the NIST P-256 and the Curve25519 curves.

[...]

Today most of elliptic-curve cryptography relies on the same set of curves: ANSSI FRP256v1, NIST P-256, NIST P-384, Curve25519, secp256k1, brainpoolP256t1, Curve1174 and a few others.

However, most of these curves parameters generation processes contain unjustified choices, specific constants or specific hash algorithms. [...]

I understand the concerns over how NIST generated their curve parameters, and this does seem like a better approach. However, I didn't think Curve25519 had any suspicious constants or design decisions. What exactly is the benefit of using the "Million Dollar Curve" over Curve25519 (if there is a benefit)?

Answer 1

It's not related to the possibility of backdoors in curve25519, no one thinks that curve25519 can have backdoors. It's related to having a trusted procedure to generate publicly verifiable random numbers, which is an interesting thing to have, not only related to elliptic curves.

There is the need for a way to generate curves, any possible way is arbitrary. You can lower the number of degree of freedom (see the bada55 paper), but at the end some choices need to be made and people can have different preferences. These are not only related to the (unlikely) possibility of having backdoors but mostly related to more or less conservative options for curves.

For example, taking the case of curve25519, Bernstein made some choices with Curve25519 with the purpose of achieving efficient implementation, particularly with the choice of the prime $2^{255}-19$, which is a pseudo-Mersenne prime, and it is not congruent to $3 \mod 4$, which is a very common choice as these primes allow an efficient square root calculation and a better cofactor for the twist curve(see "twist security" in 6.1 of the million dollar curve paper). Basically he says that the curve is rigid because it is the fastest among those with a similar security level. But speed depends on implementations and platforms and one might wonder if this is a good way to measure rigidity.

His method doesn't allow for an algorithm to generate curves at arbitrary security levels, therefore some people might prefer to have a procedure, more than a curve, that they can trust. I think this is one of the advantages of the "million dollar curve" project.

Others have argued that having a prime whose bitsize is not a power of two is strange because it doesn't meet the usual definition of security level. In fact, in the common definition of security level, curve25519 doesn't meet the 128 bit security level, see this answer.

That is why, for example, Microsoft NUMS curves requires a prime of 256 bit for a 128 bit security level.

Others, again, tends to prefer random primes (e.g. Brainpool), and not primes of special form. Random primes have some advantages (over pseudo-mersenne prime) when protection against side-channel is required, and are considered a more conservative choice (because they don't belong to a family they are not subject to some possible attack exploiting properties of that family. Not that such an attack exists on Elliptic Curves, but it exists for multiplicative groups).

I think it is an interesting project, but it's not going to replace curve25519 or P-256 in implementations or protocols.