why hyperelliptic curves?

Zooko Wilcox-O'Hearn zooko at zooko.com
Sat Jul 18 13:03:45 EDT 2009

Oh, and by the way the way that TahoeLAFS uses public key  
cryptography highlights some of the weaknesses of current public key  
techniques and some of the strengths of possible future techniques  
such as hyperelliptic curves.  (I know that Tanja Lange has done a  
lot of work on those.)

TahoeLAFS generates a unique public-private key pair for each mutable  
file and each directory.  (Immutable files don't use public key  
cryptography at all -- they are secured solely with a stream cipher  
and secure hashes.)  The "file handle" or "capability" to a mutable  
file or directory contains the actual public key (if it is a read- 
only capability) or the actual private key (if it is a read-write  
capability).  Therefore some of our most important measures of  
performance are public key size and keypair generation time.   
Unfortunately, we blundered into using one of the worst possible  
public key signature algorithms for such requirements: RSA!  Our  
current project is replacing RSA with ECDSA.  TahoeLAFS v2.0 will  
support ECDSA-based capabilities (in addition to RSA-based ones for  
backward compatibility).

TahoeLAFS also requires more than two levels of privilege.  With  
traditional public/private keys there are exactly two levels: you  
either know the private key or you don't.  We need to have an  
intermediate level of privilege -- someone who doesn't know the  
private key but who does know something that not everyone knows.   
(Everyone knows the public key.)  We use these three levels of  
privilege to create read-write capabilities, read-only capabilities  
and verify capabilities.   (A verify capability gives the ability to  
check integrity of the ciphertext, which everyone has, because  
everyone knows the public key).  If this doesn't make sense to you  
then see if my longer explanation in lafs.pdf makes any more sense.

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.  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).


Zooko Wilcox-O'Hearn

P.S.  Oh, I told a lie in the interests of brevity when I said that  
file handles contain actual public keys or actual private keys.  RSA  
keys are way too big for that.  So instead we go through interesting  
contortions to make a "surrogate" value which can be used to check  
the correctness of the RSA key (i.e. the surrogate value is derived  
from the RSA key by secure hashing) as well as can be used to control  
access to the RSA key (the RSA key is encrypted with a stream cipher  
using the surrogate value as the symmetric encryption key).  The  
surrogate value therefore offers the same integrity and access  
control properties as the RSA key itself (when the user also has  
access to the encrypted RSA key itself), but it is sufficiently short  
to embed directly into the file handles a.k.a. capabilities.  This  
too is explained more fully in lafs.pdf.

[1] http://allmydata.org/~zooko/lafs.pdf
[2] http://allmydata.org/trac/tahoe/ticket/217#comment:50

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com

More information about the cryptography mailing list