3
$\begingroup$

The smallest signature sizes that I can find are for elliptic curve public key systems where the signature is 4 times the security level (2 x the key size). In my case I can change the key every day, after which it is OK if the key is revealed.

So my questions are:

  1. is there a more efficient signature than 2 x key size?
  2. what would be the minimal acceptable key size for implementations over the next 10 years or so. Looking at a table of key size vs. operations to crack I get a 108 bit ECC key requires 1.8 x 10^8 MIPS, but I'm not sure how to interpret MIPS these days when graphics processors are so powerful. Is 1.8 x 10^8 MIPS a lot of compute power?
$\endgroup$
4
  • $\begingroup$ Are you aware of symmetric message authentication codes, or do you absolutely need to sign every packet with a public key signature? Because the obvious alternative would be to use symmetric crypto; compute a MAC tag over each packet. SipHash was designed with this sort of application in mind, and produces 64-bit tags. $\endgroup$ Feb 7, 2017 at 2:21
  • 1
    $\begingroup$ I believe I need a public key signature because I cannot trust that someone who has the symmetric key will not be the guy who tries to spoof messages. $\endgroup$
    – Relavak
    Feb 7, 2017 at 23:21
  • $\begingroup$ I don't know the exact details of your problem, but I'd say don't rule out a MAC-based solution too quickly. For example, if you need to prove to yourself that you were the author of a message, one simple approach is to use a MAC to tag your own messages with a key only you have. $\endgroup$ Feb 8, 2017 at 0:24
  • $\begingroup$ In my case I have a device that is broadcasting interesting information that someone else may want to spoof, either by replay or by synthesizing wrong information, and my solution is to publish a public key and then sign each broadcast message using the corresponding private key. I cannot use a session key because there is no path to send a message from the listener to the broadcaster. I can update the keys periodically though, once a day would be easy. $\endgroup$
    – Relavak
    Feb 8, 2017 at 4:02

1 Answer 1

4
$\begingroup$

A Signature-Scheme known for it's short signatures is the Boneh-Lynn-Shacham (BLS) Signature Scheme, that uses not only Elliptic Curves but Bilinear Pairings over the curve. The paper can be found here and lists signature sizes provided. For example the paper states that you can

… get a signature of length 154 bits with security comparable to 320-bit DSA or 320-bit ECDSA …

$\endgroup$
2
  • $\begingroup$ Thanks, I'll check it out. Looks like signatures are half the ECDSA algorithm which is a big improvement. $\endgroup$
    – Relavak
    Feb 8, 2017 at 4:06
  • $\begingroup$ Beware that there have been results that show that the BLS signature is not as secure as ECDSA for the same key sizes, see e.g. here. $\endgroup$
    – Maarten Bodewes
    May 27, 2022 at 2:12

Your Answer

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

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