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

[Tanja Lange]

----- Forwarded message from Zooko Wilcox-O'Hearn <zooko at zooko.com> -----

From: Zooko Wilcox-O'Hearn <zooko at zooko.com>
Date: Wed, 19 Aug 2009 15:26:03 -0600
To: Tanja Lange <tanja at hyperelliptic.org>
Subject: Re: why hyperelliptic curves?
X-Mailer: Apple Mail (2.753.1)

Dear Tanja Lange:

I would prefer it if you would send your letter to tahoe- 
dev at allmydata.org .  I've made sure that "tanja at hyperelliptic.org" is  
on the white-list so that your mail will go through even if you are  
not a subscriber.

If that is inconvenient for you then I will forward your letter to  
tahoe-dev myself.  Note that the discussion of "what public key  
crypto to use for the next version of Tahoe-LAFS" has started anew,  
e.g.:

http://allmydata.org/pipermail/tahoe-dev/2009-August/002661.html

Regards,

Zooko

On Sunday,2009-08-09, at 21:22 , Tanja Lange wrote:

>Dear Zooko,
>I still owe you a reply but given that the thread is now a bit old I
>just reply to you instead of the whole mailing list. Feel free to  
>share,
>though.
>
>I intended to read in more detail about your requirements to give
>somewhat better advice, but so far that just led to postponing my  
>reply.
>So, please filter for stuff that might be useful.
>
>>Anyway, if it is true that hyperelliptic curves have a security level
>>commensurate with the number of bits in the public key, then
>>hyperelliptic curves with semi-private keys would be the ideal public
>>key crypto signature scheme for TahoeLAFS.
>>
>The field size for genus-2 hyperelliptic curves is the same as the
>security level but the group size is twice the size (and so is the
>public key).
>This is nothing particular to elliptic or hyperelliptic curves; in any
>group we have attacks that run in time proportional to the square-root
>of the group order. That's why you always get twice the bitsize (at
>best) for representing the elements.
>I said "at best" because elliptic curves and hyperelliptic curves of
>genus 2 are the positive exception. For most other groups we know
>stronger attacks (e.g. the original Diffie-Hellman key exchange  
>setting
>in finite fields has subexponential attacks) and so even larger key
>sizes and representations are needed.
>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. 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 - where the bit pattern is fixed for an
>application and thus does not to be communicated as part of the public
>key. Saving space for the private key usually comes at the price of
>reduced randomness but can be done, too.
>
>>Unfortunately, semi-
>>private keys aren't proven secure nor properly peer-reviewed, and
>>hyperelliptic curves aren't well implemented or widely appreciated.
>>Hopefully someday TahoeLAFS v3.0 will support semi-private-
>>hyperelliptic-curve-based capabilities (in addition to RSA and ECDSA
>>for backward compatibility).
>>
>Looking at speeds, hyperelliptic curves can win if you need scalar
>multiplication only (i.e. Diffie-Hellman or El Gamal encryption)  
>due to
>Pierrick Gaudry's very fast differential addition. If more additions
>are needed, e.g. in signatures, the best arithmetic currently  
>available
>is on elliptic curves. We have some implementations in our  
>benchmarking
>competition at
>	http://bench.cr.yp.to/results-dh.html
>and
>	http://bench.cr.yp.to/results-sign.html
>surf127 is a hyperelliptic curve implementation; gls1271 is a special
>type of elliptic curves which have extra endomorphisms that give extra
>speed. If you don't feel limited to NIST curves there is quite a  
>wealth
>of options to choose from (representation of the curve and points,
>different arithmetic, endomorphisms etc.) and all these influence
>performance and to a much lesser extent security. Do you need to worry
>about side-channel (e.g. 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.
>
>All the best
>	Tanja


----- End forwarded message -----