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

Well...

[morgan_greywolf]

It doesn't necessarily mean the end of public key cryptography, it just means we'll have to come up with something other than prime factoring to compute the keys.

What this does mean is that there's going to be a lot of money to be made replacing public-key cryptograhy in custom code ala Y2K.

Re:I'm not sure how big of a deal this is.

[jellomizer]

Well Students of colleges (Perhaps undgrads, or people pretending to be an actual student) can have access to such systems. 10-20 years down the line when such systems become obsolete they get in the hands of the public. Or engineering Quantum Computers becomes more feasable then everyone may have one.

Re:More like the Chinese gov

[multisync]

More like the Chinese government wants to break the encryption so they can more easily hack other governments data. They just post it under "Research".

Yeah, the Chinese government is the only government that would like to do that.

Re:bigger keys?

[brunascle]

not really. they can still use the same algorithm, it'll just take longer. it might work for a while, but it's not a long term solution.

plus, cryptography is very resource-intensive, growing exponentially with key size. there comes a point when it's just not practical to use a key that large, as it will take too long to encrypt/decrypt/generate the key.

Not the end

[drabgah]

The quantum computer referenced in the summary managed the immense feat of finding the factors of the number 15. While it is true that factoring numbers of the magnitude used in cryptography is now a "matter of engineering", there are profound difficulties involved in scaling quantum computing. The fundamental problem is called "decoherence" and describes the tendency of quantum systems to become entangled with their environment, and the consequent loss of pure quantum states. The issues involved in quantum computation connect to deep issues of thermodynamics and entropy, and research on quantum computation has potentially great significance for fundamental physics. Cryptography may have to develop and implement new, extended standards as computational techniques evolve, but the encryption sky is not yet falling.

new decryption methods == new encryption methods

[jgarra23]

This means that people will come up with new encryption methods that I couldn't possibly imagine (not much of a stretch). Based off these newly powerful methods people will find new impregnable methods. Sort of like how when people came up with the idea of wooden shields, someone came up with a way to pierce them so someone came up with metallic armor and then someone came up with the idea of a combustion-powered missile (gun) and someone came up with Kevlar and so on...

Re:I'm not sure how big of a deal this is.

[Vellmont]

This poses a big threat to governments, and possibly financial institutions, but not individuals.

As an individual, I consider threats to governments and financial institutions "a big deal".

No big deal

[jd]

RSA uses primes. This leaves the ones that don't: HFE, NTRU, ECC, XTR, Paillier, ElGamal, ....

Not PK encryption per se, the RSA implementation

[ishmalius]

The general handshaking mechanism itself is not in danger. It is the prime factor-based RSA algorithm. There might be other key algorithms in danger as well, but this doesn't reflect on the PK framework.

some perspective...

[Anonymous Coward]

Let me share a quote that my Complexity Theory professor at Carnegie Mellon said about this back in 1999:

"Quantum computing has the potential to change everything, no doubt about it. However, I won't get excited about it until they can factor a number larger than, oh, let's say, FIFTEEN. Until then, everything in this class about turing machines, P, NP, etc is still the world we live in."

That's the quote as best as I can remember it, and the number he said was really close to 15 if I recall. Bottom line, what he said is still true--this is fascinating, fascinating stuff, but we really need to see it happen for larger numbers!

-Jaro

Re:how hard is it to build a quantum computer?

[Tanman]

It is illegal. You just aren't allowed to see the law because the government has classified it "secret." If people were allowed to read the law, the justice department believes it would provide insight to enemies of the state on a possible exploitable vulnerability.

by the way, I'm just making this up, but I bet you believed me. Sad state of affairs we're in.

What Codes?

[segedunum]

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.

It might just show how sadly cynical I am regarding many companies' attitudes towards security, but I looked at that sentence and and thought "This would actually make a difference?"

Re:bigger keys?

[geekgirlandrea]

No, the problem is that Shor's algorithm can factor in polynomial time. To make keys big enough to be impractical to factor with it, they'd also have to be too big to practically use. Public-key cryptosystems depend on the ratio of the time to break the key to the time to use it scaling exponentially with key size.

Therefore... Quantum Computing Illegal in US?

[zrgn]

So can I guess an American university has not been able to do this because they would be put in jail (DMCA). "I'm sorry we can't cure your cancer because the technology used to do this could circumvent digital property rights and encryption algorithms."

Re:bigger keys?

[Solra Bizna]

Properly applied, one-time pad encryption is not crackable. Ever. Using any amount of technology or resources.

Unless you already know the key, any message of the proper length could be the plaintext you're looking for. Even a huge quantum computer wouldn't be able to tell that the ciphertext "VPx\PztI-H&jAL" decrypts to "attack at dawn" and not "attack at dusk" or "retreating now". (or even "yay ice cream!") It might seem like this would break down with degenerate plaintext (such as signed messages), but as long as no key bits are reused and the key is not compromised, it holds up.

"If it's so perfect, why doesn't everyone use it," you ask? "Proper" OTP requires the key to be as big as (or bigger than) the message, and requires the entire key to be shared between both parties, securely, beforehand. Not exactly something eBay can roll out tomorrow.

-:sigma.SB

Re:Not the end

[blueg3]

Factoring a four-bit number on a quantum computer requires quite a lot of qbits. You require 20 qbits just to store a four-bit number, and more just to execute the algorithm. This is a big improvement on the few-qbit machines previously made. At this point, while decoherence is still a large barrier, it's solely an engineering barrier, and one should expect it to last for too long. (Where "too long" is in physics terms. You'll probably be okay for 20 years or so.)

Re:bigger keys?

[imbaczek]

There's a problem with quantum computers: decoherence - the bigger the the key, the more qubits are needed and decoherence is more likely. Of course, that's a technical issue.

Re:SO what if they break the encryption?

[CajunArson]

That might be theoretically true, but in practice public keys are in use for YEARS (if not decades).

Example, vising gmail and checking out the certificate Google (which is pretty security conscious) has a key valid from 05/03/2007 through 05/14/2008 (over a year).
In order to trivially look at EVERY session encrypted over gmail an attack would need to crack that key ONCE. Google is pretty good by the way, there are certs in existence for far longer than 1 year out on the intraweb.

It is true that every session uses a symmetric cypher with a different session key... but how do you think the keys are exchanged? Once the PKI encryption is broken, the attacker will be able to read the session key in plaintext and decrypt the entire session. And this is for every single person using Google's certificate. That is why cracking PKI is so profitable, the long-term nature of the keys means once it is cracked, you have free reign for a long time.

Re:SO what if they break the encryption?

[Sique]

Generating the assymmetric keys takes time, that's why you use symmetric keys for real time encryption. So changing the assymmetric keys too often is unfeasible right now. You want them to be valid for a longer time than just a few seconds.

Re:Just RSA, actually

[rjh]

Superpositional computation works very nicely against ECC and the discrete logarithm problem.

SC doesn't work against things in class NP-COMPLETE, but it's quite effective against many problems that are in NP but less than NP-COMPLETE. In fact, I'm scratching my head trying to find one that SC doesn't work against.

Also, the total number of qubits required is twice the number of bits in the key. While nontrivial, it is not as ridiculous as you're making it out to be. It's possible we'll have this in twenty years. Less, if engineering breakthroughs go our way; more, if they don't.

Re:bigger keys?

[owlstead]

Normally we refer to keys used in symmetric encryption as secret keys, not as private keys. For asymmetric encryption, where two mutually dependent keys are used it's private and public keys.

Anywho, it is said that AES-256 should be strong enough to withstand attacks by quantum computing. Of course, by definition, one time pads are resistant against every attack, as long as the keys are really kept safe. The reason why they are not commonly used is the size of the keys (as long as the plain text) and key distribution & memory issues.

So symmetric encryption is still rather safe, and as long as they aren't able to build a rather large quantum computer, I presume that asymmetric encryption is still safe as well.