----- Forwarded message from Zooko Wilcox-O'Hearn <[email protected]> -----
From: Zooko Wilcox-O'Hearn <[email protected]> Date: Wed, 19 Aug 2009 15:26:03 -0600 To: Tanja Lange <[email protected]> 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- [email protected] . I've made sure that "[email protected]" 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 ----- _______________________________________________ tahoe-dev mailing list [email protected] http://allmydata.org/cgi-bin/mailman/listinfo/tahoe-dev
