Quantum Computing Not an Imminent Threat To Public Encryption 119
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.
Re:Schneier knows his stuff (Score:5, Interesting)
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.
Re:Quantum computing is no threat because... (Score:2, Interesting)
Encryption will move on, too (Score:2, Interesting)
Re:Well, lucky for us (Score:3, Interesting)
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.
Re:Well, lucky for us (Score:3, Interesting)
Shor's Algorithm (Score:4, Interesting)
If that's the case, it's probably worthwhile to discuss Pollard's Rho algorithm [wikipedia.org], 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.
There is a problem with this (Score:5, Interesting)
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?
Re:Schneier knows his stuff (Score:3, Interesting)
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!