I came across the following statement on Ycombinator’s Hackernews:
Quantum computing will defeat RSA, DH, ECC, asymmetric crypto, but it will only weaken symmetric crypto (eg. AES) by a factor of two.
Can anyone explain why some forms of encryptions are more succceptible to Quantum computing attacks than others?
The short answer is simply that different forms of encryption are based on different mathematical problems, and quantum computing helps with some kinds of math problems but not others. For some problems, like factoring (which is the basis of RSA, which in turn is the basis for most modern cryptography), there’s a known algorithm for using a quantum computer to get an answer much faster than a classical computer. There are probably also some problems for which it is known that an efficient quantum algorithm exists, but where the algorithm is unknown. There are other problems where it’s not known if an efficient quantum algorithm exists, and yet others where it’s known that an efficient quantum algorithm does not exist (at least, so long as an efficient classical algorithm doesn’t exist, which we also don’t actually know).
There is one well known provably secure crypto system: one-time pads. The problem with these are:
Both parties need the same book of codes.
It’s going to be huge.
Both need to keep it secret.
Modern symmetric systems “pare things down”. You use a much smaller base code. That takes care of point 2 and helps a bit with points 1 and 3. (The small base code is used to generate really long codes that are give you something close to but not entirely like one-time pads.;))
Public key systems are asymmetric. You give out a public key, someone encodes their message using that and sends it to you. Only you can decode it. That really takes care of 1 and 2 and 3 is now only a one person condition. This public key is a foothold into decryption. Esp. the Mathematical methods that are generally used. (But one might be developed in the future that is Shor’s algorithm proof.)
It’s not all cut and dried like the OP’s quote, but it gives a vague picture of the issues.
Well there’s a confusion here.
In todays quantum computers each quantum system would have a trivial number of energy levels , eg 40 ? This means it would be the same as transistor logic in capability. You could do something equivalent of an 8 bit adder from one system.
I think the “crack encryption” quantum system would require the single quantum element have billions of energy levels… which seems far fetched to me. Isn’t there observability issues , if the difference between energy levels is so small, observing would result in interfering ?
“Factor of two” isn’t quite right. It actually speeds things up by a square root: that is to say, AES with a 128-bit key would require 2[sup]128[/sup] operations to brute-force, but a quantum computer could reduce this to 2[sup]64[/sup] ops, which is just about achievable.
The factor of two they’re referring to is key length–a QC makes keys of length N equivalent to N/2. But that’s still a tremendous speedup; of order 2[sup]64[/sup], 2[sup]128[/sup], or more depending on what you started with.
For a quantum computer, you don’t need one system with a bajillion different eigenstates. You need a bunch of systems, each of which has two eigenstates. The catch is that you need one system per bit, and you need to keep them all pretty well-controlled. That’s why the technology isn’t there yet: Nobody’s yet been able to build a quantum computer with the hundreds of qubits needed for standard encryption.
After I made my post I figured out that the “factor of two” thing in the OP might be referring to Grover’s algorithm. As you note it is really a quadratic speed up and the “factor of two” involves keylengths.
In other words, the quote in the OP is a heavily condensed paraphrasing of some general knowledge in crypto leaving so much out that it’s basically useless.