[cryptography] short signature scheme?

Jonathan Katz jkatz at cs.umd.edu
Tue Nov 9 19:26:18 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?

Thanks to everyone who answered. (And I especially liked the suggestion to 
use the [GJKW] scheme!) I was actually hoping for something even shorter, 
though maybe that is not known.

A few questions remain:
- In general, what are the patent issues involved in using dlog-based 
signature schemes (whether DSS or [GJKW] or something else...) when 
instantiated using elliptic curve groups?

- Some people mentioned that 2^k security requires signatures of length 
2k, presumably by analogy with hash functions. Although I see some 
intuition for thinking this, I don't see formally why this must be the 
case. (In particular, I don't see why it's an issue if two legitimately 
issued signatures happen to be the same, as long as they couldn't have 
been forged in advance.) Even more so if some application is signing short 
messages to begin with.

More information about the cryptography mailing list