Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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
1  
Have a quick look at security.stackexchange.com/q/4286/485 as well - John and Thomas both list algorithms which are resistant. –  Rory Alsop Aug 18 '11 at 7:55
add comment

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.

2 Answers

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.

share|improve this answer
add comment

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
2  
Would you please quote the important parts of the site in your answer? –  Falcon Aug 17 '11 at 15:16
add comment

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