Which elliptic curves are quantum resistant? [closed]

Question

If I want to learn about quantum resistant crytography what are the best resources? Which type of elliptic curves should I be studying?

Answer 1

Post-quantum crypto is a very young field and is still changing quite rapidly. If you just want a reading list to introduce you to the topics, I would recommend the March 2015 report released by the EU's PQCrypto Project, and the April 2016 report from NIST.

---

As of today, here's an (incomplete) list of candidate algorithms for post-quantum cryptography with a link to the best reading material I could find for each:

• Hashes: everything we have now is fine, you just have to double the output size against a Grover search:

  • SHA-2 256 and up
  • SHA-3 256 and up (aka Keccak)

• Hash-based Signatures:

  • XMSS
  • Sphincs

• Symmetric Encryption: everything we have now is fine, you just have to double the key size against a Grover search:

  • AES 256

• Asymmetric Encryption (some of which also include signature schemes, but why would you when hash-based sigs work so well?):

  • NTRU (lattice-based cryptography)
  • McEliece (code-based cryptography)
  • Ring Learning with Errors (R-LWE) (lattice-based cryptography)
  • Multivariate polynomials (no specific algorithm yet)
  • Isogenies on supersingular elliptic curves (no specific algorithm yet)

---

Since you specifically asked about elliptic curves, you'll notice that ECC in its current form is not on this list. That is because the discrete log problem of reversing elliptic curve point multiplication is easily solved by Shor's algorithm on a quantum computer.

That said, elliptic curves do appear on the list in the form of isogonies: transformations mapping a point on one curve to a point on a (potentially) different curve are conjectured to be hard to invert on both classical and quantum computers.

Personally this is my favourite algorithm from the list above for two reasons:

1. The keys are smaller and the runtime faster than the other approaches

2. The other approaches all have the flavour "do some linear algebra which is possible for Eve to invert, so sprinkle in some error that both Bob and Eve have to guess in order to widen the computational gab between them. This fundamental approach makes me kinda uneasy.

---

The more future-proof answer to this question is to watch NIST: they are gearing up to run a competition-like thing over the next 18 months to select the best post-quantum encryption primitives.

Answer 2

What we traditionally call Elliptic Curve Cryptography (working in the group of points on an elliptic curve over a finite field) is vulnerable to an attack by a quantum computer running Shor's algorithm and is thus not considered a Quantum-Safe or Post Quantum Cryptographic algorithm.

However there is an true Post Quantum Key Exchange algorithm which uses the mathematics of elliptic curves and is considered secure by experts who have studied it so far. This key exchange has come to be known as the "Supersingular Isogeny Diffie-Hellman." It was the subject of a recent in depth study by researchers at Microsoft. Their work can be found here.

The algorithm works with rational maps between supersingular elliptic curves called "Isogenies." This algorithm is due to DeFeo, Jao, and Plut. A key element of this exchange is that the isogenies of a supersingular elliptic curve form a NONABELIAN group (which blocks Shor's algorithm). An earlier isogeny based elliptic curve was based on the ABELIAN group formed from ordinary elliptic curves. However it suffers from a subexponential attack.

To answer your question directly, you should look at supersingular elliptic curves which allow for efficient computation of isogenies. Reference 1 provides more background.