2
$\begingroup$

I have an application that would benefit from very small (e.g. 16-20 byte) EDDSA keys and small signatures. It's an application where the goal is more to deter DOS attacks than "hard" security, so having the signature be attackable by someone with a lot of resources is not a huge problem. (Full ed25519 or similar are used for the real security parts of the system.)

How would one go about generating such a curve? Or is this an extremely nontrivial thing to do? I can find some sample code for general EDDSA but no curves other than 25519 and 448. This makes sense since small curves wouldn't have many use cases, but I have one. :)

Right now I have sample code using traditional ECDSA with the Brainpool P-160t curve. It works but I'm wondering if an Edwards curve would be faster and would offer better security with an even smaller key and signature size.

$\endgroup$
  • 1
    $\begingroup$ This thesis could be a starting point. $\endgroup$ – puzzlepalace Feb 12 at 19:24
  • $\begingroup$ It seems you want Edwards to be safer and faster than Brainpool. Speed requires a dedicated implementation. Do you need an implementation or a curve for which a fast implementation can be developed ? $\endgroup$ – Ruggero Feb 13 at 13:01
  • $\begingroup$ That would be nice, but actually implementing an Edwards curve is a bit over my head and far beyond my time budget. I'm probably going to just go with Brainpool since it will work just fine. $\endgroup$ – Adam Ierymenko Feb 13 at 15:25
  • $\begingroup$ BTW the application is this: I want to be able to have key owners in a distributed key/value store assign key=value entries where the key is masked (a hash of a plain text key). But I want to prevent someone from assigning a bogus entry for a masked key. So if I define hash(plain key) to be a public key in a deterministic key pair then sign the message with it, I can prove knowledge of the key without revealing it. If someone managed to defeat this measure it wouldn't be catastrophic but it might allow certain kinds of denial of service attacks against certain use cases. $\endgroup$ – Adam Ierymenko Feb 13 at 15:25
  • $\begingroup$ I realize there are other more sophisticated proof-of-knowledge schemes but this one (from what I can find) seems simpler for this use case and is built on more standard primitives. $\endgroup$ – Adam Ierymenko Feb 13 at 15:27
1
$\begingroup$

After more Googling I found a paper called "A note on high-security general-purpose elliptic curves" which contains some "legacy strength" Edwards curves that might work. Thought I'd self-answer in case anyone else ever needs something like this.

$\endgroup$
  • 1
    $\begingroup$ A nice find, but can we please ask you to summarize or quote some basic ideas from the linked paper? Otherwise if the link ever dies (which happens more often than one might think) this answer will cease to be helpful. $\endgroup$ – Ella Rose Feb 12 at 19:48
  • $\begingroup$ The linked paper contains a few samples of smaller Edwards curves. Unfortunately there is nothing out there in the way of code to make them usable, so it's not that useful. $\endgroup$ – Adam Ierymenko Feb 12 at 20:17
  • 1
    $\begingroup$ I see, I did not actually read it before but it is indeed short. I think it could still be helpful to copy the table and maybe the information about the implementations. $\endgroup$ – Ella Rose Feb 12 at 20:38

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.