Authenticators and signatures

Given a user's 32-byte secret key, Surface1271 computes the user's 48-byte public key. Given the user's 32-byte secret key and another user's 48-byte public key, Surface1271 computes a 48-byte secret shared by the two users. This secret can then be used to authenticate and encrypt messages between the two users.

Surface1271 has one big advantage over
Curve25519:
it's considerably faster!
But it also has a big disadvantage:
it isn't finished yet.
If you want working cryptographic software, use Curve25519.
Right now this page simply documents progress towards Surface1271,
explaining why it's reasonable to predict that
we *will* eventually have a faster Diffie-Hellman function.

Surface1271 computes scalar multiples on a Kummer surface in squared inverted Gaudry form. The surface parameters a,b,c,d are chosen to be very small to save time in arithmetic. Surface1271 has the same security as the Jacobian of a genus-2 hyperelliptic curve over Z/(2^127-1). To complete the definition of Surface1271 I'm going to have to specify choices for a,b,c,d.

Here's the big problem: only a small fraction of all choices of a,b,c,d are (conjecturally) secure.
Right now we aren't able to recognize secure choices,
because we aren't able to count points on such a large genus-2 Jacobian.
My student Nikki Pitcher has recently set speed records for Schoof's original algorithm
and is now investigating genus-2 point counting,
so I hope that soon we *will* be able to count points and recognize secure choices of a,b,c,d.

There are occasional genus-2 hyperelliptic curves, the CM curves, for which counting points is much easier. However, it would be awfully surprising for the corresponding surfaces to have very small parameters a,b,c,d.

As an initial basis for speed evaluations,
I've written software for the Pentium M
for scalar multiplication on a Kummer surface with *arbitrary* a,b,c,d.
You can download, test, and time the software as follows:

wget http://cr.yp.to/hecdh/gaudry-20060918.tar.gz gunzip gaudry-20060918.tar tar -xf gaudry-20060918.tar cd gaudry-20060918 make ./gaudrytest | openssl md5 ./gaudryspeedOutput on my laptop:

17f757166e87a3854bb2bdf8ebcdd6a6 ... gaudry 582277 ...That's 582277 cycles for scalar multiplication. Specialized surfaces would be considerably faster. For comparison, Curve25519 is slightly over 640000 Pentium M cycles, about 10% slower.

I'm giving a talk on this topic at ECC 2006.