Slashdot Mirror
Quantum Computing Not an Imminent Threat To Public Encryption
Bruce Schneier's latest blog entry points out an interesting analysis of how quantum computing will affect public encryption. The author takes a look at some of the mathematics involved with using a quantum computer to run a factoring algorithm, and makes some reasonable assumptions about the technological constraints faced by the developers of the technology. He concludes that while quantum computing could be a threat to modern encryption, it is not the dire emergency some researchers suggest.
While I'm critical of Schneier's work in general security consulting, he is still a god in the cryptography world. His book Practical Cryptography is a friendly guide to encryption that doesn't assume too much knowledge of the heady math involved. Plus, the man invented Blowfish, one of the most popular and fast algorithms around.
The day PKIs that use factoring or discrete logs become easy to crack is the day when there's going to be a lot of tremendous amount of money spent on stop-gap security measures until someone figures out something new...
Am I part of the core demographic for Swedish Fish?
Yes, but what about the matters you've already encrypted? Early buzz around PGP was that it would supposedly take millions of years to decrypt even a single message. For those people who encrypted their private communications, it is a big shock that all your secrets may be read in just a few years.
you disconnect it. First posts are encrypted by mod down, taken out of sight.
The best encryption is disconnection. Its unbreakable even by quantum computers to the nth power.
the next best is perhaps a sequence of seemingly unrelated actions followed by a false positive... or other such use of seemingly unrelated data/actions.
A few might remember the seemingly different things you could do to cause a developer hidden message to come up on the Amiga.
This calculation illustrates a good point about the difference between asymptotic analysis of algorithms and real-world implementation of the same algorithsm. Computer science defines "efficient" as "bounded polynomially in terms of the input size". In practice, even if polynomial has a small degree (like a cubic) it already means that the resource rquirements are very large. Theory and practice are only the same in theory.
...the rate of increase of power of quantum computers isn't faster than Moore's law. I've written more on this here.
-- SIGFPE
Well, even if it were to be true that quantum computing algos can break the existing encryption algos, I think it is being paranoid for two reasons: (1) Quantum computing is not yet mainstream and I doubt if mischief mongers (aka thieves who wish to break into financial sustems) have the wherewithal today to work with quantum computing algos, and (2) By the time QC moves to anywhere near mainstream, I have little doubt that encryption methods would have handsomely moved along too.
As far as I know, it is not known whether quantum computers can solve NP-hard problems in polynomial time. To say that they fail at NP-problems may be premature.
I mispoke. No current algorithms are known for solving NP problems fast with a quantum machine, and it is suspected none exist.But no proof of the converse exists. However, using a nonlinear operator permits NP complete problems to be solved in polynomial time with small error. So it's more pessimistic then I thought.
Inventions have long since reached their limit, and I see no hope for further development.-- Frontinus, 1st cent. AD
Presumably the article is alluding to Shor's Alorithm, which is a a method to factorize integers which uses quantum computation to yield a worst-case complexity significantly better than any existing deterministic methods.
If that's the case, it's probably worthwhile to discuss Pollard's Rho algorithm, which has a poorly understood worst-case complexity (as a Monte Carlo method), but has a potential average case complexity that is comparable to the quantum.
Since the Sci Am article is subscription-only, you may want to check the complete draft-version of Scott Aaronsons article for Scientific American (before editors changes) here:
http://www.scottaaronson.com/writings/limitsqc-draft.pdf
Scott posted it on his blog on 2/18, see http://www.scottaaronson.com/blog/
(The blog is often quite technical as you can expect but funny and worth following just for its non-techical bits. Circumcision and Australian models are also discussed on frequent basis.)
I doubt that we will ever figure out - and I suspect that even if we did figure out we couldn't do much about it
Heavier-than-air flight is impossible; a train will never go faster than a person can run or the passengers will asphyxiate; there is no reason why anyone would want a computer in the home; etc.
It's a bad idea to discount future technological advances wholesale.
He makes an extremely cogent argument, but it is hampered by the lack of information we have about the state of the art in quantum computers.
Domestic spying is massively popular with western governments right now, and if you think that the NSA and GCHQ aren't doing secret research into quantum computers you are out of your mind. Furthermore, it is a commandment of signals intelligence that you do not let the enemy know you have broken his code - and in this case the enemy is us. We have no idea how far along they are. We have no idea what the generational length is for the quantum computers that are certainly being developed in secret.
Basically, this essay could be published and make just as much sense either before or after a critical breakthrough had been made by one of the aforementioned agencies and they hadn't told anyone. Thus, we have no way of knowing if we are already past that point or not.
Given that it has already been shown that quantum computers are not infallible, would it not make sense now to start working on encryption methods designed to flummox them?
If we can put a man on the moon, why can't we shoot people for Apollo-related non-sequiturs?
I'm afraid you'll have to look those physics books back up.
Although QM computers do use basic entanglement for creating superpositions, understanding Shor's algorithm (the one everyone is concerned about since it's factoring in polynomial time) is mostly just understanding QM superposition. Entanglement gives generic QM computers great parallel processing power by superposition by explaining how QM probability wave combine under superposition, but Heisenberg limits the computing power of a QM computer in a non-trivial way as well because after you collapse the wave functions by measurement you give up the parallel processing enabled by Entanglement (e.g., if you peek inside the oven, it stops working, if some of the heat leaks out of the oven even with the door closed, it doesn't work as efficiently, the oven being the QM computer).
FWIW, Shor's algorithm essentially converts factoring into a sequence period finding exercise. You might imagine that that's something easy to do if you had a machine which given a bunch of superimposed waves with a certain modulo structure could tell you the period (hint the ones that don't modulo with a specific period with self interfere and measure as zero, where the one with that period with self-reinforce). With a QM computer you do this all in parallel with superimposed probability waves and when you measure it, the highest probability one you measure is the one that doesn't self-interfere (the ones that self-interfere has probability near zero). Basically this measurement is wave function collapse which doesn't actually depend on entanglement or heisenberg to understand (although it does require you to believe in QM wave functions and measurement operators).
Entanglement is really a strange artifact of QM that explains probability correlations that you see in QM experiments that can't be explained classically. It's really more of an artifact of the existance of probability amplitude waves (the QM wave function) rather than an effect that directly enables the QM computer. Of course if you didn't have QM wave functions you wouldn't have a QM computer so I guess that's a chicken and egg scenario. Entanglement is like the "carburator" function of the QM computer. The QM computer uses superposition of QM wave functions to work and when you have more than one QM wave function, they get entangled when you start superimposing wave functions and the way the waves entangle helps you compute in parallel so it's important to understand how these waves entangle.
Heisenberg's principle is a consequence of wave function collapse (measurement) which also limits the QM computer (this limiting effect is often called QM de-coherence). Heisenberg isn't required by a QM computer when it's computing, but you need to see the result somehow so when you measure the result, one of the side effects is the Heisenberg principle (although that's also a chicken-egg problem, since HP is a consequence of QM wave function collapse and w/o QM there's no superposition computing). The closest explanation I can think of is that Heisenberg's principle is the "heat" caused by friction of the QM computer. You need friction to stop the computer to read out the result, but at the same time you can't get rid of a little friction while it's running either (causing de-coherence). The side effect of this friction is heat.
You may have a personal opinion that superposition is a "nice way of doing statistics using discrete values for covering the not so discrete results of experiments", but there is experimental evidence that your personal opinions is at odds with physical reality. As QM computers that do QM computing (including IBM's NMR experiment which implemented shor's algorithm) have already been implemented it's hard to refute that something non-classical is going on.
It may be that in the end, QM is total malarky and there's some other weird unexpected thing going on, but there are mountains of evidence that whatever is going on, it isn't as simple as "hidden variables"
1. Entanglement: It is fact. If you send a photon through a certain type of non-linear crystal, two photons will emerge that are entangled quantum mechanically. To truly understand this requires some knowledge of quantum mechanics, a basic introduction to QM and entanglement can be found here and here if you care to learn more.
2. Heisenberg principle: You inadvertently stumbled onto the problem yourself, kinda. When trying to measure the position of the electron, you use a high energy photon and this photon. When this high energy photon interacts with the electron it alters the velocity of the electron, so you know less about the velocity of the electron. When trying to measure the velocity of the electron, you use a low energy photon. This low energy photon measures the velocity well, but it moves the electron a little bit, so you don't know its position. This issue is the essence of the Heisenberg uncertainty principle.
How are you going to get the pads to the other person? Encrypt them?
If you have a way of transmitting the pads securely then you could just use the same system to transmit the messages - no encryption needed!
No sig today...
Parent post is absolutely correct; grandparent is absolutely wrong.
;-).
Read Scott Aaronson's blog to get a clue about quantum computing.
Also read about Schor's algorithm, which is the known algorithm to factor large numbers in log(n) time *if your quantum computer has enough entangled qubits to represent the number*. Again, though, remember that FACTORING IS NOT NP COMPLETE, only NP hard. Other NP hard problems are harder than factoring (for example, any NP complete problem
Also read about Grover's algorithm, which is a general algorithm to solve NP complete problems, and which HAS BEEN PROVEN TO BE THE FASTEST way to solve the NP complete problem of lookup in an unordered dictionary. Grover's algorithm finds the answer in n^1/2. Obviously if the fastest algorithm to solve a specific NP complete problem is n^1/2, you cannot have a way to solve all NP complete problems in log(n).
Look up Grover's algorithm and Schor's algorithm on Wikipedia, and you'll see that the GP is speaking beyond his knowledge.
I should say that I also made the mistake of thinking factoring was NP complete, and made a fool of myself on Scott's blog before the many, many people more knowledgeable than I about QC on that forum corrected me.
Actually, the problem is more fundamental. What is really going on is that momentum = wavelength -- that is, what we perceive as momentum on a large scale is actually an average approximation of the existence of wavelength on a small scale. This is not intuitive at all; the only reason we believe it is because of countless experiments. But once you are willing to believe this, you see that it is logically impossible to know the position and momentum of a particle at the same time, even if you had the godlike power to measure the electron's properties without touching it. This is because for it to have both an exact momentum and an exact position, it would have to simultaneously be a perfectly non-localized wave and a perfectly localized point, which is nonsense.
Snarkiness is inversely proportional to wisdom because it emphasizes feeling right rather than being right.