Supersingular Isogeny Diffie-Hellman: Post-Quantum Curves [pdf] | Hacker News Reader

Supersingular Isogeny Diffie-Hellman: Post-Quantum Curves [pdf]

eprint.iacr.org

91 pointstptacek25 comments

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.

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.

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.

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.

download: http://research.microsoft.com/en-us/downloads/bd5fd4cd-61b6-...

works fine on x64: TESTING ISOGENY-BASED KEY EXCHANGE --------------------------------------------------------------------------------------------------------

Curve isogeny system: SIDHp751

  Key exchange tests ........................................... PASSED

BENCHMARKING ISOGENY-BASED KEY EXCHANGE --------------------------------------------------------------------------------------------------------

Curve isogeny system: SIDHp751

  Alice's key generation runs in ...............................   45806658 cycles
  Bob's key generation runs in .................................   53532976 cycles
  Alice's public key validation runs in ........................   58980241 cycles
  Bob's public key validation runs in ..........................   64155209 cycles
  Alice's shared key computation runs in .......................   42940225 cycles
  Bob's shared key computation runs in .........................   51437446 cycles

TESTING ELLIPTIC CURVE BIGMONT --------------------------------------------------------------------------------------------------------

  BigMont's scalar multiplication tests ........................ PASSED

BENCHMARKING ELLIPTIC CURVE BIGMONT --------------------------------------------------------------------------------------------------------

  BigMont's scalar multiplication runs in ......................    5950262 cycles

I love how this is developed by Microsoft and it doesn't compile on either Windows (VS) nor OSX (gcc, icc, clang) for me.

I run Arch Linux x64, compiled asm version with gcc. Works all just fine

Well, if you read my comment you'll see I only talked about OSX and Windows - Linux compiles just fine.

Well, it's still pretty typical Microsoft -- the license agreement is distributed as a .docx file.

I've built it in VS just fine:

  TESTING ISOGENY-BASED KEY EXCHANGE
  --------------------------------------------------------------------------------------------------------

  Curve isogeny system: SIDHp751

    Key exchange tests ........................................... PASSED


  BENCHMARKING ISOGENY-BASED KEY EXCHANGE
  --------------------------------------------------------------------------------------------------------

  Curve isogeny system: SIDHp751

    Alice's key generation runs in ...............................   91654657 cycles
    Bob's key generation runs in .................................  107973852 cycles
    Alice's public key validation runs in ........................  114289149 cycles
    Bob's public key validation runs in ..........................  126421809 cycles
    Alice's shared key computation runs in .......................   84909767 cycles
    Bob's shared key computation runs in .........................  104901163 cycles


  TESTING ELLIPTIC CURVE BIGMONT
  --------------------------------------------------------------------------------------------------------

    BigMont's scalar multiplication tests ........................ PASSED


  BENCHMARKING ELLIPTIC CURVE BIGMONT
  --------------------------------------------------------------------------------------------------------

    BigMont's scalar multiplication runs in ......................   13041518 cycles

It only builds targeting 'x64', though - not 'Win32'. The source is actually fairly well documented, too.

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.

Well done to the people at MSR behind this paper!

Reply on news.ycombinator.com