Follow Slashdot stories on Twitter

 



Forgot your password?
typodupeerror
Encryption Security Supercomputing

Quantum Computing Not an Imminent Threat To Public Encryption 119 119

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.
This discussion has been archived. No new comments can be posted.

Quantum Computing Not an Imminent Threat To Public Encryption

Comments Filter:
  • by pedantic bore (740196) on Sunday March 23, 2008 @10:42AM (#22836362)

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

  • the fear (Score:2, Insightful)

    by Deanalator (806515) <pierce403@gmail.com> on Sunday March 23, 2008 @11:07AM (#22836494) Homepage
    I think the fear is that by the time we get around to having decent PKI for stuff like credit cards etc, quantum computing will bust everything wide open. PKI is the only practical method of identity management these days, and while algorithms in the PKI are being tweaked, they are all pretty much based on the same principals, which quantum computing is a real threat too.
  • by owlstead (636356) on Sunday March 23, 2008 @11:16AM (#22836530)

    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.

  • Re:dongs (Score:3, Insightful)

    by CRCulver (715279) <crculver@christopherculver.com> on Sunday March 23, 2008 @11:17AM (#22836534) Homepage

    It's just a matter of changing the whole infrastructure to something else, not the end of the world.

    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 single message. For those people who encrypted their private communications, it is a big shock that all your secrets may be read in just a few years.

  • by insertwackynamehere (891357) on Sunday March 23, 2008 @11:22AM (#22836568) Journal
    Layman's terms?
  • by owlstead (636356) on Sunday March 23, 2008 @12:50PM (#22837056)
    "I am crypto-tech naive. What's the problem with using one-time pads and having every "relationship" share a pad?"

    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 need to setup a symmetric key (which is what a one time pad is, basically). Also note that you don't have a certificate infrastructure, so you cannot just go to VeriSign or any other trusted third party and buy a certificate from there. You cannot download one time pads, because you don't know who it is coming from.

    Say you have 200.000.000 client computers in the US alone, and some 5.000 sites with one time pad SSL. Then you have 1.000.000.000.000 relations to set up. Not quite as much as the number of dollars wasted on the war in Iraq, but it's getting there. Of course, you won't use each and every service, but it would take a little bit too much time to exchange disks by post when you are trying to connect to a new service.
  • by gomiam (587421) on Sunday March 23, 2008 @01:21PM (#22837264)
    Perhaps you would like to read again what NP-complete [wikipedia.org] 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.

  • by Joce640k (829181) on Sunday March 23, 2008 @04:34PM (#22838522) Homepage
    How are you going to get the pads to the other person? Encrypt them?

    If you have a way of transmitting the pads securely then you could just use the same system to transmit the messages - no encryption needed!

There's a whole WORLD in a mud puddle! -- Doug Clifford

Working...