Slashdot Log In
Quantum Computing Not an Imminent Threat To Public Encryption
Posted by
Soulskill
on Sunday March 23, @10:35AM
from the in-search-of-schrodinger's-catastrophe dept.
from the in-search-of-schrodinger's-catastrophe dept.
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.
Related Stories
[+]
Time Running Out for Public Key Encryption 300 comments
holy_calamity writes "Two research teams have independently made quantum computers that run the prime-number-factorising Shor's algorithm — a significant step towards breaking public key cryptography. Most of the article is sadly behind a pay-wall, but a blog post at the New Scientist site nicely explains how the algorithm works. From the blurb: 'The advent of quantum computers that can run a routine called Shor's algorithm could have profound consequences. It means the most dangerous threat posed by quantum computing - the ability to break the codes that protect our banking, business and e-commerce data - is now a step nearer reality. Adding to the worry is the fact that this feat has been performed by not one but two research groups, independently of each other. One team is led by Andrew White at the University of Queensland in Brisbane, Australia, and the other by Chao-Yang Lu of the University of Science and Technology of China, in Hefei.'"
[+]
Science: The Limits of Quantum Computing 228 comments
The Narrative Fallacy writes "Scott Aaronson has posted a draft of his article from this month's Scientific American on the limitations of quantum computers (PDF) discussing the question: Will quantum computers let us transcend the human condition and become as powerful as gods, or are they a physical absurdity destined to be exposed as the twenty-first century's perpetual-motion machine? Aaronson says that while a quantum computer could quickly factor large numbers, and thereby break most of the cryptographic codes used on the Internet today, there's reason to think that not even a quantum computer could solve the crucial class of NP-complete problems efficiently. Aaronson contends that any method for solving NP-complete problems in polynomial time may violate the laws of physics and that this may be a fundamental limitation on technology no different than the second law of thermodynamics or the impossibility of faster-than-light communication."
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Schneier knows his stuff (Score:4, Informative)
Re:Schneier knows his stuff (Score:5, Informative)
Re:Schneier knows his stuff (Score:5, Insightful)
The darned things would be like oracles, just ask them any super hard question, like how to prove Fermat's Last Theorem, and they'd just spit out the answer. The things would be like talking directly to God. Is that even remotely possible? I don't think so. Factoring numbers is just not as hard as any NP complete problem.
You might as well conclude that grass is purple, for all the sense that paragraph makes.
Re:Schneier knows his stuff (Score:4, Informative)
What you described is the property "NP-hard".
For a problem to qualify as NP-complete, it is also neccessary that an algorithm that can solve this problem can also be used to solve every other NP-hard problem, with only an additional transformation of its input and output in polynomial time.
Prime factoring is not NP-complete. There is as far as I know no transformation for the input and output of a prime-factoring algorithm, that would allow it to solve other np-hard problems as well.
If prime factoring was np-complete, then since a quantum algorithm is known for it, it would be certain that a quantum computer could also solve all other np-hard problems.
As far as I know, no quantum algorithm with polynomial time has been found for any NP-complete problem. So we do not know whether a quantum computer could do this
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: (Score:3, Insightful)
Re:Schneier knows his stuff (Score:5, Funny)
Hope that clears it up for you...
not exactly a "threat" (Score:4, Insightful)
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...
Re:not exactly a "threat" (Score:4, Insightful)
I imagine one-time pads will come back in style.
Re: (Score:3, Informative)
Re: (Score:3, Insightful)
Well, just think about all the SSL enabled sites out there, and remember you will now have a N * N (client * server) number of relations that
Re: (Score:3, Informative)
"polynomial time" (Score:4, Informative)
Quantum computing is no threat because... (Score:3, Informative)
Re: (Score:3, Informative)
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.
Complete article (without subscription) (Score:3, Informative)
http://www.scottaaronson.com/writings/limitsqc-draft.pdf [scottaaronson.com]
Scott posted it on his blog on 2/18, see http://www.scottaaronson.com/blog/ [scottaaronson.com]
(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.)
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: (Score:3, Insightful)
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 sin
And the answer is ..Re:So how do you encript ..... (Score:3, Funny)
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 f
Re: (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:5, Informative)
Re: (Score:3, Interesting)
Re:Does exist any quantum computer proven to work? (Score:5, Informative)
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"
Re:Does exist any quantum computer proven to work? (Score:4, Informative)
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 [ipod.org.uk] and here [davidjarvis.ca] 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.