This stuff is mindbending, but the paper itself is pretty impressive. Microsoft actually got this working:
We present a full-fledged, high-speed implementation of (unauthenticated)
ephemeral SIDH that currently provides 128 bits of quantum security and 192 bits of classical security.
This implementation uses 48-byte private keys to produce 751-byte ephemeral Diffie-Hellman
public keys, and is currently written almost entirely in C with only a limited set of functions
written in assembly. To our knowledge, our library presents the first SIDH software that
runs in constant-time, i.e., that is designed to resist timing and cache timing attacks.
And making it PFS and authenticated isn't even the hard part. Slap on hash signatures to preserve quantum security there too and use temporary key exchange keys, done. Making the key exchange itself work securely is 99% of the work.
It's too early to do that. Researchers are trying to study whether the primitives are going to work --- ie, that the new hard problems they're based on will hold up against quantum speedups and that they're secure against conventional adversaries. Simple DH is a straightforward backdrop for that problem. Composing DH into an AKE doesn't much help, as long as the primitive is flexible enough.
Isogenies are mappings between curves. So maybe one way to start getting your head around isogeny crypto is that you're dealing in higher-order curve structures.
You should see their (much faster!) subsequent paper. It develops an entirely new mapping to take advantage of Intel vector extensions, then invokes Valefor instead of Bael.
Diffie-Hellman is a key-exchange protocol. If two people want to exchange some encrypted information, they first need to share a secret key to do the encryption with. The problem is, they can't just send the key in plain-text, since any eavesdroppers would get the key too.
Diffie-Hellman gets around this by having each side share only part of a key, while keeping the other part secret. Both sides can then mix their own secret part with the other side's shared part to derive a common encryption key. An eavesdropper can't learn anything, though, since they only see the shared parts, not the critically-important secret parts.
The Diffie-Hellman algorithm comes in several different flavors. The current state-of-the-art is ECDH, which is fast and uses small keys. The problem is that ECDH only provides security against classical computers. If an eavesdropper has access to a big 256-bit quantum computer, they can work backwards from the shared parts to learn the encryption key.
Big quantum computers don't exist yet, but they might one day. Therefore, cryptographers are busily searching for alternatives to ECDH that don't have quantum weaknesses. We have some alternatives already, but they are either slow or require enormous keys.
This paper shows a way to do quantum-resistant Diffie-Hellman in a way that is significantly faster and smaller than anything we have see so far. It's still a lot slower than the best ECDH (~50 million vs ~50k cycles), and they keys are still a lot bigger (751 bytes vs 32 bytes), but it's still really impressive progress. Many of the alternatives have keys measured in KB or MB, which is obviously impractical.
48 bytes get expanded to 751. Whether you count this as 751 or 48 depends on what you want to compare.
Also, your description implies DH exchanges are zero knowledge exchanges - that there is no way to infer the private key from the public exchange - but that's not true. It is perfectly possible - in fact, in most DH variants a 1-1 transformation - except it is entirely infeasible.
Those 48 bytes are the two random numbers used as the private key, correct? The actual public key that gets sent over the wire is the 751 byte thing, if I read the paper correctly.
works fine on x64:
TESTING ISOGENY-BASED KEY EXCHANGE
--------------------------------------------------------------------------------------------------------
This looks really great. I wonder how long it will be before these algorithms are usable in projects like libressl and GnuPG, as well as how long it will take standards bodies to include them in future versions of TLS and OpenPGP (IIRC we are /still/ waiting on ed25519 to be included in OpenPGP).
It'll be a while yet. OpenSSL is still the standard platform for trading research implementations and AFAIK the problem isn't characterised with enough depth to suggest it as a recommended hard problem to base post-quantum cryptographic primitives on. The next few years will be very exciting though!
I recently had the privilege of listening to Brian LaMacchia speak on this and other developments in the post-quantum cryptography space at Microsoft research. What they're doing is remarkable and their commitment to the space is impressive. SIDH is an exciting problem and I'm looking forward to reading more work on implementations and cryptanalysis.
I have to say that "Supersingular Isogeny" and "Post-Quantum Curves" sound like really good technobabble. You know, like when a car mechanic tells you that the "Johnson Rod" is broke, only in a cryptography context.
25 comments
[ 10.5 ms ] story [ 73.4 ms ] threadWe present a full-fledged, high-speed implementation of (unauthenticated) ephemeral SIDH that currently provides 128 bits of quantum security and 192 bits of classical security. This implementation uses 48-byte private keys to produce 751-byte ephemeral Diffie-Hellman public keys, and is currently written almost entirely in C with only a limited set of functions written in assembly. To our knowledge, our library presents the first SIDH software that runs in constant-time, i.e., that is designed to resist timing and cache timing attacks.
https://s-media-cache-ak0.pinimg.com/736x/0f/92/7f/0f927f795...
Isogenies are mappings between curves. So maybe one way to start getting your head around isogeny crypto is that you're dealing in higher-order curve structures.
Diffie-Hellman gets around this by having each side share only part of a key, while keeping the other part secret. Both sides can then mix their own secret part with the other side's shared part to derive a common encryption key. An eavesdropper can't learn anything, though, since they only see the shared parts, not the critically-important secret parts.
The Diffie-Hellman algorithm comes in several different flavors. The current state-of-the-art is ECDH, which is fast and uses small keys. The problem is that ECDH only provides security against classical computers. If an eavesdropper has access to a big 256-bit quantum computer, they can work backwards from the shared parts to learn the encryption key.
Big quantum computers don't exist yet, but they might one day. Therefore, cryptographers are busily searching for alternatives to ECDH that don't have quantum weaknesses. We have some alternatives already, but they are either slow or require enormous keys.
This paper shows a way to do quantum-resistant Diffie-Hellman in a way that is significantly faster and smaller than anything we have see so far. It's still a lot slower than the best ECDH (~50 million vs ~50k cycles), and they keys are still a lot bigger (751 bytes vs 32 bytes), but it's still really impressive progress. Many of the alternatives have keys measured in KB or MB, which is obviously impractical.
[edit: fixed numbers]
Also, your description implies DH exchanges are zero knowledge exchanges - that there is no way to infer the private key from the public exchange - but that's not true. It is perfectly possible - in fact, in most DH variants a 1-1 transformation - except it is entirely infeasible.
works fine on x64: TESTING ISOGENY-BASED KEY EXCHANGE --------------------------------------------------------------------------------------------------------
Curve isogeny system: SIDHp751
BENCHMARKING ISOGENY-BASED KEY EXCHANGE --------------------------------------------------------------------------------------------------------Curve isogeny system: SIDHp751
TESTING ELLIPTIC CURVE BIGMONT -------------------------------------------------------------------------------------------------------- BENCHMARKING ELLIPTIC CURVE BIGMONT --------------------------------------------------------------------------------------------------------Well done to the people at MSR behind this paper!