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.
Bruce didn't actually write that article. He only linked to it on his blog, which isn't particularly relevant. And, although Bruce is a brilliant cryptographer, he doesn't know squat about quantum computers, nor does the person that wrote that article. One of the most glaring errors is corrected in comment posted on the article page. Besides that, his argument isn't completely sound. The biggest problem with quantum computers isn't managing to build one with a tons of quantum gates, it's getting the error rate down on the components. If you do that, you ought to be able to build as many gates as you want with enough effort and money. The author's argument seems akin to saying we couldn't possibly build a 100-billion transistor count processor today. We could, its just going to be very expensive and you're not going to mass-produce it.
Right now a lot of people working in the field say quantum computers are about 40 years off. The scary thing though is how its likely to play out. For a few decades quantum computers will likely remain "40 years off" (in the fusion sense), but then someone is going to figure out how to get the error rates below threshold, and then quantum computers will be only 10 years away. That doesn't give us much time to stop using our favorite public key algorithms. That's too bad for nTru; (they have a public key system that is likely resistant to quantum computers), their patents will be long expired.
It's way too early to make predictions based on trends. Quantum computing is in its infancy. We haven't even built anything that could/should really be called a working quantum computer (yes, I know we factored 15). We're going to see revolutionary changes to the field, not just evolutionary. So, every once in a while we're going to see great leaps forward, followed by a period where people just improve upon that idea. Its going to take a lot of revolutionary ideas to get a practical quantum computer, and its nearly impossible to say how long it will take to think of them. Just look at fusion, which now I don't even think anyone bothers to say is "40 years off".
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.
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?
While solving NP-complete in P time with a quantum computer sounds insane, I still find even the factoring thing pretty creepy. I suppose it is really just bringing in all the crazy truths of quantum mechanics up into the human scale where we are forced to deal with their strangeness directly. I still harbor a secret hope that someone will discover that a quantum computer needs energy proportional to 2^N (N = number of qubits), thus making them no more powerful than a classical computer. I have zero evidence to back this up, though!