5
$\begingroup$

I am looking for a strong alternative to elliptic curve cryptography. It should be something that could face quantum computing attacks, but nothing created by the NSA.

I heard about isogeny key exchange, i.e. supersingular isogeny, is it really secure? Otherwise, what would be an alternative that fulfills the above?

In addition, what would be a post-quantum algorithm for file encryption? Perhaps snow 3g?

$\endgroup$
  • $\begingroup$ Looking for something that can replace EC and strong facing quantum attacks without NSA footprint. $\endgroup$ – user2360915 Oct 3 '14 at 6:53
  • $\begingroup$ cr.yp.to/codes/mceliece-20080807.pdf $\;$ $\endgroup$ – user991 Oct 3 '14 at 18:11
  • 2
    $\begingroup$ If you are worried about NSA, look at crypto (also elliptic curves) done by Dan Bernstein. For post quantum cryptography look at pqcrypto.org (Dan is involved there too). $\endgroup$ – j.p. May 22 '15 at 14:53
8
$\begingroup$

Supersingular isogenies are a rather recent attempt at post quantum security. You will have a hard time finding an efficient and secure implementation, and even if you write one yourself, the algorithms have not yet seen that much cryptanalysis. (Although that's a subjective judgement call.)

If post quantum security wasn't a concern, you could choose from any number of non-NSA elliptic curves. However, quantum computers, if practical, can break elliptic curves (using Shor's algorithm).

NTRU is, like the other answer notes, a more practical and established alternative for post quantum cryptography. It still isn't necessarily as efficient or well studied as elliptic curves, though. As a practical matter the main implementation is under GPLv2.

For key exchange there is also the "new hope" lattice algorithm which is being field-tested by Google as a possible successor of ECC in TLS. (Personally I find this to be one of the likelier algorithms to see use, but I would not use it – alone – for anything important yet.)

For file encryption, or anything that works with a secret key, you can use existing symmetric algorithms. You may want to choose a key size of at least 256-bits, though, to account for the quantum Grover's attack. SNOW 3G in particular isn't post quantum secure for that reason – it has a 128-bit key. Other standardized general purpose ciphers like AES-256 or something on the eSTREAM portfolio (Salsa20 at least has a 256-bit key) would work fine.

$\endgroup$
5
$\begingroup$

If you need security against quantum attacks, there aren't that many options. I would go for a lattice-based encryption like NTRU or something based on ring learning with errors. There are no "magic numbers" involved and the assumptions they are based on have been scrutinized by the academic community.

NTRU has been around for a decade and has pretty good implementations. If you want to go with RLWE, which is based on a slightly better cryptographic assumption, there is an open source project implementing some of the more mature ideas called HElib (besides being quantum-resistant they are also interesting because of their homomorphic properties). None of the implementations are as complete as you will get with EC crypto yet though.

$\endgroup$
  • 1
    $\begingroup$ In my opinion, NTRU is not the best choice due to many reasons. The most important one is because this scrutiny process, as you mentioned, has found several vulnerabilities, demanding subsequent corrections. Besides, NTRU is covered by patents. $\endgroup$ – mczraf Oct 3 '14 at 16:30
  • $\begingroup$ Do you have any alternatives to suggest? Most ciphers are covered by patents. ECC is patented. RLWE is patented. Not sure how you're going to get around that. Also, as far as I am aware, the vulnerabilities in NTRU came from the fact that it was not initially clear what good parameter choices were going to be, since lattice-based cryptography was so new. $\endgroup$ – Travis Mayberry Oct 4 '14 at 11:08
  • 4
    $\begingroup$ @Travis: RLWE is most definitely not patented. (I'm one of the inventors, and I've never patented anything.) $\endgroup$ – Chris Peikert May 22 '15 at 21:55
3
$\begingroup$

There is some software available for the isogeny key exchange. It was developed by one of the designers of the key exchange (DeFeo). It is available on GitHub her:

https://github.com/defeo/ss-isogeny-software/

The key exchange was first published in late 2011 and its security has held up under analysis since then. A 2014 paper from Indocrypt supports the security of the scheme.

http://cacr.uwaterloo.ca/techreports/2014/cacr2014-24.pdf

Luiz

$\endgroup$
  • $\begingroup$ There is a Wikipedia article on this key exchange. The title of the article is Supersingular Isogeny Key Exchange $\endgroup$ – Luiz Carvalho May 22 '15 at 10:49
0
$\begingroup$

You can take a look at Dan Berstein's Curve25519. It's a non-NIST, non-NSA curve and he has his own adaptation of DSA that goes with it. However, I suppose it's possible to parallelize an attack on this, so it may not be resistant to quantum computing attacks.

As for symmetric encryption, it's important to note that AES was developed by the international community and is considered by most to NOT have NSA fingerprints on it. As you probably already know, it is the defacto symmetric encryption standard of today.

$\endgroup$
  • 2
    $\begingroup$ Quantum computers can efficiently compute discrete logarithms in groups, including finite fields and elliptic curves. So Diffie-Hellman is dead once QC's capable of running Shor's algorithm appear. $\endgroup$ – CodesInChaos Oct 3 '14 at 20:14
  • $\begingroup$ Agreed that it's possible to use quantum computers to conduct DLP attacks (that's why I stated that in my answer). Some researchers have proposed techniques to do this (via Shor's algorithm). $\endgroup$ – Laplacian Oct 3 '14 at 20:42

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.