Quantum Computing Not an Imminent Threat To Public Encryption

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.

Comments

not exactly a "threat"

[pedantic bore]

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

Re:not exactly a "threat"

[owlstead]

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:not exactly a "threat"

[owlstead]

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

the fear

[Deanalator]

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.

Re:dongs

[CRCulver]

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.

Re:Schneier knows his stuff

[insertwackynamehere]

Layman's terms?

Re:Schneier knows his stuff

[gomiam]

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.

You have to get the pads to the other person...

[Joce640k]

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!