[cryptography] short signature scheme?

James A. Donald jamesd at echeque.com
Mon Nov 8 22:05:42 EST 2010


On 2010-11-09 11:36 AM, David-Sarah Hopwood wrote:
> 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>

This is, I think, based on Gap Diffie Helman groups.  I would assume the 
rest of them are also.

Source code from http://crypto.stanford.edu/pbc/


> <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.

The library does not mention any patent issues.

Of course anyone can patent anything, and probably will.  Everything is 
patented, which means one has little choice but to act as if nothing is 
patented.  In practice, the patent trolls usually go after the big 
pockets, such as Microsoft.






More information about the cryptography mailing list