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?

marked as duplicate by AviD Aug 27 '11 at 20:40

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


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.

  • 2
    Would you please quote the important parts of the site in your answer? – Falcon Aug 17 '11 at 15:16

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.

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