Time Running Out for Public Key Encryption

holy_calamity writes "Two research teams have independently made quantum computers that run the prime-number-factorising Shor's algorithm — a significant step towards breaking public key cryptography. Most of the article is sadly behind a pay-wall, but a blog post at the New Scientist site nicely explains how the algorithm works. From the blurb: 'The advent of quantum computers that can run a routine called Shor's algorithm could have profound consequences. It means the most dangerous threat posed by quantum computing - the ability to break the codes that protect our banking, business and e-commerce data - is now a step nearer reality. Adding to the worry is the fact that this feat has been performed by not one but two research groups, independently of each other. One team is led by Andrew White at the University of Queensland in Brisbane, Australia, and the other by Chao-Yang Lu of the University of Science and Technology of China, in Hefei.'"

Comments

Re:Tor like oatmeals!

[Anonymous Coward]

The Magic Words are Squeamish Ossifrage

Re:More like the Chinese gov

[Nos.]

The thing I worry about, is, regardless of which government or group is working on it is this, if this is what they're releasing to the public, how much farther ahead are they behind closed doors.

Just RSA, actually

[geekgirlandrea]

*sigh*

This doesn't break "public-key cryptography". Even if you could build a Shor-factorization machine big enough to use against real-world keys (and that's a *big* if), it's only good against RSA. Elliptic-curve cryptosystems, for example, would be entirely unaffected. In general, the question of whether general-purpose quantum computers would break all public-key cryptography is a really hard one. It's equivalent to whether there are any trapdoor one-way functions which are in P but with inverses not in BQP. Even the existence of non-trapdoor one-way functions is still an open question; they would have to have inverses in , and proving that would also imply P != NP. All the existence of Shor's algorithm really shows about that problem is that there is at least one problem, integer factorization, which is in BQP but (probably) not in P.

Anyway, it's a long way from running Shor's algorithm to factor 15 to being able to factor a 4096-bit RSA key. Remember that because of the no-cloning theorem you can't build a flip-flop for qubits, so quantum circuits are all combinatorial logic. Applying Shor's algorithm to real-world RSA keys would require building a complete modular exponentiator combinatorially out of quantum logic gates, wide enough to deal with the biggest key sizes practical for anyone to use (and the cost of RSA encryption/decryption only scales linearly with the key size). We couldn't even build that out of regular non-quantum logic.

Re:not quite...

[E 99]

Lastly, not all public key crypto is shafted, only things that rely on factorisation as a problem. ECC will be quite safe until (if?) somebody develops a quantum algorithm for discrete logs.

Factoring and discrete logs are codependent on each other being hard problems. Either one can solve the other. I'm not familiar enough with ECC to know if being able to solve regular discrete logs necessary breaks it; but if so, then factoring breaks it too.

Storage will beat Crypto

[DanielMarkham]

Cheap storage will eventually destroy any kind of crypto/anti-crypto technology.

What are the new DVD formats getting? 50GB of data RW? Will options up to 250GB or so of RW storage?

How much information do you really, really need to hide, anyway? Maybe a couple of megabytes of financial-related data per day? A one-time pad on a DVD should provide you with centuries of totally secure communications.

So you sign up for your bank account. The bank snail mails you a 10GB random noise memory stick. You add it to your 10TB secure random storage system and you and the bank can talk for the rest of your life without anybody else being able to listen in.

Re:bigger keys?

[TheRaven64]

It's been a while since I looked at Shor's algorithm, but I was under the impression that you needed a quantum computer with a number of qbits greater than or equal to the key length in order to get that kind of scalability with the algorithm. Due to entanglement problems, building a quantum computer with a sufficiently large capacity to run Shor's algorithm on keys of a useful length is still very hard. We've had quantum computers that can use it to quickly factorise trivial keys for a while now, but making bigger ones is very hard.