19
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Could you find a more objective way of asking what you are after? (I.e. a specific answerable question.) This is very subjective and open ended, such questions are off topic. $\endgroup$ – otus May 21 '16 at 7:56
  • 3
    $\begingroup$ "Which type of elliptic curves should I be studying?" - for quantum resistance... none of them $\endgroup$ – Richie Frame May 21 '16 at 8:15
  • $\begingroup$ "Quantum attacks on public key cryptosystems" $\endgroup$ – Meysam Ghahramani May 21 '16 at 9:28
  • 6
    $\begingroup$ @RichieFrame uhh, elliptic curves do make an appearance in quantum resistance ... but rather than doing point multiplication on them, we're computing isogenies between them. Specifically, we're looking at supersingular curves. $\endgroup$ – Mike Ounsworth May 21 '16 at 10:59
19
$\begingroup$

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:

  • 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?):


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.

$\endgroup$
  • $\begingroup$ Keccak and AES-256 are Post quantum too. $\endgroup$ – Biv May 21 '16 at 11:11
  • $\begingroup$ @Biv As is the SHA2 family. Fine, I'll add hashes and symmetric ciphers. $\endgroup$ – Mike Ounsworth May 21 '16 at 11:14
  • 1
    $\begingroup$ Actually, while isogenies do have small key and ciphertext sizes (NTRU is competitive there), however from what I've seen, the run time is rather slower than other approaches. More fundamentally, isogenies is based on a problem that (IMHO) is not very well studied at all; it would seem premature to put a great deal of trust in it $\endgroup$ – poncho May 21 '16 at 13:54
  • $\begingroup$ @poncho yeah, I'm certainly not writing an implementation of it yet, but I'm following the research with interest. $\endgroup$ – Mike Ounsworth May 21 '16 at 13:56
  • $\begingroup$ Aren't sponge constructions reduced to $2^{n/3}$ instead of $2^{n/2}$? $\endgroup$ – forest May 20 '18 at 4:26
11
$\begingroup$

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.

$\endgroup$

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