Does quantum computing really present a threat to current encryption technology
Results 1 to 10 of 10

Thread: Does quantum computing really present a threat to current encryption technology

  1. #1
    Senior Member
    Join Date
    Apr 2003
    Location
    Silver Lake
    Posts
    4,811

    Does quantum computing really present a threat to current encryption technology

    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?
    IMPORTANT: STOP using the mysql extension. Use mysqli or pdo instead.
    World War One happened 100 years ago. Visit Old Grey Horror for the agony and irony.

  2. #2
    High Energy Magic Dept. NogDog's Avatar
    Join Date
    Aug 2006
    Location
    Ankh-Morpork
    Posts
    13,820
    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.
    Please give us a simple answer, so that we don't have to think, because if we think, we might find answers that don't fit the way we want the world to be." ~ from Nation, by Terry Pratchett

    "But the main reason that any programmer learning any new language thinks the new language is SO much better than the old one is because hes a better programmer now!" ~ http://www.oreillynet.com/ruby/blog/...ck_to_p_1.html


    eBookworm.us

  3. #3
    Senior Member
    Join Date
    Apr 2003
    Location
    Silver Lake
    Posts
    4,811
    Quote Originally Posted by NogDog View Post
    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.
    IMPORTANT: STOP using the mysql extension. Use mysqli or pdo instead.
    World War One happened 100 years ago. Visit Old Grey Horror for the agony and irony.

  4. #4
    Senior Member traq's Avatar
    Join Date
    Jun 2011
    Location
    so.Cal
    Posts
    949
    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^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.

  5. #5
    Senior Member
    Join Date
    Apr 2003
    Location
    Silver Lake
    Posts
    4,811
    Quote Originally Posted by traq View Post
    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^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.

    Quote Originally Posted by traq View Post
    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...puting-ai-lab/
    IMPORTANT: STOP using the mysql extension. Use mysqli or pdo instead.
    World War One happened 100 years ago. Visit Old Grey Horror for the agony and irony.

  6. #6
    Pedantic Curmudgeon Weedpacket's Avatar
    Join Date
    Aug 2002
    Location
    General Systems Vehicle "Thrilled To Be Here"
    Posts
    21,774
    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.)
    THERE IS AS YET INSUFFICIENT DATA FOR A MEANINGFUL ANSWER
    FAQs! FAQs! FAQs! Most forums have them!
    Search - Debugging 101 - Collected Solutions - General Guidelines - Getting help at all

  7. #7
    Senior Member
    Join Date
    Apr 2003
    Location
    Silver Lake
    Posts
    4,811
    Quote Originally Posted by Weedpacket View Post
    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?

    Quote Originally Posted by Weedpacket View Post
    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?

    Quote Originally Posted by Weedpacket View Post
    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.
    IMPORTANT: STOP using the mysql extension. Use mysqli or pdo instead.
    World War One happened 100 years ago. Visit Old Grey Horror for the agony and irony.

  8. #8
    Senior Member
    Join Date
    Apr 2003
    Location
    Silver Lake
    Posts
    4,811
    They produced this video to explain their research. I think it's fascinating.
    http://www.youtube.com/watch?v=nmC0ygr08tE
    IMPORTANT: STOP using the mysql extension. Use mysqli or pdo instead.
    World War One happened 100 years ago. Visit Old Grey Horror for the agony and irony.

  9. #9
    High Energy Magic Dept. NogDog's Avatar
    Join Date
    Aug 2006
    Location
    Ankh-Morpork
    Posts
    13,820
    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.
    Please give us a simple answer, so that we don't have to think, because if we think, we might find answers that don't fit the way we want the world to be." ~ from Nation, by Terry Pratchett

    "But the main reason that any programmer learning any new language thinks the new language is SO much better than the old one is because hes a better programmer now!" ~ http://www.oreillynet.com/ruby/blog/...ck_to_p_1.html


    eBookworm.us

  10. #10
    Senior Member
    Join Date
    Apr 2003
    Location
    Silver Lake
    Posts
    4,811
    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/dev-tutorial-intro.html

    this looks like a pretty technical primer:
    http://math.uci.edu/~brusso/kribslinalgapp.pdf
    IMPORTANT: STOP using the mysql extension. Use mysqli or pdo instead.
    World War One happened 100 years ago. Visit Old Grey Horror for the agony and irony.

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
  •