2
$\begingroup$

I was reading the Wikipedia article on Post Quantum Cryptography and was interested in opinions as to whether the Supersingular Elliptic Curve Isogeny Diffie-Hellman listed there would be a good Post Quantum replacement for Elliptic Curve Diffie-Hellman that is being implemented today?

$\endgroup$
5
$\begingroup$

The Supersingular Elliptic Curve Isogeny Key Exchange that you refer to was first published in 2011 by DeFeo, Jao, and Plut. It builds on but is quite distinct from earlier work by Rostovetsev and Stolbunov in 2006. As a Post Quantum/Quantum Safe replacement for Elliptic Curve Diffie-Hellman (ECDH) it has several good properties:

  1. The number of bits that need to be exchanged over the communications channel is roughly the same as a normal Diffie-Hellman key exchange. Not as small as an ECDH but not nearly as large as in other Post Quantum schemes like McEliece or NTRU.

  2. It uses the very well studied mathematics of elliptic curves rather than the more recently accepted lattice approaches to secure cryptography. If you look in the literature you will see that lattice cryptography has been prone to insecurity in the past.

  3. It offers forward secrecy, just like Diffie-Hellman and ECDH. McEliece and NTRU need to add an additional exchange to provide forward secrecy.

  4. It uses elliptic curve arithmetic in a finite field which has been widely implementd.

  5. Most importantly, it has withstood 4 years of academic analysis. Two notable papers which are relevant to the security of this key exchange are:

    Computing Isogenies between Supersingular Elliptic Curves over Fp by Delfs and Galbraith http://arxiv.org/pdf/1310.7789v1.pdf

    A Quantum Algorithm for Computing Isogenies between Supersingular Elliptic Curves by Biasse, Jao and Sankar http://cacr.uwaterloo.ca/techreports/2014/cacr2014-24.pdf

Both papers support the basic security of the Supersingular Isogeny Key exchange though it should be noted that one of the authors (Jao) is also one of the inventors of the key exchange.

  1. There seem to be no patents on the key exchange.

However there is a shortcoming:

Computing Isogenies of Supersingular Elliptic curves and composing these isogenies is computationally harder than other post quantum schemes being considered like McEliece, NTRU, or the Ring-LWE schemes.

In the paper which presented the key exchange, the authors present algorithms which require over 100ms of computation on a 2.5GHz computer for each side of the exchange. Half of that can be done offline but it is worth noting. There has been further work by Shumow and Shumow and Moody on creating more efficient computational models. Both the original inventors of the key exchange and Shumow have posted their code online. It is a good bet that if people became more interested in actually using this key exchange, there could be some significant improvements in computation like Dan Bernstein and Tanja Lange have done for standard Elliptic curve cryptography. A coding contest for the fastest Elliptic Curve Isogeny computations for 768-bit supersingular curves would be an good way to test the performance limits.

Does that answer your question?

$\endgroup$
2
$\begingroup$

Two approaches to Post Quantum Key Exchange that have acceptable bandwidth requirements are the NTRU/Ring-LWE lattice designs and the ECC Isogeny Key exchange you mention. Since the UK spy agency published an attack on a lattice based scheme they had designed, there has been an active discussion between Dan Bernstein and the Lattice Cryptographers over the importance of that result and whether the NTRU/Ring-LWE schemes are really ready to be trusted. You can find Bernstein's thoughts here:

http://blog.cr.yp.to/20140213-ideal.html

Because of these doubts, the Supersingular Curve Isogeny Key Exchange seem like a safer design at the moment. Independent groups of researchers have looked at its security and all appear to support its security. As Carvalho notes, the Supersingular Isogeny design is not as efficient as lattice based schemes. However if you want to use something today that will give you security in the distant future I think sticking with the ECC base is a good idea. You should be able to use a lot of the same arthmetic speed ups from ECC for the Isogeny Design.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.