3

Possible Duplicate:
Are the encryptions "broken" with great computing power?

I just wondered which algorithms will be used once quantum computers become common. Are there already existing algorithms that don't rely on factorization problems and thus could replace RSA when the age of quantum computers starts?

Improve this question
1

2 Answers 2

Reset to default
8

The eminent programmer and cryptographer Daniel J. Bernstein has a page dedicated to that. The shortest version:

Hash trees, NTRU, McEliece, and multivariate-quadratic systems.

McEliece, for example, is immune to quantum speedups because it relies on "the hardness of decoding a general linear code (which is known to be NP-hard[4])." Since NP is not in BQP, NP-hard problems remain hard; even with practical quantum computers.

Improve this answer
1
  • 2
    Would you please quote the important parts of the site in your answer?
    – Falcon
    Aug 17, 2011 at 15:16
5

NIST did a survey of Quantum Resistant Public Key Cryptography. Quote:

Of the various lattice based cryptographic schemes that have been developed, the NTRU family of cryptographic algorithms [25, 26, 27] appears to be the most practical.

There is an open source implementation of NTRU at http://ntru.sf.net/.

Another algorithm worth mentioning is the signature scheme GMSS for which there is also an open source implementation.

Other quantum resistant algorithms like McEliece suffer from the fact that key sizes are in the 100's of kbytes or more.

Improve this answer

Not the answer you're looking for? Browse other questions tagged .