Hacker News Reader

Comment by tptacek | Hacker News Reader

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.

View on HN

Can you explain that for non-cryptographers, please?

Hah. Here's a diagram from a recent isogeny paper:

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.

This looks like something you'd find in a cult.

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.

The Cult of the Higher-Order Curves would be a great band name.

Can you provide a link to the paper?

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.

[edit: fixed numbers]

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.

Now if they made it authenticated with PFS, that would be cool.

This is just Diffie-Hellman. It's working at a level lower than PFS and authenticated key exchange; it's a primitive, not a complete cryptosystem.

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.

I just was surprised no one really made post-quantum AKE with PFS. Or at least I haven't managed to find it. The closest thing I saw is this one: http://csrc.nist.gov/groups/ST/post-quantum-2015/papers/sess...

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.

Reply on news.ycombinator.com