Surface1271: high-speed genus-2-hyperelliptic-curve cryptography D. J. Bernstein
Authenticators and signatures

The future of Diffie-Hellman functions

This page will eventually provide complete software and documentation for Surface1271, a state-of-the-art Diffie-Hellman function suitable for a wide variety of applications.

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:

     gunzip gaudry-20060918.tar
     tar -xf gaudry-20060918.tar
     cd gaudry-20060918
     ./gaudrytest | openssl md5
Output on my laptop:
     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.