
Does quantum computing really present a threat to current encryption technology
Soooo a nontechnical friend of mine recently claimed that quantum computing threatens to render encryption technology obsolete (at least for nationstates) 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?

High Energy Magic Dept.
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 botnet), so I would assume that means it could perform what might otherwise be considered impractically long calculations and/or bruteforce processes in a more practical timeframe.

Originally Posted by 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 botnet), so I would assume that means it could perform what might otherwise be considered impractically long calculations and/or bruteforce processes in a more practical timeframe.
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 notquitehereandnotquitethere 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.

Senior Member
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 16bit machine could represent 2^16 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.

Originally Posted by 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 16bit machine could represent 2^16 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.
Originally Posted by traq
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 publickey 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] Latticebased 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 wellstudied 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...putingailab/

Pedantic Curmudgeon
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.)

Originally Posted by 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;
"spawn new instances of the processor" ? What on earth does that mean? Could you elaborate a bit?
Originally Posted by Weedpacket
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?
Originally Posted by Weedpacket
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 quantumlike behavior can arise from classical systems. He's expressed skepticism about the waveparticle 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.

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

High Energy Magic Dept.
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.

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/sc...agewanted=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/devtutorialintro.html
this looks like a pretty technical primer:
http://math.uci.edu/~brusso/kribslinalgapp.pdf
Thread Information
Users Browsing this Thread
There are currently 1 users browsing this thread. (0 members and 1 guests)
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

