2
$\begingroup$

I need some guidance on elliptic curves that support signing and key agreement.

I am trying to develop a protocol for sending encrypted, deniably authenticated messages. To do this I will sign the message with a 2-key ring signature using the sender's signing key and the recipient's encryption key.

Is there a sensible elliptic curve to use for this? Ideally it would meet the safe curves standards and provide the same level of security as Curve25519 (i.e. 256 bit length / 128 bit security).

Ed448-Goldilocks looks like it fits the bill as a curve intended to support both functions but is there anything more lightweight?

Improve this question
$\endgroup$
5
  • $\begingroup$ What's wrong with Curve25519? $\endgroup$
    – SEJPM
    Jan 15, 2017 at 22:36
  • $\begingroup$ I don't know. That's one reason I'm asking the question. I'm having a hard time tracking down any literature that gives a good account of why there are separate Bernstein curves for signing (Ed25519) and key agreement (Curve25519). $\endgroup$
    – geoff_h
    Jan 15, 2017 at 22:47
  • 1
    $\begingroup$ @geoff_h Ed25519 refers to a signature system. The curve it uses to create those signatures is isomorphic to Curve25519, so they are abstractly the same curve — only the representation is different. In any case, ring signatures seem overkill for your purpose: Once you have a shared key, can't you just use public-key authenticators, as is for instance done in NaCl's crypto_box? $\endgroup$
    – yyyyyyy
    Jan 15, 2017 at 23:11
  • $\begingroup$ Ok. But can you point me at a rationale for using different isomorphisms? I believe you and it's my understanding as well but I'd like to understand the split before taking that route. Thanks. $\endgroup$
    – geoff_h
    Jan 15, 2017 at 23:19
  • 2
    $\begingroup$ Nitpick: the curves are birationally equivalent, not isomorphic. $\endgroup$
    – CurveEnthusiast
    Jan 16, 2017 at 8:11

1 Answer 1

Reset to default
4
$\begingroup$

Technically, any elliptic curve can support both signing and key agreement. However, Curve25519 as described in the original paper is meant for $x$-only arithmetic. This means that one never computes the $y$-coordinate. The issue is that you need the $y$-coordinate for signature verification in the standard algorithms (ECDSA, EdDSA).

Therefore, if you want to do signatures with the Curve25519 curve, you need to compute the $y$-coordinate. There are different ways to do this, one is to simply leave the curve as is (in "Montgomery form") and compute its $y$-coordinate. A different way, is to transform the curve into a new shape (the "twisted Edwards form") and do arithmetic there. This new curve is called Ed25519, and it is "(birationally) equivalent" to the old curve. There are even more flavours.

Again, the choice you make will be for efficiency and security. Not because one curve can be used for signatures while the other can't. I suppose the $y$-coordinate computation on Curve25519 is slow enough for people to prefer using Ed25519 instead.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ A minor detail: computing the $y$-cordinate on Montgomery curves costs only about 13 Multiplications. The issue is that in verification you need a full point addition which is not present in the Montgomery ladder, so you need to add code for that, and it has exceptions (when adding $P+P$, $P+\infty$, etc.). Furthermore for efficiency montgomery ladder is good for variable base but in signature you might use fixed based and in verification double base, and both favors Edwards. $\endgroup$
    – Ruggero
    Jan 16, 2017 at 10:41
  • $\begingroup$ @Ruggero Not sure if I would say "only", 13 multiplications is not cheap. I like your comment about fixed-base, which indeed influences the efficiency a lot. $\endgroup$
    – CurveEnthusiast
    Jan 16, 2017 at 11:54
  • 2
    $\begingroup$ Actually, you don't need to compute the full point addition, at the cost of a single bit of security. See Joost Renes and Benjamin Smith, ‘qDSA: Small and Secure Digital Signatures with Curve-based Diffie-Hellman Key Pairs’, IACR Cryptology ePrint Archive: Report 2017/518 for details, which explains the x-only Curve25519 Montgomery signatures in Mike Hamburg's STROBE. $\endgroup$
    – Squeamish Ossifrage
    Aug 27, 2017 at 16:01
  • 1
    $\begingroup$ @SqueamishOssifrage Agreed, I like the paper but it only came out a couple of months after my answer! :-) $\endgroup$
    – CurveEnthusiast
    Sep 5, 2017 at 0:16

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.