[tahoe-dev] [zooko at zooko.com: Re: why hyperelliptic curves?]

[Zooko Wilcox-O'Hearn]

On Sunday,2009-08-09, at 21:22 , Tanja Lange wrote:
> This means that as long as you stick with groups and DLP you can't  
> do with less than 2*security level for the bitsize generically.

Oh, so the Pollard Rho attack of finding a certain kind of collision  
and then using that to find the private key can be used on *any*  
group?  It is impossible to have a group-and-DLP digital signature  
scheme which is immune to that attack?

Are there any other types of digital signature scheme which can have  
public keys shorter than 2*security level bits?

> There are other possibilities - if you invest more time in  
> generating the keys you can keep trying random secret keys until  
> you hit one with a specified bit pattern in the top X bits

Requiring about 2^x work to save x bits of the public key?  Not worth  
it!

> Do you need to worry about side-channel (e.g. timing) attacks?

Tahoe-LAFS is likely to be used (by people other than me) in a  
variety of situations, including "cloud computing" where you're  
sharing a CPU and cache with a stranger.

I would greatly prefer to choose constant-time algorithms in upgrades  
of Tahoe-LAFS so that I don't have to worry about timing attacks.  :-)

> We're currently working on a networking and cryptography library
> 	http://nacl.cace-project.eu/
> DH on ECC is already implemented; signatures are still missing but  
> will come.

I've been following the development of nacl.  What sort of signature  
scheme do you plan to add?

Thank you very much for sharing your expertise.

Regards,

Zooko