6
$\begingroup$

I'm volunterely working for a crypto library and we're planning on adding Curve25519 support (finally). At the same point I had the idea of adding support for EdDSA in the same run.

Our library is highly modular, so the question needs to be asked:
Is there any (good) reason to limit the use of EdDSA solely to twisted Edwards curves?

According to the paper "EdDSA for more curves" by Bernstein, Lange et al. one can use any odd-prime field, however EdDSA is usually only being talked about in the context of Ed448 and Ed25519.

$\endgroup$
3
$\begingroup$

Strictly speaking EdDSA, as defined in "EdDSA for more curves" by Bernstein, Lange et al., can only work for (twisted) Edwards Curves.

Thus, IMHO, the correct answer your question is no.

In the paper, they define the curve parameters as being the parameters of a (twisted) Edwards curve, the addition law as the addition law on twisted Edwards curves, etc.

Note that even the base point $B$ is defined as lying on the (twisted) Edwards curve. This means that even if you have a curve birationally equivalent to a (twisted) Edwards you can't compute on the original curve, because the $R$ parameter of the signature will be a point lying on the equivalent (twisted) Edwards. (Well, of course you can convert input points on your curve and convert back the output to the twisted Edwards but this, in general, will have performance penalties)

If you, instead, allow a more elastic definition of EdDSA, then yes, the scheme is generic for any group, as Schnorr's signature scheme is (from which EdDSA is derived). The only reasons to stick to (twisted) Edwards are those related the the definition of "safe" curves used in safecurves' website, which, by the way, don't limit to the applicability of EdDSA, and are probably the reasons why the EdDSA authors restricted EdDSA to (twisted) Edwards.

I also believe EdDSA is commonly associated with Ed448 and Ed25519 because it's a new algorithm and it just has been applied to new curves.

But you can apply the same modification to Schnorr's signature scheme as done by EdDSA (e.g. use ECC, signature is $(\underline{R},\underline{S})$, use point encoding/compression, include encoded public key $\underline{A}$ in hash, have a deterministic generation of $r$, use key derivation from "secret key", etc.) without constraining to (twisted) Edwards.

Security proofs rely on the discrete log being hard. Since every curve defined over prime fields can be written in short Weierstrass form, the discrete log can't be easier for one family of curves, so you can't loose security just by using a non twisted Edwards curve.

Note: above I used "family" to mean the curve's shape. Of course discrete log is easier, in general, for e.g. supersingular of curves (where embedding degree is $\leq 6$ allowing efficient MOV attack), but that's independent of their shape. For example: $y^2 = x^3 + x$ over $\mathbb{F}_{19}$ is supersingular and has a point $(18,6)$ of order $4$, which makes the curve birationally equivalent to an Edwards curve by Theorem 3.3 of the Twisted Edwards Curve paper

$\endgroup$

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.