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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ This thesis could be a starting point. $\endgroup$
    – puzzlepalace
    Feb 12, 2019 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, 2019 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, 2019 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, 2019 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, 2019 at 15:27

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • 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, 2019 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, 2019 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, 2019 at 20:38

Your Answer

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

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