Does quantum computing really present a threat to current encryption technology

This site is best viewed in a modern browser with JavaScript enabled.

Does quantum computing really present a threat to current encryption technology

sneakyimp

Soooo a non-technical friend of mine recently claimed that quantum computing threatens to render encryption technology obsolete (at least for nation-states) thanks to some kind of magical ability to prime factor large numbers. I won't degrade this forum with the useless link he sent, but it occurs to me that I have no technical understanding of quantum computing whatsoever. I doubt that anyone here has access to a quantum computer or direct research with one, but what do we think? Is encryption dead? Is quantum computing really threatening the state of security?

NogDog

My limited understanding is that QC will, if it works, provide an ability to run massively parallel processing all on the same machine (as opposed to a server farm or bot-net), so I would assume that means it could perform what might otherwise be considered impractically long calculations and/or brute-force processes in a more practical time-frame.

sneakyimp

NogDog;11029541 wrote:
My limited understanding is that QC will, if it works, provide an ability to run massively parallel processing all on the same machine (as opposed to a server farm or bot-net), so I would assume that means it could perform what might otherwise be considered impractically long calculations and/or brute-force processes in a more practical time-frame.

I could be wrong, but I don't think it's quite as simple as QC simply providing 'massively parallel processing' but rather that QC can solve certain classes of problems that we currently tackle using massively parallel processing. E.g., prime factoring a very large number n that is the product of two prime numbers. A traditional approach would be to have a computer divide n by all the prime numbers smaller than n/2 or something (there's probably a better algorithm out there). QC, due to its not-quite-here-and-not-quite-there quantum states might be able to solve this factoring intuitionally or something. Wikipedia mentions Shor's algorithm, which I've yet to read about.

To say that QC arbitrarily provide massively parallel computing seems a bit of an oversimplification to me -- at the very least because in order to make use of this massively parallel computing, there would need to be a way to extract the computing results from the device in an orderly fashion which suggests at least an engineering hurdle.

traq

the advantage of quantum computing, IIUC, is in its ability to represent multiple states at once. Where a normal bit is either 1 or 0, a quantum bit is either 1 or 0 and may also be 0 or 1 (or vice versa) at the same time. I don't know the actual algorithm, but I've read (for example) that a 16-bit machine could represent 2¹⁶ states at any given time.

The disadvantage is that calculations are not deterministic: the answer to a math routine might be correct and might not. If you'll pardon me, I have to go read wikipedia footnotes now.

sneakyimp

traq;11029579 wrote:
the advantage of quantum computing, IIUC, is in its ability to represent multiple states at once. Where a normal bit is either 1 or 0, a quantum bit is either 1 or 0 and may also be 0 or 1 (or vice versa) at the same time. I don't know the actual algorithm, but I've read (for example) that a 16-bit machine could represent 2¹⁶ states at any given time.

That sounds somewhat more concise. I have this vague feeling (not backed by any actual study) that the computer's ability to use this uncertainty relies on nudging the computer toward the optimal solution by somehow taking advantage of some basic laws of physics or something which sort of suck the uncertain states toward certain ones in such a way to avoid violating some kind of constraint.

traq;11029579 wrote:
The disadvantage is that calculations are not deterministic: the answer to a math routine might be correct and might not. If you'll pardon me, I have to go read wikipedia footnotes now.

A Douglas Adams episode comes to mind.

The wikipedia article on QC does offer a little more detail regarding encryption:

other existing cryptographic algorithms do not appear to be broken by these algorithms.[14][15] Some public-key algorithms are based on problems other than the integer factorization and discrete logarithm problems to which Shor's algorithm applies, like the McEliece cryptosystem based on a problem in coding theory.[14][16] Lattice-based cryptosystems are also not known to be broken by quantum computers, and finding a polynomial time algorithm for solving the dihedral hidden subgroup problem, which would break many lattice based cryptosystems, is a well-studied open problem.

Regarding the impact of QC on encryption, two questions arise:
1) Are these other algorithms commonly used for encryption or does most encryption currently rely on the algorithms vulnerable to Shor's algorithm?
2) Is there yet a viable, working QC computer than actually crack anything?

Regarding #2, this article looks interesting: http://www.technologyreview.com/news/514846/google-and-nasa-launch-quantum-computing-ai-lab/

Weedpacket

Part of it is the exponential speedup allowed by being able to spawn new instances of the processor every time the search tree branches; the other (trickier) part is getting the dead end searches to cancel each other out so that the only states that remain to be selected from at the end of the computation are the successful outcomes. (If at first you don't succeed, destroy any evidence you tried.)

Thing to keep in mind: in quantum mechanics there is no "uncertainty" or "randomness". They only arise once you decide to stop treating the system as though it were a quantum entity and start treating it like a classical one. (And the point where you decide to do that is one of the biggest issues in modern physics.)

sneakyimp

Weedpacket;11029589 wrote:
Part of it is the exponential speedup allowed by being able to spawn new instances of the processor every time the search tree branches;

"spawn new instances of the processor" ? What on earth does that mean? Could you elaborate a bit?

Weedpacket;11029589 wrote:
the other (trickier) part is getting the dead end searches to cancel each other out so that the only states that remain to be selected from at the end of the computation are the successful outcomes. (If at first you don't succeed, destroy any evidence you tried.)

This also sounds tantalizingly close to something I might comprehend. Perhaps you could recommend a link or primer of some kind for me to read?

Weedpacket;11029589 wrote:
Thing to keep in mind: in quantum mechanics there is no "uncertainty" or "randomness". They only arise once you decide to stop treating the system as though it were a quantum entity and start treating it like a classical one. (And the point where you decide to do that is one of the biggest issues in modern physics.)

I used to work for this guy, M.I.T. Professor J.W.M. Bush, in a lab when he was working on his doctorate. He's got some interesting ideas about how quantum-like behavior can arise from classical systems. He's expressed skepticism about the wave-particle duality thing and tends to suggest that the subatomic world just beyond our observational capabilities might not be as otherworldly or bizarre as people like to think.

sneakyimp

They produced this video to explain their research. I think it's fascinating.
http://www.youtube.com/watch?v=nmC0ygr08tE

NogDog

My hunch for awhile now is that while quantum mechanics does a fine job of providing highly accurate (like 14 decimal places or more) predictions of physical systems at the quantum level, we're still waiting for some Einstein on mental steroids to come along who can conceive of an underlying rationale for why those quantum probabilities and such actually work.

Of course, it could be "turtles all the way down", with no end in sight as to how many layers of the onion still need to be peeled away before anyone could truly claim to understand how/why everything is the way everything is. For that matter, maybe it's "turtles all the way up" if we move toward the macroscopic end of things.

sneakyimp

I was taught to believe that, because we rely mainly on photons to observe things, it is more or less pointless to try and observe anything so small that it would be sent flying by a collision with a single photon. I've been pretty impressed with the improvements in observational resolution that have been accomplished by scientists.

But we digress. The question was about QC's potential effect on the security of current encryption technology. This article is good for a layman's description:
http://www.nytimes.com/2011/12/06/science/scott-aaronson-quantum-computing-promises-new-insights.html?_r=3&ref=science&pagewanted=all&

I'm not so sure about this one, but I believe this is the company that NASA and Google are investing in:
http://www.dwavesys.com/en/dev-tutorial-intro.html

this looks like a pretty technical primer:
http://math.uci.edu/~brusso/kribslinalgapp.pdf