What kinds of encryption are _not_ breakable via Quantum Computers?

As usual, journalism talking about technical subjects tends to be fuzzy about details...

Assuming that a true Quantum Computer can be built, then:

• RSA, and other algorithms which rely on the hardness of integer factorization (e.g. Rabin), are toast. Shor's algorithm factors big integers very efficiently.
• DSA, Diffie-Hellman ElGamal, and other algorithms which rely on the hardness of discrete logarithm, are equally broken. A variant of Shor's algorithm also applies. Note that this is true for every group, so elliptic curve variants of these algorithms fare no better.

• Symmetric encryption is weakened; namely, a quantum computer can search through a space of size 2ⁿ in time 2^n/2. This means that a 128-bit AES key would be demoted back to the strength of a 64-bit key -- however, note that these are 2⁶⁴ quantum-computing operations; you cannot apply figures from studies with FPGA and GPU and blindly assume that if a quantum computer can be built at all, it can be built and operated cheaply.

• Similarly, hash function resistance to various kind of attacks would be similarly reduced. Roughly speaking, a hash function with an output of n bits would resist preimages with strength 2^n/2 and collisions up to 2^n/3 (figures with classical computers being 2ⁿ and 2^n/2, respectively). SHA-256 would still be as strong against collisions as a 170-bit hash function nowadays, i.e. better than a "perfect SHA-1".

So symmetric cryptography would not be severely damaged if a quantum computer turned out to be built. Even if it could be built very cheaply actual symmetric encryption and hash function algorithms would still offer a very fair bit of resistance. For asymmetric encryption, though, that would mean trouble. We nonetheless know of several asymmetric algorithms for which no efficient QC-based attack is known, in particular algorithms based on lattice reduction (e.g. NTRU), and the venerable McEliece encryption. These algorithms are not very popular nowadays, for a variety of reasons (early versions of NTRU turned out to be weak; there are patents; McEliece's public keys are huge; and so on), but some would still be acceptable.

Study of cryptography under the assumption that efficient quantum computers can be built is called post-quantum cryptography.

---

Personally I don't believe that a meagre 80 millions dollars budget would get the NSA far. IBM has been working on that subject for decades and spent a lot more than that, and their best prototypes are not amazing. It is highly plausible that NSA has spent some dollars on the idea of quantum computing; after all, that's their job, and it would be a scandal if taxpayer money did not go into that kind of research. But there is a difference between searching and finding...

Quantum computing will make most dramatic impact on asymmetric encryption, but symmetric algorithms are considered safe with a large enough key size (256 bits). So, yeah, we'll have to reinvent x509/SSL by the time quantum computing really takes off (which is a large enough TODO), but there will be large areas of cryptography that will remain relatively safe.

http://en.wikipedia.org/wiki/Post-quantum_cryptography http://www.pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf

When Cryptographers speak about quantum computer and post-quantum cryptography,actually they speak about power of Shor's algorithm in factoring numbers,so hard problems based on factoring number that are used for creating cryptosystems are broken with Shor's algorithm(quantum computer) so RSA,DSA,ELGamal,Diffie-Hellman Key Exchabge,ECC are vulnerable to Quantum Computing!

In public key cryptography,three schemes are quantum-secure:

1. Lattice based cryptography like NTRUEncrypt;based on lattices
2. code-based cryptography like McEliece cryptosystem;based on information theory
3. multivariate cryptography like Hidden Fields Equations

and in symmetric encryption like AES,if you choose a long key;you are safe against quantum computer and NSA!

for future reading:Quanta magazine link and post-quantum cryptography book