Information Security Stack Exchange is a question and answer site for information security professionals. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
