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

[tptacek]

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.

[eslaught]

Can you explain that for non-cryptographers, please?

[EvgeniyZh]

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

[bediger4000]

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.

[kinai]

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

[KenanSulayman]

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

[mjevans]

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).

[ecma]

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!

[ecma]

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!