[tahoe-dev] Down with ECDSA

[Paul Crowley]

[I'm not on this list so please include me in Cc's - thanks!]

Zooko Wilcox-O'Hearn wrote:
> Could you please post your note to tahoe-dev at allmydata.org?

I recommend against the use of ECDSA in new systems.  It is widely used 
and has survived many years of cryptanalysis, but for a public key 
primitive that's a rather low bar to set.  What one wants is a tight 
reduction to a problem that is believed hard.  We can often place more 
trust in a relatively new scheme that has such a reduction than an older 
scheme that lacks one; in many cases, we can infer from the proofs that 
any attack which breaks the newer scheme necessarily leads to an attack 
that breaks the older scheme, but not vice versa.

I have a couple of recommendations, depending on your needs.  If what 
you need is short signatures, the second scheme in this paper ("A 
Signature Scheme Based on the DDH Problem") has a many appealing properties:

http://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf

Given a group of size 2^q and a security parameter k, the scheme 
produces signatures of size q + k bits; it is secure if the Decisional 
Diffie-Hellman problem is hard in the chosen group.  Generating 
signatures requires two exponentiations, checking them needs three, and 
public keys consist of three group elements, though there may be a way 
to reduce that to two if this is important.  Like DSA, you can do the 
bulk of the work of signing before the message arrives, though this 
makes the reduction very slightly less tight.  There is also a much 
looser reduction to the discrete log problem.

If large signatures are acceptable but verification time must be 
minimized, I recommend this scheme:

http://cr.yp.to/sigs.html

This scheme has *extremely* fast probabilistic verification, and - 
unlike for example RSA - a tight reduction to the difficulty of 
factoring large integers.

If you have other needs that neither of these schemes meet, let me know 
and I'll see what else I can find - thanks!
-- 
   [][][] Paul Crowley
     [][] LShift Ltd
   []  [] www.lshift.net