[cryptography] short signature scheme?

David-Sarah Hopwood david-sarah at jacaranda.org
Mon Nov 8 20:36:00 EST 2010


On 2010-11-08 15:51, Jonathan Katz wrote:
> I am looking for a short signature scheme (certainly shorter than RSA
> signatures, as short as possible would be nice...) that is *patent-free* and
> (less important) easy to implement. Any suggestions?

The family of schemes with the shortest signatures that I'm aware of for a
given security level, but that are still based on reasonably credible security
assumptions, are the 'BLS' (Dan Boneh, Ben Lynn, Hovav Shacham) scheme and
various improvements on it. They use bilinear pairings on elliptic curves,
and have signatures of length just over 2k bits for a 2^k attack cost.

<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.107.1494>
<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.5374>
<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.6191>
<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.74.8292>

I do not know the patent status of any of these schemes. They are all more
complicated to implement than most other signature schemes, certainly than
DSA.

The 'Quartz' scheme claimed shorter signatures than this, but has been broken
in <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.8124>.

A variant of McEliece called CFS also has short signatures, but a large
public key; I don't know much about it:
<http://hal.inria.fr/docs/00/07/25/11/PDF/RR-4118.pdf>

Note that no signature scheme with signatures shorter than 2k bits can resist
a "duplicate signature attack" with cost 2^k. Such attacks (where the signer
generates two messages with the same signature), are not important for many
applications, though.

-- 
David-Sarah Hopwood  ⚥  http://davidsarah.livejournal.com

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 292 bytes
Desc: OpenPGP digital signature
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20101109/bf231a6b/attachment.asc>


More information about the cryptography mailing list