Slashdot Mirror

← Back to Stories (view on slashdot.org)

Quantum Computing Not an Imminent Threat To Public Encryption

Posted by Soulskill on 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.

3 of 119 comments (clear)

  1. not exactly a "threat" by pedantic+bore · · Score: 3, Insightful

    ... more like guaranteed employment for security experts everywhere!

    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...

    --
    Am I part of the core demographic for Swedish Fish?
    1. Re:not exactly a "threat" by owlstead · · Score: 3, 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...

      I imagine one-time pads will come back in style.

      One time pads are replacements for symmetric encryption (both sides use the same key), not asymmetric encryption. You cannot authenticate a server to multiple clients using one time pads for instance. Everybody would have the one time pad, so everybody could pose as the server. Anyway, there *are* asymmetric algorithms that should be safe against crypto analysis using quantum computing. There is no need to go distributing Blu-Ray disks filled with random valued bits (one disk per application and user) just yet.

  2. Re:Schneier knows his stuff by gomiam · · Score: 4, Insightful
    Perhaps you would like to read again what NP-complete means: being able to quickly check (read: in polynomial time) whether a solution is right or not by using a deterministic algorithm. Quantum computers are non-deterministic, and that's why they can be used to factor large integers. "Check all periods of r so a^r=1 (mod N) at the same time" certainly isn't deterministic.

    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.