Information Security Stack Exchange is a question and answer site for information security professionals. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question

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.

Have a quick look at as well - John and Thomas both list algorithms which are resistant. – Rory Alsop Aug 18 '11 at 7:55

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.

share|improve this answer
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

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.

share|improve this answer

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