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
signature.asc
Description: OpenPGP digital signature
_______________________________________________ cryptography mailing list [email protected] http://lists.randombit.net/mailman/listinfo/cryptography
